Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/72786
| Title: | การปรับปรุงการสร้างแผนภาพตัดสินใจทวิภาค โดยเทคนิคการเรียนรู้ต้นไม้ตัดสินใจและขั้นนตอนวิธีทางพันธุกรรม |
| Other Titles: | An improvement of construction of binary decision diagrams by the decision tree learning technique and genetic algorithm |
| Authors: | จิตติ เมตตาเมธา |
| Advisors: | อาทิตย์ ทองทักษ์ บุญเสริม กิจศิริกุล |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | Arthit.T@Chula.ac.th Boonserm.K@Chula.ac.th |
| Subjects: | แผนภาพตัดสินใจทวิภาค การเรียนรู้ต้นไม้ตัดสินใจ จีเนติกอัลกอริทึม |
| Issue Date: | 2544 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | แผนภาพตัดสินใจทวิภาคเป็นโครงสร้างข้อมูลแบบกราฟที่มีประสิทธิภาพในการแทนฟังก์ชันบูลีน แต่เนื่องจากขนาดของแผนภาพตัดสินใจขึ้นอยู่กับลำดับของตัวแปรที่ใช้ในการสร้าง ดังนั้นจึงได้มีการนำเทคนิคการเรียนเต้นไม้ตัดสินใจมาใช้สร้างแผนภาพตัดสินใจซึ่งมีลำดับตัวแปรเริ่มต้นที่ดี ต่อมาจึงใช้การพัฒนาทีละขั้นแต่ละวิธีหาลำดับตัวแปรที่ทำให้แผนภาพตัดสินใจมีขนาดเล็กลง แต่แผนภาพดังกล่าวยังสามารถทำให้เล็กลงได้อีก ดังนั้นงานวิจัยนี้จึงนำขั้นตอนวิธีพันธุกรรมที่สามารถค้นหาคำตอบที่ดีที่สุดจากปัญหาที่มีความซับซ้อนมากได้ มาใช้ในการหาลำดับของชุดวิธีการพัฒนาทีละ ขั้นเพื่อใช้หาลำดับตัวแปรที่ดีที่ทำให้แผนภาพตัดสินใจมีขนาดเล็ก หลังจากใช้เทคนิคการเรียนเต้นไม้ตัดสินใจสร้างแผนภาพแล้ว จากการทดลองการใช้ขั้นตอนวิธีพันธุกรรมหาลำดับวิธีการพัฒนาทีละขั้นพบว่า ต้องมีการดัดแปลงวิธีการพัฒนาทีละขั้นที่อยู่ในสายโครโมโซมเพื่อให้สามารถลดขนาดแผนภาพตัดสินใจ ทวิภาคได้ดีกว่าวิธี SIFTING โดยการลดการทำงานของวิธีพัฒนาทีละขั้นลงและยอมให้แผนภาพมีขนาดใหญ่ขึ้นได้ในบางช่วงของหาลำดับตัวแปร และใช้ตัวอย่างเรียนที่เหมาะสม |
| Other Abstract: | 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 |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2544 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาศาสตร์คอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/72786 |
| ISBN: | 9740314873 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Jitti_me_front_p.pdf | หน้าปก สารบัญ และบทคัดย่อ | 832.72 kB | Adobe PDF | View/Open |
| Jitti_me_ch1_p.pdf | บทที่ 1 | 646.09 kB | Adobe PDF | View/Open |
| Jitti_me_ch2_p.pdf | บทที่ 2 | 1.15 MB | Adobe PDF | View/Open |
| Jitti_me_ch3_p.pdf | บทที่ 3 | 699.74 kB | Adobe PDF | View/Open |
| Jitti_me_ch4_p.pdf | บทที่ 4 | 1.04 MB | Adobe PDF | View/Open |
| Jitti_me_ch5_p.pdf | บทที่ 5 | 626.34 kB | Adobe PDF | View/Open |
| Jitti_me_back_p.pdf | บรรณานุกรมและภาคผนวก | 1.48 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.