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

การค้นหาแบบทาบูเชิงสุ่ม — เมตาฮิวริสติกแบบสุ่มที่มีหน่วยความจำ (Stochastic Tabu Search: Randomized Metaheuristic with Memory)

ผู้เสนอ
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
ปี
1990s
ประเภท
Stochastic metaheuristic optimizer
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

Stochastic Tabu Search (STS) เป็นส่วนขยายของ Tabu Search แบบดั้งเดิมที่นำเสนอความเป็นสุ่มเข้าไปในขั้นตอนการสำรวจคำตอบข้างเคียงและการเลือกการเคลื่อนที่ โดยการรวมหน่วยความจำแบบ tabu — ซึ่งห้ามการเข้าชมคำตอบล่าสุด — เข้ากับการยอมรับแบบสุ่มหรือการสุ่มตัวอย่างตัวเลือกแบบสุ่ม STS สามารถหลีกเลี่ยงค่าเหมาะที่สุดเฉพาะที่ (local optima) ได้อย่างมีประสิทธิภาพมากขึ้น และสำรวจภูมิทัศน์คำตอบที่ซับซ้อนซึ่ง TS แบบกำหนดแน่นอน (deterministic)อาจไม่สามารถผ่านไปได้

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

Tabu Search แบบคลาสสิกนำทางพื้นที่คำตอบโดยการเคลื่อนที่ไปยังคำตอบข้างเคียงที่ดีที่สุดที่อนุญาตเสมอ โดยใช้หน่วยความจำระยะสั้น (รายการ tabu) เพื่อป้องกันการวนซ้ำ อย่างไรก็ตาม ในทางปฏิบัติ การเคลื่อนที่ที่ดีที่สุดที่อนุญาตยังคงสามารถกักอัลกอริทึมไว้ในย่านหนึ่งของภูมิทัศน์ได้ Stochastic Tabu Search ฉีดความเป็นสุ่มที่ควบคุมได้: การเคลื่อนที่ถัดไปจะถูกเลือกตามความน่าจะเป็นจากชุดคำตอบข้างเคียงที่เสนอ แทนที่จะเลือกแบบละโมบ และการรบกวนแบบสุ่มจะถูกนำมาใช้เป็นครั้งคราวเพื่อกระจายการค้นหา สิ่งนี้จะรักษาหลักการนำทางด้วยหน่วยความจำของ TS ในขณะที่เพิ่มพลังการสำรวจที่การลดลงแบบกำหนดแน่นอน (deterministic)ล้วนขาดไป

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

Tabu Search ถูกนำเสนออย่างเป็นทางการโดย Fred Glover ในปี 1986 และได้รับการขยายความในบทความสำคัญในช่วงปี 1989-1990 ส่วนขยายแบบสุ่มเริ่มปรากฏขึ้นในช่วงทศวรรษ 1990 เมื่อนักวิจัยตระหนักว่าการประเมินคำตอบข้างเคียงแบบกำหนดแน่นอน (deterministic)เป็นคอขวดในปัญหาขนาดใหญ่ การสุ่มตัวอย่างตัวเลือกแบบสุ่ม การยอมรับการเคลื่อนที่ตามความน่าจะเป็น และการฉีดสัญญาณรบกวนถูกนำมาใช้เพื่อปรับปรุงการกระจาย ทำให้เกิดสิ่งที่เรียกว่า Stochastic Tabu Search เทคนิคนี้ถูกนำไปใช้อย่างกว้างขวางในวิจัยดำเนินงาน การออกแบบทางวิศวกรรม และการหาค่าเหมาะที่สุดของไฮเปอร์พารามิเตอร์ (hyperparameter optimization) ในการเรียนรู้ของเครื่อง

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

ใช้ Stochastic Tabu Search เมื่อแก้ปัญหาการหาค่าเหมาะที่สุดแบบผสม (combinatorial) หรือแบบต่อเนื่อง (continuous) ที่มีภูมิทัศน์ซับซ้อนและหลายรูปแบบ (multimodal) ซึ่งการค้นหาเฉพาะที่แบบกำหนดแน่นอน (deterministic)มักติดอยู่ (เช่น การจัดตารางเวลา, การกำหนดเส้นทาง, การเลือกคุณลักษณะ) มีประโยชน์อย่างยิ่งเมื่อการประเมินคำตอบข้างเคียงทั้งหมดมีค่าใช้จ่ายในการคำนวณสูง ทำให้การสุ่มตัวอย่างย่อยเป็นสิ่งจำเป็น *ห้าม* ใช้ STS เมื่อปัญหามีลักษณะนูน (convex) หรือมีรูปแบบเดียว (unimodal) — วิธีการที่ใช้เกรเดียนต์หรือวิธีที่แม่นยำจะเร็วกว่าและให้คำตอบที่เหมาะที่สุด หลีกเลี่ยงเมื่อคุณต้องการการรับประกันคำตอบที่เหมาะที่สุดระดับรวม (global optimum) เนื่องจาก STS ไม่มีการรับประกันการลู่เข้าเกินกว่าคำตอบที่ดีที่สุดที่พบด้วยฮิวริสติก นอกจากนี้ยังหลีกเลี่ยงเมื่อฟังก์ชันวัตถุประสงค์ประเมินได้เร็วและครบถ้วน และ TS แบบกำหนดแน่นอน (deterministic)พร้อมการค้นหาคำตอบข้างเคียงแบบครบถ้วนเป็นไปได้

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

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

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

จุดแข็ง

  • หลีกเลี่ยงค่าเหมาะที่สุดเฉพาะที่ได้ดีกว่า Tabu Search แบบกำหนดแน่นอน (deterministic) โดยการรวมหน่วยความจำเข้ากับการสำรวจตามความน่าจะเป็น
  • ปรับขนาดให้เข้ากับโครงสร้างย่านคำตอบข้างเคียงขนาดใหญ่โดยการสุ่มตัวอย่างตัวเลือก ช่วยลดต้นทุนการคำนวณต่อรอบการวนซ้ำ
  • หน่วยความจำ Tabu ป้องกันการวนซ้ำ ซึ่งเป็นโหมดความล้มเหลวทั่วไปของวิธีการสุ่มล้วนๆ เช่น Random Restart Hill Climbing
  • กรอบการทำงานที่ยืดหยุ่น: ความน่าจะเป็นของการรบกวนและอายุ tabu สามารถปรับแต่งเพื่อสร้างสมดุลระหว่างการเน้นค้นรอบจุดดี (intensification) และการกระจาย (diversification)
  • สามารถนำไปใช้ได้กับทั้งปัญหาแบบผสม (TSP, การจัดตารางเวลา) และการหาค่าเหมาะที่สุดแบบต่อเนื่องด้วยการปรับเปลี่ยนเล็กน้อย

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

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

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

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

1

สร้างคำตอบเริ่มต้น x0 (แบบสุ่มหรือแบบฮิวริสติก) ตั้งค่ารายการ tabu T ให้ว่าง กำหนดอายุ tabu tau, ขีดจำกัดการวนซ้ำ I_max และพารามิเตอร์สุ่ม (เช่น ขนาดรายการตัวเลือกที่เสนอ k, ความน่าจะเป็นของการรบกวน p_perturb)

2

ในแต่ละรอบการวนซ้ำ ให้สุ่มตัวอย่างชุดย่อย N_s ของคำตอบข้างเคียงทั้งหมด N(x_current) แทนที่จะประเมินคำตอบข้างเคียงทั้งหมด สิ่งนี้ช่วยลดต้นทุนต่อรอบการวนซ้ำและนำเสนอความเป็นสุ่มในการเลือกย่านที่จะสำรวจ

3

เลือกคำตอบถัดไป x_next จาก N_s: (a) เลือกตัวเลือกที่ดีที่สุดที่ไม่ใช่ tabu ด้วยความน่าจะเป็น 1-p_perturb หรือ (b) ด้วยความน่าจะเป็น p_perturb เลือกตัวเลือกแบบสุ่มที่ไม่ใช่ tabu เพื่อกระจาย เกณฑ์ข้อยกเว้น (aspiration criteria) อาจมีผลเหนือสถานะ tabu หาก x_next ปรับปรุงคำตอบที่ดีที่สุดที่ทราบ

4

เพิ่ม x_current (หรือคุณลักษณะการเคลื่อนที่) ลงในรายการ tabu T ลบรายการที่เก่าที่สุดออกหาก |T| > tau อัปเดตคำตอบที่ดีที่สุดที่ทราบ x_best หาก f(x_next) < f(x_best)

5

