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

Robust Tabu Search — อัลกอริทึมเหนือการค้นหาแบบ Tabu ที่มีความทนทานต่อความไม่แน่นอน

ผู้เสนอ
Glover, F. (Tabu Search); robustness extensions by various authors
ปี
1989 (TS); robust variant ~2000s
ประเภท
Metaheuristic with robustness mechanism
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Robust Tabu Search (RTS) เป็นการพัฒนาต่อยอดจากอัลกอริทึมเหนือการค้นหาแบบ Tabu (Tabu Search) แบบดั้งเดิม โดยการประเมินผลของคำตอบที่เป็นไปได้ ไม่เพียงแต่พิจารณาจากค่าวัตถุประสงค์ตามปกติ (nominal objective value) เท่านั้น แต่ยังรวมถึงประสิทธิภาพภายใต้สภาวะความไม่แน่นอนด้วย แทนที่จะหาคำตอบที่ดีที่สุดสำหรับสถานการณ์เดียว RTS จะหาคำตอบที่ทำงานได้ดีในหลากหลายสถานการณ์หรือผลลัพธ์ โดยแลกเปลี่ยนความเหมาะสมสูงสุดกับความน่าเชื่อถือ

แนวคิดเบื้องหลังวิธีการ

Tabu Search แบบดั้งเดิมสามารถหาคำตอบที่ยอดเยี่ยมได้โดยการห้ามการเคลื่อนที่ที่เพิ่งเยี่ยมชมไปและนำทางการค้นหาผ่านเพื่อนบ้าน (neighborhood) ในทางปฏิบัติ อย่างไรก็ตาม ข้อมูลนำเข้าในโลกแห่งความเป็นจริง เช่น ต้นทุน ความต้องการ หรือเวลาเดินทาง อาจมีการเปลี่ยนแปลง คำตอบที่ดูเหมือนเหมาะสมที่สุดภายใต้ค่าที่สมมติไว้อาจทำงานได้ไม่ดีเมื่อความเป็นจริงแตกต่างออกไป Robust Tabu Search ได้ฝังเกณฑ์ความทนทาน (robustness criterion) เข้าไปในฟังก์ชันการประเมินโดยตรง: คำตอบที่เป็นไปได้แต่ละรายการจะถูกประเมินผ่านหลายสถานการณ์ (สุ่มตัวอย่างหรือแจกแจง) และการค้นหาจะให้ความสำคัญกับคำตอบที่มีประสิทธิภาพที่เสถียรและมีความแปรปรวนต่ำ สิ่งนี้ทำให้คำตอบสุดท้ายมีความยืดหยุ่นต่อการเปลี่ยนแปลงของพารามิเตอร์โดยไม่จำเป็นต้องปรับให้เหมาะสมใหม่หลังจากนั้น

ประวัติศาสตร์

Tabu Search ถูกนำเสนอโดย Fred Glover ในปี 1989–1990 ในฐานะอัลกอริทึมเหนือการค้นหาที่ใช้หน่วยความจำ ซึ่งหลีกเลี่ยงจุดเหมาะสมที่สุดเฉพาะที่ (local optima) โดยการห้ามการเคลื่อนที่ที่ย้อนกลับไปเมื่อเร็วๆ นี้ การพัฒนาแบบ Robust ได้เกิดขึ้นในช่วงปลายทศวรรษ 1990 และ 2000 ควบคู่ไปกับความสนใจที่เพิ่มขึ้นในการหาค่าที่เหมาะสมที่สุดแบบ Robust (robust optimization) นักวิจัยได้รวมการประเมินตามสถานการณ์และกรณีที่เลวร้ายที่สุดเข้ากับการประเมินเพื่อนบ้านของ TS ทำให้เกิด Robust Tabu Search ในฐานะเครื่องมือที่ใช้งานได้จริงสำหรับปัญหาทางวิศวกรรมและโลจิสติกส์ภายใต้ความไม่แน่นอน

ควรใช้เมื่อใด

