อัลกอริทึมทางพันธุกรรมเหมาะสำหรับปัญหาเช่นปัญหา Knuth หรือไม่?
เราทุกคนทราบดีว่า Genetic Algorithms สามารถให้โซลูชันที่ดีที่สุดหรือใกล้เคียงที่สุด ดังนั้นในปัญหาบางอย่างเช่นปัญหา NP-hard ด้วยการแลกเปลี่ยนระหว่างเวลาและวิธีแก้ปัญหาที่ดีที่สุดวิธีแก้ปัญหาที่ใกล้เคียงที่สุดนั้นดีพอ
เนื่องจากไม่มีการรับประกันว่าจะพบโซลูชันที่ดีที่สุด GA จึงถือเป็นทางเลือกที่ดีสำหรับการแก้ปัญหา Knuth หรือไม่
ตามปัญญาประดิษฐ์: แนวทางสมัยใหม่ (ฉบับที่สาม) ส่วน 3.2 (น. 73):
Knuth คาดเดาว่าเริ่มต้นด้วยหมายเลข 4 ลำดับของการดำเนินการแฟกทอเรียลรากที่สองและพื้นจะได้จำนวนเต็มบวกที่ต้องการ
ตัวอย่างเช่น 5 สามารถเข้าถึงได้จาก 4:
ชั้น (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
ดังนั้นหากเรามีตัวเลข (5) และเราต้องการทราบลำดับของการดำเนินการของทั้ง 3 ตัวที่กล่าวถึงเพื่อให้ได้จำนวนที่กำหนดยีนของโครโมโซมแต่ละตัวจะเป็นตัวเลขที่แสดงถึงการดำเนินการบางอย่างโดยมีจำนวนเพิ่มเติมสำหรับ (ไม่มีการดำเนินการ) และฟังก์ชันการออกกำลังกายจะเป็นความแตกต่างที่แน่นอนระหว่างจำนวนที่กำหนดและจำนวนที่เราได้รับจากการใช้การดำเนินการตามลำดับที่แน่นอนสำหรับโครโมโซมแต่ละตัว (ถึงต่ำสุด) ลองพิจารณาว่าจำนวนการทำซ้ำ (รุ่น) นั้นทำได้โดยไม่มีวิธีแก้ปัญหาที่ดีที่สุดและจำนวนที่ใกล้ที่สุดที่เรามีคือ 4 (ด้วยสมรรถภาพ 1) ปัญหาคือเราจะได้รับ 4 จากการใช้การไม่ใช้ 4 ในขณะที่ 5 เราต้องการ การดำเนินการจำนวนมากดังนั้นโซลูชันที่ใกล้เคียงที่สุดจึงไม่ได้อยู่ใกล้กับโซลูชัน
แล้ว GA ไม่เหมาะกับปัญหาแบบนี้หรือ? หรือการแสดงโครโมโซมที่แนะนำและการทำงานของสมรรถภาพไม่ดีพอ?
คำตอบ
ก่อนที่จะพยายามตอบคำถามของคุณอย่างตรงไปตรงมาให้ฉันชี้แจงบางสิ่ง
ผู้คนมักใช้คำว่าอัลกอริทึมทางพันธุกรรม (GAs) แต่ในหลาย ๆ กรณีสิ่งที่พวกเขาหมายถึงจริงๆคืออัลกอริธึมวิวัฒนาการ (EAs) ซึ่งเป็นชุดของอัลกอริธึมที่อิงตามประชากร (กล่าวคือการรักษาหลายโซลูชันในเวลาเดียวกัน) อัลกอริทึมการเพิ่มประสิทธิภาพและ วิธีการที่มีแรงบันดาลใจจากความชัดเจนและความอยู่รอดของ fittest GAs เป็นหนึ่งในวิธีการเหล่านี้โดยที่โครโมโซมเป็นไบนารีและคุณมีทั้งการกลายพันธุ์และการดำเนินการข้าม มีวิธีอื่น ๆ เช่นการมีกลยุทธ์วิวัฒนาการหรือโปรแกรมทางพันธุกรรม
อย่างที่คุณสังเกตเห็น EAs เป็น meta-heuristics และแม้ว่าจะมีงานวิจัยบางอย่างเกี่ยวกับคุณสมบัติการลู่เข้า [ 1 ] แต่ในทางปฏิบัติก็ไม่อาจบรรจบกันได้ อย่างไรก็ตามเมื่อแนวทางอื่นที่เป็นไปได้ล้มเหลว EAs จะมีประโยชน์อย่างแน่นอน
ในกรณีของคุณปัญหาคือการค้นหานิพจน์แบบปิด (หรือเชิงวิเคราะห์ ) ของฟังก์ชันซึ่งประกอบด้วยฟังก์ชันอื่น ๆ ที่มีขนาดเล็กกว่า นี่คือสิ่งที่การเขียนโปรแกรมทางพันธุกรรม (โดยเฉพาะอย่างยิ่ง GP แบบต้นไม้) ถูกสร้างขึ้นเพื่อ ในความเป็นจริงปัญหา Knuth เป็นตัวอย่างเฉพาะของปัญหาการถดถอยเชิงสัญลักษณ์ซึ่งเป็นปัญหาทั่วไปที่ GP นำไปใช้ ดังนั้น GP น่าจะเป็นแนวทางแรกที่คุณควรลอง
ในขณะเดียวกันฉันได้ติดตั้งโปรแกรมง่ายๆใน DEAP ที่พยายามแก้ปัญหา Knuth ตรวจสอบที่นี่ ความเหมาะสมของโซลูชันที่ดีที่สุดที่พบจนถึงตอนนี้ (ที่มีเมล็ดพันธุ์) คือ 4 และวิธีแก้ปัญหาคือfloor(sqrt(float(sqrt(4))))(ที่นี่floatจะแปลงอินพุตเป็นตัวเลขทศนิยมเพื่อให้แน่ใจว่าประเภทปลอดภัย) ฉันใช้ความแตกต่างเป็นฟังก์ชันการออกกำลังกายและใช้อัลกอริทึม GP สำหรับ 100 ชั่วอายุคนโดยมี 100 คนสำหรับแต่ละรุ่น (ซึ่งไม่มาก!) ฉันไม่ได้ปรับแต่งค่าไฮเปอร์พารามิเตอร์มากนักบางทีด้วยเมล็ดพันธุ์และพารามิเตอร์ไฮเปอร์ที่ถูกต้องคุณสามารถหาวิธีแก้ปัญหาที่เหมาะสมได้
โดยหลักการแล้วเพื่อจัดการกับข้อกังวลของคุณคุณสามารถใช้การเข้ารหัสนั้นได้ แต่ตามที่คุณทราบ GA สามารถส่งคืนได้ $4$ เป็นทางออกที่ดีที่สุด (ซึ่งจริงๆแล้วไม่ไกล $5$), which you could avoid my killing, at every generation, any individuals that have just that value.
I didn't spend too much time on my implementation and thinking about this problem, but, as I said above, even with genetic programming and using only Knuth's operations, it could get stuck in local optima. You could try to augment my (or your) implementation with other operations, such as the multiplication and addition, and see if something improves.