Chulalongkorn University Theses and Dissertations (Chula ETD)

วิธีออปชันจริงในการหาเวลาหยุดเหมาะสุดของขั้นตอนวิธีเชิงพันธุกรรม

Other Title (Parallel Title in Other Language of ETD)

Real options approach to finding optimal stopping time in genetic algorithms

Year (A.D.)

2008

Document Type

Thesis

First Advisor

ดาริชา สุธีวงศ์

Second Advisor

ประภาส จงสถิตย์วัฒนา

Faculty/College

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

Degree Name

วิศวกรรมศาสตรดุษฎีบัณฑิต

Degree Level

ปริญญาเอก

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2008.1290

Abstract

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

Other Abstract (Other language abstract of ETD)

This thesis proposes using a real-options approach to find an optimal stopping time of genetic algorithms. The real options methodology is an evaluation tool for making decision under uncertainty, such as analyzing various investments. Applying this approach to guide algorithms decisions is a novelty of this thesis. The optimal stopping time analysis using the real options technique offers us two pieces of information: an algorithm value, which is the value of algorithms in searching for a solution optimally, and a stopping criterion based on boundary of a fitness value in each generation. This research proposes using an algorithm value as a quantitative measure for comparing the efficiency of algorithms in terms of benefit. It takes a computational cost, time and the possibility of finding a solution into account. The bounds of a fitness value in each generation guide the algorithm on whether to terminate or to keep searching for a solution. The experimental results show that when the genetic algorithms follow the proposed boundary as a stopping criterion, the number of fitness evaluations can be reduced.

Link to Full Text

Share

COinS