Chulalongkorn University Theses and Dissertations (Chula ETD)

Hybrid positive and negative correlation learning in estimation of distribution algorithm for combinatorial optimization problems

Other Title (Parallel Title in Other Language of ETD)

การเรียนรู้สหสัมพันธ์ลูกผสมเชิงบวกและเชิงลบ ในขั้นตอนวิธีการประมาณการแจกแจงสำหรับปัญหาการหาค่าเชิงการจัดที่เหมาะที่สุด

Year (A.D.)

2010

Document Type

Thesis

First Advisor

Prabhas Chongstitvatana

Faculty/College

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

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2010.1735

Abstract

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.

Other Abstract (Other language abstract of ETD)

ศึกษาบทบาทของความรู้เชิงลบในขั้นตอนวิธีเชิงวิวัฒน์ บทสมุติฐาน ส่วนประกอบเชิงลบมีใจความว่า “ขั้นตอนวิธีใดๆ สามารถค้นหาคำตอบที่ดีขึ้นได้โดยการหลีกเลี่ยงการประกอบกัน ของโครงสร้างทางความรู้ที่มีขนาดเล็กที่มีประสิทธิภาพต่ำ ที่เราเรียกกันว่าส่วนประกอบเชิงลบ" สมมุติฐานดังกล่าวถูกทดสอบโดยการพัฒนาขั้นตอนวิธีการประมาณการแจกแจงจากเส้นเชื่อม ที่มีชื่อว่า ขั้นตอนวิธีการบรรจวบ (COIN) ขั้นตอนวิธีดังกล่าวใช้ประโยชน์จากส่วนประกอบเชิงลบที่ซ่อนอยู่ในคำตอบที่ต่ำกว่าค่าเฉลี่ย เพื่อใช้ในการหลีกเลี่ยงการประกอบกันของส่วนประกอบเชิงลบนั้นๆ ขั้นตอนวิธี COIN ถูกทดสอบในปัญหาเชิงการจัดที่มีคำตอบหลายรูปแบบ ทั้งนี้ ผลการทดลองสรุปได้ว่าขั้นตอนวิธี COIN มีส่วนช่วยในการสร้างคำตอบทั้งในเชิงปริมาณและในเชิงคุณภาพ บทบาทของความรู้เชิงลบในปัญหาเชิงการจัดที่ได้จากการทดลอง อาจสรุปได้ดังนี้ (1) ความรู้เชิงลบบังคับในขั้นตอนวิธีค้นหาคำตอบนอกพื้นที่ที่ถูกห้ามเอาไว้ (2) ความรู้เชิงลบช่วยให้ขั้นตอนวิธีผลิตคำตอบที่หลากหลาย ทั้งนี้ต้องมีความแตกต่างจากคำตอบที่มีคุณภาพต่ำ (3) ความรู้เชิงลบเมื่อใช้ร่วมกันกับความรู้เชิงบวก แล้วมีส่วนช่วยในการแยกแยะส่วนประกอบที่ดีและไม่ดีได้ (4) ความรู้เชิงลบช่วยให้ขั้นตอนวิธีเชิงการสร้างค้นหาและประกอบโครงสร้างที่ดีขึ้นได้ ท้ายที่สุด ขั้นตอนวิธี Coin ถูกนำไปทดสอบบนปัญหาที่ใช้งานจริงในหลายวัตถุประสงค์ และแสดงศักยภาพที่เหนือกว่าขั้นตอนวิธีที่ถูกนำมาเปรียบเทียบ

Link to Full Text

Share

COinS