ใช้ Robust Tabu Search เมื่อคุณเผชิญกับปัญหาการหาค่าที่เหมาะสมที่สุดแบบผสมหรือแบบไม่ต่อเนื่อง ซึ่งพารามิเตอร์นำเข้าที่สำคัญไม่แน่นอนหรือผันแปรได้ — ปัญหาการจัดเส้นทาง การจัดตารางเวลา การมอบหมาย หรือการออกแบบเครือข่ายภายใต้ความไม่แน่นอนของความต้องการหรือต้นทุน เหมาะอย่างยิ่งเมื่อต้นทุนของการปรับให้เหมาะสมใหม่หลังจากการใช้งานสูง หรือเมื่อคำตอบต้องได้รับการรับรองว่าน่าเชื่อถือก่อนการนำไปใช้ หลีกเลี่ยง RTS เมื่อปัญหามีความแน่นอนอย่างสมบูรณ์ (Tabu Search แบบดั้งเดิมก็เพียงพอแล้ว) เมื่อชุดสถานการณ์มีขนาดใหญ่เกินกว่าจะสุ่มตัวอย่างได้อย่างมีประสิทธิภาพโดยไม่สิ้นเปลืองทรัพยากรมากเกินไป หรือเมื่อปัญหาเป็นแบบเรียบและนูน (gradient-based robust methods จะเร็วกว่าและน่าเชื่อถือกว่า)

ข้อจำกัดและข้อควรพิจารณา

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

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ค้นหาคำตอบที่ทนทานต่อความแปรปรวนของข้อมูลนำเข้าโดยไม่ต้องมีการตรวจสอบความทนทานภายหลังแยกต่างหาก
  • สืบทอดประสิทธิภาพเชิงประจักษ์ที่แข็งแกร่งของ Tabu Search ในปัญหาแบบผสมที่ซับซ้อน (การจัดตารางเวลา, VRP, TSP variants)
  • เกณฑ์ความทนทานที่ยืดหยุ่น: รองรับวัตถุประสงค์แบบ minimax, ค่าคาดหวัง, ค่าเฉลี่ย-ความแปรปรวน และแบบเปอร์เซ็นไทล์
  • ไม่ต้องการความเป็นนูนของปัญหาหรือความสามารถในการหาอนุพันธ์ — ใช้ได้กับวัตถุประสงค์แบบกล่องดำ (black-box) และแบบไม่ต่อเนื่อง
  • กลไก tabu ป้องกันการติดอยู่ในคำตอบที่ทนทานในระดับท้องถิ่นแต่โดยรวมแล้วปานกลาง

การประยุกต์ใช้

  • การจัดเส้นทางยานพาหนะแบบ Robust ภายใต้เวลาเดินทางแบบสุ่มหรือความต้องการของลูกค้า
  • การจัดตารางงานแบบ Job-shop และ Flow-shop ด้วยเวลาดำเนินการที่ไม่แน่นอน
  • การออกแบบเครือข่ายและการวางแผนความจุภายใต้ความผันผวนของความต้องการ
  • การหาค่าที่เหมาะสมที่สุดของห่วงโซ่อุปทานด้วยเวลานำหรือต้นทุนของผู้จัดจำหน่ายที่ไม่แน่นอน
  • การกำหนดความถี่ในการสื่อสารโทรคมนาคมภายใต้ความไม่แน่นอนของการรบกวน
  • การหาค่าที่เหมาะสมที่สุดของพอร์ตโฟลิโอด้วยผลตอบแทนสินทรัพย์ที่ไม่แน่นอนโดยใช้ข้อจำกัดแบบผสม

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

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

1

