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

Tabu Search — ฮิวริสติกการค้นหาเฉพาะที่

ผู้เสนอ
Fred Glover
ปี
1989
ประเภท
Local-search metaheuristic

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

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

ใช้ทำอะไร?

Tabu Search เป็นฮิวริสติกการค้นหาเฉพาะที่ (local-search metaheuristic) ที่ Fred Glover นำเสนอในปี 1989 โดยใช้รายการต้องห้าม (tabu list) — หน่วยความจำระยะสั้นของผลเฉลยที่เพิ่งเยี่ยมชม — เพื่อป้องกันการวนซ้ำและหลุดออกจากจุดเหมาะสมเฉพาะที่ (local optima) การห้ามการเคลื่อนที่ที่ย้อนกลับการตัดสินใจล่าสุดอย่างชัดเจน ทำให้อัลกอริทึมสำรวจปริภูมิการค้นหาได้กว้างขึ้น และผ่านโครงสร้างหน่วยความจำระยะยาว เช่น เกณฑ์การยอมรับ (aspiration criteria) มีเป้าหมายที่จะเข้าใกล้จุดเหมาะสมที่สุดทั่วโลก (global optimum) แม้ในปัญหาการจัดหมู่ (combinatorial problems) ที่มีขนาดใหญ่และซับซ้อน

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

ลองนึกภาพการเดินทางในภูมิประเทศที่เป็นภูเขาในความมืด พยายามหาจุดสูงสุดที่สูงที่สุด การค้นหาเฉพาะที่แบบง่ายๆ จะก้าวขึ้นเขาเสมอและติดอยู่ที่เนินเขาที่ใกล้ที่สุดที่ไปถึง Tabu Search จะพกสมุดบันทึกของจุดที่เพิ่งไปเยือนและปฏิเสธที่จะกลับไปที่นั่น แม้ว่าการย้อนกลับจะดูน่าดึงดูดก็ตาม การลืมการเคลื่อนที่ล่าสุดที่บังคับนี้จะผลักดันการค้นหาออกจากทางตันและเข้าสู่พื้นที่ที่ยังไม่ได้สำรวจ ทำให้สามารถค้นพบพื้นที่ที่สูงกว่ามากได้ในที่สุด ซึ่งการค้นหาเฉพาะที่ธรรมดาๆ จะไม่สามารถทำได้

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

Tabu Search ถูกนำเสนอโดย Fred Glover ในบทความสำคัญปี 1989 ในวารสาร ORSA Journal on Computing ซึ่งนำเสนอเป็นกลยุทธ์ในการนำทางการค้นหาเฉพาะที่โดยใช้ประโยชน์จากหน่วยความจำของการเคลื่อนที่ในอดีต แนวคิดพื้นฐานได้รับการรวบรวมและขยายความในตำราของ Glover และ Laguna ปี 1997 โดย Springer ซึ่งได้กำหนดรายการต้องห้ามระยะสั้นที่เป็นมาตรฐาน เกณฑ์การยอมรับ และกลยุทธ์การกระจายตัวและการเข้มข้นระยะยาวที่ยังคงเป็นหัวใจสำคัญของวิธีการนี้ในปัจจุบัน นับตั้งแต่เปิดตัว Tabu Search ได้ถูกนำไปใช้อย่างกว้างขวางในวิจัยดำเนินงาน (operations research) การจัดตารางเวลา โลจิสติกส์ และการออกแบบเชิงจัดหมู่ และยังคงเป็นฮิวริสติกมาตรฐานสำหรับการเปรียบเทียบเคียงข้างกับ simulated annealing และ genetic algorithms

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

Tabu Search เหมาะอย่างยิ่งสำหรับปัญหาการหาค่าเหมาะสมที่สุดแบบจัดหมู่ (combinatorial optimization) และแบบไม่ต่อเนื่อง (discrete optimization) ที่ปริภูมิผลเฉลยมีขนาดใหญ่เกินกว่าวิธีการที่แม่นยำ (exact methods) จะจัดการได้ และโครงสร้างปัญหาสามารถกำหนดเพื่อนบ้านที่มีความหมายได้ การใช้งานทั่วไป ได้แก่ ปัญหาการจัดตารางเวลา (scheduling) การกำหนดเส้นทาง (routing) การจัดสรร (assignment) และการจัดลำดับ (sequencing) มีประสิทธิภาพเป็นพิเศษเมื่อภูมิทัศน์การค้นหามีจุดเหมาะสมเฉพาะที่จำนวนมากที่ดักจับวิธีการที่ง่ายกว่า ไม่จำเป็นต้องใช้ฟังก์ชันวัตถุประสงค์ที่สามารถหาอนุพันธ์ได้หรือต่อเนื่อง การกำหนดเพื่อนบ้านและอายุการต้องห้ามต้องปรับให้เข้ากับปัญหาเฉพาะอย่างระมัดระวัง การเลือกเพื่อนบ้านที่ไม่ดี หรืออายุที่สั้นหรือยาวเกินไป อาจทำให้ประสิทธิภาพลดลงอย่างมาก จำเป็นต้องมีรอบการทำซ้ำอย่างน้อยหลายร้อยครั้ง — และควรเป็นมากกว่าหนึ่งพันครั้ง — เพื่อให้การค้นหาสำรวจปริภูมิได้อย่างเพียงพอ

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

  • ประสิทธิภาพขึ้นอยู่กับการกำหนดเพื่อนบ้านและอายุการต้องห้าม การเลือกที่ไม่ดีอาจทำให้การค้นหาติดขัดหรือวนซ้ำได้แม้จะมีกลไกต้องห้าม
  • ต้องการงบประมาณรอบการทำซ้ำขั้นต่ำ — โดยทั่วไปมากกว่า 1,000 รอบการทำซ้ำ — เพื่อสำรวจเพื่อนบ้านอย่างเพียงพอ หากรอบการทำซ้ำน้อยเกินไป ผลลัพธ์จะไม่ดีไปกว่าการค้นหาเฉพาะที่แบบธรรมดา
  • รายการต้องห้ามเก็บคุณลักษณะการเคลื่อนที่แทนผลเฉลยทั้งหมด ดังนั้นจึงจำเป็นต้องมีเกณฑ์การยอมรับเพื่อป้องกันการปิดกั้นการเคลื่อนที่ที่ดีจริงๆ โดยไม่ได้ตั้งใจ
  • แตกต่างจากตัวแก้ที่แม่นยำ Tabu Search ไม่มีการรับประกันความเป็นค่าเหมาะสมที่สุด และคุณภาพของผลลัพธ์อาจแตกต่างกันไปในแต่ละครั้งที่รัน หากผลเฉลยเริ่มต้นหรือเพื่อนบ้านมีความสุ่ม

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

