การหาค่าเหมาะที่สุดด้วยอนุภาคฝูงผึ้งแบบทนทาน — อัลกอริทึมเหนือธรรมชาติแบบฝูงผึ้งที่คำนึงถึงความไม่แน่นอน
- ผู้เสนอ
- 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
- สามารถประมวลผลแบบขนานได้: การประเมินสถานการณ์สำหรับอนุภาคแต่ละตัวสามารถกระจายไปยังโหนดคอมพิวเตอร์ได้
การประยุกต์ใช้
- การออกแบบทางวิศวกรรมภายใต้ความคลาดเคลื่อนในการผลิต (เช่น การหาค่าเหมาะที่สุดเชิงโครงสร้าง การออกแบบเสาอากาศ)
- การหาค่าเหมาะที่สุดของห่วงโซ่อุปทานและโลจิสติกส์ด้วยความไม่แน่นอนของอุปสงค์หรือระยะเวลารอคอย
- การหาค่าเหมาะที่สุดของพารามิเตอร์เหนือสุดในแมชชีนเลิร์นนิงที่การประเมินมีความผันผวน
- การวางแผนระบบพลังงานภายใต้ความไม่แน่นอนของการผลิตพลังงานหมุนเวียน
- การหาค่าเหมาะที่สุดของพอร์ตการลงทุนทางการเงินด้วยความไม่แน่นอนของผลตอบแทนสินทรัพย์
- การปรับจูนตัวควบคุมแบบทนทานในการควบคุมกระบวนการด้วยความไม่แน่นอนของแบบจำลอง
วิธีการทำงาน
วิธีการทำงาน
เริ่มต้นฝูงผึ้งที่มีอนุภาค N ตัว โดยแต่ละตัวแทนเวกเตอร์คำตอบที่เป็นไปได้ x ในปริภูมิการตัดสินใจ กำหนดตำแหน่งและความเร็วแบบสุ่ม กำหนดชุดความไม่แน่นอน U เพื่อจับความผันแปรของพารามิเตอร์ สัญญาณรบกวนในการประเมินวัตถุประสงค์ หรือการรบกวนในข้อจำกัด
สำหรับตำแหน่งอนุภาค x แต่ละตำแหน่ง ให้สร้างหรือสุ่มตัวอย่างชุดการรับรู้ความไม่แน่นอน U(x) — ซึ่งอาจเป็นชุดสถานการณ์จำกัด การแจกแจงของการรบกวนวัตถุประสงค์ หรือบริเวณใกล้เคียงในปริภูมิพารามิเตอร์ เลือกเกณฑ์ความทนทาน: กรณีที่เลวร้ายที่สุด (minimax) ค่าคาดหวัง หรือการวัดตามควอนไทล์
ประเมินค่าความเหมาะสมแบบทนทาน f_robust(x) โดยการรวมค่าวัตถุประสงค์ตามการรับรู้ความไม่แน่นอนใน U(x) สำหรับความทนทานแบบ minimax: f_robust(x) = max_{u in U} f(x, u) สำหรับความทนทานแบบคาดหวัง: f_robust(x) = E_u[f(x, u)] ซึ่งประมาณโดยการหาค่าเฉลี่ยจากสถานการณ์ที่สุ่มตัวอย่าง
ปรับปรุงความเร็วและตำแหน่งของอนุภาคแต่ละตัวโดยใช้กฎการปรับปรุง PSO มาตรฐาน แต่ใช้ f_robust เป็นสัญญาณวัดความเหมาะสม ตำแหน่งที่ดีที่สุดส่วนบุคคล (pbest) และตำแหน่งที่ดีที่สุดโดยรวม (gbest) จะถูกติดตามเทียบกับค่าความเหมาะสมแบบทนทาน เพื่อให้แน่ใจว่าฝูงผึ้งเคลื่อนที่ไปยังบริเวณที่มีค่าเหมาะสมแบบทนทานของปริภูมิการค้นหา
ทำซ้ำขั้นตอนการประเมินแบบทนทานและการปรับปรุงฝูงผึ้งจนกว่าจะถึงเกณฑ์การหยุด — จำนวนรอบสูงสุด ระดับความเหมาะสมคงที่ หรือค่าความคลาดเคลื่อนในการลู่เข้า ส่งคืนตำแหน่งที่ดีที่สุดโดยรวม 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 เมื่อคำตอบที่ใช้งานจะเผชิญกับความผันผวนในโลกแห่งความเป็นจริงที่ไม่สามารถจับได้ด้วยการประเมินวัตถุประสงค์ตามค่าปกติเพียงค่าเดียว และเมื่อต้นทุนของคำตอบที่เปราะบาง (คำตอบที่เสื่อมสภาพอย่างรุนแรงภายใต้การเปลี่ยนแปลงพารามิเตอร์เล็กน้อย) มีค่ามากกว่าต้นทุนการคำนวณเพิ่มเติมของการประเมินแบบทนทาน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm Intelligence. Morgan Kaufmann Publishers.
ISBN: 9781558605954คัดลอกแล้ว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คัดลอกแล้ว