Chulalongkorn University Theses and Dissertations (Chula ETD)

หน่วยการสร้างในการคำนวณเชิงวิวัฒน์เพื่อแก้ปัญหาหลายจุดประสงค์

Other Title (Parallel Title in Other Language of ETD)

Building blocks in evolutionary computation for solving muti-objective problems

Year (A.D.)

2009

Document Type

Thesis

First Advisor

ประภาส จงสถิตย์วัฒนา

Faculty/College

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

Degree Name

วิศวกรรมศาสตรดุษฎีบัณฑิต

Degree Level

ปริญญาเอก

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2009.1353

Abstract

ศึกษาการใช้การระบุหน่วยการสร้างโดยเมทริกซ์ไคกำลังสอง (BICM) เพื่อปรับปรุงวิธีการไขว้เปลี่ยนให้เป็นแบบใช้หน่วยการสร้าง เพื่อนำไปแก้ปัญหาหลายจุดประสงค์ การทดลองในวิทยานิพนธ์นี้ได้ศึกษาทั้งในกรณีจุดประสงค์เดียวและหลายจุดประสงค์ ในกรณีปัญหาจุดประสงค์เดียว ได้ทดลองนำกลวิธีระบุหน่วยการสร้างไปใช้ปรับปรุงการไขว้เปลี่ยนของขั้นตอนวิธีเชิงพันธุกรรมอย่างง่าย และได้พบว่าสามารถแก้ปัญหากับดักได้ดีกว่าขั้นตอนวิธีเชิงพันธุกรรมอย่างง่าย โดยเฉพาะปัญหาขนาดใหญ่และมีหน่วยการสร้างหลวม จากนั้นได้ทดลองแก้ปัญหาหลายจุดประสงค์ โดยปรับวิธีการไขว้เปลี่ยนของขั้นตอนวิธี NSGA-II ให้เป็นวิธีการไขว้เปลี่ยนแบบใช้หน่วยการสร้าง และได้ออกแบบวิธีการหาและใช้หน่วยการสร้างสำหรับปัญหาหลายจุดประสงค์ที่ต่างกัน 4 แบบคือ 1) การใช้หน่วยการสร้างร่วมจากคำตอบในพาเรโตฟรอนท์ 2) การผสมหน่วยการสร้างแบบเชื่อมั่น 3) การผสมหน่วยการสร้างแบบขยาย และ 4) ใช้หน่วยการสร้างจากแต่ละจุดประสงค์แยกกัน จากผลการทดลองพบว่า สำหรับปัญหาขนาดใหญ่ขั้นตอนวิธีที่นำเสนอทั้งสี่แบบ ให้ผลการทดลองดีกว่าขั้นตอนวิธี NSGA-II เดิมซึ่งใช้วิธีการไขว้เปลี่ยนแบบสองจุด

Other Abstract (Other language abstract of ETD)

To study the use of building block identification in conjunction with chi-square matrix to solve multi-objective problems. The canonical crossover operator in the evolutionary algorithm is substituted by the building-block-wise crossover operator. The experiments in this thesis are carried out on both single and multi- objective problems. In case of single objective problems, the crossover operator in simple genetic algorithm is replaced by the BB-wise one. The results show that for the trap problems, BB-wise genetic algorithm has better performance especially for difficult problems such as the large problems and the problems that have loose linkage. For multi-objective problems, the well-known algorithm, NSGA-II is used as the base algorithm. Four different building-block-wise crossover operators are proposed and investigated: 1) BB based on solutions in Pareto front 2) BB from all objectives in conjunctive form 3) BB from all objectives in disjunctive form 4) BB by mixing BB from each objective. The results of the experiments show that for the large problems, all proposed operators out-perform the two-point crossover operator in the original NSGA-II.

Link to Full Text

Share

COinS