Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/11154
Title: A genetic algorithm for finite state machine inference
Other Titles: ขั้นตอนวิธีเชิงพันธุกรรมสำหรับการอนุมานเครื่องจักรสถานะจำกัด
Authors: Nattee Niparnan
Advisors: Prabhas Chongstitvatana
Other author: Chulalongkorn University. Faculty of Engineering
Advisor's Email: Prabhas.C@chula.ac.th
Subjects: Genetic algorithms
Finite state machine
Inductive inference
Issue Date: 2002
Publisher: Chulalongkorn University
Abstract: This thesis tackles the problem of finite state machine inference. The objective of the problem is to synthesize a finite state machine that can mimic the target machine by passively inspecting the input/output of the target machinte. This work proposes a genetic algorithm for the problem. The experiments are carried out to compare the performance and the efficiency of the proposed algorithm. The result indicates that the proposed algorithm outperforms other methods. This work also gives an analysis of the algorithm in comparison with other algorithms. The analysis shows interesting issues in genetic algorithms such as introns and the linkage problem.
Other Abstract: วิทยานิพนธ์ฉบับนี้ได้ศึกษาปัญหาการอนุมานเครื่องจักรสถานะจำกัด โดยมีเป้าหมายเพื่อที่จะสร้างเครื่องจักรสถานะจำกัด ที่สามารถลอกเลียนแบบพฤติกรรมของเครื่องจักรเป้าหมายโดยการสังเกตอินพุตและเอาต์พุตของเครื่องจักรเป้าหมาย วิทยานิพนธ์นี้ได้นำเสนอขั้นตอนวิธีเชิงพันธุกรรมสำหรับปัญหาดังกล่าว และได้ทำการทดลองเปรียบเทียบขั้นตอนวิธีดังกล่าวกับขั้นตอนวิธีต่างๆ ที่ใช้ในการแก้ไขปัญหาเดียวกัน ผลจากการทดลองแสดงให้เห็นว่า ขั้นตอนวิธีที่ได้นำเสนอนั้น มีประสิทธิภาพในการทำงานที่ดีกว่าวิธีอื่นๆ ที่นำมาเปรียบเทียบ นอกจากนี้วิทยานิพนธ์ฉบับนี้ยังได้ทำการวิเคราะห์ขั้นตอนวิธีดังกล่าว เปรียบเทียบกับขั้นตอนวิธีอื่นๆ ซึ่งผลจากการวิเคราะห์ได้ชี้ให้เห็นถึงแง่มุมต่างๆ ที่น่าสนใจในเรื่องของขั้นตอนวิธีเชิงพันธุกรรมตัวอย่างเช่น อินตรอน และปัญหาการเชื่อมโยงของโครโมโซม
Description: Thesis (M.Eng.)--Chulalongkorn University, 2002
Degree Name: Master of Engineering
Degree Level: Master's Degree
Degree Discipline: Computer Engineering
URI: http://cuir.car.chula.ac.th/handle/123456789/11154
ISBN: 9741717881
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
Nattee.pdf621.27 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.