Skip to content
กลับไปยังผลการค้นหา

การหาค่าเหมาะที่สุดด้วยฝูงอนุภาคแบบหลายวัตถุประสงค์ (Multi-Objective Particle Swarm Optimization: MOPSO)

ผู้เสนอ
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
ปี
2004
ประเภท
Population-based swarm metaheuristic
กลุ่มวิธี
Simulation / optimization

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

Multi-Objective Particle Swarm Optimization (MOPSO) เป็นเมตาฮิวริสติกส์แบบฝูงอัจฉริยะ (swarm-intelligence metaheuristic) ที่ขยายขีดความสามารถของ Particle Swarm Optimization (PSO) แบบดั้งเดิม เพื่อจัดการกับฟังก์ชันวัตถุประสงค์ที่ขัดแย้งกันหลายฟังก์ชันพร้อมกัน โดยจะรักษาคลังข้อมูลพาเรโตภายนอก (external Pareto archive) และใช้การคัดเลือกโดยอาศัยการครอบงำ (dominance-based selection) เพื่อนำพาประชากรของคำตอบที่เป็นไปได้ไปสู่พาเรโตฟรอนต์ที่แท้จริง (true Pareto front) โดยไม่จำเป็นต้องมีข้อมูลความชอบล่วงหน้า

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพฝูงนกที่กำลังหาอาหารร่วมกันในภูมิประเทศที่มีเนินเขาสูงต่ำหลายแห่งซึ่งไม่สามารถปีนขึ้นไปได้ทั้งหมดพร้อมกัน การไต่ระดับความสูงบนเนินเขาหนึ่งมักจะหมายถึงการสูญเสียพื้นที่บนเนินเขาอื่น MOPSO ปล่อยฝูงอนุภาค (particles) ไปทั่วปริภูมิการแลกเปลี่ยนหลายมิติ (multi-dimensional trade-off space) อนุภาคแต่ละตัวจะจดจำตำแหน่งที่ดีที่สุดที่ไม่ถูกครอบงำ (best non-dominated position) ของตนเอง และเรียนรู้จากคลังข้อมูลภายนอกของคำตอบที่ดีที่สุดที่ไม่ถูกครอบงำระดับส่วนกลาง (global) ที่พบจนถึงปัจจุบัน ด้วยการผสมผสานความจำส่วนบุคคล การเรียนรู้ทางสังคม และการสุ่มแบบควบคุม ฝูงอนุภาคจะค่อยๆ สร้างแผนที่พาเรโตฟรอนต์ทั้งหมด เผยให้เห็นสเปกตรัมที่สมบูรณ์ของการแลกเปลี่ยนที่มีประสิทธิภาพ แทนที่จะเป็นเพียงการประนีประนอมเพียงจุดเดียว

ประวัติศาสตร์

Particle Swarm Optimization ถูกนำเสนอโดย Kennedy และ Eberhart ในปี 1995 โดยได้รับแรงบันดาลใจจากพฤติกรรมทางสังคมของการรวมฝูงนก ส่วนขยายแบบหลายวัตถุประสงค์ที่ได้รับการยอมรับอย่างกว้างขวางตัวแรกคือ MOPSO ซึ่งเสนอโดย Coello Coello, Pulido และ Lechuga ในปี 2004 โดยมีการนำเสนอคลังข้อมูลพาเรโตภายนอกและการเลือกผู้นำโดยใช้ hypercube เป็นหลัก รุ่นต่อๆ มา — รวมถึง OMOPSO, dMOPSO และ SMPSO — ได้ปรับปรุงการจัดการคลังข้อมูล พารามิเตอร์แบบปรับได้ และการจัดการข้อจำกัด ทำให้ MOPSO กลายเป็นอัลกอริทึมหลักในการประมาณค่าพาเรโตฟรอนต์ ควบคู่ไปกับ NSGA-II

ควรใช้เมื่อใด

