A Novel Binary Discretization for Particle Swarm Optimization Algorithm

Abstract

Particle Swarm Optimization Algorithm (PSO) is well known as one of artificial intelligence. PSO was developed by Kennedy and Eberhart in 1995, based on natural behavior of flocking animal, that does not has a specific leader but they are searching for food by following a member who is the nearest source food. At the beginning, the original PSO was developed properly for continuous optimization problems, however the PSO can be modified to solve discrete optimization problems but it need a discretization method for encoding to discrete space. The sigmoid function is binary discretization that is used to be employed in the most of literatures that study in the discrete PSO.

This research proposes a novel binary discretization for PSO that called “Sic Bo game method”, then the PSO with the sic bo game method, the sigmoid function method and the hyperbolic tangent function method were modified to solve 9 test problems “uncapacitated facility location problems (UFLP)” from OR – Library that have 3 difference levels for compared their performances, the results of comparison show that the sic bo game method is more effective than the others because the sic bo game method delivers the best computation solution, searching for optimum accurately, the most consistency of optimum, the best behavior of convergence to problem’s global optimum, and decreasing the PSO’s computational time.

ขั้นตอนวิธีการหาค่าเหมาะที่สุดแบบกลุ่มอนุภาคเป็นหนึ่งในปัญญาประดิษฐ์ที่นักวิจัยรู้จักตั้งแต่ปีพ.ศ. 2538 นำเสนอโดย Kennedy และ Eberhart หลักการทำงานของขั้นตอนวิธีการมาจากการเลียนแบบพฤติกรรมธรรมชาติการหาอาหารของฝูงสัตว์ที่หาอาหารแบบเป็นฝูง โดยฝูงสัตว์นั้นจะไม่มีหัวหน้าฝูงนำทาง แต่สมาชิกของฝูงจะหาอาหารโดยติดตามสมาชิกตัวที่ใกล้แหล่งอาหารดีที่สุดในขณะนั้น ในเริ่มแรกขั้นตอนวิธีการดังกล่าวได้ถูกออกแบบเพื่อใช้สำหรับการค้นหาค่าเหมาะที่สุดของปัญหาแบบค่าต่อเนื่องเท่านั้น ต่อมาได้ถูกพัฒนาให้นำไปใช้กับปัญหาค่าไม่ต่อเนื่องได้ แต่ต้องมีวิธีการเข้ารหัสตำแหน่งของอนุภาคแบบไม่ต่อเนื่องมาใช้ในการเข้ารหัสตำแหน่งของอนุภาคในขั้นตอนวิธีการ วิธีการเข้ารหัสแบบไม่ต่อเนื่องมีหลายวิธี แต่วิธีที่ได้รับความนิยมมากที่สุดคือวิธีซิกมอยด์ฟังก์ชัน

งานวิจัยนี้ได้นำเสนอวิธีการเข้ารหัสเลขฐานสองของขั้นตอนวิธีการหาค่าเหมาะที่สุดแบบกลุ่มอนุภาคแบบใหม่ “วิธีเกมพนันลูกเต๋า” และนำขั้นตอนวิธีการหาค่าเหมาะที่สุดแบบกลุ่มอนุภาคที่เข้ารหัสเลขฐานสองด้วย วิธีเกมพนันลูกเต๋า วิธีไฮเพอร์โบลิกแทนเจนต์ฟังก์ชัน และวิธีซิกมอยด์ฟังก์ชัน ไปประยุกต์ใช้กับปัญหาทดสอบปัญหาการเลือกตำแหน่งที่ตั้งแบบไม่มีข้อจำกัดกำลังการผลิตจากเว็บไซต์ OR – Library จำนวน 9 ปัญหา ที่มีขนาดของปัญหาแตกต่างกัน 3 ระดับ ในการประเมินประสิทธิภาพจะเทียบกับวิธีไฮเพอร์โบลิกแทนเจนต์ฟังก์ชันและวิธีซิกมอยด์ฟังก์ชัน ผลที่ได้จากการทดลองคือวิธีเกมพนันลูกเต๋ามีประสิทธิภาพกว่าวิธีไฮเพอร์โบลิกแทนเจนต์ฟังก์ชันและวิธีซิกมอยด์ฟังก์ชันทั้งในด้านประสิทธิภาพในการคำนวณหาค่าเหมาะที่สุด ความแม่นยำในการหาค่าเหมาะที่สุด ความสม่ำเสมอของค่าเหมาะที่สุด พฤติกรรมการลู่เข้าสู่คำตอบที่เหมาะที่สุด และเวลาการทำงานของขั้นตอนวิธีการ