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

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)

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

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

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

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

1

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

2

ชุดคำตอบที่เป็นไปได้แต่ละชุดจะถูกให้คะแนนโดยฟังก์ชันวัตถุประสงค์ เนื่องจาก GWO เป็นแบบไร้เกรเดียนต์ ฟังก์ชันอาจเป็นกล่องดำ — โดยจะต้องส่งคืนค่าความเหมาะสมแบบสเกลาร์สำหรับตำแหน่งผู้สมัครแต่ละตำแหน่งเท่านั้น

3

ผู้สมัครจะถูกจัดเรียงตามความเหมาะสม ชุดคำตอบที่ดีที่สุดจะถูกกำหนดให้เป็นอัลฟา (α) ชุดคำตอบที่ดีที่สุดอันดับสองเป็นเบตา (β) และชุดคำตอบที่ดีที่สุดอันดับสามเป็นเดลตา (δ) ผู้สมัครที่เหลือทั้งหมดเป็นหมาป่าโอเมกา (ω) บทบาทเหล่านี้จะถูกกำหนดใหม่ในการวนซ้ำแต่ละครั้ง ดังนั้นป้ายกำกับจะติดตามตำแหน่งที่ดีที่สุดสามตำแหน่งในปัจจุบันเสมอ

4

หมาป่าโอเมกาแต่ละตัวจะอัปเดตตำแหน่งของตนโดยการคำนวณเวกเตอร์ระยะทางสามเวกเตอร์ — หนึ่งเวกเตอร์ไปยัง α, β และ δ แต่ละตัว — และเคลื่อนที่ไปยังจุดศูนย์กลางของตำแหน่งเป้าหมายสามตำแหน่งที่ได้ พารามิเตอร์ควบคุม a จะลดลงเชิงเส้นจาก 2 เป็น 0 ตลอดการทำงาน: ค่า a ที่มากจะขับเคลื่อนการสำรวจ (ผู้สมัครสามารถเคลื่อนที่เกินและค้นหาห่างจากผู้นำได้) ค่า a ที่น้อยจะขับเคลื่อนการใช้ประโยชน์ (ผู้สมัครจะรวมตัวกันอย่างแน่นหนารอบผู้นำ)

5

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

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

  • การตั้งค่าขนาดประชากรที่เล็กเกินไป (ต่ำกว่าประมาณ 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 ลดลงช้าหรือเร็วเพียงใด

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

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

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. 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
    คัดลอกแล้ว