ใช้ MOPSO เมื่อคุณเผชิญกับปัญหาการหาค่าเหมาะสมที่สุดแบบต่อเนื่อง (continuous optimization problem) ที่มีวัตถุประสงค์ขัดแย้งกันตั้งแต่สองวัตถุประสงค์ขึ้นไป และต้องการประมาณค่าพาเรโตฟรอนต์ทั้งหมด แทนที่จะเป็นคำตอบเดียว วิธีนี้เหมาะอย่างยิ่งสำหรับการออกแบบทางวิศวกรรม ระบบซัพพลายเชน ระบบพลังงาน และการปรับจูนไฮเปอร์พารามิเตอร์ (hyperparameter tuning) ที่การประเมินวัตถุประสงค์มีค่าใช้จ่ายปานกลางและปริภูมิการตัดสินใจเป็นแบบต่อเนื่อง ควรเลือกใช้ NSGA-II หรือ NSGA-III สำหรับปัญหาแบบผสม (combinatorial) หรือแบบจำนวนเต็มผสม (mixed-integer) และควรเลือกใช้วิธีการหาค่าเหมาะสมที่สุดแบบหลายวัตถุประสงค์โดยใช้อนุพันธ์ (gradient-based multi-objective methods) เมื่อวัตถุประสงค์มีความเรียบและสามารถหาอนุพันธ์ได้ ไม่ควรใช้ MOPSO เมื่อจำนวนวัตถุประสงค์เกินห้าถึงเจ็ดวัตถุประสงค์ — ปัญหาที่มีวัตถุประสงค์จำนวนมาก (many-objective problems) ต้องการอัลกอริทึมเฉพาะทาง (เช่น NSGA-III, MOEA/D) และหลีกเลี่ยงการใช้วิธีนี้เมื่อการประเมินฟังก์ชันแต่ละครั้งมีค่าใช้จ่ายสูงมาก (มีเพียงน้อยกว่า 100 การประเมิน) — วิธีการที่ใช้ surrogate model จะเหมาะสมกว่าในสถานการณ์นั้น

ข้อจำกัดและข้อควรพิจารณา

  • ประสิทธิภาพขึ้นอยู่กับ inertia weight (w) และค่าสัมประสิทธิ์ความเร่ง (c1, c2) พารามิเตอร์ที่ปรับไม่ดีอาจทำให้เกิดการลู่เข้าเร็วเกินไปหรือการเคลื่อนที่มากเกินไป
  • การจัดการคลังข้อมูลและการเลือกผู้นำเพิ่มไฮเปอร์พารามิเตอร์ (ขนาดคลังข้อมูล, ตัวชี้วัดความหนาแน่น) ที่ขึ้นอยู่กับปัญหา
  • การรับประกันการลู่เข้าและความหลากหลายเป็นแบบฮิวริสติก ไม่ใช่เชิงคณิตศาสตร์ — พาเรโตฟรอนต์โดยประมาณอาจพลาดบางส่วนของพาเรโตฟรอนต์ที่แท้จริง
  • มีปัญหาในการจัดการวัตถุประสงค์มากกว่าห้าถึงเจ็ดวัตถุประสงค์ เนื่องจากคำสาปแห่งมิติ (curse of dimensionality) ในการคัดเลือกโดยอาศัยการครอบงำ
  • ไม่สามารถนำไปใช้โดยตรงกับปริภูมิการค้นหาแบบไม่ต่อเนื่อง (discrete) หรือแบบผสม (combinatorial) ได้หากไม่มีการเข้ารหัสปัญหาเฉพาะและการจำกัดความเร็ว (velocity clamping) ที่ปรับให้เหมาะ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • ประมาณค่าพาเรโตฟรอนต์ทั้งหมดได้อย่างเป็นธรรมชาติในการทำงานครั้งเดียว ทำให้ผู้ตัดสินใจมีชุดคำตอบการแลกเปลี่ยนที่มีประสิทธิภาพหลากหลาย
  • ไม่ต้องการข้อมูลอนุพันธ์ ทำให้สามารถนำไปใช้กับฟังก์ชันวัตถุประสงค์ที่ไม่สามารถหาอนุพันธ์ได้ มีสัญญาณรบกวน หรือเป็นแบบกล่องดำ (black-box)
  • กลไกการอัปเดตความเร็ว-ตำแหน่งที่เรียบง่ายมีน้ำหนักในการคำนวณน้อยและง่ายต่อการนำไปใช้แบบขนาน
  • คลังข้อมูลพาเรโตภายนอกรักษาคำตอบที่ดีที่สุดที่พบตลอดการค้นหา ป้องกันการสูญเสียจุดที่ไม่ถูกครอบงำที่มีคุณภาพสูง
  • กรอบการทำงานที่ยืดหยุ่นรองรับการจัดการข้อจำกัด (constraint handling) การควบคุมพารามิเตอร์แบบปรับได้ (adaptive parameter control) และการผสมผสานกับการค้นหาเฉพาะที่ (local search)

