Tabu search

Taboo search

ทาบูเสิร์ช (Tabu Search : TS)

TS ถูกพัฒนาอย่างอิสระโดย Glover (1986) และ Hansen (1986) เพื่อใช้แก้ปัญหาแบบการหาค่าที่เหมาะที่สุดเชิงการจัด (Combinatorial optimization problem) ซึ่งมีความสามารถขจัดปัญหาการค้นหาผลเฉลยที่เป็นผลเฉลยเฉพาะพื้นที่ (Local optimum) ได้ ดังนั้น TS จึงสามารถค้นหาผลเฉลยที่เป็นค่าที่เหมาะที่สุด (global optimum) ในพื้นที่การหาผลเฉลยแบบ Multimodal กระบวนการทำงานพื้นฐานของ TS ที่สามารถขจัดปัญหาการพบผลเฉลยเฉพาะพื้นที่จะอยู่ที่การประเมินค่าผลเฉลย ซึ่งจะเลือกผลเฉลยที่มีการประเมินค่าสูงที่สุดในแต่ละรอบของการทำงาน (iteration) หมายถึงว่าจะเคลื่อนย้าย (Move) จากผลเฉลยปัจจุบันไปยังผลเฉลยบริเวณใกล้เคียง (Neighbourhood) ที่ให้ผลดีที่สุดโดยดูจากค่าฟังก์ชั่นเป้าหมายและกฎการควบคุมของทาบู (taboo restrictions)

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

ตัวอย่างของงานวิจัยที่ประยุกต์ใช้ TS (Alvarez-Valdes et al., 2002; Souza et al., 2001 ; Costa, 1994) คือ Alvarez-Valdes et al. ได้พัฒนาโปรแกรมประยุกต์ เพื่อแก้ปัญหาการจัดตารางสอนชื่อ HORARIS โดยใช้ TS เป็นวิธีหลักในการแก้ปัญหา ซึ่งได้มีการพัฒนาและทดสอบเพื่อให้ทำงานได้อย่างรวดเร็วและมีประสิทธิภาพ ผลการทดสอบการทำงานพบว่าได้ผลการจัดตารางสอนเป็นที่น่าพอใจ ต่อมา Souza ได้ใช้ TS ในปี 2001 ในการแก้ปัญหาการจัดตารางสอนของโรงเรียน โดยต้องการให้ได้ตารางสอนที่มีค่าฟังก์ชั่นเป้าหมายน้อยที่สุด ในขั้นตอนของการสร้างผลเฉลยเริ่มต้นได้ใช้ greedy procedure ช่วยในการสร้างผลเฉลย จากนั้นจึงใช้ TS ปรับปรุงคุณภาพของตารางและทดลองนำ Intraclasses – Interclasses procedure เข้ามาช่วยปรับปรุงหลังจากที่ TS ให้ตารางที่ดีแล้ว พบว่าการใช้ TS ร่วมกับ Intraclasses-Interclasses procedure ให้ตารางสอนที่มีคุณภาพดีและรวดเร็วยิ่งขึ้น Costaได้ใช้ TS ในปี 1994 ในการแก้ปัญหาการจัดตารางโรงเรียนมัธยมศึกษา พบว่าได้ผลดีพอๆ กับการจัดด้วยมือแต่ใช้เวลาในการทำงานน้อยกว่า แต่การกำหนดข้อบังคับบางข้อก็ยากที่จะทำให้ได้ตามความต้องการทั้งหมด