จุดแข็ง

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

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

  • การจัดตารางงานแบบ Job-shop และ Flow-shop — การหาค่าเหมาะสมที่สุดของลำดับการดำเนินการเพื่อลด makespan หรือ tardiness
  • การกำหนดเส้นทางยานพาหนะ — การค้นหาเส้นทางการจัดส่งที่มีประสิทธิภาพภายใต้ข้อจำกัดด้านความจุและกรอบเวลา
  • การจัดสรรและการจัดหาที่ตั้ง — การจัดสรรงานให้กับทรัพยากร หรือการจัดหาที่ตั้งเพื่อลดต้นทุน
  • การระบายสีแผนที่ (Graph colouring) การออกแบบเครือข่าย และโทรคมนาคม — การแก้ปัญหาการหาค่าเหมาะสมที่สุดของโครงสร้างแบบไม่ต่อเนื่อง
  • การเลือกคุณลักษณะ (Feature selection) และการค้นหาไฮเปอร์พารามิเตอร์ (hyperparameter search) — การสำรวจปริภูมิการกำหนดค่าแบบไม่ต่อเนื่องในไปป์ไลน์การเรียนรู้ของเครื่อง

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

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

1

การค้นหาเริ่มต้นจากผลเฉลยตัวอย่างเริ่มต้น ซึ่งสามารถสร้างขึ้นแบบสุ่มหรือด้วยฮิวริสติกแบบละโมบ (greedy heuristic) รายการต้องห้ามจะถูกตั้งค่าเป็นคิวที่มีความยาวคงที่ว่างเปล่า และผลเฉลยที่ดีที่สุดที่พบจนถึงขณะนี้จะถูกบันทึกไว้ โครงสร้างเพื่อนบ้าน (neighbourhood structure) — กฎที่กำหนดว่าผลเฉลยใดอยู่ห่างออกไปหนึ่งก้าวจากผลเฉลยปัจจุบัน — ต้องถูกกำหนดในลักษณะที่มีความหมายสำหรับปัญหาเฉพาะ

2

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

3

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

4

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

5

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

6

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

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

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

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

Tabu Search แตกต่างจาก simulated annealing อย่างไร?

ทั้งสองวิธีรับการเคลื่อนที่ที่แย่ลงเพื่อหลุดออกจากจุดเหมาะสมเฉพาะที่ แต่แตกต่างกันในกลไก Simulated annealing รับการเคลื่อนที่ที่แย่ลงตามความน่าจะเป็น โดยมีตัวควบคุมอุณหภูมิที่กำลังเย็นลงเป็นตัวนำทาง Tabu Search รับการเคลื่อนที่ที่ไม่ต้องห้ามที่ดีที่สุดที่มีอยู่แบบกำหนด (deterministically) โดยใช้หน่วยความจำที่ชัดเจนของการเคลื่อนที่ล่าสุด Tabu Search โดยทั่วไปมีประสิทธิภาพมากกว่าในปัญหาเชิงจัดหมู่ที่มีโครงสร้าง Simulated annealing อาจปรับแต่งได้ง่ายกว่าในปัญหาที่มีภูมิทัศน์ต่อเนื่องหรือใกล้เคียงต่อเนื่อง และเป็นที่ต้องการเมื่อมีงบประมาณรอบการทำซ้ำน้อย (ต่ำกว่าประมาณ 1,000 รอบการทำซ้ำ)

อายุของรายการต้องห้ามควรนานเท่าใด?

อายุการต้องห้าม (tabu tenure) — จำนวนรอบการทำซ้ำที่การเคลื่อนที่ยังคงถูกห้าม — ขึ้นอยู่กับปัญหา จุดเริ่มต้นที่กล่าวถึงบ่อยคืออายุที่แปรผันตามรากที่สองของขนาดปัญหา แต่นี่ควรได้รับการปรับแต่งจากการทดลอง อายุที่สั้นเกินไปจะทำให้เกิดการวนซ้ำ อายุที่ยาวเกินไปจะจำกัดการค้นหามากเกินไป กลยุทธ์อายุแบบปรับได้หรือแบบสุ่มสามารถลดความไวต่อการเลือกนี้ได้

Tabu Search รับประกันว่าจะพบจุดเหมาะสมที่สุดทั่วโลกหรือไม่?

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

เกณฑ์การยอมรับคืออะไรและทำไมจึงจำเป็น?

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

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

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

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

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    คัดลอกแล้ว