กำหนดปัญหาการหาค่าที่เหมาะสมที่สุดแบบผสม (combinatorial optimization) หรือแบบต่อเนื่อง (continuous optimization) ระบุพารามิเตอร์ที่ไม่แน่นอน (เช่น ความต้องการ ต้นทุน เวลาดำเนินการ) และระบุชุดสถานการณ์ S ที่แสดงถึงผลลัพธ์ที่เป็นไปได้ — ไม่ว่าจะโดยการสุ่มตัวอย่างจากการแจกแจงหรือการสร้างชุดความไม่แน่นอนแบบไม่ต่อเนื่อง กำหนดวัตถุประสงค์ความทนทาน: ลดต้นทุนในกรณีที่เลวร้ายที่สุด (worst-case cost) ลดต้นทุนที่คาดหวัง (expected cost) หรือลดค่าผสมถ่วงน้ำหนักของค่าเฉลี่ยและความแปรปรวน

2

สำหรับคำตอบที่เป็นไปได้แต่ละรายการ x ที่พบระหว่างการค้นหา ให้ประเมินค่าวัตถุประสงค์ f(x, s) ภายใต้สถานการณ์ s แต่ละรายการใน S คำนวณค่ามาตรวัดความทนทาน R(x) — ตัวอย่างเช่น R(x) = max_{s in S} f(x,s) สำหรับความทนทานแบบ minimax หรือ R(x) = E[f(x,s)] + lambda * Var[f(x,s)] สำหรับความทนทานแบบค่าเฉลี่ย-ความแปรปรวน (mean-variance robustness) สิ่งนี้จะเข้ามาแทนที่การประเมินค่าเดียวตามปกติที่ใช้ใน Tabu Search แบบดั้งเดิม

3