การประยุกต์ใช้

  • การออกแบบทางวิศวกรรมแบบหลายวัตถุประสงค์: การลดน้ำหนัก ต้นทุน และความเค้นในชิ้นส่วนโครงสร้างและเครื่องจักรกลพร้อมกัน
  • ระบบพลังงาน: การแลกเปลี่ยนที่เหมาะสมที่สุดของพาเรโต ระหว่างต้นทุน ความน่าเชื่อถือ และการปล่อยมลพิษ ในการจัดตารางการทำงานของโครงข่ายไฟฟ้าและการวางแผนพลังงานหมุนเวียน
  • การจัดการซัพพลายเชน: การหาค่าเหมาะสมที่สุดร่วมกันของระดับการบริการ ต้นทุนสินค้าคงคลัง และระยะเวลารอคอย (lead time) ทั่วทั้งเครือข่ายหลายระดับ (multi-echelon networks)
  • การปรับจูนไฮเปอร์พารามิเตอร์การเรียนรู้ของเครื่อง: การสร้างสมดุลระหว่างความแม่นยำของแบบจำลองกับเวลาในการอนุมาน (inference time) หรือปริมาณหน่วยความจำที่ใช้
  • การจัดการทรัพยากรน้ำ: การหาค่าเหมาะสมที่สุดของนโยบายการปล่อยน้ำจากอ่างเก็บน้ำสำหรับวัตถุประสงค์ที่แข่งขันกัน ได้แก่ การผลิตไฟฟ้า การควบคุมน้ำท่วม และการไหลของน้ำเพื่อระบบนิเวศ
  • การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุน: การประมาณค่าขอบเขตที่มีประสิทธิภาพ (efficient frontier) ของผลตอบแทนที่คาดหวังเทียบกับความเสี่ยง สำหรับการจัดสรรสินทรัพย์ทางการเงิน

วิธีการทำงาน

วิธีการทำงาน

1

สร้างประชากรอนุภาค N ตัว ด้วยตำแหน่งและความเร็วแบบสุ่มในปริภูมิการตัดสินใจ (decision space) ประเมินฟังก์ชันวัตถุประสงค์ทั้งหมดสำหรับอนุภาคแต่ละตัว และเติมคลังข้อมูลพาเรโตภายนอกด้วยคำตอบเริ่มต้นทั้งหมดที่ไม่ถูกครอบงำ กำหนดค่า personal best (pbest) ของอนุภาคแต่ละตัวให้เท่ากับตำแหน่งเริ่มต้น

2

คำนวณค่าฟังก์ชันวัตถุประสงค์ทั้งหมดสำหรับอนุภาคทุกตัวในฝูงปัจจุบัน ใช้การเปรียบเทียบการครอบงำ: คำตอบ x ครอบงำ y ถ้า x ไม่แย่กว่าในทุกวัตถุประสงค์ และดีกว่าอย่างน้อยหนึ่งวัตถุประสงค์ อัปเดต pbest ของอนุภาคแต่ละตัว หากตำแหน่งใหม่ครอบงำค่า personal best ที่เก็บไว้ หรือไม่ถูกครอบงำเมื่อเทียบกับค่าดังกล่าว

3

แทรกคำตอบใหม่ทั้งหมดที่ไม่ถูกครอบงำเข้าไปในคลังข้อมูลภายนอก ลบสมาชิกคลังข้อมูลที่ถูกครอบงำโดยคำตอบใหม่ หากคลังข้อมูลเกินขีดจำกัดความจุ ให้ใช้กลยุทธ์การตัดแต่งตามความหนาแน่น (เช่น hypercube crowding หรือ nearest-neighbour distance) เพื่อรักษาความหลากหลายทั่วทั้งการประมาณค่าพาเรโตฟรอนต์

4

สำหรับอนุภาคแต่ละตัว เลือกผู้นำที่ดีที่สุดระดับส่วนกลาง (global best leader - gbest) จากคลังข้อมูลภายนอก ผู้นำมักจะถูกเลือกจากบริเวณคลังข้อมูลที่มีความหนาแน่นน้อยกว่า โดยใช้กลไกการแข่งขัน (tournament) หรือรูเล็ต (roulette) ตามระยะห่างความหนาแน่น (crowding distance) เพื่อให้แน่ใจว่าฝูงอนุภาคจะถูกดึงดูดไปยังส่วนของพาเรโตฟรอนต์ที่ยังไม่ถูกสำรวจ แทนที่จะลู่เข้าสู่บริเวณเดียวเร็วเกินไป

5

อัปเดตความเร็วและตำแหน่งสำหรับอนุภาคแต่ละตัวโดยใช้กฎการอัปเดตของ PSO: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x) โดยที่ w คือ inertia weight ที่ควบคุมสมดุลระหว่างการสำรวจ/การใช้ประโยชน์ (exploration/exploitation), c1 และ c2 คือค่าสัมประสิทธิ์ความเร่งด้านความรู้ (cognitive) และสังคม (social), และ r1, r2 คือตัวเลขสุ่มแบบสม่ำเสมอ (uniform random numbers) ใช้การจัดการขอบเขต (boundary handling) เพื่อให้อนุภาคอยู่ในปริภูมิการตัดสินใจที่เป็นไปได้

สูตร
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)
6

ทำซ้ำขั้นตอน ประเมิน–อัปเดตคลังข้อมูล–เลือกผู้นำ–เคลื่อนที่อนุภาค จนกว่าจะถึงเกณฑ์การหยุด (จำนวนรอบสูงสุด, จำนวนการประเมินฟังก์ชันสูงสุด, หรือพาเรโตฟรอนต์หยุดนิ่ง) ส่งคืนคลังข้อมูลภายนอกสุดท้ายเป็นเซตที่เหมาะสมที่สุดของพาเรโตโดยประมาณ (approximated Pareto-optimal set) ซึ่งผู้ตัดสินใจจะตรวจสอบเพื่อเลือกคำตอบการแลกเปลี่ยนที่ต้องการ

ข้อผิดพลาดที่พบบ่อย

  • การตั้งความจุของคลังข้อมูลเล็กเกินไปทำให้เกิดการตัดแต่งที่รุนแรงซึ่งทำลายความหลากหลายของพาเรโตฟรอนต์ การตั้งค่าใหญ่เกินไปทำให้การเลือกผู้นำช้าลงและเพิ่มต้นทุนหน่วยความจำ
  • การใช้ผู้นำส่วนกลาง (global leader)เพียงตัวเดียวสำหรับทั้งฝูงนำไปสู่การลู่เข้าเร็วเกินไป — ควรใช้กลไกการเลือกผู้นำที่คำนึงถึงความหลากหลายเสมอ (เช่น tournament ตาม crowding distance)
  • การละเลยการจัดการขอบเขตทำให้อนุภาคหลุดออกจากปริภูมิที่เป็นไปได้ ทำให้เกิดคำตอบที่เป็นไปไม่ได้ (infeasible)ซึ่งปนเปื้อนคลังข้อมูล
  • การรายงานเฉพาะคลังข้อมูลสุดท้ายโดยไม่มีตัวชี้วัดการลู่เข้าและความหลากหลาย (เช่น hypervolume indicator, generational distance) ทำให้ไม่สามารถเปรียบเทียบผลลัพธ์ระหว่างการทำงานหรือวิธีการต่างๆ ได้
  • การมอง MOPSO เป็นตัวหาค่าเหมาะสมที่สุดแบบกล่องดำโดยไม่ได้ตรวจสอบว่าวัตถุประสงค์ของปัญหานั้นขัดแย้งกันจริงหรือไม่ — หากวัตถุประสงค์สอดคล้องกัน การใช้ PSO แบบวัตถุประสงค์เดียว หรือ gradient descent ก็เพียงพอแล้ว

