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

อัลกอริทึมการหาค่าเหมาะสมที่สุดเชิงเลขคณิต

ผู้เสนอ
Laith Abualigah
ปี
2020
ประเภท
Mathematical metaheuristic algorithm
กลุ่มวิธี
Mathematical Optimization

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

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

ใช้ทำอะไร?

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

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

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

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

AOA นำเสนอโดย Laith Abualigah และผู้ร่วมงานในปี 2020 และได้รับการตีพิมพ์ในวารสาร Applied Mathematics and Computation อัลกอริทึมนี้แสดงถึงการเปลี่ยนแปลงจากเมตาฮิวริสติกที่ได้แรงบันดาลใจจากธรรมชาติล้วนๆ แต่กลับใช้ทฤษฎีการหาค่าเหมาะสมที่สุดบนพื้นฐานของการดำเนินการทางคณิตศาสตร์ แนวทางนี้ให้มุมมองใหม่ในการออกแบบอัลกอริทึม และได้พิสูจน์แล้วว่ามีประสิทธิภาพในปัญหาเกณฑ์มาตรฐานจำนวนมากและการใช้งานจริง

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

สร้างประชากรเริ่มต้นของโซลูชันผู้สมัครที่กระจายอย่างสม่ำเสมอในปริภูมิการค้นหา

2

ใช้ตัวดำเนินการคูณและหารเพื่อสร้างโซลูชันใหม่ที่หลากหลายและสำรวจพื้นที่ที่ยังไม่ได้สำรวจ

3

ใช้ตัวดำเนินการบวกและลบเพื่อปรับปรุงโซลูชันรอบตำแหน่งที่ดีที่สุดที่ค้นพบ

4

ประเมินค่าความเหมาะสมของโซลูชันใหม่ และอัปเดตประชากรและตัวติดตามโซลูชันที่ดีที่สุด

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

  • การตั้งค่าความน่าจะเป็นของตัวดำเนินการที่มุ่งเน้นการคูณ/หารมากเกินไปอาจขัดขวางการลู่เข้า
  • การสำรวจไม่เพียงพอในช่วงต้นของการหาค่าเหมาะสมที่สุดนำไปสู่การติดอยู่ในค่าเหมาะสมที่สุดเฉพาะที่
  • การปรับสเกลตัวแปรตัดสินใจที่ไม่เหมาะสมเมื่อเทียบกับขอบเขตปริภูมิการค้นหาส่งผลต่อประสิทธิภาพการค้นหา

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

เหตุใดจึงใช้การคูณและการหารเพื่อการสำรวจใน AOA?

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

AOA แตกต่างจากอัลกอริทึมพันธุกรรมอย่างไร?

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

AOA สามารถจัดการกับปัญหาการหาค่าเหมาะสมที่สุดแบบไม่ต่อเนื่องได้หรือไม่?

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

ความซับซ้อนในการคำนวณของ AOA ต่อรอบคืออะไร?

AOA มีความซับซ้อนในการคำนวณเชิงเส้น O(N*D) ต่อรอบ โดยที่ N คือขนาดประชากร และ D คือมิติของปัญหา ทำให้มีประสิทธิภาพในการคำนวณเมื่อเทียบกับอัลกอริทึมที่ต้องการการคำนวณระยะห่างแบบคู่

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

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

  1. Abualigah, L., Yousri, D., Abd Elaziz, M., Ewees, A. A., Al-qaness, M. A., & Gandomi, A. H. (2021). Arithmetic optimization algorithm: A new metaheuristic algorithm for solving optimization problems. Applied Mathematics and Computation, 392, 125450.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว