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

Stochastic Particle Swarm Optimization — การค้นหาทั่วโลกแบบสุ่มที่อิงฝูง

ผู้เสนอ
Kennedy, J. and Eberhart, R. (base PSO); stochastic extensions by Clerc, Kennedy and community
ปี
1995–2002
ประเภท
Metaheuristic optimization — stochastic swarm intelligence
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

Stochastic Particle Swarm Optimization (Stochastic PSO) เป็นเมตาฮิวริสติกแบบสวอร์มอัจฉริยะที่ขยายกรอบการทำงานของ PSO มาตรฐาน โดยรวมเอาองค์ประกอบสุ่มที่ชัดเจน เช่น น้ำหนักความเฉื่อยแบบสุ่ม การรีเซ็ตความเร็วแบบความน่าจะเป็น หรือการฉีดสัญญาณรบกวน เพื่อหลีกหนีจากจุดเหมาะสมที่สุดเฉพาะที่และรักษาความหลากหลายของประชากรตลอดการค้นหา มีการประยุกต์ใช้อย่างกว้างขวางกับปัญหาการหาค่าเหมาะสมที่สุดแบบต่อเนื่อง แบบผสม และแบบมีสัญญาณรบกวน ในสาขาวิศวกรรม การวิจัยดำเนินงาน และการออกแบบที่อิงการจำลอง

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

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

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

Particle Swarm Optimization ได้รับการแนะนำโดย Kennedy และ Eberhart ในปี 1995 โดยได้รับแรงบันดาลใจจากพฤติกรรมทางสังคมของฝูงนกและฝูงปลา Clerc และ Kennedy (2002) ได้กำหนดรูปแบบสัมประสิทธิ์การหดตัวและวิเคราะห์ความเสถียร ซึ่งวางรากฐานทางทฤษฎี ส่วนขยายแบบสุ่ม เช่น น้ำหนักความเฉื่อยแบบสุ่ม ความเร็วที่เพิ่มสัญญาณรบกวน การรีเซ็ตแบบความน่าจะเป็น ได้เกิดขึ้นตลอดช่วงปลายทศวรรษ 1990 และ 2000 เมื่อนักวิจัยระบุว่าการลู่เข้าก่อนเวลาอันควรเป็นจุดอ่อนหลักในทางปฏิบัติของอัลกอริทึมดั้งเดิม

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

ใช้ Stochastic PSO เมื่อพื้นที่การค้นหามีหลายโหมด มีสัญญาณรบกวน หรือมีมิติสูง และ PSO มาตรฐานมีแนวโน้มที่จะลู่เข้าก่อนเวลาอันควร เหมาะอย่างยิ่งสำหรับการหาค่าเหมาะสมที่สุดที่อิงการจำลอง ซึ่งฟังก์ชันวัตถุประสงค์เป็นแบบสุ่มหรือมีค่าใช้จ่ายในการประเมินสูง และสำหรับปัญหาการออกแบบทางวิศวกรรมที่มีจุดต่ำสุดเฉพาะที่จำนวนมาก ควรเลือกใช้ Stochastic PSO เหนือรูปแบบเชิงกำหนดเมื่อการรักษาความหลากหลายมีความสำคัญอย่างยิ่ง ห้ามใช้เมื่อปัญหาเป็นแบบนูน มีวัตถุประสงค์แบบโหมดเดียวและมีการประเมินที่ราคาถูก — วิธีการที่อิงการไล่ระดับหรือวิธีการที่แม่นยำจะเร็วกว่าและแม่นยำกว่า นอกจากนี้ ควรหลีกเลี่ยงเมื่อความสามารถในการทำซ้ำของการรันทุกครั้งเป็นสิ่งจำเป็นโดยไม่มีนโยบายการกำหนด seed สุ่มที่แน่นอน เนื่องจากสัญญาณรบกวนแบบสุ่มทำให้การทำซ้ำที่แม่นยำซับซ้อนขึ้น

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

  • ความไวของไฮเปอร์พารามิเตอร์: พารามิเตอร์สัญญาณรบกวนและการแจกแจงน้ำหนักความเฉื่อยส่งผลกระทบอย่างมากต่อความเร็วในการลู่เข้าและคุณภาพของผลลัพธ์
  • ไม่มีการรับประกันทางทฤษฎีว่าจะพบค่าเหมาะสมที่สุดทั่วโลกในเวลาจำกัดสำหรับปัญหาที่ไม่เป็นนูนโดยพลการ
  • การเริ่มต้นใหม่แบบสุ่มอาจทิ้งอนุภาคที่มีแนวโน้มดีออกไป ซึ่งบางครั้งทำให้สิ้นเปลืองการประเมินความเหมาะสม
  • ประสิทธิภาพลดลงในพื้นที่ที่มีมิติสูงมาก (ปัญหาของมิติ) เมื่อเทียบกับวิธีการที่เฉพาะเจาะจงกับปัญหา
  • อาจต้องมีการรันหลายครั้งเพื่อสร้างความมั่นใจในคุณภาพของผลลัพธ์ ซึ่งเพิ่มต้นทุนการคำนวณทั้งหมด

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

จุดแข็ง

  • รักษาความหลากหลายของประชากรผ่านความเป็นสุ่มที่ควบคุมได้ ซึ่งช่วยลดการลู่เข้าก่อนเวลาอันควรได้อย่างมากเมื่อเทียบกับ PSO มาตรฐาน
  • ไม่ต้องการข้อมูลการไล่ระดับและจัดการกับฟังก์ชันวัตถุประสงค์ที่ไม่เรียบ ไม่ต่อเนื่อง หรือแบบกล่องดำได้
  • ขนานได้ง่าย: การประเมินอนุภาคแต่ละตัวเป็นอิสระภายในหนึ่งรอบ
  • ยืดหยุ่น: ระดับความเป็นสุ่ม (ระดับสัญญาณรบกวน, การแจกแจงความเฉื่อย) สามารถปรับแต่งเพื่อสร้างสมดุลระหว่างการสำรวจและการใช้ประโยชน์
  • จัดการกับฟังก์ชันความเหมาะสมแบบสุ่มหรือที่อิงการจำลองได้อย่างเป็นธรรมชาติ ซึ่งการประเมินมีสัญญาณรบกวนโดยธรรมชาติ
  • แนวคิดเรียบง่ายพร้อมไฮเปอร์พารามิเตอร์ไม่กี่ตัว (ขนาดฝูง N, สัมประสิทธิ์ความรู้ความเข้าใจ c1, สัมประสิทธิ์ทางสังคม c2, และพารามิเตอร์สัญญาณรบกวน)

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

  • การหาค่าเหมาะสมที่สุดในการออกแบบทางวิศวกรรม: การปรับแต่งรูปทรงอากาศพลศาสตร์, การออกแบบอาร์เรย์เสาอากาศ, การหาค่าเหมาะสมที่สุดเชิงโครงสร้างภายใต้ความไม่แน่นอน
  • การฝึกโครงข่ายประสาทเทียม: การหาค่าเหมาะสมที่สุดของน้ำหนักสำหรับโครงข่ายแบบฟีดฟอร์เวิร์ดและแบบวนซ้ำบนชุดข้อมูลที่มีสัญญาณรบกวน
  • ห่วงโซ่อุปทานและการจัดตารางเวลา: การจัดตารางเวลาการผลิตแบบสุ่ม, การหาค่าเหมาะสมที่สุดของสินค้าคงคลังภายใต้ความไม่แน่นอนของอุปสงค์
  • การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนทางการเงิน: การเพิ่มผลตอบแทนที่ปรับความเสี่ยงด้วยแบบจำลองตลาดแบบสุ่ม
  • การหาค่าเหมาะสมที่สุดที่อิงการจำลอง: การปรับเทียบแบบจำลองที่อิงตัวแทนหรือแบบจำลองพลวัตของระบบให้เข้ากับข้อมูลเชิงประจักษ์
  • การปรับแต่งไฮเปอร์พารามิเตอร์สำหรับไปป์ไลน์การเรียนรู้ของเครื่อง ซึ่งพื้นผิวการสูญเสียจากการตรวจสอบความถูกต้องมีสัญญาณรบกวน

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

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

1

เริ่มต้นฝูงอนุภาค N ตัว ด้วยตำแหน่ง x_i และความเร็ว v_i ที่สุ่มอย่างสม่ำเสมอภายในพื้นที่ค้นหาที่เป็นไปได้ ประเมินฟังก์ชันวัตถุประสงค์ f(x_i) สำหรับแต่ละอนุภาค และกำหนด p_i = x_i เป็นค่าที่ดีที่สุดส่วนบุคคล และ g = argmin f(x_i) เป็นค่าที่ดีที่สุดทั่วโลก

2

อัปเดตความเร็วของแต่ละอนุภาคโดยใช้กฎสุ่ม: v_i(t+1) = omega * v_i(t) + c1*r1*(p_i - x_i) + c2*r2*(g - x_i) โดยที่ r1, r2 ~ Uniform(0,1) เป็นค่าสุ่มใหม่ในแต่ละรอบ ใน Stochastic PSO ตัว omega เองอาจถูกสุ่มจากฟังก์ชันการแจกแจง (เช่น Uniform(0.4, 0.9)) หรือมีการเพิ่มเทอมสัญญาณรบกวนแบบเกาส์เซียน epsilon ~ N(0, sigma^2) เพื่อรักษาความหลากหลาย

สูตร
v_i(t+1) = \omega v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))
3

ย้ายแต่ละอนุภาคไปยังตำแหน่งผู้สมัครใหม่: x_i(t+1) = x_i(t) + v_i(t+1) ใช้การจัดการขอบเขต (การสะท้อน, การหนีบ, หรือการห่อแบบทอรัส) เพื่อให้อนุภาคอยู่ในโดเมนที่ใช้งานได้จริง

สูตร
x_i(t+1) = x_i(t) + v_i(t+1)
4

ใช้กลไกสุ่มเพิ่มเติมขึ้นอยู่กับรูปแบบย่อย: (a) น้ำหนักความเฉื่อยแบบสุ่มที่สุ่มในแต่ละรอบ, (b) การรบกวนแบบเกาส์เซียนของค่าที่ดีที่สุดส่วนบุคคลเพื่อหลีกหนีจากแอ่งดึงดูดเฉพาะที่, หรือ (c) การเริ่มต้นใหม่แบบสุ่มของอนุภาคที่มีอัตราการปรับปรุงต่ำกว่าเกณฑ์ เพื่อฟื้นฟูความสามารถในการสำรวจ

5

ประเมิน f(x_i(t+1)) สำหรับอนุภาคทั้งหมด; อัปเดตค่าที่ดีที่สุดส่วนบุคคลและค่าที่ดีที่สุดทั่วโลก ทำซ้ำการอัปเดตความเร็วผ่านการตรวจสอบการลู่เข้าเป็นเวลา T รอบ หรือจนกว่าจะถึงเกณฑ์การหยุด (เช่น การปรับปรุงความเหมาะสม < epsilon ใน K รอบติดต่อกัน) ส่งคืนค่าที่ดีที่สุดทั่วโลก g เป็นผลลัพธ์

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

  • การตั้งค่าความแปรปรวนของสัญญาณรบกวนสูงเกินไปจะเปลี่ยนอัลกอริทึมเป็นการค้นหาแบบสุ่มเกือบทั้งหมด; ต่ำเกินไปจะไม่ให้ประโยชน์ใดๆ เหนือ PSO มาตรฐาน — ควรปรับเทียบกับปัญหาการตรวจสอบความถูกต้องก่อน
  • การละเลยการจัดการขอบเขตในขั้นตอนการรบกวนแบบสุ่มอาจทำให้อนุภาคหลุดออกจากบริเวณที่ใช้งานได้จริง ซึ่งทำให้เกิดผลลัพธ์ที่ไม่ถูกต้องหรือไม่สมเหตุสมผล
  • การเปรียบเทียบ Stochastic PSO กับวิธีการพื้นฐานเชิงกำหนดในการรันครั้งเดียวเป็นการเข้าใจผิด; ควรรายงานสถิติ (ค่าเฉลี่ย, ส่วนเบี่ยงเบนมาตรฐาน) จากการรันอิสระหลายครั้งเสมอ
  • การใช้ seed สุ่มที่คงที่สำหรับอนุภาคทั้งหมดจะลบประโยชน์ด้านความหลากหลายออกไป — ตรวจสอบให้แน่ใจว่าอนุภาคแต่ละตัวใช้กระแสสุ่มที่เป็นอิสระ

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

Stochastic PSO แตกต่างจาก PSO มาตรฐานอย่างไร?

PSO มาตรฐานใช้ค่าสัมประสิทธิ์สุ่ม r1 และ r2 ที่สุ่มอย่างสม่ำเสมอในแต่ละรอบอยู่แล้ว Stochastic PSO จงใจจัดโครงสร้างหรือขยายความเป็นสุ่มนี้ — ตัวอย่างเช่น โดยการสุ่มน้ำหนักความเฉื่อย omega จากการแจกแจงความน่าจะเป็นในแต่ละรอบ การเพิ่มสัญญาณรบกวนแบบเกาส์เซียนให้กับตำแหน่งอนุภาค หรือการเริ่มต้นใหม่แบบความน่าจะเป็นของอนุภาคที่หยุดนิ่ง — เพื่อให้การรักษาความหลากหลายแข็งแกร่งขึ้น

ฉันควรใช้อนุภาคกี่ตัว?

จุดเริ่มต้นทั่วไปคือ 20–50 อนุภาคสำหรับปัญหาที่มีมิติสูงสุดประมาณ 30 มิติ ฝูงขนาดใหญ่ขึ้น (50–200) ช่วยปรับปรุงการครอบคลุมในพื้นที่ที่มีมิติสูงหรือมีหลายโหมดอย่างมาก โดยมีค่าใช้จ่ายในการประเมินฟังก์ชันต่อรอบมากขึ้น

ฉันจะเลือกความแปรปรวนของสัญญาณรบกวนสำหรับการรบกวนแบบสุ่มได้อย่างไร?

ปรับเทียบกับตัวอย่างที่เป็นตัวแทนของประเภทปัญหาของคุณ หลักการปฏิบัติคือการตั้งค่าส่วนเบี่ยงเบนมาตรฐานของสัญญาณรบกวนแบบเพิ่มให้ประมาณ 1–5% ของความกว้างของพื้นที่ค้นหาต่อมิติ จากนั้นปรับแต่งตามการวินิจฉัยการลู่เข้า — ตัวชี้วัดความหลากหลายไม่ควรลดลงจนเกือบเป็นศูนย์ก่อนที่งบประมาณจะหมดลง

ฉันควรเลือก Stochastic PSO เหนือ Differential Evolution หรือ Genetic Algorithms เมื่อใด?

Stochastic PSO มีแนวโน้มที่จะลู่เข้าเร็วกว่าในปัญหาแบบต่อเนื่องที่มีมิติปานกลางถึงต่ำ และใช้งานง่ายมาก Differential Evolution และ Genetic Algorithms มักจะจัดการโครงสร้างแบบผสมผสานหรือแบบไม่ต่อเนื่องได้ดีกว่า หากปัญหาของคุณเป็นแบบต่อเนื่องและมีหลายโหมดอย่างแท้จริง Stochastic PSO เป็นตัวเลือกแรกที่แข็งแกร่ง

Stochastic PSO เหมาะสำหรับปัญหาหลายวัตถุประสงค์หรือไม่?

รูปแบบวัตถุประสงค์เดียวที่อธิบายไว้ที่นี่ไม่ได้ออกแบบมาโดยตรงสำหรับปัญหาหลายวัตถุประสงค์ สำหรับปัญหาเหล่านั้น ให้ใช้ Multi-Objective PSO (MOPSO) หรือ NSGA-II ซึ่งรักษาคลังข้อมูลของผลลัพธ์ที่ไม่ถูกครอบงำแบบ Pareto ไว้อย่างชัดเจน

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

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

  1. Kennedy, J., Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4, pp. 1942-1948. IEEE.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Clerc, M., Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.

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