Particle Swarm Optimization: PSO (part1)

การหาค่าเหมาะสมที่สุดแบบกลุ่มอนุภาค (Particle Swarm Optimization) หรือ PSO พัฒนาขึ้นโดยอีเบอร์ฮาร์ดและเคนเนดี้ (J.Kennedy and R.Eberthart, 1995) โดยมีแนวคิดมาจากการจำลองวิธีการหาค่าเหมาะสมที่สุดจากพฤติกรรมการเดินทางหรือหาอาหารของฝูงสัตว์ โดยเฉพาะฝูงนก ฝูงปลา

..........

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

PSO เป็นการจำลองการหาอาหารของฝูงนก ในการหาค่าเหมาะที่สุดแบบนี้ นกแต่ละตัวในฝูงจะถูกแทนด้วยอนุภาค (particle) ในอนุภาคแต่ละตัวจะมีค่า ฟิตเน็ส (fitness value) ที่บอกถึงระยะห่างของตัวมันจากแหล่งอาหาร โดยอนุภาคทั้งหมดจะบินตามอนุภาคที่มีค่าฟิตเน็ตที่ดีที่สุดในแต่ละช่วง/รอบ (Iteration)

แนวคิดของ PSO จะเริ่มต้นด้วยการสุ่มหาตำแหน่งของอนุภาค (ซึ่งตำแหน่งต่างๆ ของอนุภาคเหล่านั้นก็คือคำตอบที่เป็นไปได้) ขึ้นมาชุดหนึ่ง จากนั้นก็จะหาค่าเหมาะสมที่สุดด้วยการปรับปรุงค่าในแต่ละรอบของการตัดสินใจ โดยที่อนุภาคแต่ละตัวจะมีการปรับปรุงค่าด้วยการเปลี่ยนตำแหน่งตามค่าที่ดีที่สุด (Best) ซึ่งมี 2 ค่า ได้แก่

1. ค่าที่ดีที่สุดของอนุภาค (pbest : particle best) คือค่าตำแหน่งที่ดีที่สุดของการเคลื่อนที่ที่ผ่านมาของตัวมันเอง
2. ค่าที่ดีที่สุดของสากล (gbest : global best) คือค่าที่เป็นค่าที่ดีที่สุดการเคลื่อนที่ที่ผ่านมาของทั้งกลุ่ม (ฝูง)

การทำงานของ PSO เป็นกระบวนการที่ทำงานเป็นรอบ (Iteration) ซึ่งในแต่ละรอบของการทำงานความเร็วของอนุภาคแต่ละตัวจะถูกปรับปรุงโดยมีตัวแปรที่สำคัญ 3 ตัว คือ

1. ความเร็วปัจจุบันของอนุภาคนั้น (velocity)
2. ข้อมูลที่อนุภาคมีอยู่ (pbest)
3. ข้อมูลรวมของอนุภาคทั้งกลุ่ม (gbest)

หลังจากนั้นอนุภาคแต่ละตัวจะปรับตำแหน่งของมันโดยใช้ความเร็วใหม่ที่คำนวณได้ โดยพิจารณาจากสมการดังต่อไปนี้

คำนวนค่าความเร็วใหม่ของอนุภาคตามสมการ 1.1
v_ik(t+1) = v_ik(t) + [c₁ * r₁ * (p(t) - x_ik(t))] + [c₂ * r₂ * (g(t) - x_ik(t))]

ปรับปรุงค่าตำแหน่งใหม่ของอนุภาคตามสมการ 1.2
x_ik(t+1) = x_ik(t) + v_ik(t+1)                                             

** c1,c2 คือค่าคงที่ บางครั้งถูกเรียกว่า ค่าแฟคเตอร์การเรียนรู้ (เอาไว้ถ่วงน้ำหนักความจำ) โดยทั่วไปจะเท่ากับ 2 แต่ก็สามารถใช้ค่าอื่นๆ ได้ โดยที่จะมีช่วงระหว่าง [0,4] หรือ 0 ถึง 4

ค่า c1 = 0.729 และ c2 = 1.494 เป็นค่าที่เคอร์ (Clerc,1999) แนะนำ **


อัลกอริทึม PSO

** สำหรับตอนนี้คงขอจบเท่านี้ก่อน ตอนต่อไปจะเป็นเรื่องของขั้นตอนการทำงานของ PSO และจะลองมาคำนวณกันดูว่าแต่ละรอบการทำงานของ PSO ค่าที่ได้มีอะไรบ้าง ไว้พบกันใหม่ตอนต่อไปครับ

แหล่งอ้างอิง:
[1] บุญเจริญ ศิริเนาวกุล. ปัญญาประดิษฐ์ : ปัญญาเชิงกลุ่ม = Artificial Intelligence : Swarm Intelligence. -- กรุงเทพฯ : ท้อป, 2555.
[2] อาทิตย์ ศรีแก้ว. ปัญญาเชิงคำนวณ, Computational Intelligence. พิมพ์ครั้งที่ 1 (ฉบับปรับปรุงปี 2552), บจก. จรัลสนิทวงศ์การพิมพ์, กุมภาพันธ์ 2553