Chulalongkorn University Theses and Dissertations (Chula ETD)

การปรับปรุงการสร้างแผนภาพตัดสินใจทวิภาค โดยเทคนิคการเรียนรู้ต้นไม้ตัดสินใจและขั้นนตอนวิธีทางพันธุกรรม

Other Title (Parallel Title in Other Language of ETD)

An improvement of construction of binary decision diagrams by the decision tree learning technique and genetic algorithm

Year (A.D.)

2001

Document Type

Thesis

First Advisor

อาทิตย์ ทองทักษ์

Second Advisor

บุญเสริม กิจศิริกุล

Faculty/College

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

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2001.1099

Abstract

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

Other Abstract (Other language abstract of ETD)

A Binary Decision Diagram (BDD) is an efficient graphical data structure for representing boolean functions. Since the size of the diagram depends on the variable ordering of the diagram, a decision tree learning technique has been used to construct a good initial binary decision diagram. Then, a gradual improvement technique has been used to reduce the size of the diagram. However, the diagram can be more reduced. Therefore, this research proposes to use a genetic algorithm, which can search for the optimal result of very complicated problems, to search for a sequence of the gradual improvement techniques for reducing the diagram. Then this sequence of techniques is applied to find the opitmal variable ordering for compacting the diagram obtained by the decision tree learning technique. Due to the experiment, the gradual improvement technique, which is in a chromosome, has to be modified so that it can be more reduce the size of the diagram than SIFTING method. The modification can be done by reducing the working steps or allowing the diagram to be larger in some period of finding the variable ordering. Moreover, the set of learning sample is also important to increase the effectiveness of the sequence of the gradual improvement techniques

Link to Full Text

Share

COinS