Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems
Thesis (Ph.D.)--Chulalongkorn University, 2010
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Theses and Dissertations |
| Language: | English |
| Published: |
Chulalongkorn University
2012
|
| Subjects: | |
| Online Access: | http://cuir.car.chula.ac.th/handle/123456789/21048 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Chulalongkorn University |
| Language: | English |
| id |
th-cuir.21048 |
|---|---|
| record_format |
dspace |
| spelling |
th-cuir.210482012-07-21T02:47:49Z Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems การเรียนรู้สหสัมพันธ์ลูกผสมเชิงบวกและเชิงลบ ในขั้นตอนวิธีการประมาณการแจกแจงสำหรับปัญหาการหาค่าเชิงการจัดที่เหมาะที่สุด Warin Wattanapornprom Prabhas Chongstitvatana Chulalongkorn University. Faculty of Engineering Combinatorial optimization Machine learning Thesis (Ph.D.)--Chulalongkorn University, 2010 This dissertation studies the roles of negative correlation learning of building blocks in evolutionary algorithms. It is based on a hypothesis called a Negative Building Block Hypothesis (NBBH) simply states that “An algorithm can seeks new-optimal performance by avoiding the juxtaposition of short, low-order, low-performance schemata, called the negative building blocks”. The hypothesis is tested by developing of a new edge based estimation of distribution algorithm named Coincidence algorithm (COIN). Such algorithm utilizes the negative building blocks contained in the below average solution in order to avoid the composition of bad substructures. COIN is tested in several multimodal combinatorial problems. The results conclude that the negative correlation capability of COIN contributes in both quantity and quality of the solutions. In summary, the roles of negative knowledge in combinatorial optimization extracted from the experiments are as follows: (i) The negative knowledge forces the algorithm to explore out of the search space marked as forbidden areas. (ii) The negative knowledge helps producing more diverse solutions, however dissimilar to the solutions considered to be bad quality. (iii) In cooperating with the positive knowledge, the negative knowledge contributes in discrimination of good and bad building blocks. (iv) The negative knowledge enhances a constructive algorithm to recognize better substructures and to compose better solutions. Finally, COIN is tested in several real world multiobjective applications and has shown competitive results compared to the other algorithms in the experiments. ศึกษาบทบาทของความรู้เชิงลบในขั้นตอนวิธีเชิงวิวัฒน์ บทสมุติฐาน ส่วนประกอบเชิงลบมีใจความว่า “ขั้นตอนวิธีใดๆ สามารถค้นหาคำตอบที่ดีขึ้นได้โดยการหลีกเลี่ยงการประกอบกัน ของโครงสร้างทางความรู้ที่มีขนาดเล็กที่มีประสิทธิภาพต่ำ ที่เราเรียกกันว่าส่วนประกอบเชิงลบ” สมมุติฐานดังกล่าวถูกทดสอบโดยการพัฒนาขั้นตอนวิธีการประมาณการแจกแจงจากเส้นเชื่อม ที่มีชื่อว่า ขั้นตอนวิธีการบรรจวบ (COIN) ขั้นตอนวิธีดังกล่าวใช้ประโยชน์จากส่วนประกอบเชิงลบที่ซ่อนอยู่ในคำตอบที่ต่ำกว่าค่าเฉลี่ย เพื่อใช้ในการหลีกเลี่ยงการประกอบกันของส่วนประกอบเชิงลบนั้นๆ ขั้นตอนวิธี COIN ถูกทดสอบในปัญหาเชิงการจัดที่มีคำตอบหลายรูปแบบ ทั้งนี้ ผลการทดลองสรุปได้ว่าขั้นตอนวิธี COIN มีส่วนช่วยในการสร้างคำตอบทั้งในเชิงปริมาณและในเชิงคุณภาพ บทบาทของความรู้เชิงลบในปัญหาเชิงการจัดที่ได้จากการทดลอง อาจสรุปได้ดังนี้ (1) ความรู้เชิงลบบังคับในขั้นตอนวิธีค้นหาคำตอบนอกพื้นที่ที่ถูกห้ามเอาไว้ (2) ความรู้เชิงลบช่วยให้ขั้นตอนวิธีผลิตคำตอบที่หลากหลาย ทั้งนี้ต้องมีความแตกต่างจากคำตอบที่มีคุณภาพต่ำ (3) ความรู้เชิงลบเมื่อใช้ร่วมกันกับความรู้เชิงบวก แล้วมีส่วนช่วยในการแยกแยะส่วนประกอบที่ดีและไม่ดีได้ (4) ความรู้เชิงลบช่วยให้ขั้นตอนวิธีเชิงการสร้างค้นหาและประกอบโครงสร้างที่ดีขึ้นได้ ท้ายที่สุด ขั้นตอนวิธี Coin ถูกนำไปทดสอบบนปัญหาที่ใช้งานจริงในหลายวัตถุประสงค์ และแสดงศักยภาพที่เหนือกว่าขั้นตอนวิธีที่ถูกนำมาเปรียบเทียบ 2012-07-21T02:47:20Z 2012-07-21T02:47:20Z 2010 Thesis http://cuir.car.chula.ac.th/handle/123456789/21048 en Chulalongkorn University 3905237 bytes application/pdf application/pdf Chulalongkorn University |
| institution |
Chulalongkorn University |
| building |
Chulalongkorn University Library |
| country |
Thailand |
| collection |
Chulalongkorn University Intellectual Repository |
| language |
English |
| topic |
Combinatorial optimization Machine learning |
| spellingShingle |
Combinatorial optimization Machine learning Warin Wattanapornprom Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| description |
Thesis (Ph.D.)--Chulalongkorn University, 2010 |
| author2 |
Prabhas Chongstitvatana |
| author_facet |
Prabhas Chongstitvatana Warin Wattanapornprom |
| format |
Theses and Dissertations |
| author |
Warin Wattanapornprom |
| author_sort |
Warin Wattanapornprom |
| title |
Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| title_short |
Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| title_full |
Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| title_fullStr |
Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| title_full_unstemmed |
Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| title_sort |
hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems |
| publisher |
Chulalongkorn University |
| publishDate |
2012 |
| url |
http://cuir.car.chula.ac.th/handle/123456789/21048 |
| _version_ |
1681412429960970240 |