Chulalongkorn University Theses and Dissertations (Chula ETD)

A genetic algorithm for finite state machine inference

Other Title (Parallel Title in Other Language of ETD)

ขั้นตอนวิธีเชิงพันธุกรรมสำหรับการอนุมานเครื่องจักรสถานะจำกัด

Year (A.D.)

2002

Document Type

Thesis

First Advisor

Prabhas Chongstitvatana

Faculty/College

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

Degree Name

Master of Engineering

Degree Level

Master's Degree

Degree Discipline

Computer Engineering

DOI

10.58837/CHULA.THE.2002.1592

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 (Other language abstract of ETD)

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

Link to Full Text

Share

COinS