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

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)
  • การจัดตารางเวลาเรียนและหลักสูตรทางวิชาการ โดยมีตัวแทนระดับภาควิชาแบบกระจายศูนย์

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

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

1

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

2

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

3

ตัวแทนแต่ละตัวจะดำเนินการวนซ้ำการค้นหาแบบ tabu search ของตนเอง: สร้างละแวกบ้านของผลลัพธ์ปัจจุบัน ประเมินผลลัพธ์เพื่อนบ้านทั้งหมด (หรือบางส่วน) เลือกเพื่อนบ้านที่ไม่ใช่ tabu ที่ดีที่สุดเป็นการเคลื่อนที่ครั้งต่อไป (เกณฑ์การยอมรับ (aspiration criterion) อนุญาตให้ยกเลิกบัญชีรายชื่อ tabu ได้หากผู้สมัครมีคุณสมบัติเหนือกว่าผลลัพธ์ที่ดีที่สุดทั่วโลก) และอัปเดตบัญชีรายชื่อ tabu โดยการเพิ่มการเคลื่อนที่ย้อนกลับด้วยระยะเวลา (tenure) ที่ดึงมาจากช่วงคงที่หรือช่วงที่ปรับได้

4

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

5

สิ้นสุดการทำงานเมื่อถึงงบประมาณการทำซ้ำสูงสุด, ขีดจำกัดเวลาจริง (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 ให้ข้อได้เปรียบในการค้นหาที่แข็งแกร่ง

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

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

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว