Chulalongkorn University Theses and Dissertations (Chula ETD)

Other Title (Parallel Title in Other Language of ETD)


Year (A.D.)


Document Type


First Advisor

Prabhas Chongstitvatana


Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Department (if any)

Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)

Degree Name

Master of Engineering

Degree Level

Master's Degree

Degree Discipline

Computer Engineering




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)

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



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.