การหาค่าเหมาะที่สุดด้วยฝูงอนุภาค (Particle Swarm Optimization: PSO)
- ปี
- 1995
- ประเภท
- Population-based metaheuristic / swarm intelligence
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Particle Swarm Optimization (PSO) เป็นอัลกอริทึมเมตาฮิวริสติกแบบประชากรที่นำเสนอโดย Kennedy และ Eberhart ในปี 1995 โดยได้รับแรงบันดาลใจจากการเคลื่อนที่ร่วมกันของฝูงนกและฝูงปลา คำตอบตัวเลือก (candidate solution) แต่ละรายการ — เรียกว่าอนุภาค — เคลื่อนที่ผ่านปริภูมิการค้นหาโดยการอัปเดตความเร็วและตำแหน่งตามประสบการณ์ที่ดีที่สุดของตนเองและประสบการณ์ที่ดีที่สุดของฝูงทั้งหมด ทำให้เกิดการลู่เข้าอย่างรวดเร็วสำหรับปัญหาการหาค่าที่เหมาะสมที่สุดแบบต่อเนื่อง
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพฝูงนกที่กำลังค้นหาแหล่งอาหารที่อุดมสมบูรณ์ที่สุดในทุ่งกว้าง ไม่มีนกตัวใดมีแผนที่ แต่แต่ละตัวจำจุดที่ดีที่สุดที่ตนเองเคยไปเยือนและรับรู้ถึงจุดที่ดีที่สุดที่นกตัวใดก็ตามในบริเวณใกล้เคียงพบ นกแต่ละตัวจะบังคับทิศทางการบินบางส่วนไปยังตำแหน่งที่ดีที่สุดที่ตนเองจำได้ และบางส่วนไปยังตำแหน่งที่ดีที่สุดโดยรวมของฝูง โดยปรับความเร็วตามนั้น การอัปเดตหลายครั้งเช่นนี้จะทำให้ทั้งฝูงลู่เข้าสู่บริเวณที่อุดมสมบูรณ์ที่สุด PSO ทำงานเช่นนี้: อนุภาคแต่ละตัวคือคำตอบตัวเลือก ตำแหน่งของมันคือคำตอบนั้นเอง และฝูงจะมุ่งหน้าสู่ค่าที่เหมาะสมที่สุดโดยการรวมความจำส่วนบุคคลและสังคมเข้าด้วยกัน
ประวัติศาสตร์
PSO ถูกนำเสนอโดย James Kennedy และ Russell Eberhart ในการประชุม IEEE International Conference on Neural Networks ปี 1995 โดยได้รับแรงบันดาลใจโดยตรงจากแบบจำลองการจำลองพฤติกรรมทางสังคมในฝูงนกและฝูงปลา เอกสารพื้นฐานปี 1995 ได้กำหนดสมการอัปเดตความเร็วและตำแหน่งที่ยังคงเป็นหัวใจสำคัญของอัลกอริทึม ในปี 1998 Shi และ Eberhart ได้นำพารามิเตอร์น้ำหนักความเฉื่อยมาใช้ในการอัปเดตความเร็ว ซึ่งช่วยปรับปรุงการควบคุมการลู่เข้าอย่างมีนัยสำคัญ และกลายเป็นส่วนอัปเดตมาตรฐานที่งานวิจัยต่อมานำมาใช้ PSO ได้รับความนิยมอย่างรวดเร็วในฐานะทางเลือกที่ใช้งานได้จริงแทนอัลกอริทึมพันธุกรรม (genetic algorithms) สำหรับการหาค่าที่เหมาะสมที่สุดแบบต่อเนื่อง เนื่องจากความเรียบง่ายและความเร็วในการลู่เข้าที่แข่งขันได้ และได้ถูกนำไปใช้ในด้านวิศวกรรม การปรับแต่งไฮเปอร์พารามิเตอร์ของแมชชีนเลิร์นนิง การประมวลผลสัญญาณ และการสร้างแบบจำลองทางวิทยาศาสตร์
ควรใช้เมื่อใด
PSO เหมาะสำหรับปัญหาการหาค่าที่เหมาะสมที่สุดแบบต่อเนื่อง ซึ่งฟังก์ชันฟิตเนสสามารถประเมินค่าได้ ณ จุดใดก็ตามในปริภูมิการค้นหา แต่อาจไม่สามารถหาอนุพันธ์ได้ มีหลายโหมด หรือมีค่าใช้จ่ายสูงในการคำนวณเชิงวิเคราะห์ ไม่จำเป็นต้องมีข้อสมมติฐานเกี่ยวกับความเป็นปกติและไม่มีขนาดตัวอย่างขั้นต่ำ ทำให้สามารถนำไปใช้ได้ในหลากหลายสาขา วิธีการนี้ทำงานได้ดีที่สุดเมื่อทราบขอบเขตของปริภูมิการค้นหาล่วงหน้า เมื่อน้ำหนักความเฉื่อยและสัมประสิทธิ์ความเร่งได้รับการปรับแต่งอย่างระมัดระวัง และเมื่อจัดสรรจำนวนรอบที่เพียงพอ หากจำนวนรอบน้อยเกินไป (น้อยกว่าไม่กี่ร้อยสำหรับปัญหาที่ซับซ้อน) การลู่เข้าก่อนกำหนดมีแนวโน้มสูง และการหาค่าที่เหมาะสมที่สุดแบบเบย์เซียน (Bayesian optimization) อาจเป็นทางเลือกที่ปลอดภัยกว่า
ข้อจำกัดและข้อควรพิจารณา
- ออกแบบมาสำหรับปริภูมิการค้นหาแบบต่อเนื่อง ไม่สามารถนำไปใช้กับปัญหาแบบไม่ต่อเนื่องหรือแบบผสมได้โดยตรงหากไม่มีการปรับเปลี่ยน
- การลู่เข้าก่อนกำหนดเป็นความเสี่ยงที่ทราบกันดี: ฝูงอาจรวมกลุ่มกันรอบค่าที่เหมาะสมที่สุดเฉพาะที่ (local optimum) หากน้ำหนักความเฉื่อยและสัมประสิทธิ์ถูกเลือกไม่ดี
- ความเร็วในการลู่เข้าและคุณภาพของคำตอบมีความอ่อนไหวต่อการเลือกน้ำหนักความเฉื่อยและสัมประสิทธิ์ความเร่ง
- ไม่มีการรับประกันทางทฤษฎีว่าจะพบค่าที่เหมาะสมที่สุดโดยรวม (global optimum) ในจำนวนรอบที่จำกัด
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- การลู่เข้าอย่างรวดเร็วในปริภูมิการค้นหาแบบต่อเนื่องเมื่อเทียบกับวิธีการแบบประชากรส่วนใหญ่
- มีพารามิเตอร์น้อยมากที่ต้องปรับแต่ง — ส่วนใหญ่คือน้ำหนักความเฉื่อยและสัมประสิทธิ์ความเร่งสองตัว
- ไม่ต้องการข้อมูลเกรเดียนต์หรืออนุพันธ์ ทำให้สามารถนำไปใช้กับฟังก์ชันฟิตเนสที่ไม่สามารถหาอนุพันธ์ได้และฟังก์ชันแบบกล่องดำ (black-box)
- ปรับขนาดได้ตามธรรมชาติสำหรับปัญหาแบบต่อเนื่องที่มีมิติสูง
- แนวคิดเรียบง่ายและตรงไปตรงมาในการนำไปใช้
การประยุกต์ใช้
- การปรับแต่งไฮเปอร์พารามิเตอร์สำหรับโมเดลแมชชีนเลิร์นนิงในปริภูมิพารามิเตอร์แบบต่อเนื่อง
- การหาค่าที่เหมาะสมที่สุดในการออกแบบทางวิศวกรรม — การออกแบบโครงสร้างอากาศพลศาสตร์ และระบบไฟฟ้า
- การฝึกน้ำหนักโครงข่ายประสาทเทียมและการค้นหาโครงสร้าง
- การประมวลผลสัญญาณและการออกแบบเสาอากาศ
- การจัดส่งทางเศรษฐกิจและการหาค่าที่เหมาะสมที่สุดของระบบพลังงาน
- การประมาณค่าพารามิเตอร์ในแบบจำลองทางวิทยาศาสตร์และการจำลอง
วิธีการทำงาน
วิธีการทำงาน
ฝูงอนุภาคจะถูกวางไว้ในตำแหน่งสุ่มภายในปริภูมิการค้นหาที่กำหนด และอนุภาคแต่ละตัวจะได้รับความเร็วเริ่มต้นแบบสุ่ม อนุภาคแต่ละตัวจะบันทึกตำแหน่งที่ดีที่สุดส่วนบุคคล — คำตอบที่ดีที่สุดที่เคยพบจนถึงปัจจุบัน — และฝูงจะติดตามตำแหน่งที่ดีที่สุดโดยรวมที่พบโดยอนุภาคใดๆ น้ำหนักความเฉื่อย สัมประสิทธิ์ด้านการรู้คิด และสัมประสิทธิ์ทางสังคมจะถูกตั้งค่าก่อนเริ่มการทำงาน เนื่องจากความสมดุลของสิ่งเหล่านี้เป็นตัวกำหนดโดยตรงว่าฝูงจะสำรวจอย่างกว้างขวางหรือใช้ประโยชน์จากบริเวณที่ดีที่ทราบ
ฟังก์ชันฟิตเนส (fitness function) จะถูกคำนวณสำหรับอนุภาคแต่ละตัวในตำแหน่งปัจจุบัน นี่เป็นขั้นตอนเดียวที่เฉพาะเจาะจงกับปัญหา: PSO ไม่ได้กำหนดข้อจำกัดใดๆ เกี่ยวกับรูปแบบของฟังก์ชันฟิตเนส นอกเหนือจากข้อกำหนดที่ว่าฟังก์ชันนั้นจะต้องสามารถประเมินค่าได้ ณ จุดใดก็ตามในปริภูมิการค้นหาแบบต่อเนื่อง ตำแหน่งที่ดีที่สุดส่วนบุคคลของอนุภาคแต่ละตัวและตำแหน่งที่ดีที่สุดโดยรวมของฝูงจะถูกอัปเดตเมื่อใดก็ตามที่ตำแหน่งใหม่ให้ค่าฟิตเนสที่ดีขึ้น
ความเร็วของอนุภาคแต่ละตัวจะถูกอัปเดตโดยใช้สามส่วนประกอบ: ส่วนของความเฉื่อย (ความเร็วที่ปรับตามสัดส่วนของความเร็วที่ผ่านมา ส่งเสริมโมเมนตัม) ส่วนด้านการรู้คิด (cognitive) (แรงดึงดูดไปยังตำแหน่งที่ดีที่สุดส่วนบุคคลของอนุภาคเอง) และส่วนทางสังคม (แรงดึงดูดไปยังตำแหน่งที่ดีที่สุดโดยรวมของฝูง) จากนั้นตำแหน่งใหม่จะถูกคำนวณโดยการบวกความเร็วที่อัปเดตแล้วเข้ากับตำแหน่งปัจจุบัน น้ำหนักความเฉื่อยควบคุมการแลกเปลี่ยนระหว่างการสำรวจและการใช้ประโยชน์: ค่าที่สูงขึ้นส่งเสริมการสำรวจอย่างกว้างขวาง ในขณะที่ค่าที่ต่ำลงส่งเสริมการใช้ประโยชน์อย่างละเอียดในบริเวณที่ดีที่ทราบ
ขั้นตอนการประเมินและอัปเดตจะถูกทำซ้ำตามจำนวนรอบที่กำหนด ฝูงจะค่อยๆ จำกัดการค้นหาให้อยู่ในบริเวณที่มีแนวโน้มมากที่สุด การทำงานจะสิ้นสุดลงเมื่อถึงขีดจำกัดจำนวนรอบ ณ จุดนั้น ตำแหน่งที่ดีที่สุดโดยรวมจะถูกรายงานเป็นคำตอบ จำนวนรอบที่เพียงพอ — โดยทั่วไปอย่างน้อยหลายร้อยถึงหนึ่งพันสำหรับปัญหาที่ซับซ้อน — เป็นสิ่งจำเป็นเพื่อให้ฝูงลู่เข้า การหยุดเร็วเกินไปมีความเสี่ยงที่จะให้ผลลัพธ์ที่ไม่เหมาะสมที่สุด
ข้อผิดพลาดที่พบบ่อย
- การทำงานจำนวนรอบน้อยเกินไป — สำหรับปัญหาที่ซับซ้อน จำนวนรอบที่ไม่เพียงพอจะขัดขวางไม่ให้ฝูงลู่เข้า ควรเลือกการหาค่าที่เหมาะสมที่สุดแบบเบย์เซียนเมื่องบประมาณการคำนวณมีจำกัดมาก
- การเลือกน้ำหนักความเฉื่อยที่สูงเกินไปจะทำให้อนุภาคสำรวจไปเรื่อยๆ ไม่หยุด และทำให้การลู่เข้าล่าช้าเกินไป หากต่ำเกินไปจะทำให้เกิดการรวมกลุ่มรอบค่าที่เหมาะสมที่สุดเฉพาะที่ก่อนกำหนด
- การละเลยขอบเขตของปริภูมิการค้นหา — อนุภาคที่ลอยออกนอกขอบเขตที่ตั้งใจไว้จะสำรวจบริเวณที่ไม่เกี่ยวข้องและบิดเบือนค่าที่ดีที่สุดโดยรวม
- การถือว่า PSO เหมาะสมสำหรับปัญหาแบบไม่ต่อเนื่องหรือแบบผสมโดยไม่มีการปรับเปลี่ยน — สมการอัปเดตความเร็วและตำแหน่งมาตรฐานจะสมมติว่าปริภูมิเป็นค่าจริง
- การลู่เข้าก่อนกำหนดจะตรวจไม่พบหากความคืบหน้าของฟิตเนสไม่ได้รับการตรวจสอบตลอดจำนวนรอบ — ควรติดตามค่าฟิตเนสที่ดีที่สุดโดยรวมเทียบกับจำนวนรอบเสมอ
คำถามที่พบบ่อย
PSO แตกต่างจากอัลกอริทึมพันธุกรรมอย่างไร?
ทั้งสองเป็นเมตาฮิวริสติกแบบประชากรสำหรับการหาค่าที่เหมาะสมที่สุด แต่แตกต่างกันในกลไก อัลกอริทึมพันธุกรรมจะพัฒนาประชากรผ่านตัวดำเนินการคัดเลือก การผสมข้าม และการกลายพันธุ์ที่ได้รับแรงบันดาลใจจากวิวัฒนาการทางชีววิทยา ในทางกลับกัน PSO จะเคลื่อนอนุภาคผ่านปริภูมิแบบต่อเนื่องโดยการอัปเดตความเร็วตามความจำส่วนบุคคลและสังคม — ไม่มีการผสมข้ามหรือการกลายพันธุ์ PSO มักมีพารามิเตอร์น้อยกว่าที่ต้องปรับแต่ง และมักจะลู่เข้าเร็วกว่าในปัญหาแบบต่อเนื่อง ในขณะที่อัลกอริทึมพันธุกรรมสามารถปรับให้เข้ากับปริภูมิแบบไม่ต่อเนื่องหรือแบบผสมได้ง่ายกว่า
พารามิเตอร์หลักคืออะไรและควรตั้งค่าอย่างไร?
พารามิเตอร์หลักสามตัวคือ น้ำหนักความเฉื่อย (w) ซึ่งควบคุมปริมาณความเร็วที่ผ่านมาที่จะคงไว้ สัมประสิทธิ์ด้านการรู้คิด (cognitive coefficient: c1) ซึ่งปรับขนาดแรงดึงดูดไปยังตำแหน่งที่ดีที่สุดส่วนบุคคลของอนุภาค และสัมประสิทธิ์ทางสังคม (c2) ซึ่งปรับขนาดแรงดึงดูดไปยังตำแหน่งที่ดีที่สุดโดยรวมของฝูง จุดเริ่มต้นทั่วไปจากวรรณกรรมคือน้ำหนักความเฉื่อยประมาณ 0.7–0.9 สัมประสิทธิ์ c1 และ c2 ประมาณ 1.5–2.0 น้ำหนักความเฉื่อย มักจะลดลงเชิงเส้นตลอดจำนวนรอบ เพื่อเปลี่ยนฝูงจากการสำรวจในช่วงต้นไปสู่การใช้ประโยชน์ในช่วงหลัง
PSO สามารถจัดการกับปัญหาแบบไม่ต่อเนื่องหรือแบบผสมได้หรือไม่?
PSO มาตรฐานถูกกำหนดสำหรับปริภูมิการค้นหาแบบต่อเนื่อง และใช้การอัปเดตความเร็วและตำแหน่งที่สมมติว่าพิกัดเป็นค่าจริง มีรูปแบบที่ไม่ต่อเนื่องหรือแบบผสมอยู่ — เช่น binary PSO — แต่สิ่งเหล่านี้ต้องการการปรับเปลี่ยนสมการอัปเดตที่ไม่ใช่เรื่องง่าย สำหรับปัญหาแบบผสมล้วนๆ เช่น การจัดเส้นทางหรือการจัดตารางเวลา Ant Colony Optimization มักเป็นตัวเลือกที่เหมาะสมกว่า
ฉันจะทราบได้อย่างไรว่าฝูงลู่เข้าก่อนกำหนด?
ติดตามค่าฟิตเนสที่ดีที่สุดโดยรวมตลอดจำนวนรอบ หากกราฟราบเรียบก่อนที่จะใช้โควต้าจำนวนรอบหมด และคำตอบที่รายงานไม่น่าพอใจ แสดงว่าอาจเกิดการลู่เข้าก่อนกำหนด วิธีแก้ไขทั่วไป ได้แก่ การเพิ่มน้ำหนักความเฉื่อย การเริ่มต้นฝูงใหม่จากตำแหน่งสุ่ม หรือการเพิ่มขนาดฝูง หากงบประมาณการคำนวณไม่อนุญาตให้มีรอบเพิ่มเติม การหาค่าที่เหมาะสมที่สุดแบบเบย์เซียนอาจเป็นทางเลือกที่มีประสิทธิภาพมากกว่า
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วShi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว