Grey Wolf Optimizer — GWO
- ผู้เสนอ
- Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
- ปี
- 2014
- ประเภท
- Swarm-intelligence metaheuristic
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Grey Wolf Optimizer (GWO) เป็นเมตาฮิวริสติกส์แบบสวอร์มอัจฉริยะที่ Mirjalili, Mirjalili และ Lewis นำเสนอในปี 2014 ซึ่งจำลองลำดับชั้นทางสังคมและพฤติกรรมการล่าแบบร่วมมือกันของหมาป่าสีเทา ประชากรของชุดคำตอบที่เป็นไปได้จะถูกแบ่งออกเป็นสี่ลำดับชั้นผู้นำ ได้แก่ อัลฟา เบตา เดลตา และโอเมกา และชุดคำตอบที่ดีที่สุดสามชุดในการวนซ้ำแต่ละครั้งจะนำทางฝูงทั้งหมดไปยังพื้นที่ที่ดีขึ้นเรื่อย ๆ ในปริภูมิการค้นหา
แนวคิดเบื้องหลังวิธีการ
ลองจินตนาการถึงฝูงหมาป่าสีเทาที่สะกดรอยตามเหยื่อผ่านภูมิประเทศที่รกทึบ หมาป่าอัลฟาเป็นผู้ตัดสินใจขั้นสุดท้าย หมาป่าเบตาและเดลตาให้คำแนะนำ และหมาป่าที่เหลือในฝูงจะปรับตำแหน่งของตนเพื่อตอบสนองต่อผู้นำทั้งสาม GWO เลียนแบบสิ่งนี้อย่างแม่นยำ: ชุดคำตอบที่เหมาะสมที่สุดสามชุดที่พบจนถึงปัจจุบันทำหน้าที่เป็นสัญญาณนำทาง และผู้สมัครอื่น ๆ ทุกคนจะปรับตำแหน่งของตนเป็นการผสมผสานแบบถ่วงน้ำหนักของทิศทางที่สัญญาณนำทางทั้งสามชี้ พารามิเตอร์เดียวคือ a จะค่อย ๆ ลดลงจาก 2 เป็น 0 เมื่อการวนซ้ำดำเนินไป ดังนั้นฝูงจะกระจายออกไปกว้าง ๆ เพื่อสำรวจก่อน จากนั้นจึงกระชับวงกลมเพื่อใช้ประโยชน์จากพื้นที่ที่ดีที่สุดที่พบ
ประวัติศาสตร์
GWO ได้รับการเสนอโดย Seyedali Mirjalili, Seyed Mohammad Mirjalili และ Andrew Lewis ในปี 2014 ในวารสาร Advances in Engineering Software อัลกอริทึมได้รับแรงบันดาลใจจากการสังเกตทางนิเวศวิทยาของโครงสร้างฝูงหมาป่าสีเทา: ลำดับชั้นทางสังคมที่เข้มงวด (อัลฟา เบตา เดลตา โอเมกา) และกลยุทธ์การล่าสามขั้นตอนของการล้อม การรบกวน และการโจมตีเหยื่อ Mirjalili และคณะ ได้เปรียบเทียบ GWO กับ Particle Swarm Optimization, Gravitational Search Algorithm และ Differential Evolution ในฟังก์ชันทดสอบ 29 ฟังก์ชันและปัญหาการออกแบบทางวิศวกรรมหลายอย่าง โดยรายงานผลลัพธ์ที่แข่งขันได้หรือเหนือกว่า ตั้งแต่ปี 2014 อัลกอริทึมได้สร้างวรรณกรรมติดตามผลจำนวนมาก: Faris และคณะ (2018) ได้สำรวจตัวแปรต่าง ๆ มากกว่าหนึ่งทศวรรษ — ไบนารี หลายวัตถุประสงค์ วุ่นวาย และส่วนขยายแบบไฮบริด — และบันทึกการใช้งานในการเลือกคุณสมบัติ ระบบไฟฟ้า การแบ่งส่วนภาพ และการจัดตารางเวลา
ควรใช้เมื่อใด
GWO เหมาะสำหรับปัญหาการหาค่าเหมาะที่สุดแบบต่อเนื่องที่ฟังก์ชันวัตถุประสงค์มีค่าใช้จ่ายสูงในการประเมินเชิงวิเคราะห์หรือเป็นกล่องดำ ไม่ต้องใช้ข้อมูลเกรเดียนต์และไม่มีข้อสมมติฐานการแจกแจงเกี่ยวกับข้อมูล วิธีนี้เหมาะสำหรับงานออกแบบทางวิศวกรรม การปรับพารามิเตอร์ และการเลือกคุณสมบัติ เนื่องจากเป็นวิธีที่อิงตามประชากร จึงแนะนำให้มีขนาดประชากรขั้นต่ำประมาณ 10–30 ตัวแทน ประชากรขนาดเล็กมากจะลดความหลากหลายและเพิ่มความเสี่ยงของการลู่เข้าก่อนกำหนด GWO ไม่เหมาะสมสำหรับปัญหาแบบไม่ต่อเนื่องหรือแบบเชิงผสมโดยไม่มีการปรับเปลี่ยน และไม่เหมาะสำหรับปัญหาที่มีคำตอบทางคณิตศาสตร์ที่แน่นอนอยู่แล้ว
ข้อจำกัดและข้อควรพิจารณา
- ไม่รับประกันการลู่เข้าสู่ค่าเหมาะที่สุดทั่วโลก คุณภาพขึ้นอยู่กับความหลากหลายของประชากรและจำนวนการวนซ้ำ
- ไม่เหมาะกับปริภูมิการค้นหาแบบไม่ต่อเนื่อง แบบไบนารี หรือแบบเชิงผสมโดยไม่มีการเข้ารหัสแบบกำหนดเอง
- เช่นเดียวกับวิธีการสวอร์มส่วนใหญ่ มันสามารถหยุดนิ่งได้หากผู้นำทั้งสามรวมกลุ่มกันก่อนกำหนดในพื้นที่ที่ไม่เหมาะสม
- ปรับขนาดได้ไม่ดีกับปริภูมิการค้นหาที่มีมิติสูงมากเมื่อเทียบกับตัวแก้ปัญหาที่อิงตามเกรเดียนต์เมื่อวัตถุประสงค์ราบรื่น
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ไร้เกรเดียนต์: ทำงานกับฟังก์ชันวัตถุประสงค์ใด ๆ ที่ส่งคืนค่าสเกลาร์ รวมถึงการจำลองและแบบจำลองกล่องดำ
- การกำหนดพารามิเตอร์น้อยที่สุด: ต้องตั้งค่าเฉพาะขนาดประชากรและจำนวนการวนซ้ำเท่านั้น; a จะลดลงโดยอัตโนมัติ
- สร้างสมดุลระหว่างการสำรวจและการใช้ประโยชน์ผ่านพารามิเตอร์เดียวที่ลดลงเชิงเส้น ทำให้กลไกการสร้างสมดุลมีความโปร่งใส
- ประสิทธิภาพที่แข่งขันได้ในการวัดประสิทธิภาพการออกแบบทางวิศวกรรมด้วยความซับซ้อนในการนำไปใช้งานต่ำ (ระดับความยาก 2 จาก 5)
การประยุกต์ใช้
- การหาค่าเหมาะที่สุดในการออกแบบทางวิศวกรรม: การลดน้ำหนักโครงสร้าง การออกแบบเสาอากาศ การประมาณค่าพารามิเตอร์ระบบไฟฟ้า
- การปรับจูนไฮเปอร์พารามิเตอร์ของแมชชีนเลิร์นนิงและการเลือกคุณสมบัติสำหรับงานการจำแนกประเภท
- ระบบพลังงาน: การจัดสรรพลังงานที่เหมาะสมในโครงข่ายไฟฟ้าและการจัดวางหน่วยพลังงานหมุนเวียน
- การแบ่งส่วนภาพและการวิเคราะห์ภาพทางการแพทย์ผ่านการหาค่าเหมาะที่สุดของการกำหนดเกณฑ์
- ปัญหาการจัดตารางเวลาและการจัดสรรทรัพยากรด้วยการผ่อนคลายแบบต่อเนื่อง
วิธีการทำงาน
วิธีการทำงาน
ประชากรของชุดคำตอบที่เป็นไปได้จะถูกสร้างขึ้นแบบสุ่มอย่างสม่ำเสมอภายในขอบเขตล่างและบนที่กำหนดของปริภูมิการค้นหา ขนาดประชากรและจำนวนการวนซ้ำสูงสุดเป็นเพียงสองพารามิเตอร์ที่ต้องตั้งค่าก่อนเริ่มการทำงาน
ชุดคำตอบที่เป็นไปได้แต่ละชุดจะถูกให้คะแนนโดยฟังก์ชันวัตถุประสงค์ เนื่องจาก GWO เป็นแบบไร้เกรเดียนต์ ฟังก์ชันอาจเป็นกล่องดำ — โดยจะต้องส่งคืนค่าความเหมาะสมแบบสเกลาร์สำหรับตำแหน่งผู้สมัครแต่ละตำแหน่งเท่านั้น
ผู้สมัครจะถูกจัดเรียงตามความเหมาะสม ชุดคำตอบที่ดีที่สุดจะถูกกำหนดให้เป็นอัลฟา (α) ชุดคำตอบที่ดีที่สุดอันดับสองเป็นเบตา (β) และชุดคำตอบที่ดีที่สุดอันดับสามเป็นเดลตา (δ) ผู้สมัครที่เหลือทั้งหมดเป็นหมาป่าโอเมกา (ω) บทบาทเหล่านี้จะถูกกำหนดใหม่ในการวนซ้ำแต่ละครั้ง ดังนั้นป้ายกำกับจะติดตามตำแหน่งที่ดีที่สุดสามตำแหน่งในปัจจุบันเสมอ
หมาป่าโอเมกาแต่ละตัวจะอัปเดตตำแหน่งของตนโดยการคำนวณเวกเตอร์ระยะทางสามเวกเตอร์ — หนึ่งเวกเตอร์ไปยัง α, β และ δ แต่ละตัว — และเคลื่อนที่ไปยังจุดศูนย์กลางของตำแหน่งเป้าหมายสามตำแหน่งที่ได้ พารามิเตอร์ควบคุม a จะลดลงเชิงเส้นจาก 2 เป็น 0 ตลอดการทำงาน: ค่า a ที่มากจะขับเคลื่อนการสำรวจ (ผู้สมัครสามารถเคลื่อนที่เกินและค้นหาห่างจากผู้นำได้) ค่า a ที่น้อยจะขับเคลื่อนการใช้ประโยชน์ (ผู้สมัครจะรวมตัวกันอย่างแน่นหนารอบผู้นำ)
ขั้นตอนการล่าจะถูกทำซ้ำจนกว่าจะถึงจำนวนการวนซ้ำสูงสุดหรือตรงตามเกณฑ์การหยุด ตำแหน่งของหมาป่าอัลฟาเมื่อสิ้นสุดจะถูกส่งคืนเป็นชุดคำตอบที่ดีที่สุดที่พบ
ข้อผิดพลาดที่พบบ่อย
- การตั้งค่าขนาดประชากรที่เล็กเกินไป (ต่ำกว่าประมาณ 10) ทำให้ความหลากหลายลดลงอย่างรวดเร็ว ผู้นำทั้งสามจะลู่เข้าก่อนกำหนด และการทำงานจะสำรวจเพียงพื้นที่เล็ก ๆ เท่านั้น
- การทำงานที่วนซ้ำน้อยเกินไปทำให้วงจรการล่าไม่เพียงพอ การทำงานที่สิ้นสุดในขณะที่ a ยังคงมีค่ามากยังไม่ได้เข้าสู่ระยะการใช้ประโยชน์
- การใช้ GWO กับปัญหาที่มีตัวแปรจำนวนเต็มหรือตัวแปรเชิงหมวดหมู่โดยไม่มีแผนการทำให้เป็นไม่ต่อเนื่องจะทำให้เกิดการอัปเดตตำแหน่งที่ไม่มีความหมาย
- การละเลยขนาดของขอบเขตการค้นหา — ขอบเขตที่กว้างมากเมื่อรวมกับประชากรขนาดเล็กทำให้พื้นที่ส่วนใหญ่ไม่ถูกสุ่มตัวอย่างในการวนซ้ำแรก ๆ
คำถามที่พบบ่อย
ฉันจะเลือกขนาดประชากรและจำนวนการวนซ้ำได้อย่างไร
จุดเริ่มต้นทั่วไปคือ 30 ตัวแทนและ 200–500 การวนซ้ำสำหรับปัญหาที่มีมิติปานกลาง (สูงสุดประมาณ 30 ตัวแปร) เพิ่มขนาดประชากรและการวนซ้ำเมื่อมิติของปัญหาเพิ่มขึ้น เนื่องจาก GWO เป็นแบบสุ่ม ให้รันอย่างน้อย 20–30 ครั้งด้วยเมล็ดสุ่มที่แตกต่างกัน และรายงานค่าเฉลี่ยและส่วนเบี่ยงเบนมาตรฐานของค่าความเหมาะสมที่ดีที่สุด
GWO สามารถจัดการกับตัวแปรแบบไม่ต่อเนื่องหรือแบบไบนารีได้หรือไม่
โดยพื้นฐานแล้วไม่ได้ สมการการอัปเดตตำแหน่งมาตรฐานถูกกำหนดไว้สำหรับปริภูมิค่าจริงแบบต่อเนื่อง ตัวแปรแบบไบนารีหรือแบบไม่ต่อเนื่องมีอยู่ในวรรณกรรม — โดยทั่วไปจะใช้ฟังก์ชันถ่ายโอนเพื่อแมปตำแหน่งต่อเนื่องกับการตัดสินใจแบบไบนารี — แต่สิ่งเหล่านี้เป็นส่วนขยายมากกว่าอัลกอริทึมดั้งเดิม
GWO เปรียบเทียบกับ Particle Swarm Optimization อย่างไร
ทั้งสองเป็นวิธีการสวอร์มอัจฉริยะที่มีต้นทุนการคำนวณที่คล้ายกัน GWO ใช้ผู้นำสามคน (อัลฟา เบตา เดลตา) แทนที่จะเป็นค่าที่ดีที่สุดทั่วโลกเพียงค่าเดียวและค่าที่ดีที่สุดส่วนบุคคลของแต่ละอนุภาค ซึ่งมีแนวโน้มที่จะรักษาความหลากหลายได้นานขึ้น Mirjalili และคณะ (2014) พบว่า GWO แข่งขันได้หรือเหนือกว่า PSO ในชุดการวัดประสิทธิภาพของพวกเขา แต่ประสิทธิภาพขึ้นอยู่กับปัญหา ไม่มีวิธีใดที่เหนือกว่าโดยทั่วไป
พารามิเตอร์ a ควบคุมอะไร และฉันจำเป็นต้องปรับจูนหรือไม่
พารามิเตอร์ a จะลดลงเชิงเส้นจาก 2 เป็น 0 ตลอดการทำงาน และควบคุมว่าหมาป่าจะสำรวจ (a สูง) หรือใช้ประโยชน์ (a ต่ำ) กำหนดการนี้ถูกกำหนดโดยอัลกอริทึม — คุณไม่ต้องปรับจูน a โดยตรง ตัวควบคุมเดียวที่คุณควบคุมได้คือขนาดประชากรและจำนวนการวนซ้ำทั้งหมด ซึ่งรวมกันแล้วจะกำหนดว่า a ลดลงช้าหรือเร็วเพียงใด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วFaris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว