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 ด้วยเวลาดำเนินการที่ไม่แน่นอน
- การออกแบบเครือข่ายและการวางแผนความจุภายใต้ความผันผวนของความต้องการ
- การหาค่าที่เหมาะสมที่สุดของห่วงโซ่อุปทานด้วยเวลานำหรือต้นทุนของผู้จัดจำหน่ายที่ไม่แน่นอน
- การกำหนดความถี่ในการสื่อสารโทรคมนาคมภายใต้ความไม่แน่นอนของการรบกวน
- การหาค่าที่เหมาะสมที่สุดของพอร์ตโฟลิโอด้วยผลตอบแทนสินทรัพย์ที่ไม่แน่นอนโดยใช้ข้อจำกัดแบบผสม
วิธีการทำงาน
วิธีการทำงาน
กำหนดปัญหาการหาค่าที่เหมาะสมที่สุดแบบผสม (combinatorial optimization) หรือแบบต่อเนื่อง (continuous optimization) ระบุพารามิเตอร์ที่ไม่แน่นอน (เช่น ความต้องการ ต้นทุน เวลาดำเนินการ) และระบุชุดสถานการณ์ S ที่แสดงถึงผลลัพธ์ที่เป็นไปได้ — ไม่ว่าจะโดยการสุ่มตัวอย่างจากการแจกแจงหรือการสร้างชุดความไม่แน่นอนแบบไม่ต่อเนื่อง กำหนดวัตถุประสงค์ความทนทาน: ลดต้นทุนในกรณีที่เลวร้ายที่สุด (worst-case cost) ลดต้นทุนที่คาดหวัง (expected cost) หรือลดค่าผสมถ่วงน้ำหนักของค่าเฉลี่ยและความแปรปรวน
สำหรับคำตอบที่เป็นไปได้แต่ละรายการ 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 แบบดั้งเดิม
สร้างเพื่อนบ้าน N(x) ของคำตอบปัจจุบัน x โดยการใช้การเคลื่อนที่ที่เป็นไปได้ทั้งหมด (การสลับ การแทรก การย้อนกลับ ฯลฯ) ประเมิน R(x') สำหรับเพื่อนบ้านแต่ละรายการ x' โดยไม่รวมการเคลื่อนที่ที่อยู่ในรายการ tabu เว้นแต่ว่าเกณฑ์การยอมรับ (aspiration criterion) จะเป็นไปตามนั้น เลือกเพื่อนบ้าน x* ที่มีค่าความทนทาน R(x*) ดีที่สุด
ย้ายไปยัง x* และบันทึกการเคลื่อนที่ย้อนกลับของการเคลื่อนที่ที่ใช้ในรายการ tabu ด้วยระยะเวลา t (โดยทั่วไปคือ 5–20 รอบ) รายการ tabu ป้องกันการวนซ้ำและส่งเสริมการสำรวจ เกณฑ์การยอมรับ — เช่น การยอมรับการเคลื่อนที่แบบ tabu หากสร้างคำตอบ robust ที่ดีที่สุดทั่วโลก — อาจยกเลิกข้อจำกัด tabu
ปรับปรุงคำตอบ 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) จะมีความจำเป็น การประเมินสถานการณ์แบบขนานผ่านเธรดหรือเครื่องจักรเป็นวิธีการบรรเทาผลกระทบที่พบบ่อย
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วDolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว