Chulalongkorn University Theses and Dissertations (Chula ETD)

Building-block identification by simultaneity matrix

Other Title (Parallel Title in Other Language of ETD)

การจำแนกส่วนประกอบโดยเมทริกซ์ความพร้อมเพรียง

Year (A.D.)

2004

Document Type

Thesis

First Advisor

Prabhas Chongstitvatana

Faculty/College

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

Degree Name

Doctor of Engineering

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2004.1530

Abstract

The simultaneity matrix is an l x l matrix of numbers. The matrix is constructed according to a set of l-bit solutions. The matrix element m[subscript ij] is the degree of linkage between bit positions i and j. We partition {0,...,l-1} by putting i and j in the same partition subset if m[subscript ij] is significantly high. The partition represents the bit positions of building blocks. The partition is exploited in solution recombination so that the bits governed by the same partition subset are passed together. It can be shown that identifying building blocks by the simultaneity matrix can solve the additively decomposable functions (ADFs) and hierarchically decomposable functions (HDFs) in a polynomial relationship between the number of function evaluations required to reach the optimum and the problem size. A comparison to the hierarchical Bayesian optimization algorithm (hBOA) is made. The hBOA uses less number of function evaluations than that ofour algorithm. However, computing the matrix is 10 times faster and uses 10 times less memory than constructing Bayesian network

Other Abstract (Other language abstract of ETD)

เมทริกซ์ความพร้อมเพรียงคือเมทริกซ์ของตัวเลขขนาด l x l เมทริกซ์ถูกสร้างขึ้นมาจากเซตของคำตอบที่มีความยาว l บิท สมาชิกของเมทริกซ์ (m[subscript ij]) แสดงค่าความสัมพันธ์ระหว่างบิทที่ตำแหน่ง i และบิทที่ตำแหน่ง j เราแบ่งพาร์ทิชันของ {0,...,l-1} โดยใส่ i และ j ไว้ในพาร์ทิชันสับเซ็ทเดียวกัน ถ้า m[subscript ij] มีค่ามาก พาร์ทิชันจะถูกใช้ในการผสมคำตอบ เพื่อที่ว่าบิทที่อยู่ในพาร์ทิชันสับเซ็ทเดียวกันจะติดไปด้วยกัน การใช้เมทริกซ์ความพร้อมเพรียงทำให้หาผลเฉลยที่ดีที่สุดของ Additively Decomposable Function (ADFs) และ Hierarchically Decomposable Functions (HDFs) ได้โดยใช้จำนวนครั้งในการคำนวณฟังก์ชันเพิ่มขึ้นแบบพหุนามตามขนาดของปัญหา การเปรียบเทียบกับ hierarchical Bayesian Optimization Algorithm (hBOA) แสดงให้เห็นว่า hBOA คำนวณค่าฟังก์ชันเป็นจำนวนครั้งน้อยกว่า แต่การคำนวณเมทริกซ์เทียบกับการสร้างโครงข่ายของเบย์ ใช้เวลาน้อยกว่า 10 เท่า และใช้หน่วยความจำน้อยกว่า 10 เท่า

Link to Full Text

Share

COinS