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

การหาค่าเหมาะที่สุดด้วยอนุภาคฝูงผึ้งแบบทนทาน — อัลกอริทึมเหนือธรรมชาติแบบฝูงผึ้งที่คำนึงถึงความไม่แน่นอน

ผู้เสนอ
Kennedy, J. & Eberhart, R. C. (PSO); robustness extensions by multiple authors, 2000s
ปี
2000s
ประเภท
Metaheuristic — robust swarm-based optimizer
กลุ่มวิธี
Simulation / optimization

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

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

ใช้ทำอะไร?

การหาค่าเหมาะที่สุดด้วยอนุภาคฝูงผึ้งแบบทนทาน (Robust PSO) เป็นการขยายอัลกอริทึมเหนือธรรมชาติ PSO แบบดั้งเดิม เพื่อพิจารณาความไม่แน่นอนในฟังก์ชันวัตถุประสงค์ ข้อจำกัด หรือตัวแปรตัดสินใจอย่างชัดเจน แทนที่จะหาค่าเหมาะที่สุดตามค่าปกติเพียงค่าเดียว คำตอบที่เป็นไปได้แต่ละรายการจะถูกประเมินตามชุดของสถานการณ์ความไม่แน่นอน และการวัดความเหมาะสมจะพิจารณาจากเกณฑ์ความทนทาน เช่น ประสิทธิภาพในกรณีที่เลวร้ายที่สุด หรือค่าคาดหวัง ซึ่งจะให้คำตอบที่ยังคงใกล้เคียงค่าเหมาะที่สุดแม้ว่าเงื่อนไขจะเบี่ยงเบนไปจากข้อสมมติฐานปกติ

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

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

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

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

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

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

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

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

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

จุดแข็ง

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

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

  • การออกแบบทางวิศวกรรมภายใต้ความคลาดเคลื่อนในการผลิต (เช่น การหาค่าเหมาะที่สุดเชิงโครงสร้าง การออกแบบเสาอากาศ)
  • การหาค่าเหมาะที่สุดของห่วงโซ่อุปทานและโลจิสติกส์ด้วยความไม่แน่นอนของอุปสงค์หรือระยะเวลารอคอย
  • การหาค่าเหมาะที่สุดของพารามิเตอร์เหนือสุดในแมชชีนเลิร์นนิงที่การประเมินมีความผันผวน
  • การวางแผนระบบพลังงานภายใต้ความไม่แน่นอนของการผลิตพลังงานหมุนเวียน
  • การหาค่าเหมาะที่สุดของพอร์ตการลงทุนทางการเงินด้วยความไม่แน่นอนของผลตอบแทนสินทรัพย์
  • การปรับจูนตัวควบคุมแบบทนทานในการควบคุมกระบวนการด้วยความไม่แน่นอนของแบบจำลอง

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

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

1

เริ่มต้นฝูงผึ้งที่มีอนุภาค N ตัว โดยแต่ละตัวแทนเวกเตอร์คำตอบที่เป็นไปได้ x ในปริภูมิการตัดสินใจ กำหนดตำแหน่งและความเร็วแบบสุ่ม กำหนดชุดความไม่แน่นอน U เพื่อจับความผันแปรของพารามิเตอร์ สัญญาณรบกวนในการประเมินวัตถุประสงค์ หรือการรบกวนในข้อจำกัด

2

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

3

ประเมินค่าความเหมาะสมแบบทนทาน f_robust(x) โดยการรวมค่าวัตถุประสงค์ตามการรับรู้ความไม่แน่นอนใน U(x) สำหรับความทนทานแบบ minimax: f_robust(x) = max_{u in U} f(x, u) สำหรับความทนทานแบบคาดหวัง: f_robust(x) = E_u[f(x, u)] ซึ่งประมาณโดยการหาค่าเฉลี่ยจากสถานการณ์ที่สุ่มตัวอย่าง

4

ปรับปรุงความเร็วและตำแหน่งของอนุภาคแต่ละตัวโดยใช้กฎการปรับปรุง PSO มาตรฐาน แต่ใช้ f_robust เป็นสัญญาณวัดความเหมาะสม ตำแหน่งที่ดีที่สุดส่วนบุคคล (pbest) และตำแหน่งที่ดีที่สุดโดยรวม (gbest) จะถูกติดตามเทียบกับค่าความเหมาะสมแบบทนทาน เพื่อให้แน่ใจว่าฝูงผึ้งเคลื่อนที่ไปยังบริเวณที่มีค่าเหมาะสมแบบทนทานของปริภูมิการค้นหา

5

ทำซ้ำขั้นตอนการประเมินแบบทนทานและการปรับปรุงฝูงผึ้งจนกว่าจะถึงเกณฑ์การหยุด — จำนวนรอบสูงสุด ระดับความเหมาะสมคงที่ หรือค่าความคลาดเคลื่อนในการลู่เข้า ส่งคืนตำแหน่งที่ดีที่สุดโดยรวม gbest เป็นคำตอบที่เหมาะที่สุดแบบทนทาน พร้อมกับโปรไฟล์ความทนทานตามสถานการณ์

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

  • การใช้สถานการณ์น้อยเกินไปเพื่อประมาณชุดความไม่แน่นอนนำไปสู่การประเมินความทนทานที่มองโลกในแง่ดีเกินไปซึ่งไม่เป็นจริงในการปฏิบัติ
  • การสับสนระหว่าง PSO แบบสุ่ม (ซึ่งสุ่มกลไกการปรับปรุงฝูงผึ้ง) กับ Robust PSO (ซึ่งสุ่มการประเมินวัตถุประสงค์) — ทั้งสองจัดการกับแหล่งที่มาของความสุ่มที่แตกต่างกัน
  • การเลือกความทนทานแบบ minimax เมื่อกรณีที่เลวร้ายที่สุดเกิดขึ้นได้ยากมาก อาจนำไปสู่คำตอบที่อนุรักษ์นิยมเกินไป พิจารณาเกณฑ์ค่าคาดหวังหรือควอนไทล์สำหรับการตั้งค่าที่เสี่ยงน้อยกว่า
  • การละเลยการตรวจสอบคำตอบแบบทนทานนอกกลุ่มตัวอย่าง: คำตอบที่ทนทานในกลุ่มตัวอย่างอาจยังคงล้มเหลวภายใต้การเปลี่ยนแปลงการแจกแจง

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

ความแตกต่างระหว่าง Robust PSO และ Stochastic PSO คืออะไร?

Stochastic PSO แนะนำความสุ่มเข้าไปในกลไกการปรับปรุงอนุภาคเอง (ความเร็ว ตำแหน่ง หรือโทโพโลยี) ในขณะที่ Robust PSO จัดการกับความไม่แน่นอนในฟังก์ชันวัตถุประสงค์หรือพารามิเตอร์ของปัญหาโดยเฉพาะ Robust PSO ประเมินคำตอบแต่ละรายการผ่านหลายสถานการณ์เพื่อตัดสินความทนทาน ในขณะที่ stochastic PSO เป็นเทคนิคหลักในการปรับปรุงการสำรวจปริภูมิการค้นหา

ต้องใช้สถานการณ์กี่สถานการณ์สำหรับการประเมินแบบทนทานที่เชื่อถือได้?

ขึ้นอยู่กับมิติของปริภูมิความไม่แน่นอนและความแม่นยำที่ต้องการของการประมาณค่าความทนทาน ในทางปฏิบัติ การสุ่มตัวอย่างสถานการณ์ 30–200 ครั้งต่อการประเมินอนุภาคเป็นเรื่องปกติ แต่ปัญหาที่ต้องใช้การคำนวณสูงอาจใช้จำนวนน้อยกว่า การสุ่มตัวอย่างแบบ Latin hypercube หรือลำดับแบบกึ่งสุ่มสามารถปรับปรุงการครอบคลุมด้วยจำนวนตัวอย่างที่น้อยลงเมื่อเทียบกับการสุ่มแบบบริสุทธิ์

Robust PSO สามารถจัดการกับปัญหาหลายวัตถุประสงค์ได้หรือไม่?

ได้ Robust PSO สามารถรวมกับกรอบการทำงานของ PSO หลายวัตถุประสงค์ (เช่น MOPSO) เพื่อค้นหา Pareto front ของคำตอบที่ไม่ถูกครอบงำแบบทนทาน จากนั้นแต่ละวัตถุประสงค์จะถูกประเมินแบบทนทาน และการครอบงำของ Pareto จะถูกประเมินตามค่าความเหมาะสมแบบทนทาน

Robust PSO รับประกันว่าจะหาค่าเหมาะที่สุดทั่วโลกแบบทนทานได้หรือไม่?

ไม่ เช่นเดียวกับอัลกอริทึมเหนือธรรมชาติทั้งหมด Robust PSO ไม่มีการรับประกันทางทฤษฎีเกี่ยวกับค่าเหมาะที่สุดทั่วโลก เป็นวิธีการเชิงประจักษ์ที่ทำงานได้ดีในปัญหาที่ซับซ้อน สำหรับปัญหาที่ต้องการการรับประกันที่พิสูจน์ได้ ควรพิจารณาวิธีการหาค่าเหมาะที่สุดแบบทนทานอย่างเป็นทางการด้วยชุดความไม่แน่นอนที่เป็นรูปนูน

เมื่อใดที่ควรเลือก Robust PSO แทน PSO มาตรฐาน?

ควรเลือก Robust PSO เมื่อคำตอบที่ใช้งานจะเผชิญกับความผันผวนในโลกแห่งความเป็นจริงที่ไม่สามารถจับได้ด้วยการประเมินวัตถุประสงค์ตามค่าปกติเพียงค่าเดียว และเมื่อต้นทุนของคำตอบที่เปราะบาง (คำตอบที่เสื่อมสภาพอย่างรุนแรงภายใต้การเปลี่ยนแปลงพารามิเตอร์เล็กน้อย) มีค่ามากกว่าต้นทุนการคำนวณเพิ่มเติมของการประเมินแบบทนทาน

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

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

  1. Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm Intelligence. Morgan Kaufmann Publishers.

    ISBN: 9781558605954
    คัดลอกแล้ว
  2. Dellino, G., Kleijnen, J. P. C., & Meloni, C. (2010). Robust optimization in simulation: Taguchi and Response Surface Methodology. International Journal of Production Economics, 125(1), 52–59.

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