[Algorithm]Particle Swarm Optimization

 

สวัสดีครับวันนี้ผมจะมาสอนอัลกอลิทึมที่ใช้ในการหาค่าที่ดีที่สุดแบบ Particle Swarm Optimization(PSO) โดยเจ้าอัลกอลิทึมตัวนี้เป็นการนำเอาโครงสร้างทางสังคมเพื่อหาคำตอบที่เหมาะสมที่สุดของปัญหา โดยอัลกอลิทึมตัวนี้ ถูกคิดค้นขึ้นมาโดย อีเบอฮาท (Eberhart) และ เคนเนดี้ (Kennedy) ในปี 1995 โดยมีแรงบันดาลใจในการพัฒนามาจากการสังเกตการเคลื่อนไหวของฝูงนกที่มีลักษณะการเคลื่อนที่สอดคล้องกันในเวลาออกหาอาหารฝูงนกเหล่านั้นจะมีการส่งสัญญาณเพื่อสื่อสารกันให้ทราบถึงตำแหน่งที่มีอาหารอยู่และทำการเคลื่อนที่ไปยังแหล่งอาหารที่ได้รับข้อมูลมา เมื่อได้แนวคิดดังนั้น PSO จึงใช้วิธีการค้นหาคำตอบด้วยการใช้อนุภาค (Particles) จำนวนมาก เคลื่อนที่ไปบนพื้นที่ที่ต้องการค้นหา (Search Space) เพื่อค้นหาคำตอบที่ดีที่สุด

  • Particle คือสมาชิก 1 ตัวที่อยู่ในกลุ่มประชากร ผมขอให้นึกถึงฝูงนกที่มี Particle มารวมกันจนกลายเป็นฝูงนก โดย Particle หรือนกจะประกอบไปด้วย ความเร็ว(Velocity) และ ตำแหน่ง(Position) ซึ่ง Particle จะมีการรับรู้ตำแหน่งของมัน ณ ปัจจุบัน และรู้คำตอบของตำแหน่งนั้นๆ บน Search Space ซึ่งในตำแหน่งที่ดีที่สุดนั้นเราจะเรียกมันว่า Personal Best Position 
  • กลุ่มประชากร คือเซตของ Particle ที่มี n ตัว ซึ่งมีตั่งแต่ 1 ถึง n หรืออาจะเรียกว่า ฝูง (Swarm)
  • Position ของ Particle ตัวที่ i ที่การวนซ้ำครั้งที่ t ถูกเขียนแทนด้วย Xi(t) โดยตำแหน่งดังกล่าวประกอบด้วยมิติ D มิติ คือ Xi(t) = (xi1(t),…, xid(t),…,xiD(t)) โดยที่ xid(t) คือค่าของตำแหน่งของมิติที่ d ของตัว Particle ตัวที่ i แต่ละตำแหน่ง Xi(t) สามารถแปลงเป็นคำตอบ (Solution) ของปัญหาทางคณิตศาสตร์ โดยค่านอกตำแหน่งมีถูกจำกัดในขอบเขต [Xmin, Xmax]
  • ค่าความเหมะสม (Fitness Value) คือ f(Xi(t)) คือค่าของคำตอบที่แปลงมาจากตำแหน่ง Xi(t) โดยจะถูกเรียกว่าค่าความเหมาะสมของตำแหน่ง Xi(t)
  • ความเร็ว (Velocity) คือ Vi(t) แทนค่าความเร็วของตัว Particle ตัวที่ i ที่การวนซ้ำครั้งที่ t คือถูกเขียนแทนด้วยค่าเวคเตอร์ที่มีมิติ D มิติ คือ Vi(t) = (vi1(t),…, vid(t),…, viD(t)) โดย vid(t) คือค่าของความเร็วที่มิติที่ d ของตัวพาร์ทิเคิลตัวที่ i ที่การวนซ้ำครั้งที่ t และ Vi(t + 1) คืออัตราเร็วที่ตัว Particle ตัวที่ i จะเคลื่อนที่จากตำแหน่ง Xi(t) ไปตำแหน่ง Xi(t + 1)
  • ความเร็สสูงสุด (Maximum Velocity) คือVmax คือขีดจำกัดของความเร็ว โดยแต่ละ vid(t) ไม่สามารถมีค่าออกนอกช่วง [−Vmax, Vmax] หรืออาจพูดง่ายๆ ว่านกแต่ละตัวต้องมีความเร็วสูงสุด และต้องไม่ต่ำไปไม่งั้นจะเคลื่อนที่ไม่ได้
  • น้ำหนักแรงเฉื่อย (Inertia Weight) คือ w(t) ซึ่งเป็นพารามิเตอร์ตัวที่ใช้ในการควบคุมผลกระทบของความเร็วของการทำงานก่อนหน้า ซึ่งตัวนี้จะทำให้ Particle ของเราทั่งหมดได้รับการกำหนดค่าลงไปด้วย
  • Personal Best Position คือ Pi คือตำแหน่งที่ถูกพบโดยตัว Paritcle ตัวที่ i ที่มีค่าความเหมาะสมที่ดีที่สุด
  • Global Best Position คือ Pg เป็นสัญลักษณ์ที่ใช้แทนตำแหน่งที่ดีสุด คือตำแหน่งที่ดีที่สุดที่ถูกพบโดยฝูง
  • Maximum Iteration คือ T ใช้เขียนแทนค่าการวนซ้ำสูงสุด โดยจะหยุดการวนเมื่อจำนวนการวนเท่ากับค่าสูงสุด

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

  1. สร้างอนุภาคโดยสุ่มตำแหน่งเริ่มต้นให้กับอนุภาคและกำหนดค่า T = 1 จากนั้นกำหนดความเร็วและตำแหน่งให้กับ Particle
  2. คำนวณหาค่าความเหมาะสม ถ้าหากว่าค่าความเหมาะสมที่ได้มีค่ามากกว่าค่าเดิม (Personal Best Position) ให้เปลี่ยนไปใช้ค่าที่มากกว่า
  3. เลือกค่าความเหมาะสมที่ดีที่สุดจากอนุภาคทุกตัวแล้ว
    ใช้เป็นค่าที่ดีที่สุด (Global Best Position)
  4. ในทุกๆรอบให้กำหนดตำแหน่งและความเร็วใหม่ด้วยใช้สมาการ 2 , 3 ครับ
  5. เคลื่อนที่อนุภาคไปยังตำแหน่งใหม่ ทำวนซ้ำจนได้คำตอบหรือครบจำนวนรอบที่กำหนด

Image

อีกตัวอย่างครับนำมาใช้กับ Image Processing 

อ้างอิงPantip , hindawi smartfields stanfordtracer uc3m es , เอกสารประกอบการเรียน ภาควิชาวิศวกรรมการผลิต คณะวิศวกรรมศาสตร์ สถาบันเทคโนโลยีไทย–ญี่ปุ่น ,  บท ความวิจัย การเพิ่มความสามารถในการค้นหาพื้นที่ใกล้เคียงของเจเนติค อัลกอริทึม โดยใช้เทคนิค พาติเคิล สวอม ออปติไมเซชั่น Improve Neighbor Search Ability of Genetic AlgorithmsUsing Particle Swarm Optimization Technique 

Facebook Comments