ซอฟต์แอนท์: ระบบมดในการแก้ปัญหาการเดินทางของพนักงานขาย (Soft-Ant: An Ant System for Traveling Saleman Problem)
Keywords:
ระบบอาณานิคมมด (Ant colony system), การคำนวณแบบซอฟต์ (Soft computing), ปัญญาเชิงคำนวณ (Computational intelligence)Abstract
งานวิจัยฉบับนี้นำเสนอการประยุกต์เทคนิคการคำนวณแบบซอฟต์ (Soft Computing) เพื่อพัฒนาขั้นตอนวิธี ซอฟต์แอนท์ (Soft-Ant) ระบบมดในการแก้ปัญหาการเดินทางของพนักงานขาย ผู้วิจัยได้ทำการปรับปรุงขั้นตอนวิธีระบบอาณานิคมมด (Ant Colony System : ACS) ในส่วนของกฎการปรัปปรุงฟีโรโมนแบบเฉพาะที่ (Local pheromone update rule) โดยการปรับปรุงค่าฟีโรโมนเริ่มต้น (τ0) ด้วยการประยุกต์เทคนิคการคำนวณแบบซอฟต์ ผลการวิจัยสามารถประยุกต์เทคนิคการคำนวณแบบซอฟต์ เพื่อพัฒนาอัลกอริทึมซอฟต์แอนท์ ได้เป็นผลสำเร็จ อัลกอริทึมซอฟต์แอนท์ ที่ผู้วิจัยพัฒนาขึ้นสามารถแก้ปัญหาการเดินทางของพนักงานขายแบบสมมาตร(Symmetric) และอสมมาตร (Asymmetric)ได้ ผลการทดลองเปรียบเทียบอัลกอริทึมระบบอาณานิคมมด (ACS) ดังเดิม กับอัลกอริทึมซอฟต์แอนท์ (Soft-Ant) ในการแก้ปัญหาการเดินทางของพนักงานขาย โดยใช้ชุดข้อมูลจาก TSPLIB ทั้งหมด 6 ชุด พบว่าโดยเฉลี่ยอัลกอริทึมซอฟต์แอนท์ ให้ผลลัพธ์การทำงานดีกว่าอัลกอริทึมระบบอาณานิคมมด สามารถหาผลเฉลยของปัญหาที่ดีกว่า มีค่าเปอร์เซนต์ความผิดพลาดน้อยกว่า และใช้เวลาน้อยกว่า ดังนั้นการประยุกต์เทคนิคการคำนวณแบบซอฟต์ สามารถที่จะเป็นวิธีทางเลือกใหม่ในการปรับปรุงขั้นตอนวิธีระบบอาณานิคมมดในการแก้ปัญหาการเดินทางของพนักงานขายได้
This research proposes a new approach which derived from soft computing, for the construction Soft-Ant : An ant system for traveling salesman problem. We are approved Ant Colony System (ACS) algorithm. In local pheromone update rule, the initial value of pheromone (τ0) are determined by soft computing. This research can use soft computing technical for construction Soft-Ant : An ant system for traveling salesman problem. The proposes can solve symmetric traveling salesman problem (TSP) and asymmetric traveling salesman problem (ATSP). Experimental result show that the proposed Soft-Ant: An ant system for traveling salesman problem outperform the conventional Ant Colony System (ACS). The Soft-ant can find the better solution of the problem, percentage of error less and take less time. Hence, soft computing is expected to be a new alternative way to the construction of ACS model for traveling salesman problem.