คำถามที่พบบ่อย

MOPSO แตกต่างจาก NSGA-II อย่างไร?

ทั้งสองวิธีประมาณค่าพาเรโตฟรอนต์โดยใช้ประชากรของคำตอบและการคัดเลือกโดยอาศัยการครอบงำ แต่มีความแตกต่างกันในกลไก NSGA-II ใช้ตัวดำเนินการ crossover และ mutation กับประชากรผสมระหว่างพ่อแม่และลูกหลาน พร้อมกับการจัดเรียงตาม crowding distance ส่วน MOPSO ใช้การเคลื่อนที่ของอนุภาคโดยอาศัยความเร็วที่นำโดยผู้นำส่วนบุคคลและผู้นำจากคลังข้อมูล โดยทั่วไป MOPSO จะเร็วกว่าต่อรอบการทำงานสำหรับปริภูมิแบบต่อเนื่อง ในขณะที่ NSGA-II เหมาะสมกับปัญหาแบบ permutation และ combinatorial มากกว่า

ควรใช้ขนาดคลังข้อมูลเท่าใด?

ค่าเริ่มต้นทั่วไปคือ 100–200 คำตอบสำหรับปัญหาที่มีสองหรือสามวัตถุประสงค์ คลังข้อมูลที่ใหญ่ขึ้นช่วยเพิ่มความครอบคลุมของพาเรโตฟรอนต์ แต่ทำให้การเลือกผู้นำช้าลง สำหรับปัญหาที่มีสี่วัตถุประสงค์ขึ้นไป ขนาดคลังข้อมูลควรปรับตามความซับซ้อนที่คาดหวังของพาเรโตฟรอนต์ กลไกการจัดการคลังข้อมูลแบบปรับได้สามารถช่วยได้

MOPSO สามารถจัดการกับข้อจำกัดได้หรือไม่?

ได้ โดยใช้ฟังก์ชันการลงโทษ (penalty functions) กฎความเป็นไปได้ (feasibility rules - ให้ความสำคัญกับคำตอบที่เป็นไปได้มากกว่าคำตอบที่เป็นไปไม่ได้ในการเปรียบเทียบการครอบงำ) หรือตัวดำเนินการซ่อมแซม (repair operators) สูตรดั้งเดิมของ Coello Coello มีกลไกการจัดการข้อจำกัดอย่างง่ายโดยอาศัยการแข่งขันเพื่อความเป็นไปได้ (feasibility tournaments)

MOPSO สามารถจัดการกับฟังก์ชันวัตถุประสงค์ได้กี่ฟังก์ชันอย่างมีประสิทธิภาพ?

MOPSO ทำงานได้ดีสำหรับวัตถุประสงค์สองถึงสี่วัตถุประสงค์ เมื่อเกินห้าถึงเจ็ดวัตถุประสงค์ แรงกดดันจากการครอบงำจะลดลงอย่างมาก — คำตอบเกือบทั้งหมดจะกลายเป็นคำตอบที่ไม่ถูกครอบงำซึ่งกันและกัน — และอัลกอริทึมหาค่าที่เหมาะสมที่สุดสำหรับวัตถุประสงค์จำนวนมาก (many-objective optimizers) เช่น NSGA-III, MOEA/D หรือวิธีการแบบแบ่งส่วน (decomposition-based methods) จะทำงานได้ดีกว่า MOPSO มาตรฐาน

ควรใช้ตัวชี้วัดใดในการประเมินผลลัพธ์ของ MOPSO?

ควรรายงาน hypervolume indicator (วัดปริมาตรของปริภูมิวัตถุประสงค์ที่ถูกครอบงำโดยฟรอนต์โดยประมาณ — ยิ่งมากยิ่งดี) generational distance (ความใกล้เคียงกับพาเรโตฟรอนต์อ้างอิง) และตัวชี้วัด spread หรือ delta (ความสม่ำเสมอของการกระจาย) จำเป็นต้องมีการทำงานอิสระหลายครั้งพร้อมการเปรียบเทียบทางสถิติสำหรับการทดสอบประสิทธิภาพที่น่าเชื่อถือ

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว