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

Multi-objective Tabu Search (MOTS) — เมตาฮิวริสติกสำหรับผลลัพธ์แบบ Pareto-optimal

ผู้เสนอ
Hansen, M. P.; building on Glover (1989) Tabu Search
ปี
1997
ประเภท
Metaheuristic multi-objective optimization
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

Multi-objective Tabu Search (MOTS) เป็นอัลกอริทึมเมตาฮิวริสติกที่ต่อยอดจากกรอบการทำงานของ Tabu Search แบบคลาสสิก เพื่อเพิ่มประสิทธิภาพฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันสองอย่างขึ้นไปพร้อมกัน แทนที่จะหาค่าเหมาะสมที่สุดเพียงค่าเดียว MOTS พยายามประมาณค่า Pareto front ซึ่งเป็นชุดของผลลัพธ์ที่ไม่มีวัตถุประสงค์ใดสามารถปรับปรุงได้โดยไม่ทำให้วัตถุประสงค์อื่นแย่ลง ทำให้เหมาะสำหรับปัญหาการหาค่าเหมาะสมที่สุดแบบเชิงผสมและต่อเนื่องที่ซับซ้อนในด้านวิศวกรรม โลจิสติกส์ และการวิจัยการดำเนินงาน

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

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

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

Multi-objective Tabu Search เป็นการต่อยอดจาก Tabu Search แบบวัตถุประสงค์เดียวที่ Fred Glover นำเสนอในปี 1989 การกำหนดสูตร MOTS อย่างเป็นระบบครั้งแรก — รวมถึงการเก็บถาวร Pareto และเกณฑ์ความปรารถนาแบบหลายวัตถุประสงค์ — นำเสนอโดย M. P. Hansen ในการประชุม MCDM ปี 1997 งานวิจัยต่อมาโดย Gandibleux, Teghem และคนอื่น ๆ ได้กำหนดรูปแบบต่าง ๆ สำหรับปัญหาเชิงผสม และ MOTS ได้ถูกนำไปใช้กับการจัดตารางเวลา โลจิสติกส์ และการออกแบบทางวิศวกรรมในฐานะทางเลือกที่แข่งขันได้กับอัลกอริทึมวิวัฒนาการแบบหลายวัตถุประสงค์

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

เริ่มต้นการค้นหาด้วยหนึ่งหรือหลายผลลัพธ์เริ่มต้น (สร้างขึ้นแบบสุ่มหรือสร้างขึ้นด้วยฮิวริสติก) กำหนดรายการต้องห้ามว่างเปล่าที่มีความยาวคงที่ L และเริ่มต้นคลังข้อมูล Pareto ด้วยผลลัพธ์ที่ไม่ถูกครอบงำจากประชากรเริ่มต้น

2

สร้างย่านใกล้เคียง N(s) ของผลลัพธ์ปัจจุบัน s โดยใช้ตัวดำเนินการย้าย (การสลับ การแทรก การรบกวน) ประเมินผลลัพธ์ข้างเคียงทั้งหมดในแต่ละฟังก์ชันวัตถุประสงค์เพื่อระบุผู้สมัครสำหรับการดำเนินการต่อไป

3

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

4

เลือกเพื่อนบ้านที่ไม่ต้องห้ามที่ดีที่สุด (หรือผู้ชนะเกณฑ์ความปรารถนา) เป็นผลลัพธ์ปัจจุบันถัดไป อัปเดตคลังข้อมูล Pareto โดยการเพิ่มผลลัพธ์ใหม่หากไม่ถูกครอบงำ; ลบสมาชิกคลังข้อมูลใด ๆ ที่ถูกครอบงำโดยรายการใหม่

5

ใช้กลยุทธ์การกระจายเมื่อการค้นหาหยุดนิ่ง: หน่วยความจำความถี่ระยะยาวระบุภูมิภาคที่เยี่ยมชมน้อยครั้ง; เริ่มต้นใหม่จากผลลัพธ์คลังข้อมูลชั้นยอดหรือผลลัพธ์ที่ถูกรบกวนแบบสุ่มเพื่อขยายขอบเขตของ Pareto front

6

ทำซ้ำขั้นตอนย่านใกล้เคียง ตัวกรอง และคลังข้อมูลจนกว่าจะถึงเกณฑ์การหยุด — โดยทั่วไปคือจำนวนการวนซ้ำสูงสุด การประเมินฟังก์ชัน หรือเวลา CPU ที่ผ่านไป ส่งคืนคลังข้อมูล Pareto เป็น Pareto-optimal front ที่ประมาณค่าแล้ว

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

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

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

MOTS จัดการรายการต้องห้ามอย่างไรเมื่อมีวัตถุประสงค์หลายอย่าง?

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

คลังข้อมูล Pareto คืออะไรและควรมีขนาดเท่าใด?

คลังข้อมูล Pareto จะเก็บผลลัพธ์ที่ไม่ถูกครอบงำทั้งหมดที่พบระหว่างการค้นหา โดยทั่วไปขนาดสูงสุดจะถูกจำกัด (เช่น 100–500 ผลลัพธ์) เพื่อให้การจัดการหน่วยความจำและค่าใช้จ่ายในการอัปเดตสามารถจัดการได้ เมื่อคลังข้อมูลเต็ม การตัดแต่งโดยใช้ระยะห่างความแออัดหรือตามกริดจะลบผลลัพธ์ออกจากพื้นที่ที่มีความแออัดมากเกินไปเพื่อรักษาความหลากหลาย

MOTS เปรียบเทียบกับ NSGA-II สำหรับปัญหาแบบหลายวัตถุประสงค์อย่างไร?

NSGA-II ใช้วิธีการวิวัฒนาการแบบประชากรที่มีการผสมข้ามและการกลายพันธุ์ ทำให้ดีกว่าในการสำรวจทั่วโลกในช่วงต้นของการค้นหา MOTS อาศัยการย้ายย่านใกล้เคียงและหน่วยความจำ ซึ่งมักจะให้คุณภาพการค้นหาเฉพาะที่ที่ดีกว่า ในทางปฏิบัติ MOTS มักจะมีประสิทธิภาพดีกว่าในปัญหาเชิงผสมที่มีโครงสร้างย่านใกล้เคียงที่แข็งแกร่ง ในขณะที่ NSGA-II ถูกนำมาใช้กันอย่างแพร่หลายสำหรับปัญหาต่อเนื่อง

โดยทั่วไปต้องใช้การวนซ้ำกี่ครั้ง?

ไม่มีกฎสากล การปฏิบัติทั่วไปคือการจัดสรรงบประมาณการประเมินฟังก์ชันมากกว่าการวนซ้ำ — โดยทั่วไปคือ 10,000 ถึง 100,000 การประเมินขึ้นอยู่กับขนาดของปัญหา — และดำเนินการเริ่มต้นอิสระหลายครั้งเพื่อประเมินคุณภาพของผลลัพธ์และความเสถียรของ Pareto front

MOTS สามารถจัดการวัตถุประสงค์มากกว่าสองอย่างได้หรือไม่?

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

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

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

  1. Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

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