ทำซ้ำ neighborhood_sampling ผ่าน tabu_update จนกว่าจะถึงจำนวนรอบการวนซ้ำ I_max, บรรลุค่าเป้าหมาย หรือไม่มีการปรับปรุงเกิดขึ้นในช่วงเวลาที่กำหนด ส่งคืน x_best เป็นคำตอบสุดท้าย

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

  • การตั้งค่าอายุ tabu สั้นเกินไปจะทำให้เกิดการวนซ้ำแม้จะมีรายการ tabu แต่ถ้าตั้งไว้นานเกินไปจะปิดกั้นย่านที่มีแนวโน้มดีโดยไม่จำเป็น
  • การใช้รายการตัวเลือกที่เล็กเกินไป (การสุ่มตัวอย่างย่อยแบบเข้มข้น) อาจทำให้การค้นหาพลาดคำตอบข้างเคียงที่ดีอย่างต่อเนื่อง
  • การละเลยเกณฑ์ข้อยกเว้น (aspiration)ทำให้อัลกอริทึมปฏิเสธการเคลื่อนที่ที่ปรับปรุงคำตอบในระดับรวม (global)ซึ่งบังเอิญเป็น tabu
  • การรายงานเพียงการรันเดียวโดยไม่มีการเริ่มต้นใหม่หลายครั้งหรือ seed หลายตัวให้ภาพที่ทำให้เข้าใจผิดเกี่ยวกับคุณภาพคำตอบทั่วไป
  • การสับสน Stochastic Tabu Search กับ Simulated Annealing: ทั้งสองเป็น metaheuristics แบบสุ่ม แต่แตกต่างกันโดยพื้นฐาน — STS ใช้หน่วยความจำที่ชัดเจนในขณะที่ SA ใช้การยอมรับแบบสุ่มตามอุณหภูมิโดยไม่มีหน่วยความจำ

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

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

ทั้งสองเป็น metaheuristics แบบสุ่ม แต่ STS ใช้หน่วยความจำ tabu ที่ชัดเจนเพื่อห้ามการเคลื่อนที่ที่เพิ่งเยือน ป้องกันการวนซ้ำ SA ไม่มีหน่วยความจำ — มันยอมรับคำตอบที่แย่กว่าด้วยความน่าจะเป็นที่ลดลงเมื่อเวลาผ่านไป (ตารางอุณหภูมิ) โดยทั่วไป STS มักได้เปรียบกว่าในปัญหาแบบผสมที่การกลับไปเยือนการเคลื่อนที่เดิมซ้ำเป็นอันตรายที่ชัดเจน

ฉันควรรันกี่รอบ (I_max)?

ไม่มีกฎสากล แนวทางปฏิบัติทั่วไปคือการรันหลายๆ ครั้งโดยอิสระ (เช่น เริ่มต้นใหม่ 10-30 ครั้ง) ด้วยงบประมาณที่ได้สัดส่วนกับขนาดปัญหา จากนั้นจึงรายงานผลที่ดีที่สุดและค่าเฉลี่ย สำหรับการเปรียบเทียบ ให้จับคู่งบประมาณการประเมินฟังก์ชันทั้งหมดที่ใช้โดยวิธีการคู่แข่ง

Stochastic Tabu Search สามารถจัดการกับตัวแปรต่อเนื่องได้หรือไม่?

ได้ แต่ต้องมีการกำหนดคำตอบข้างเคียงแบบต่อเนื่อง (เช่น การรบกวนแบบ Gaussian รอบคำตอบปัจจุบัน) และคุณลักษณะที่เหมาะสมสำหรับรายการ tabu (เช่น ย่านหรือทิศทาง) เอกสารส่วนใหญ่เกี่ยวกับ STS มุ่งเป้าไปที่ปัญหาแบบผสม สำหรับพื้นที่ต่อเนื่อง Differential Evolution หรือ CMA-ES มักเป็นทางเลือกที่เป็นธรรมชาติมากกว่า

บทบาทของเกณฑ์ข้อยกเว้น (aspiration) คืออะไร?

เกณฑ์ข้อยกเว้น (aspiration)จะยกเลิกสถานะ tabu ของการเคลื่อนที่ หากการเลือกการเคลื่อนที่นั้นให้คำตอบที่ดีกว่าคำตอบที่ดีที่สุดที่พบจนถึงขณะนี้ หากไม่มีเกณฑ์ข้อยกเว้น (aspiration) อัลกอริทึมอาจปฏิเสธการเคลื่อนที่ที่ปรับปรุงคำตอบในระดับรวม (global) อย่างถาวรซึ่งบังเอิญเป็น tabu ซึ่งจำกัดคุณภาพของคำตอบอย่างรุนแรง

ฉันควรกำหนด seed แบบสุ่มเพื่อความสามารถในการทำซ้ำหรือไม่?

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

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

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

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

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