[Algorithm] Particle Swarm Optimization

NSLog0
NSLog0
Jan 31 · 2 min read

โพสเก่าจาก Blog เดิม เมษายน 23, 2013

Image for post
Image for post

สวัสดีครับวันนี้ผมจะมาสอน Algoritm ที่ใช้ในการหาค่า 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 Processing

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

AlgorithmTut

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store