Hybrid Approaches

ปี 2003 Blum and Roli ได้ทำการศึกษาและจำแนกรูปแบบของวิธีการไฮบริดไว้ 3 แบบ

            1 การไฮบริดในรูปแบบของการแลกเปลี่ยนส่วนประกอบระหว่างขั้นตอนวิธีแบบ meta-heuristic หรือการรวมเอาส่วนประกอบของขั้นตอน วิธีใดวิธีหนึ่งเข้าไปไว้ในการทำงานของขั้นตอนวิธีแบบอื่นๆ แนวทางในการไฮบริดรูปแบบนี้ เช่น การใช้ Simulated Annealling, local search ในขั้นตอนการทำงานของ ACO (Ant Colony Optimization) หรือ Genetic Algorithm การนำเอา Local search ไปใช้ในGenetic Algorithm เรียกวิธีการแบบนี้ว่า มีมีติกอัลกอริทึม (Memetic  algorithm)

            2 การไฮบริดในรูปแบบการทำงานร่วมกันของขั้นตอนวิธีต่างๆ แล้วมีการแลกเปลี่ยนข้อมูลข่าวสาร (information) กัน ซึ่งเป็นการทำงานในรูปแบบที่เป็นอิสระต่อกันหรือทำงานในแบบขนาน (parallel) โดยอาจจะใช้ขั้นตอนวิธีแตกต่างกันแล้วแลกเปลี่ยนข้อมูลข่าวสารกัน หรือใช้ขั้นตอนวิธีแบบเดียวกันแต่ทำงานโดยกำหนดค่าพารามิเตอร์แตกต่างกัน

            3 การไฮบริดในรูปแบบของการรวมขั้นตอนวิธีแบบกะประมาณ (approximate method) กันแบบมีระเบียบแบบแผน (conventional method) เช่น การใช้ขั้นตอนวิธีแบบมีระเบียบแบบแผนในการสร้างส่วนหนึ่งของผลเฉลย จากนั้นใช้ meta-heuristic ในการทำให้ได้ผลเฉลยที่สมบูรณ์

            มีตัวอย่างของงานวิจัยที่ใช้วิธีการไฮบริด ได้ศึกษาเปรียบเทียบผลการทำงานของ SA, TS, GA และ ACS (Ant Colony System) ในการแก้ปัญหาการจัดตารางสอบ โดยตารางสอบที่เป็นผลเฉลยเริ่มต้นสำหรับการทำงานของ Simulated Annealling, Taboo Search และ Genetic Algorithm จะสร้างจากการสุ่มทั้งหมด แต่ ACS จะมีกฎเกณฑ์ในการสร้างผลเฉลย ดังนั้น ACS จึงมีผลเฉลยเริ่มต้นดีที่สุด เมื่อให้ประมวลผลจนสิ้นสุดการทำงาน พบว่า หากพิจารณาตามความสามารถในการหาผลเฉลย ACS ให้ผลเฉลยดีที่สุด รองลงมาคือ Genetic Algorithm และ Taboo Search ส่วน SA อยู่อันดับสุดท้าย แต่หากพิจารณาตามความสามารถในการลดค่าฟังชั่นต้นทุนโดยเปรียบเทียบตามช่วงเวลาเดียวกันพบว่า TS ดีที่สุด จึงได้ทำการศึกษาต่อไปโดยวิธีการไฮบริด ระหว่าง ACS กับ Taboo Search แล้วได้ทำการทดลองสลับลำดับการทำงานของ ACS กับ Taboo Search ในรูปแบบต่างๆ พบว่าการให้ ACS สร้างผลเฉลยเริ่มต้นแล้วใช้ผลเฉลยนั้นทำงานใน Taboo Search ให้ผลเฉลยดีที่สุด

            นอกจากนี้ยังพบว่าวิธีการแบบไฮบริดให้ผลเฉลยที่ดีกว่าการทำงานของ Simulated Annealling, Taboo Search, Genetic Algorithm และ ACS แบบอัลกอริทึมเดี่ยวๆ ในขณะที่ Murata et al. (1996) ได้ศึกษาเปรียบเทียบการทำงานของ Genetic Algorithm กับขั้นตอนวิธีอื่นๆ ได้แก่ Simulated Annealling, Taboo Search, Local search และการใช้เทคนิคการสุ่มสร้างผลเฉยของปัญหา Flow shop scheduling พบว่า Genetic Algorithm ทำงานได้ดีกว่าการสุ่มสร้างผลเฉลยอย่างเห็นได้ชัดเจน แต่ยังด้อยกว่าผลเฉลยที่ได้จากขั้นตอนวิธีอื่นๆ ในข้างต้น จึงทำการทดสอบโดยใช้วิธีการไฮบริด Genetic Algorithm ดีขึ้นกว่าเดิม และเมื่อเปรียบเทียบผลเฉลยที่ได้จาก Genetic Algorithm หรือ Simulated Annealling หรือ Local search แล้วพบว่าวิธีการไฮบริดให้ผลเฉลยดีกว่า

[นัท]

เก่งจัง เราอ่านไม่รู้เรื่องเลย แต่เป็นกำลังใจให้นะค่ะ