Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การแบ่งปันความรู้ในขั้นตอนวิธีเชิงพันธุกรรมอย่างย่อแบบมีส่วนร่วม
Year (A.D.)
2018
Document Type
Thesis
First Advisor
Prabhas Chongstitvatana
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
Master of Engineering
Degree Level
Master's Degree
Degree Discipline
Computer Engineering
DOI
10.58837/CHULA.THE.2018.152
Abstract
The compact genetic algorithm is derived from the genetic algorithm in which the population is represented by the probabilistic vector. To improve the search capability and avoiding local minima, parallelization has been employed where many search processes are deployed concurrently. In order to coordinate the work of multiple processes, knowledge sharing is necessary. Multiple processes share their probabilistic vectors partially. To escape from local minima the restart step is introduced. The experiment compares the proposed algorithm with two other competitive algorithms using Traveling Salesman problem, Bin Packing problem, Subset Sum problem, and Knapsack problem. The results show that the proposed algorithm is more efficient in finding solutions than the competing algorithms. The detailed analysis of the restart step provides insight into the behaviour of the proposed algorithm.
Other Abstract (Other language abstract of ETD)
อัลกอริทึมขั้นตอนวิธีเชิงพันธุกรรมอย่างย่อแบบมีส่วนร่วมนั้นมาจากอัลกอริทึมขั้นตอนวิธีเชิงพันธุกรรมที่ประชากรแทนด้วยเวกเตอร์ความน่าจะเป็น เพื่อพัฒนาความสามารถในการค้นหาคำตอบและหลีกเลี่ยงคำตอบเฉพาะที่ดังนั้นการทำงานแบบขนานจึงถูกใช้เมื่อโพรเซสหลายโพรเซสทำงานพร้อมกัน เนื่องจากการทำงานไปพร้อมกันของโพรเซสหลายโพรเซสการแบ่งปันข้อมูลจึงเป็นสิ่งจำเป็น โดยโพรเซสจะมีการแบ่งปันข้อมูลกันเป็นระยะ ทั้งนี้เพื่อจะหลีกหนีจากคำตอบเฉพาะที่การรีสตาร์ทจึงถูกนำเสนอ ซึ่งการทดลองเปรียบเทียบอัลกอริทึมที่นำเสนอกับอีกสองอัลกอริทึมโดยใช้ ปัญหาการเดินทางของพนักงานขาย ปัญหาการบรรจุผลิตภัณฑ์ ปัญหาผลรวมของสับเซต และปัญหาถุงกระสอบ ผลการทดลองพบว่าอัลกอริทึมนี่นำเสนอมีประสิทธิภาพในการค้นหาคำตอบได้ดีกว่าอีกสองอัลกอริทึมที่เปรียบเทียบ การวิเคราะห์ของการเกิดรีสตาร์ทแสดงให้เห็นถึงพฤติกรรมของอัลกอริทึมที่ถูกนำเสนอ
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Gateratanakul, Orakanya, "Knowledge sharing in cooperative compact genetic algorithm" (2018). Chulalongkorn University Theses and Dissertations (Chula ETD). 2283.
https://digital.car.chula.ac.th/chulaetd/2283