อัลกอริทึมทางพันธุกรรม - หัวข้อขั้นสูง

ในส่วนนี้เราจะแนะนำหัวข้อขั้นสูงใน Genetic Algorithms ผู้อ่านที่ต้องการข้อมูลเบื้องต้นเกี่ยวกับ GAs อาจเลือกที่จะข้ามส่วนนี้ไป

ปัญหาการเพิ่มประสิทธิภาพที่ จำกัด

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

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

วิธีที่ใช้บ่อยที่สุดคือ -

• การใช้ penalty functions ซึ่งช่วยลดความเหมาะสมของโซลูชันที่ไม่สามารถทำได้โดยเฉพาะอย่างยิ่งเพื่อให้ความฟิตลดลงตามสัดส่วนด้วยจำนวนข้อ จำกัด ที่ละเมิดหรือระยะห่างจากพื้นที่ที่เป็นไปได้

• การใช้ repair functions ซึ่งใช้วิธีแก้ปัญหาที่ไม่สามารถทำได้และแก้ไขเพื่อให้ข้อ จำกัด ที่ละเมิดได้รับความพึงพอใจ

• Not allowing infeasible solutions เพื่อเข้าสู่ประชากรเลย

• ใช้ special representation or decoder functions ที่รับรองความเป็นไปได้ของโซลูชัน

ความเป็นมาทางทฤษฎีพื้นฐาน

ในส่วนนี้เราจะพูดถึงทฤษฎีบทสคีมาและเอ็นเอฟแอลพร้อมกับสมมติฐานการสร้างบล็อค

Schema Theorem

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

ในส่วนนี้เราไม่ได้เจาะลึกเกี่ยวกับคณิตศาสตร์ของ Schema Theorem แต่เราพยายามที่จะพัฒนาความเข้าใจพื้นฐานเกี่ยวกับสิ่งที่ Schema Theorem คือ คำศัพท์พื้นฐานที่ควรทราบมีดังนี้ -

• ก Schemaคือ "แม่แบบ" ตามปกติจะเป็นสตริงที่ทับตัวอักษร = {0,1, *},

  โดยที่ * ไม่สนใจและสามารถใช้ค่าใดก็ได้

  ดังนั้น * 10 * 1 อาจหมายถึง 01001, 01011, 11001 หรือ 11011

  ในทางเรขาคณิตสคีมาคือไฮเปอร์ระนาบในพื้นที่ค้นหาโซลูชัน

• Order สคีมาคือจำนวนตำแหน่งคงที่ที่ระบุในยีน

• Defining length คือระยะห่างระหว่างสัญลักษณ์คงที่ที่ไกลที่สุดสองตัวในยีน

ทฤษฎีบทสคีมาระบุว่าสคีมานี้ที่มีสมรรถภาพสูงกว่าค่าเฉลี่ยความยาวที่กำหนดสั้นและลำดับที่ต่ำกว่ามีแนวโน้มที่จะอยู่รอดแบบครอสโอเวอร์และการกลายพันธุ์

สมมติฐานการสร้างบล็อค

Building Blocks เป็นสคีมาตาที่มีความยาวต่ำและมีความยาวต่ำโดยมีค่าความเหมาะสมเฉลี่ยข้างต้น สมมติฐานสำเร็จรูปกล่าวว่าหน่วยการสร้างดังกล่าวทำหน้าที่เป็นรากฐานสำหรับความสำเร็จของ GAs และการปรับตัวใน GAs เมื่อดำเนินไปโดยการระบุและรวม "แบบสำเร็จรูป" ดังกล่าวอย่างต่อเนื่อง

ทฤษฎีบทไม่มีอาหารกลางวันฟรี (NFL)

Wolpert และ Macready ในปี 1997 ตีพิมพ์บทความเรื่อง No Free Lunch Theorems for Optimization โดยพื้นฐานแล้วระบุว่าถ้าเราเฉลี่ยในพื้นที่ของปัญหาที่เป็นไปได้ทั้งหมดอัลกอริทึมกล่องดำที่ไม่ได้ตรวจสอบซ้ำทั้งหมดจะแสดงประสิทธิภาพเดียวกัน

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

การเรียนรู้ของเครื่องตาม GA

Genetic Algorithms ยังพบแอปพลิเคชันใน Machine Learning Classifier systems เป็นรูปแบบของ genetics-based machine learning(GBML) ระบบที่ใช้บ่อยในด้านการเรียนรู้ของเครื่อง วิธี GBML เป็นแนวทางเฉพาะสำหรับการเรียนรู้ของเครื่อง

ระบบ GBML มีสองประเภท -

• The Pittsburg Approach - ในแนวทางนี้โครโมโซมหนึ่งชุดได้เข้ารหัสหนึ่งโซลูชันดังนั้นความเหมาะสมจึงถูกกำหนดให้กับโซลูชัน

• The Michigan Approach - โดยทั่วไปแล้วโซลูชันหนึ่งจะแสดงด้วยโครโมโซมจำนวนมากดังนั้นความเหมาะสมจึงถูกกำหนดให้กับโซลูชันบางส่วน

ควรจำไว้ว่าปัญหามาตรฐานเช่นครอสโอเวอร์การกลายพันธุ์ Lamarckian หรือ Darwinian เป็นต้นก็มีอยู่ในระบบ GBML เช่นกัน