Skip to content
กลับไปยังผลการค้นหา

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)

วิธีการทำงาน

วิธีการทำงาน

1

กำหนดโครงสร้างแบบเพื่อนบ้านของตัวแทน (agent topology): ระบุจำนวนตัวแทน (ประชากรย่อย) โครงสร้างแบบเพื่อนบ้าน (วงแหวน, กริด, กราฟแบบ small-world, หรือเชื่อมต่อกันทั้งหมด) และโปรโตคอลการสื่อสารที่ควบคุมว่าเมื่อใดและอย่างไรที่ตัวแทนจะแลกเปลี่ยนสมาชิก ตัวแทนแต่ละตัวเป็นหน่วยประมวลผลอิสระที่มีชุดโครโมโซมของตนเอง

2

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

3

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

4

ในช่วงเวลาการย้ายถิ่นที่กำหนด ตัวแทนจะแบ่งปันชุดสมาชิกที่มีความเหมาะสมสูงสุดกับตัวแทนเพื่อนบ้านตามนโยบายการย้ายถิ่น (เช่น ส่งสมาชิกที่ดีที่สุด, รับแล้วแทนที่สมาชิกที่แย่ที่สุด) อัตราการย้ายถิ่นและโครงสร้างแบบเพื่อนบ้านมีผลต่อความสมดุลระหว่างการใช้ประโยชน์ในท้องถิ่น (local exploitation) และการสำรวจทั่วโลก (global exploration) การย้ายถิ่นบ่อยเกินไปจะทำลายความหลากหลาย การย้ายถิ่นน้อยเกินไปจะทำให้สถาปัตยกรรมแบบกระจายสูญเปล่า

5

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

6

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

ข้อผิดพลาดที่พบบ่อย

  • การตั้งค่าอัตราการย้ายถิ่นสูงเกินไปจะทำให้ความหลากหลายของประชากรย่อยรวมกันเป็นกลุ่มเดียว (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 มาตรฐาน และยังคงเป็นคำถามวิจัยเชิงทฤษฎีที่กำลังดำเนินอยู่

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Genetic algorithm. Wikipedia.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว