พื้นฐาน AI 🤖: EP 3 Local Search
มีหลายปัญหาที่เราไม่สนใจ path ของ solution แต่สนใจเฉพาะเป้าหมายสุดท้ายเท่านั้น ซึ่ง algorithm หนึ่งที่ไม่สนใจเกี่ยวกับ path เลย คือ “Local Search”
Local Search
แนวคิดคือมอง state space เป็นพื้นที่เทือกเขาโดยความสูงของภูเขากำหนดโดย heuristic cost function หรือ objective function หากต้องการหาค่าต่ำสุดหรือ global minimum ต้องไปที่หุบเขาที่ต่ำที่สุด หากต้องการหาค่าสูงสุด หรือ global maximum ต้องไปที่ยอดสูงสุดของเทือกเขา
Local search มักถูกใช้ในการแก้ปัญหา optimization เพื่อหาสถานะ (state) ที่ดีที่สุด โดยเริ่มต้นจากสถานะใดสถานะหนึ่ง กำหนดเป็น current state แล้วย้ายไป state เพื่อนบ้านของ current state เท่านั้น ซึ่งข้อดีของ local search คือ
- ใช้ memory น้อย และมักเป็นเพียงค่าคงที่ (เพราะไม่ต้องใช้ memory ในการบันทึก path)
- สามารถหา solution ที่สมเหตุสมผลได้ใน state space ที่มีขนาดอนันต์
ตัวอย่างปัญหา search: N Queen Problem
กำหนดมีราชานีอยู่ N พระองค์ มีกระดานขนาด NxN ตำแหน่งการโจมตีของราชานีเป็นไปตามหมากรุกสากลคือตัวที่อยู่ใน column, row , เส้นทแยงมุม (diagonal) เดียวกัน
จะต้องหาตำแหน่งวางราชีนีแต่ละพระองค์ไม่ให้ตีกันเอง จากภาพด้านล่างเป็นตัวอย่างกรณี N = 4
ตัวอย่างคำตอบ
Algorithm ที่อยู่ในกลุ่ม local search ได้แก่ hill climbing, simulated annealing, local beam search และ genetic algorithm
Hill Climbing
หรือ greedy local search เป็นแนวคิดที่พื้นฐาน และใช้บ่อยมาก โดยเริ่มต้นที่ state ใด state หนึ่ง แล้วย้ายไป state ที่อยู่ติดกันที่ดีกว่า state ปัจจุบัน ทำซ้ำไปเรื่อยๆจนกว่าจะไม่มี state ที่อยู่ติดกันดีกว่า state ปัจจุบันแล้ว ดังนั้นปัญหาของ hill climbing คือ local maxima และ local minima ตามกราฟด้านล่าง
Simulated Annealing
นำแนวของการหลอมโลหะมาใช้ โดยเริ่มต้นที่อุณหภูมิสูง และค่อยๆเย็นตัวลง เมื่ออุณหภูมิสูง electron จะดูดซับพลังงานมาก และเคลื่อนที่ได้เร็ว โลหะขึ้นรูปง่าย เปรียบเหมือน state ที่ย้ายไป state ใหม่ได้ระยะทางไกล และมีโอกาสยอมไปใน state ที่แย่กว่าสูง เมื่ออุณหมูิลดลง พลังงานของ electron ลดลง เคลื่อนที่ได้ช้าลง โลหะขึ้นรูปได้ยาก เปรียบเหมือน state ที่ย้ายได้ในระยะทางที่สั้นลง และโอกาสยอมไปใน state ที่แย่กว่าลดลง
กรณีที่ต้องการหา global minimum สมการยอมไป state ต่อไปคือ (ถ้าหา global maximum ก็สลับตำแหน่ง f(j) กับ f(i) )
โดย
- i: state ปัจจุบัน
- j: state ต่อไป
- Pr: ความน่าจะเป็นที่จะยอมไป state j
- c: control parameter เปรียบเสมือนอุณหภูมิ
จะเห็นได้ว่าถ้า c ยิ่งมาก ก็ยิ่งมีโอกาสยอมไป state j กรณีที่ state j ไม่ได้ดีกว่า state i
Local Beam Search
เริ่มแรกสร้าง state ขึ้นมา K state หลังจากนั้นในทุกๆ loop สร้าง state ต่อไปของ K state ก่อนหน้า และเลือก state ที่ดีที่สุด K state เข้าสู่ loop ต่อไป เปรียบเสมือนการคัดสรรโดยธรรมชาติของ Charles Darwin จากภาพด้านล่างเป็นกรณี K = 4
จะเห็นได้ว่าเมื่อเวลาผ่านไปจะมีเพียงไม่กี่ state เริ่มต้นเท่านั้นที่ได้สืบทอดรุ่นต่อไป และจำนวนรุ่นต่อไปก็เพิ่มขึ้นเรื่อนๆเป็นรูปลำแสง (beam)
Genetic Algorithm
นำแนวคิด local beam search มาต่อยอด โดยคล้ายกับการแลกเปลี่ยน chromosome จากภาพด้านล่างแบ่งเป็น step ย่อยคือ
a: กำหนด state เริ่มต้น
b: นำ state เริ่มต้นผ่าน objective function หรือในที่นี้เรียกว่า fitness function โดยจะ return ค่าที่สูงสำหรับ state ที่ดี แล้วนำค่ารวมของทุก state มาดิด percent ความน่าจะเป็นการถ่ายทอด state นั้นไปรุ่นต่อไป
c: ได้ state ที่ถูกคัดเลือกจากการสุ่มโดยใช้ความน่าจะเป็นจาก step b โดยเป็นการสุ่มทีละ state แยกกัน ดังนั้นจึงมีโอกาสที่จะมี state เดิมถูกเลือกมากกว่า 1 ครั้ง
d: สร้างลูกหลานของ state ที่ถูกคัดเลือก โดยกำหนด crossover point แล้วแลกเปลี่ยนบางส่วนให้กันและกัน
e: สุ่มให้บางส่วนมีการกลายพันธุ์ด้วยความน่าจะเป็นเพียงเล็กน้อย
อ้างอิง
หนังสือ Artificial Intelligence: A Modern Approach (4th edition)
