การเปรียบเทียบประสิทธิภาพระหว่างวิธีการคำตอบเชิงพันธุ์กรรมกับการหาค่าเหมาะสมที่สุดแบบกลุ่มอนุภาคสำหรับการแก้ปัญหาการจัดเส้นทางการขนส่ง
A comparison of the efficiency between Genetic Algorithms and Particle Swarm Optimization Algorithm for Solving VRP
คำสำคัญ:
การขนส่งสินค้า วิธีทางพันธุกรรม การหาค่าคำตอบที่เหมาะสมแบบกลุ่มอนุภาคบทคัดย่อ
การศึกษาครั้งนี้ ผู้วิจัยอาศัยทฤษฎีอัลกอริทึมทางพันธุศาสตร์ (Genetic Algorithms ; GAs) เปรียบเทียบกับวิธีการหาค่าเหมาะสมที่สุดแบบกลุ่มอนุภาค (Particle Swarm Optimization) สำหรับการแก้ปัญหาการจัดเส้นทางการขนส่งสินค้าในการค้นหาคำตอบที่ดีที่สุด โดยแนวคิดของ GAs เป็นการหาคำตอบที่ดีที่สุดโดยข้อมูลถูกพิจารณาในรูปแบบของโครโมโซมที่มีการถ่ายทอดลักษณะทางพันธุกรรมจากบรรพบุรุษไปสู่รุ่นลูกหลานโดยใช้ค่าฟังก์ชั่นความเหมาะสม (Fitness function) ที่สอดคล้องกับฟังก์ชั่นวัตถุประสงค์ (Objective function) จากขั้นตอนเหล่านี้ทำให้สามารถหาคำตอบที่มีค่าสูงสุด (หรือต่ำสุด) สมบูรณ์ได้และจากการหาคำตอบโดยใช้โครโมโซมในแต่ละรุ่น (Generations) ซึ่งมีการสุ่มคำตอบที่เป็นไปได้ทั้งหมดของปัญหา (Candidate Solution)
วิธีการหาคำตอบที่ดีที่สุดแบบการหาค่าเหมาะสมที่สุดแบบกลุ่มอนุภาค (Particle Swarm Optimization ; PSO) เป็นวิธีการหาคำตอบแบบสุ่ม (Random Search Algorithm) เช่นเดียวกับวิธีการคำตอบเชิงพันธุ์กรรม (Genetic Algorithm) จากโปรแกรมที่สร้างขึ้นนั้นมีพื้นฐานในการปรับปรุงชุดคำตอบจากหลักการทางจิตวิทยาง่ายๆ ที่เป็นความจริงพื้นฐานนำมาใส่ไว้ในโปรแกรมคอมพิวเตอร์
ผลการทดลองพบว่า การนำการกลายพันธุ์จาก GAs มาประยุกต์กับ PSO สามารถลดหรือแก้ไขปัญหาการติดโลคอล ออปติมา และสามารถที่จะเพิ่มประสิทธิภาพการค้นหาคำตอบของ PSO สำหรับการแก้ VRP โดยได้รับค่าตอบที่เหมาะสมในระยะเวลาที่เร็วกว่ากว่า GAs และ PSO แบบปกติ
เอกสารอ้างอิง
จิรรัตน์ ธีระวราพฤกษ์ และธราธร กูลภัทรนิรันดร์. (2546). การประยุกต์หลักการทางพันธุกรรมศาสตร์ในการคัดเลือกกลุ่มโครงการภายใต้ข้อจำกัดด้านงบประมาณ. การประชุมข่ายงานวิศวกรรมอุตสาหการ, ตุลาคม 2546. 153-160.
ณกร อินทร์พยุง. (2548). การแก้ปัญหาการตัดสินใจในอุตสาหกรรมการขนส่งและลอจิสติกส์. กรุงเทพฯ: บริษัท ซี เอ็ดยูเคชั่น จำกัด (มหาชน).
นพรุจ สังข์แป้น และ สุรพงษ์ ศิริกุลวัฒนา. (2557, ก.ย. - ธ.ค.). การประยุกต์ใช้วิธีการเชิงพันธุกรรมสำหรับปัญหาเส้นทางการขนส่งของโรงกำจัดซากไก่. วารสารวิชาการพระจอมเกล้าพระนครเหนือ. ปีที่ 24 ฉบับที่ 3. 526 – 536.
นรงค์ วิชาผา และ คณะ. (2562, ม.ค.–มี.ค.). การแก้ปัญหาการจัดเส้นทางการขนส่งแบบมีกรอบเวลาโดยใช้วิธีเชิงพันธุกรรมแบบผสมผสานด้วยฮิวริสติกแบบแทรกไปข้างหน้าและวิธีการค้นหาคำตอบเฉพาะที่. วารสารวิชาการพระจอมเกล้าพระนครเหนือ, ปีที่ 29 ฉบับที่ 1. 4-13.
พินิจ อ่อนน้อย. (2557). การเพิ่มประสิทธิภาพขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับด้วยการปรับเวคเตอร์ความน่าจะเป็นโดยค่าน้าหนักตามความเหมาะ. คณะวิทยาศาสตร์และเทคโนโลยีมหาวิทยาลัยราชภัฏนครปฐม.
พิศุทธิ์ พงศ์ชัยฤกษ์. (2557). การอธิบายขั้นตอนการทำงานของวิธีการพาทิเคิลสวอมออปติไมเซชั่น ผ่านตัวอย่าง (Discrete Optimization in Transport and Logistics). กรุงเทพฯ: บริษัท ซี เอ็ดยูเคชั่น จำกัด (มหาชน).
Kennedy, J. & Eberhart, R.C. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Network, New Jersey. pp. 1942-1948.
Kennedy, J., Eberhart, R.c. & Shi Y. (2001). Swarm Intelligence. Morgan Kaufmann Publishers.
L. Huang, K. Wang, c. Zhou, R. Pang, L. Dong and L. Peng,. (2003). Particle swarm optimization for traveling salesman problems. Journal of Ji Ling University (Science Edition). 477 - 480.
L. Zhong and H. Lei. (2010). A Mixed Discrete Particle Swarm Optimization for TSP. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE), 208 - 211.
ดาวน์โหลด
เผยแพร่แล้ว
รูปแบบการอ้างอิง
ฉบับ
ประเภทบทความ
สัญญาอนุญาต
จรรยาบรรณผู้เขียนบทความ
ผู้เขียนบทความต้องรับรองว่าบทความนี้ไม่เคยตีพิมพ์ในวารสารใดหรือสิ่งพิมพ์อื่นๆ มาก่อน ต้องไม่คัดลอกผลงานผู้อื่นมาปรับแต่งเป็นบทความของตน และไม่ได้อยู่ระหว่างการเสนอเพื่อพิจารณาตีพิมพ์ อีกทั้งยอมรับหลักเกณฑ์การพิจารณาและการตรวจแก้ไขบทความต้นฉบับโดยกองบรรณาธิการวารสารวิทยาลัยนครราชสีมา สาขามนุษยศาสตร์และสังคมศาสตร์
บทความทุกเรื่องได้รับการตรวจพิจารณาทางวิชาการโดยผู้ทรงคุณวุฒิที่มีประสบการณ์และมีความเชี่ยวชาญตรงตามสาขาของบทความ ซึ่งผู้เขียนต้องแก้ไขตามคำแนะนำของผู้ทรงคุณวุฒิภายในระยะเวลาที่กำหนด หากไม่เป็นไปตามกำหนดกองบรรณาธิการขอสงวนสิทธิ์และยกเลิกการตีพิมพ์โดยจะแจ้งให้ทราบต่อไป
ข้อความที่ปรากฏในบทความของวารสารนี้เป็นความคิดเห็นของผู้เขียนซึ่งไม่เกี่ยวข้องกับวิทยาลัยนครราชสีมาแต่อย่างใด และกองบรรณาธิการขอสงวนสิทธิ์ในการพิจารณาและตรวจประเมินบทความเพื่อตีพิมพ์ในวารสารของวิทยาลัยนครราชสีมา สาขามนุษยศาสตร์และสังคมศาสตร์