สร้างเพื่อนบ้าน N(x) ของคำตอบปัจจุบัน x โดยการใช้การเคลื่อนที่ที่เป็นไปได้ทั้งหมด (การสลับ การแทรก การย้อนกลับ ฯลฯ) ประเมิน R(x') สำหรับเพื่อนบ้านแต่ละรายการ x' โดยไม่รวมการเคลื่อนที่ที่อยู่ในรายการ tabu เว้นแต่ว่าเกณฑ์การยอมรับ (aspiration criterion) จะเป็นไปตามนั้น เลือกเพื่อนบ้าน x* ที่มีค่าความทนทาน R(x*) ดีที่สุด

4

ย้ายไปยัง x* และบันทึกการเคลื่อนที่ย้อนกลับของการเคลื่อนที่ที่ใช้ในรายการ tabu ด้วยระยะเวลา t (โดยทั่วไปคือ 5–20 รอบ) รายการ tabu ป้องกันการวนซ้ำและส่งเสริมการสำรวจ เกณฑ์การยอมรับ — เช่น การยอมรับการเคลื่อนที่แบบ tabu หากสร้างคำตอบ robust ที่ดีที่สุดทั่วโลก — อาจยกเลิกข้อจำกัด tabu

5

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

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

  • การใช้สถานการณ์น้อยเกินไปจะประเมินความไม่แน่นอนที่แท้จริงต่ำไปและสร้างคำตอบที่ดูเหมือนทนทานแต่ใช้งานจริงไม่ได้
  • การผสมผสาน Robust Tabu Search กับ Stochastic Tabu Search: การหาค่าที่เหมาะสมที่สุดแบบ Robust จะลดการเปิดรับต่อกรณีที่เลวร้ายที่สุด ในขณะที่ Stochastic TS จะสุ่มตัวอย่างเพื่อประมาณค่าคาดหวัง — วัตถุประสงค์และการตีความแตกต่างกัน
  • การใช้ความทนทานแบบ minimax เมื่อสถานการณ์ที่เลวร้ายที่สุดมีความน่าจะเป็นน้อยมาก จะนำไปสู่คำตอบที่อนุรักษ์นิยมเกินไปโดยมีต้นทุนที่ไม่จำเป็น
  • การละเลยเกณฑ์การยอมรับอาจทำให้การค้นหาพลาดคำตอบ robust ทั่วโลกที่บังเอิญเกี่ยวข้องกับการเคลื่อนที่แบบ tabu
  • การตั้งค่าระยะเวลา tabu สูงเกินไปจะสร้างข้อจำกัดมากเกินไป ต่ำเกินไปจะทำให้เกิดการวนซ้ำ — ทั้งสองอย่างจะลดคุณภาพของคำตอบ

คำถามที่พบบ่อย

Robust Tabu Search แตกต่างจาก Stochastic Tabu Search อย่างไร?

Stochastic Tabu Search โดยทั่วไปจะใช้การสุ่มตัวอย่างแบบสุ่มภายในกระบวนการค้นหาเอง (เช่น การยอมรับแบบสุ่มหรือการสุ่มตัวอย่างเพื่อนบ้าน) เพื่อประมาณค่าคาดหวัง Robust Tabu Search จะหาค่าที่เหมาะสมที่สุดของเกณฑ์ความทนทาน — เช่น ประสิทธิภาพในกรณีที่เลวร้ายที่สุด หรือค่าเฉลี่ย-ความแปรปรวน — ที่ประเมินจากชุดความไม่แน่นอนที่กำหนดไว้ เป้าหมายใน TS แบบ Robust คือความเสถียรของคำตอบในทุกสถานการณ์ ไม่ใช่แค่ประสิทธิภาพที่คาดหวัง

ชุดสถานการณ์ S ควรมีขนาดเท่าใด?

ไม่มีกฎสากล สำหรับชุดความไม่แน่นอนแบบไม่ต่อเนื่อง ให้แจกแจงสถานการณ์ที่น่าเชื่อถือทั้งหมดหากเป็นไปได้ สำหรับการแจกแจงแบบต่อเนื่อง การสุ่มตัวอย่าง 50–500 สถานการณ์มักให้ความครอบคลุมที่เพียงพอ เทคนิคการลดความแปรปรวน เช่น Latin hypercube sampling สามารถปรับปรุงประสิทธิภาพได้ การวิเคราะห์ความไวต่อ |S| เป็นสิ่งที่ควรทำก่อนที่จะตัดสินใจเลือกจำนวนสถานการณ์สุดท้าย

Robust Tabu Search สามารถจัดการกับปัญหาหลายวัตถุประสงค์ได้หรือไม่?

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

ควรเลือกมาตรวัดความทนทานใด?

Minimax (กรณีที่เลวร้ายที่สุด) เหมาะสมเมื่อความล้มเหลวเป็นหายนะ และแม้แต่ผลลัพธ์ที่ไม่ดีที่มีความน่าจะเป็นต่ำก็ไม่อาจยอมรับได้ ค่าคาดหวังเหมาะสำหรับผู้มีอำนาจตัดสินใจที่เป็นกลางต่อความเสี่ยง ค่าเฉลี่ย-ความแปรปรวนจะสร้างสมดุลระหว่างประสิทธิภาพเฉลี่ยและความแปรปรวน และเป็นเรื่องปกติในการออกแบบทางวิศวกรรม เมตริก Value-at-Risk (VaR) หรือ Conditional VaR ใช้ในการใช้งานทางการเงินและโลจิสติกส์ที่การรับประกันแบบเปอร์เซ็นไทล์มีความสำคัญ

Robust Tabu Search เหมาะสำหรับอินสแตนซ์ขนาดใหญ่มากหรือไม่?

ขึ้นอยู่กับต้นทุนการประเมินสถานการณ์ หากการประเมิน f(x,s) แต่ละครั้งมีต้นทุนต่ำ (มิลลิวินาที) ความทนทานต่อสถานการณ์หลายร้อยรายการยังคงสามารถจัดการได้แม้สำหรับอินสแตนซ์ขนาดใหญ่ หากการประเมินแต่ละครั้งต้องการการจำลองหรือการเรียกใช้ solver ที่มีค่าใช้จ่ายสูง การลดสถานการณ์อย่างเข้มข้นหรือแบบจำลองตัวแทน (surrogate models) จะมีความจำเป็น การประเมินสถานการณ์แบบขนานผ่านเธรดหรือเครื่องจักรเป็นวิธีการบรรเทาผลกระทบที่พบบ่อย

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

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

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

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.

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