Tabu search

Tabu search การค้นหาแบบมีข้อห้าม

         การค้นหาคำตอบแบบทาบู (Tabu  Search) เป็นวิธีการค้นหาคำตอบแบบเมตา-ฮิวริสติก(Meta-Heuristics) ซึ่งเป็นวิธีที่นิยมมากในการนำมาแก้ปัญหาที่ไม่เป็นโพลีเมียล(NP-Problem) เช่นปัญหาการกำหนดเส้นทางการขนส่งรถบรรทุก  หรือปัญหาการจัดตารางการผลิต  เป็นการยากที่จะหาคำตอบที่เหมาะสมที่สุด(Optimal  Solution)  โดยเฉพาะอย่างยิ่งเมื่อปัญหานั้นมีขนาดใหญ่(NP-hard) การหาคำตอบที่เหมาะสมที่สุดอาจใช้เวลาในการคำนวณมาก  หรือเป็นไปไม่ได้ที่หาคำตอบที่เหมาะสมที่สุด  วิธีการค้นหาคำตอบแบบเมตา-ฮิวริสติก จึงถูกนำมาใช้ในการแก้ไขปัญหาเพราะใช้เวลาในการคำนวณน้อยกว่ามาก  อีกทั้งคำตอบที่ได้จากวิธีเมตา-ฮิวริสติก  ก็สามารถยอมรับได้ในการนำไปใช้งานจริง

         ดังนั้นการใช้วิธีการค้นหาคำตอบแบบเมตา-ฮิวริสติก(Meta-Heuristics) หลายๆวิธีได้ถูกนำมาประยุกต์ใช้ในการแก้ไขปัญหาต่างๆอย่างแพร่หลาย ซึ่งเป็นที่รู้จักกันได้แก่ วิธีการค้นหาแบบทาบู  วิธีการค้นหาคำตอบแบบพันธุกรรม(Genetic  Algorithrm) และวิธีการจำลองแอนนีลลิ่ง(Simulated  Annealing) ได้ถูกพัฒนาขึ้น และทดสอบกับการปัญหาด้านอุตสาหกรรม  พบว่าวิธีเมตา-ฮิวริสติกใช้งานได้ดีทั้งคุณภาพคำตอบและเวลาที่ได้จากวิธีเมตา-ฮิวริสติก  สามารถนำมาใช้งานได้จริง  อีกทั้งยังสามารถปรับปรุงคุณภาพของคำตอบให้สูงขึ้นโดยการกำหนดระยะเวลาในการหาคำตอบให้มากขึ้นได้ในการประมวลผลเมื่อเทียบกับวิธีการหาคำตอบที่เหมาะสมที่สุ

        วิธีการค้นหาแบบทาบูมีความแตกต่างจาก เมตา-ฮิวริสติกแบบอื่นๆ ตรงที่ไม่ได้อาศัยการสุ่มหรือการเลือกจากความน่าจะเป็น  แต่เป็นวิธีการค้นหาแบบดีเทอร์มินิสติก(Deterministic) ซึ่งค้นหาคำตอบจากบริเวณข้างเคียงคำตอบที่ดีที่สุดในขณะนั้น  โดยจะมีข้อห้ามไม่ให้ค้นหาซ้ำกับเซ็ตของคำตอบเดิมที่มีอยู่  หรือที่เรียกว่ารายการต้องห้าม(Tabu  list)  ซึ่งวิธีการห้ามดังกล่าวจะเป็นการห้ามเพื่อมิให้ต้องไปหาผลเฉลยเดิม  หรือหลงในวัฏจักร(Cyclic) ซึ่งจะส่งผลไม่สามารถหาคำต้องที่ดีขึ้นได้  วิธีการค้นหาแบบทาบูนั้นเป็นที่ยอมรับว่าสามารถที่จะหลีกเลี่ยงการให้คำตอบสุดท้ายที่เป็นค่า  Local  optimum  และยังสามารถค้นหาต่อไปเรื่อยๆ  จนกระทั่งได้คำตอบใกล้เคียงกับค่า  Global  optimum

        วิธีการค้นหาแบบทาบูประกอบไปด้วยรูปแบบการค้นหา 2  รูปแบบที่สำคัญคือ  การค้นหาคำตอบโดยใช้หน่วยความจำระยะสั้น(Short  Term  Memory) และการค้นหาโดยใช้หน่วยความจำระยะยาว(Long  Term  Memory) ซึ่งการค้นหาคำตอบโดยใช้หน่วยความจำระยะสั้นถือเป็นหน่วยความจำตามเวลา(Recency  Base  Memory) หมายถึงการค้นหาอดีตหรือการจดจำประสบการณ์การค้นหาที่ผ่านมาเพียงระยะสั้น  ในทางตรงกันข้ามการค้นหาคำตอบโดยใช้หน่วยความจำระยะยาวซึ่งถือเป็นหน่วยความจำความถี่(Frequency  Base  Memory) หมายถึงการค้นหาคำตอบที่ต้องจดจำในอดีตหรือประสบการณ์ที่ผ่านมาเพื่อช่วยให้การค้นหาคำตอบเป็นไปอย่างมีประสิทธิภาพมากยิ่งขึ้น  จากหลักการการค้นหาคำตอบแบบทาบู  สามารถสรุปขั้นตอนการทำงานกับปัญหาการจัดตารางการทำงานได้ดังนี้

ขั้นตอนที่ 1    สร้างคำตอบเริ่มต้น(Initial Solution) ในการสร้างเซ็ตของคำตอบเริ่มต้นจากวิธีการสุ่ม (Random) ตามค่าเริ่มต้น (Seed) ที่กำหนด โดยที่ S คือลำดับงานที่สร้างขึ้นจากการสุ่ม โดยจะมีการลำดับงานเริ่มต้นตั่งแต่ 1 ถึง n โดยที่ n คือจำนวนงานที่ต้องหาคำตอบ

                      Initial Solution = [S₁, S_2,….., S_n] 

ขั้นตอนที่ 2    สร้างเซ็ตของคำตอบใกล้เคียง (Best Neighborhood)โดยที่    คือเซ็ตของคำตอบข้างเคียงที่เป็นไปได้จากลำดับงานเริ่มต้น  โดยจะกำหนดให้เซ็ตคำตอบข้างเคียงที่เป็นไปได้ ตั้งแต่ 1 ถึง k 

ขั้นตอนที่ 3    เลือกเซ็ตคำตอบใกล้เคียงที่ดีที่สุด(Best Neighborhood)ในการพิจารณาหาเซ็ตคำตอบข้างเคียงที่ดีที่สุดของปัญหาการจัดตารางการทำงาน จะพิจารณาจากค่าการทำงานรวม (Makespan:C_max) โดยจะเลือกจากค่าที่ให้เวลาในการทำงานรวมน้อยที่สุด C_max  =F( ) = min{F( ),F( ),….,F( )}

ขั้นตอนที่ 4    ตรวจสอบรายการต้องห้าม(Tabu List) โดยจะกำหนดให้ บันทึกให้เป็นทาบู และตรวจสอบข้อมูลของกระบวนการค้นหาในอดีต ถ้าคำตอบข้างเคียงเป็นคำตอบในรายการทาบูให้เปลี่ยนคำตอบใหม่ และถ้าคำตอบข้างเคียงเป็นทาบูเกินระยะเวลาที่กำหนดให้ยกเลิกเป็นทาบูของคำตอบใกล้เคียงนั้น

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

ขั้นตอนที่ 6    ตรวจสอบรอบการทำงาน (Stopping Criteria) เป็นการตรวจสอบรอบการทำงานว่าค้นหาคำตอบครบรอบตามที่กำหนดไว้หรือยัง โดยในการกำหนดจำนวนรอบการทำงานนั้น จะพิจารณาคุณภาพของคำตอบที่ต้องการ เพราะถ้าต้องการคำตอบที่มีคุณภาพสูงก็ต้องกำหนดจำนวนรอบในการทำงานมากขึ้น

อ้างอิง: 

สมศักดิ์  สนเทศ .(2548). การศึกษาเปรียบเทียบ วิธีการค้นหาแบบทาบูและ วิธีเชิงพันธุกรรม สำหรับพื้นผิวตอบสนอง. วิทยานิพนธ์ปริญญาวิทยาศาสตรมหาบัณฑิต  คณะวิทยาศาสตร์และเทคโนโลยี  มหาวิทยาลัยธรรมศาสตร์.