Agent-Based Tabu Search — การหาค่าเหมาะสมที่สุดแบบหลายตัวแทนแบบกระจายศูนย์
- ผู้เสนอ
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- ปี
- 1989–1995
- ประเภท
- Hybrid metaheuristic — agent-based distributed tabu search
- กลุ่มวิธี
- Simulation / optimization
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Agent-Based Tabu Search (ABTS) เป็นการผสานเทคนิค metaheuristic แบบ tabu search เข้ากับกรอบการทำงานแบบหลายตัวแทน (multi-agent framework) โดยที่ตัวแทนอิสระแต่ละตัวจะดำเนินการค้นหาแบบ tabu search แบบเดี่ยวหรือแบบร่วมมือกัน โดยแบ่งปันผลลัพธ์ที่ดีเพื่อหลีกเลี่ยงจุดเหมาะสมที่สุดเฉพาะที่ (local optima) และสำรวจปริภูมิการค้นหาแบบผสม (combinatorial) หรือแบบต่อเนื่อง (continuous) ที่มีขนาดใหญ่ได้อย่างมีประสิทธิภาพมากกว่าการดำเนินการแบบเธรดเดียว
แนวคิดเบื้องหลังวิธีการ
การค้นหาแบบ tabu search แบบดั้งเดิมอาจติดอยู่ในบริเวณการค้นหาที่แคบ แม้จะมีกลไกหน่วยความจำระยะสั้นก็ตาม การใช้ตัวแทนอิสระหลายตัว โดยแต่ละตัวจะรักษาบัญชีรายชื่อ tabu (tabu list) และโครงสร้างละแวกบ้าน (neighborhood structure) ของตนเอง ทำให้การค้นหาแผ่ขยายไปยังจุดเริ่มต้นที่หลากหลาย ตัวแทนจะแบ่งปันผลลัพธ์ชั้นยอด (intensification) เป็นระยะๆ และกระจายตัวไปยังบริเวณที่ยังไม่ได้สำรวจ (diversification) โครงสร้างแบบร่วมมือแต่เป็นอิสระนี้เลียนแบบพฤติกรรมฝูงของสิ่งมีชีวิต โดยไม่มีตัวแทนตัวใดตัวหนึ่งมีภาพรวมทั้งหมด แต่โดยรวมแล้วสามารถค้นหาผลลัพธ์คุณภาพสูงได้เร็วกว่าตัวค้นหาแต่ละตัว
ประวัติศาสตร์
Tabu search ถูกทำให้เป็นทางการโดย Fred Glover ในปี 1986–1989 รูปแบบแบบกระจายศูนย์และแบบขนานเริ่มปรากฏในช่วงต้นทศวรรษ 1990 เมื่อนักวิจัยพยายามใช้ประโยชน์จากสถาปัตยกรรมแบบหลายโปรเซสเซอร์ Verhoeven และ Aarts (1995) ได้ทำการศึกษาเชิงระบบเกี่ยวกับการค้นหาเฉพาะที่แบบขนาน รวมถึงกลยุทธ์ tabu แบบร่วมมือ การกำหนดกรอบแบบ Agent-Based กลายเป็นที่โดดเด่นในช่วงปี 2000 เมื่อคำศัพท์ Agent-Based Modeling เข้ามาในวงการวิจัยดำเนินงาน
ควรใช้เมื่อใด
ใช้ Agent-Based Tabu Search เมื่อแก้ไขปัญหาการหาค่าเหมาะสมที่สุดแบบผสม (combinatorial) หรือแบบจำนวนเต็มผสม (mixed-integer) ที่มีความซับซ้อน (การจัดตารางเวลา, การจัดเส้นทาง, การออกแบบเครือข่าย, การจัดสรรทรัพยากร) ซึ่งการค้นหาแบบ tabu search แบบเธรดเดียวเกิดการติดขัดและมีทรัพยากรการคำนวณแบบขนานพร้อมใช้งาน มีประสิทธิภาพเป็นพิเศษเมื่อภูมิทัศน์การค้นหามีจุดเหมาะสมที่สุดเฉพาะที่ (local optima) ที่มีคุณภาพใกล้เคียงกันจำนวนมาก หลีกเลี่ยงการใช้งานเมื่อปัญหามีขนาดเล็กพอสำหรับตัวแก้ที่แม่นยำ (MILP, branch-and-bound), เมื่อการประเมินครั้งเดียวมีค่าใช้จ่ายในการคำนวณสูงเกินไป (ทำให้การประเมินแบบขนานหลายครั้งเป็นไปไม่ได้), หรือเมื่อข้อกำหนดด้านความสามารถในการทำซ้ำได้ขัดแย้งกับพลวัตของการโต้ตอบระหว่างตัวแทนที่ไม่แน่นอน
ข้อจำกัดและข้อควรพิจารณา
- ค่าใช้จ่ายในการซิงโครไนซ์และต้นทุนการสื่อสารระหว่างตัวแทนอาจหักล้างผลประโยชน์จากการประมวลผลแบบขนานในระบบที่มีการเชื่อมต่ออย่างใกล้ชิดหรือเครือข่ายที่ช้า
- มีพารามิเตอร์มากกว่าการค้นหาแบบ tabu search แบบเธรดเดียว: จำนวนตัวแทน, โทโพโลยีการสื่อสาร, ความถี่ในการซิงโครไนซ์, และตัวกระตุ้นการกระจายตัว ทั้งหมดนี้ต้องการการปรับแต่ง
- การรับประกันการลู่เข้าเชิงทฤษฎีอ่อนแอกว่าวิธีการที่แม่นยำ คุณภาพของผลลัพธ์ขึ้นอยู่กับการปรับแต่งและโครงสร้างปัญหาอย่างมาก
- ความสามารถในการทำซ้ำได้ยาก เนื่องจากปฏิสัมพันธ์ของตัวแทนทำให้เกิดความไม่แน่นอนเพิ่มเติม นอกเหนือจากการเริ่มต้นแบบสุ่ม
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- การสำรวจแบบขนานช่วยลดเวลาในการหาผลลัพธ์สำหรับปัญหาแบบผสมที่มีขนาดใหญ่ได้อย่างมาก เมื่อเทียบกับการค้นหาแบบ tabu search แบบเธรดเดียว
- กรอบการทำงานแบบหลายตัวแทนสนับสนุนการกระจายตัวตามธรรมชาติ ลดความเสี่ยงของการลู่เข้าก่อนกำหนดไปยังจุดเหมาะสมที่สุดเฉพาะที่ที่ไม่ดี
- สถาปัตยกรรมที่ยืดหยุ่นช่วยให้ตัวแทนมีความแตกต่างกัน โดยมีโครงสร้างละแวกบ้านที่แตกต่างกัน, กลยุทธ์ระยะเวลา tabu ที่แตกต่างกัน, หรือแม้แต่การผสมผสานเทคนิค metaheuristics
- การแบ่งปันผลลัพธ์แบบร่วมมือกันช่วยถ่ายทอดการค้นพบระหว่างตัวแทน เร่งการเพิ่มประสิทธิภาพในบริเวณที่มีคุณภาพสูง
- ปรับขนาดได้ดีกับแกนประมวลผลที่มีอยู่ ทำให้เหมาะสำหรับสภาพแวดล้อมการคำนวณแบบ multi-core และแบบกระจายศูนย์ในปัจจุบัน
การประยุกต์ใช้
- การจัดเส้นทางยานพาหนะและโลจิสติกส์: การประสานงานตัวแทนหลายตัว ซึ่งแต่ละตัวปรับปรุงปัญหาย่อยของเส้นทาง
- การจัดตารางการผลิตแบบ Job-shop และ Flexible Manufacturing: ตัวแทนจัดการชุดย่อยของเครื่องจักรแบบร่วมมือกัน
- การออกแบบเครือข่ายโทรคมนาคม: การจัดสรรช่องสัญญาณและการหาค่าเหมาะสมที่สุดของโทโพโลยีแบบกระจายศูนย์
- การวางแผนห่วงโซ่อุปทาน: การหาค่าเหมาะสมที่สุดของสินค้าคงคลังและระบบกระจายสินค้าหลายระดับ
- การทำนายโครงสร้างโปรตีน: การค้นหาละแวกบ้านแบบขนานในปริภูมิการกำหนดค่า (conformational spaces)
- การจัดตารางเวลาเรียนและหลักสูตรทางวิชาการ โดยมีตัวแทนระดับภาควิชาแบบกระจายศูนย์
วิธีการทำงาน
วิธีการทำงาน
กำหนดกลุ่มของตัวแทนอิสระ ตัวแทนแต่ละตัวจะได้รับมอบหมายบทบาท: บางตัวมุ่งเน้นไปที่การเพิ่มประสิทธิภาพ (การค้นหาเฉพาะที่อย่างลึกซึ้งรอบๆ บริเวณที่มีแนวโน้มดี) บางตัวมุ่งเน้นไปที่การกระจายตัว (การหลีกหนีไปยังพื้นที่ที่ยังไม่ได้สำรวจ) ตัวแทนแต่ละตัวจะรักษาบัญชีรายชื่อ tabu ของตนเองสำหรับทางเดินที่ต้องห้าม ผลลัพธ์ปัจจุบัน และโครงสร้างละแวกบ้านที่ปรับให้เหมาะกับประเภทของปัญหา (เช่น การสลับ, การแทรก, หรือการเคลื่อนที่แบบ 2-opt สำหรับปัญหาแบบผสม)
เริ่มต้นตัวแทนด้วยผลลัพธ์เริ่มต้นที่แตกต่างกัน ซึ่งอาจสร้างขึ้นแบบสุ่มหรือกำหนดโดยใช้ heuristic เชิงโครงสร้าง (เช่น nearest-neighbor สำหรับการจัดเส้นทาง) ความหลากหลายของผลลัพธ์เริ่มต้นมีความสำคัญอย่างยิ่ง — การเริ่มต้นที่เหมือนกันจะนำไปสู่การค้นหาแบบขนานที่ซ้ำซ้อน ประเมินฟังก์ชันวัตถุประสงค์สำหรับผลลัพธ์เริ่มต้นแต่ละรายการ และบันทึกผลลัพธ์ที่ดีที่สุดทั่วโลก (global best) จากตัวแทนทั้งหมด
ตัวแทนแต่ละตัวจะดำเนินการวนซ้ำการค้นหาแบบ tabu search ของตนเอง: สร้างละแวกบ้านของผลลัพธ์ปัจจุบัน ประเมินผลลัพธ์เพื่อนบ้านทั้งหมด (หรือบางส่วน) เลือกเพื่อนบ้านที่ไม่ใช่ tabu ที่ดีที่สุดเป็นการเคลื่อนที่ครั้งต่อไป (เกณฑ์การยอมรับ (aspiration criterion) อนุญาตให้ยกเลิกบัญชีรายชื่อ tabu ได้หากผู้สมัครมีคุณสมบัติเหนือกว่าผลลัพธ์ที่ดีที่สุดทั่วโลก) และอัปเดตบัญชีรายชื่อ tabu โดยการเพิ่มการเคลื่อนที่ย้อนกลับด้วยระยะเวลา (tenure) ที่ดึงมาจากช่วงคงที่หรือช่วงที่ปรับได้
ตัวแทนจะสื่อสารกันในช่วงเวลาการซิงโครไนซ์ที่กำหนดไว้หรือเมื่อมีเหตุการณ์กระตุ้น กลยุทธ์ทั่วไป ได้แก่ การกระจายผลลัพธ์ที่ดีที่สุดทั่วโลกไปยังตัวแทนทั้งหมด (ซึ่งอาจเริ่มต้นใหม่จากผลลัพธ์นั้น) การนำผลลัพธ์ชั้นยอดเข้าสู่กลุ่มที่ใช้ร่วมกันซึ่งตัวแทนจะปรึกษาเป็นระยะ หรือการแลกเปลี่ยนผลลัพธ์แบบ peer-to-peer ระหว่างตัวแทนที่อยู่ใกล้เคียงกันในโทโพโลยี (วงแหวน, เชื่อมต่อสมบูรณ์, หรือสุ่ม) การควบคุมความหลากหลายจะป้องกันการลู่เข้าก่อนกำหนดโดยการลงโทษตัวแทนที่มีผลลัพธ์เหมือนกัน
สิ้นสุดการทำงานเมื่อถึงงบประมาณการทำซ้ำสูงสุด, ขีดจำกัดเวลาจริง (wall-clock time limit), หรือเกณฑ์การหยุดนิ่ง (stagnation criterion) (เช่น ไม่มีการปรับปรุงผลลัพธ์ที่ดีที่สุดทั่วโลกเป็นจำนวนการทำซ้ำที่กำหนด) เลือกผลลัพธ์ที่ดีที่สุดทั่วโลกที่พบจากตัวแทนทั้งหมดตลอดทุกการทำซ้ำเป็นผลลัพธ์สุดท้าย อาจรายงาน Pareto front หากมีการติดตามหลายวัตถุประสงค์
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่าตัวแทนทั้งหมดให้มีผลลัพธ์เริ่มต้นเหมือนกัน เป็นการสิ้นเปลืองศักยภาพแบบขนาน — ต้องแน่ใจว่ามีการเริ่มต้นที่หลากหลาย
- การสื่อสารที่บ่อยเกินไปทำให้ตัวแทนตกอยู่ในแอ่งผลลัพธ์เดียวกัน ขจัดประโยชน์ของการกระจายตัว และลดการค้นหาให้เหลือเพียงเธรดเดียวอย่างมีประสิทธิภาพ
- การละเลยเกณฑ์การยอมรับในการออกแบบบัญชีรายชื่อ tabu อาจทำให้ตัวแทนพลาดผลลัพธ์ที่ดีกว่าอย่างเห็นได้ชัด โดยเฉพาะอย่างยิ่งในระยะเริ่มต้นของการค้นหา
- การใช้ ABTS กับปัญหาที่การประเมินละแวกบ้านมีค่าใช้จ่ายสูงมากหากไม่มีแบบจำลองตัวแทน (surrogate model) จะส่งผลให้ระยะเวลารันนานเกินไป
คำถามที่พบบ่อย
Agent-Based Tabu Search แตกต่างจากการรันเธรด tabu search หลายๆ เธรดอย่างไร?
ความแตกต่างที่สำคัญคือการร่วมมือ ในการรันแบบขนานอิสระ เธรดจะไม่เคยแบ่งปันข้อมูล ใน ABTS ตัวแทนจะแลกเปลี่ยนผลลัพธ์อย่างแข็งขัน, อัปเดตคลังผลลัพธ์ชั้นยอดที่ใช้ร่วมกัน, หรือใช้ตัวกระตุ้นการกระจายตัวตามสถานะรวม — สร้างพฤติกรรมการค้นหาที่เกิดขึ้นใหม่ซึ่งไม่มีในการรันแบบอิสระ
ฉันควรใช้ตัวแทนกี่ตัว?
จุดเริ่มต้นทั่วไปคือตัวแทนหนึ่งตัวต่อแกน CPU ที่พร้อมใช้งาน งานวิจัยชี้ให้เห็นว่าผลตอบแทนจะลดลงเมื่อใช้ตัวแทนมากกว่า 8–16 ตัวสำหรับปัญหาแบบผสมส่วนใหญ่ เนื่องจากค่าใช้จ่ายในการสื่อสารเพิ่มขึ้น การทดลองนำร่องด้วยตัวแทน 4, 8 และ 16 ตัวช่วยระบุจุดที่เหมาะสมที่สุดสำหรับปัญหาที่กำหนด
ABTS สามารถจัดการกับปัญหาหลายวัตถุประสงค์ได้หรือไม่?
ได้ ตัวแทนสามารถรักษาค่าประมาณของ Pareto front ในระดับท้องถิ่น และแบ่งปันผลลัพธ์ที่ไม่ถูกครอบงำ (non-dominated solutions) ผ่านคลังเก็บข้อมูลที่ใช้ร่วมกัน บางครั้งเรียกว่า Multi-Objective Agent-Based Tabu Search และแตกต่างจาก ABTS แบบวัตถุประสงค์เดียวมาตรฐาน
โทโพโลยีการสื่อสารแบบใดดีที่สุด?
โทโพโลยีแบบเชื่อมต่อสมบูรณ์ (fully connected) แพร่กระจายผลลัพธ์ที่ดีได้เร็วที่สุด แต่สร้างต้นทุนการสื่อสารสูง โทโพโลยีแบบวงแหวน (ring) หรือแบบโลกเล็ก (small-world) สร้างสมดุลระหว่างการแพร่กระจายข้อมูลกับความเป็นอิสระ สำหรับปัญหาในทางปฏิบัติส่วนใหญ่ โทโพโลยีแบบวงแหวนหรือแบบสุ่มแบบเบาบาง (sparse) ทำงานได้ดีเป็นค่าเริ่มต้น
เมื่อใดที่ฉันควรเลือกใช้ genetic algorithm หรือ particle swarm แทน ABTS?
เลือกใช้วิธีการแบบประชากร (population-based methods) (GA, PSO) เมื่อปัญหามีภูมิทัศน์แบบต่อเนื่องและเรียบ หรือเมื่อตัวดำเนินการ crossover/recombination ถูกกำหนดไว้อย่างดี ABTS จะโดดเด่นในปัญหาแบบไม่ต่อเนื่อง (discrete) แบบผสม (combinatorial) ที่มีตัวดำเนินการละแวกบ้านที่กำหนดไว้อย่างดี ซึ่งหน่วยความจำแบบ tabu ให้ข้อได้เปรียบในการค้นหาที่แข็งแกร่ง
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วVerhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว