Agent-Based Genetic Algorithm — การค้นหาเชิงวิวัฒนาการแบบกระจายผ่านตัวแทนอิสระ
- ผู้เสนอ
- Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
- ปี
- 1990s
- ประเภท
- Hybrid evolutionary-agent simulation
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Agent-Based Genetic Algorithm (ABGA) เป็นการแบ่งประชากรของอัลกอริทึมพันธุกรรมออกเป็นกลุ่มย่อยๆ กระจายอยู่บนเครือข่ายของตัวแทนอิสระ (autonomous agents) ซึ่งแต่ละตัวแทนจะดูแลประชากรย่อยของตนเองและพัฒนาไปอย่างอิสระ ตัวแทนจะมีการแลกเปลี่ยนสมาชิก (migration) เป็นระยะๆ ตามกฎการสื่อสารหรือความใกล้ชิด ทำให้สามารถสำรวจปริภูมิการค้นหา (search space) แบบขนานไปพร้อมๆ กัน ขณะเดียวกันก็รักษาความหลากหลายของประชากรและหลีกเลี่ยงการลู่เข้าสู่ค่าที่เหมาะสมที่สุดเฉพาะที่ (premature convergence) ได้
แนวคิดเบื้องหลังวิธีการ
อัลกอริทึมพันธุกรรมแบบดั้งเดิมจะมองประชากรทั้งหมดเป็นแหล่งรวมเดียว ซึ่งอาจทำให้เกิดการลู่เข้าสู่ค่าที่เหมาะสมที่สุดเฉพาะที่อย่างรวดเร็ว เนื่องจากยีนเด่นเพียงชนิดเดียวเข้าครอบงำ ในทางตรงกันข้าม วิธีการแบบตัวแทนจะกระจายประชากรย่อยๆ ไปยังตัวแทนกึ่งอิสระที่จัดเรียงตามโครงสร้างแบบเพื่อนบ้าน (neighborhood topology) ตัวแทนแต่ละตัวจะทำการคัดเลือก (selection) การผสมข้าม (crossover) และการกลายพันธุ์ (mutation) ในระดับท้องถิ่นของตนเอง จากนั้นจึงมีการแบ่งปันสมาชิกที่มีความเหมาะสมสูงกับตัวแทนเพื่อนบ้านเป็นครั้งคราว ซึ่งเลียนแบบกระบวนการเกิดสปีชีส์ทางชีววิทยาในประชากรที่แยกจากกันทางภูมิศาสตร์แต่มีการเชื่อมต่อกันเป็นบางครั้ง ทำให้แรงกดดันเชิงวิวัฒนาการที่หลากหลายสามารถทำงานแบบขนานและรวมโซลูชันข้ามกลุ่มเฉพาะ (niches) เข้าด้วยกันได้
ประวัติศาสตร์
อัลกอริทึมพันธุกรรมแบบกระจายและแบบขนานเกิดขึ้นในช่วงต้นทศวรรษ 1990 เมื่อนักวิจัยพยายามเอาชนะปัญหาการลู่เข้าสู่ค่าที่เหมาะสมที่สุดเฉพาะที่อย่างรวดเร็วและใช้ประโยชน์จากฮาร์ดแวร์แบบขนาน Adamidis และ Petridis (1996) ได้กำหนดรูปแบบประชากรตัวแทนที่ทำงานร่วมกันซึ่งมีพฤติกรรมการวิวัฒนาการที่แตกต่างกัน กรอบแนวคิดแบบตัวแทนได้รับความนิยมในช่วงปลายทศวรรษ 1990 และทศวรรษ 2000 เมื่อการสร้างแบบจำลองแบบตัวแทนแพร่หลายไปทั่ววิทยาการคอมพิวเตอร์ โดยกำหนดรูปแบบการปฏิสัมพันธ์แบบอิสระที่ควบคุมโดยโครงสร้างแบบเพื่อนบ้าน ซึ่งปัจจุบันมีการนำไปใช้อย่างกว้างขวางในการหาค่าที่เหมาะสมที่สุดที่ซับซ้อน
ควรใช้เมื่อใด
ใช้ ABGA เมื่อปริภูมิความเหมาะสมมีความขรุขระหรือมีหลายค่าสูงสุด (rugged or multimodal) และ GA แบบมาตรฐานมักจะลู่เข้าสู่ค่าที่เหมาะสมที่สุดเฉพาะที่อย่างรวดเร็วเกินไป เมื่อมีฮาร์ดแวร์แบบขนานหรือแบบกระจายที่สามารถรองรับกระบวนการตัวแทนที่ทำงานพร้อมกันได้ หรือเมื่อโครงสร้างปัญหาแมปกับปัญหาย่อยที่กึ่งอิสระได้อย่างเป็นธรรมชาติ (เช่น ห่วงโซ่อุปทานระดับภูมิภาค, นโยบายหลายภาคส่วน) นอกจากนี้ยังเหมาะสมเมื่อต้องการสำรวจพฤติกรรมของอัลกอริทึมภายใต้แรงกดดันเชิงวิวัฒนาการที่แตกต่างกัน **ไม่ควร**ใช้เมื่อปัญหามีปริภูมิความเหมาะสมแบบค่าสูงสุดเดียว (unimodal) (GA ที่ง่ายกว่าก็เพียงพอ) เมื่อค่าใช้จ่ายในการสื่อสารระหว่างตัวแทนมีมากกว่าการคำนวณ เมื่อขนาดประชากรเล็กเกินไปที่จะแบ่งได้อย่างมีความหมาย หรือเมื่อจำเป็นต้องมีประชากรแบบรวมศูนย์เพื่อความสามารถในการทำซ้ำที่แม่นยำ
ข้อจำกัดและข้อควรพิจารณา
- การปรับนโยบายการย้ายถิ่น (อัตรา, โครงสร้าง, ความถี่) เพิ่มพารามิเตอร์ที่ต้องมีการปรับเทียบอย่างระมัดระวังและขึ้นอยู่กับปัญหา
- ค่าใช้จ่ายในการสื่อสารระหว่างตัวแทนอาจหักล้างประโยชน์ของการประมวลผลแบบขนานในสภาพแวดล้อมการคำนวณที่มีความหน่วงสูงหรือมีการเชื่อมต่อแบบหลวมๆ
- การรับประกันการลู่เข้าเชิงทฤษฎีอ่อนแอกว่า GA มาตรฐาน การวิเคราะห์พลวัตของ ABGA อย่างเป็นทางการยังคงเป็นพื้นที่วิจัยที่เปิดกว้าง
- การทำซ้ำผลลัพธ์ต้องมีการกำหนดโครงสร้างตัวแทน กำหนดการย้ายถิ่น และเมล็ดพันธุ์สุ่ม (random seeds) ให้เหมือนกันทุกตัวแทน ซึ่งทำให้การจำลองซ้ำซับซ้อนขึ้น
- หากขนาดประชากรย่อยเล็กเกินไป ตัวแทนแต่ละตัวมีแนวโน้มที่จะเกิดการลอยตัวทางพันธุกรรม (genetic drift) โดยไม่คำนึงถึงการย้ายถิ่น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รักษาความหลากหลายของประชากรได้สูงกว่า GA แบบ panmictic ลดการลู่เข้าสู่ค่าที่เหมาะสมที่สุดเฉพาะที่อย่างรวดเร็วบนปริภูมิความเหมาะสมที่ขรุขระ
- ใช้ประโยชน์จากโครงสร้างพื้นฐานการประมวลผลแบบขนานหรือแบบกระจายได้อย่างเป็นธรรมชาติสำหรับปัญหาการหาค่าที่เหมาะสมที่สุดขนาดใหญ่
- การตั้งค่าตัวดำเนินการที่แตกต่างกันต่อตัวแทนช่วยให้สามารถสำรวจและใช้ประโยชน์ผ่านกลยุทธ์ที่แตกต่างกันไปพร้อมๆ กันได้
- การย้ายถิ่นของสมาชิกที่มีความเหมาะสมสูงระหว่างตัวแทนช่วยให้เกิดการรวมกลุ่มข้ามกลุ่มเฉพาะ (cross-niche recombination) ซึ่งสามารถค้นพบโซลูชันคุณภาพสูงแบบใหม่ได้
- สถาปัตยกรรมแบบโมดูลาร์ทำให้ง่ายต่อการรวมฮิวริสติกเฉพาะทางโดเมนเข้ากับวงจรการพัฒนาของตัวแทนแต่ละตัว
- ปรับขนาดได้ดีกับมิติของปัญหาเมื่อสามารถแบ่งประชากรย่อยได้อย่างมีความหมาย
การประยุกต์ใช้
- การจัดตารางเวลาและโลจิสติกส์: ปัญหาการจัดลำดับงานแบบกระจาย (job-shop) หรือการจัดเส้นทางยานพาหนะ (vehicle routing) ที่ปัญหาย่อยตามภูมิศาสตร์แมปกับตัวแทนได้อย่างเป็นธรรมชาติ
- การหาค่าที่เหมาะสมที่สุดในการออกแบบทางวิศวกรรม: การออกแบบโครงสร้างหรืออากาศพลศาสตร์ในปริภูมิการค้นหาที่มีหลายค่าสูงสุด ซึ่งได้รับประโยชน์จากการสำรวจกลุ่มเฉพาะแบบขนาน
- การจำลองนโยบาย: การหาค่าที่เหมาะสมที่สุดของพารามิเตอร์นโยบายในแบบจำลองการจำลองทางสังคม (social simulation models) ที่ตัวแทนแสดงถึงผู้มีส่วนได้ส่วนเสียในระดับภูมิภาคหรือภาคส่วน
- การค้นหาไฮเปอร์พารามิเตอร์ของการเรียนรู้ของเครื่อง: การปรับแต่งค่าคอนฟิกูเรชันโมเดลแบบวิวัฒนาการแบบขนานบนคลัสเตอร์คอมพิวเตอร์แบบกระจาย
- ชีวสารสนเทศศาสตร์: การทำนายโครงสร้างโปรตีนและการอนุมานเครือข่ายยีน (gene network inference) บนปริภูมิความเหมาะสมที่มีมิติสูงและขรุขระ
- ปัญญาประดิษฐ์สำหรับเกมและหุ่นยนต์: การพัฒนาพฤติกรรมกลยุทธ์ของตัวแทนในสภาพแวดล้อมแบบหลายตัวแทน (multi-agent environments) ที่มีพลวัตของการวิวัฒนาการร่วม (co-evolutionary dynamics)
วิธีการทำงาน
วิธีการทำงาน
กำหนดโครงสร้างแบบเพื่อนบ้านของตัวแทน (agent topology): ระบุจำนวนตัวแทน (ประชากรย่อย) โครงสร้างแบบเพื่อนบ้าน (วงแหวน, กริด, กราฟแบบ small-world, หรือเชื่อมต่อกันทั้งหมด) และโปรโตคอลการสื่อสารที่ควบคุมว่าเมื่อใดและอย่างไรที่ตัวแทนจะแลกเปลี่ยนสมาชิก ตัวแทนแต่ละตัวเป็นหน่วยประมวลผลอิสระที่มีชุดโครโมโซมของตนเอง
เริ่มต้นประชากรย่อยเฉพาะที่ของตัวแทนแต่ละตัวด้วยโครโมโซมที่สร้างขึ้นแบบสุ่ม (หรือโซลูชันที่กำหนดไว้ล่วงหน้า) กำหนดขนาดประชากรเฉพาะที่ ตัวดำเนินการทางพันธุกรรม (ประเภทและอัตราการผสมข้าม, อัตราการกลายพันธุ์) และกลไกการคัดเลือก (การแข่งขัน, วงล้อสุ่ม, การจัดอันดับ) โดยอิสระสำหรับตัวแทนแต่ละตัว หรือเหมือนกันทั้งหมด
ตัวแทนแต่ละตัวดำเนินการคัดเลือก การผสมข้าม และการกลายพันธุ์หลายชั่วอายุบนประชากรย่อยเฉพาะที่ของตนเองอย่างอิสระ ตัวแทนจะสำรวจส่วนต่างๆ ของปริภูมิการค้นหาภายใต้การกำหนดค่าตัวดำเนินการที่อาจแตกต่างกันไป โดยทำงานแบบขนาน (หรือกึ่งขนานในการจำลองแบบลำดับ) ซึ่งช่วยรักษาความหลากหลายทั่วทั้งระบบ
ในช่วงเวลาการย้ายถิ่นที่กำหนด ตัวแทนจะแบ่งปันชุดสมาชิกที่มีความเหมาะสมสูงสุดกับตัวแทนเพื่อนบ้านตามนโยบายการย้ายถิ่น (เช่น ส่งสมาชิกที่ดีที่สุด, รับแล้วแทนที่สมาชิกที่แย่ที่สุด) อัตราการย้ายถิ่นและโครงสร้างแบบเพื่อนบ้านมีผลต่อความสมดุลระหว่างการใช้ประโยชน์ในท้องถิ่น (local exploitation) และการสำรวจทั่วโลก (global exploration) การย้ายถิ่นบ่อยเกินไปจะทำลายความหลากหลาย การย้ายถิ่นน้อยเกินไปจะทำให้สถาปัตยกรรมแบบกระจายสูญเปล่า
โครโมโซมที่นำเข้าและที่พัฒนาขึ้นในท้องถิ่นทั้งหมดจะถูกประเมินตามฟังก์ชันความเหมาะสมที่ใช้ร่วมกัน ตัวแทนอาจใช้แรงกดดันในการคัดเลือกเฉพาะที่หลังจากการย้ายถิ่นเพื่อรวมสมาชิกที่ได้รับเข้ามาในประชากรของตน ซึ่งอาจมีการคัดทิ้งสมาชิกเดิมที่มีความเหมาะสมน้อยกว่า การประเมินความเหมาะสมเป็นต้นทุนการคำนวณหลัก
สิ้นสุดเมื่อบรรลุเกณฑ์การหยุดทั่วโลก (จำนวนชั่วอายุสูงสุด, การลู่เข้าของค่าความเหมาะสมที่ดีที่สุดทั่วทั้งตัวแทน, หรือเวลาที่ผ่านไป) รวบรวมโซลูชันที่ดีที่สุดที่พบจากตัวแทนทั้งหมดเป็นผลลัพธ์สุดท้าย รายงานเส้นโค้งการลู่เข้าต่อตัวแทนเพื่อวินิจฉัยความหลากหลายของประชากรและประสิทธิภาพการย้ายถิ่น
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่าอัตราการย้ายถิ่นสูงเกินไปจะทำให้ความหลากหลายของประชากรย่อยรวมกันเป็นกลุ่มเดียว (de facto single pool) ซึ่งจะทำลายข้อได้เปรียบหลักของสถาปัตยกรรมแบบตัวแทน
- การละเลยการออกแบบโครงสร้างแบบเพื่อนบ้าน: โครงสร้างแบบเชื่อมต่อกันทั้งหมด (fully connected) ทำให้เกิดการลู่เข้าอย่างรวดเร็ว โครงสร้างแบบวงแหวนที่มีความถี่การย้ายถิ่นต่ำอาจทำให้ตัวแทนถูกแยกออกและหยุดนิ่ง
- การประเมินความเหมาะสมเฉพาะในระดับท้องถิ่นโดยไม่มีฟังก์ชันความเหมาะสมส่วนกลางที่ใช้ร่วมกัน จะทำให้ตัวแทนปรับให้เหมาะสมกับวัตถุประสงค์ที่ไม่เข้ากัน
- การสับสนระหว่าง ABGA กับ multi-objective GA: ABGA เป็นรูปแบบสถาปัตยกรรมเพื่อประสิทธิภาพในการค้นหา ไม่ใช่วิธีการหาค่าที่เหมาะสมที่สุดหลายวัตถุประสงค์โดยเนื้อแท้ การใช้ ABGA แบบ multi-objective จำเป็นต้องมีกลไก Pareto เพิ่มเติม
- การหยุดเมื่อตัวแทนแต่ละตัวลู่เข้า แทนที่จะเป็นการลู่เข้าทั่วโลก อาจทำให้พลาดโซลูชันที่ดีกว่าที่ยังคงพัฒนาอยู่ในตัวแทนอื่นๆ
คำถามที่พบบ่อย
ABGA แตกต่างจาก Parallel GA มาตรฐานอย่างไร?
Parallel GA มาตรฐานมักจะกระจายการประเมินความเหมาะสมของประชากรส่วนกลางเดียวไปยังโปรเซสเซอร์ต่างๆ ในขณะที่ ABGA ให้ประชากรย่อยอิสระแก่ตัวแทนแต่ละตัวพร้อมกับวงจรการวิวัฒนาการของตนเอง การโต้ตอบเกิดขึ้นผ่านการย้ายถิ่นที่ชัดเจนเท่านั้น ไม่ใช่ผ่านกลุ่มประชากรที่ใช้ร่วมกัน ความแตกต่างนี้ช่วยรักษาแรงกดดันในการคัดเลือกที่แตกต่างกันในแต่ละตัวแทน
ควรเลือกโครงสร้างแบบเพื่อนบ้าน (migration topology) แบบใด?
โครงสร้างแบบวงแหวน (ring) และกริด (grid) เป็นจุดเริ่มต้นมาตรฐาน: ช่วยจำกัดการไหลของการย้ายถิ่นและรักษาความหลากหลาย โครงสร้างแบบ small-world (เพิ่มการเชื่อมต่อระยะไกลสองสามจุดเข้าไปในวงแหวน) ช่วยเร่งการแพร่กระจายของโซลูชันที่ดีโดยไม่ทำให้ความหลากหลายลดลง โดยทั่วไปควรหลีกเลี่ยงโครงสร้างแบบเชื่อมต่อกันทั้งหมด (fully connected) เว้นแต่คุณต้องการพฤติกรรมการลู่เข้าที่รวดเร็ว
ควรมีจำนวนตัวแทนเท่าใดและขนาดประชากรย่อยเท่าใดจึงจะเหมาะสม?
หลักการทั่วไปที่พบบ่อยคือ 4-16 ตัวแทน โดยมีขนาดประชากรย่อย 20-50 สมาชิกต่อตัว ซึ่งรวมเป็นประชากรทั้งหมดเทียบเท่ากับที่ GA มาตรฐานจะใช้ จำนวนตัวแทนน้อยเกินไปจะทำให้ข้อได้เปรียบด้านความหลากหลายของสถาปัตยกรรมหมดไป จำนวนตัวแทนมากเกินไปที่มีประชากรย่อยเล็กจิ๋วจะประสบปัญหาการลอยตัวทางพันธุกรรม จำเป็นต้องมีการปรับเทียบเชิงประจักษ์กับปัญหาเฉพาะ
สามารถใช้ ABGA สำหรับการหาค่าที่เหมาะสมที่สุดหลายวัตถุประสงค์ (multi-objective optimization) ได้หรือไม่?
ได้ แต่ต้องมีการเพิ่มกลไก Pareto (เช่น การจัดอันดับ NSGA-II ภายในตัวแทนแต่ละตัว) สถาปัตยกรรมแบบตัวแทนจะช่วยรักษาการประมาณค่าหน้า Pareto (Pareto front approximation) ที่มีความหลากหลายมากขึ้น นี่คือพื้นฐานของรูปแบบ ABGA แบบ multi-objective
ABGA รับประกันว่าจะพบค่าที่เหมาะสมที่สุดทั่วโลก (global optimum) หรือไม่?
ไม่ เช่นเดียวกับ GA ทั้งหมด ABGA เป็นวิธีการแบบฮิวริสติกและไม่รับประกันความเป็นค่าที่เหมาะสมที่สุดทั่วโลก การรักษาความหลากหลายที่ดีขึ้นช่วยเพิ่มความเป็นไปได้ในการหลีกเลี่ยงค่าที่เหมาะสมที่สุดเฉพาะที่ในทางปฏิบัติ แต่การรับประกันการลู่เข้าไม่ได้ดีไปกว่า GA มาตรฐาน และยังคงเป็นคำถามวิจัยเชิงทฤษฎีที่กำลังดำเนินอยู่
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วGenetic algorithm. Wikipedia.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว