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

อัลกอริทึม Slime Mould

ผู้เสนอ
Shimin Li
ปี
2020
ประเภท
Nature-inspired metaheuristic algorithm
กลุ่มวิธี
Swarm Intelligence

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

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

ใช้ทำอะไร?

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

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

เริ่มต้นประชากรของตำแหน่งเมือกที่กระจายแบบสุ่มในพื้นที่ค้นหาและประเมินค่าความเหมาะสมของพวกมัน

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

วิศวกรรมเครื่องกล: การปรับการออกแบบโครงสร้างและการกำหนดค่าเครื่องจักรภายใต้เงื่อนไขหลายประการ

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

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

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

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

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

จุดแข็ง

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

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

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

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

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

1

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

2

คำนวณค่าฟังก์ชันวัตถุประสงค์สำหรับแต่ละตำแหน่งใหม่และเปรียบเทียบกับค่าความเหมาะสมก่อนหน้า

3

ทำซ้ำขั้นตอนการอัปเดตและการประเมินผลจนกว่าจะบรรจบกันหรือถึงจำนวนรอบสูงสุดที่กำหนด

4

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

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

  • การสำรวจไม่เพียงพอเมื่อประชากรเริ่มต้นกระจุกตัวมากเกินไปในบริเวณเล็กๆ
  • การละเลยการปรับขนาดตัวแปรตัดสินใจอย่างเหมาะสมอาจนำไปสู่ประสิทธิภาพการค้นหาที่ไม่ดี
  • เปิดตัวโดย Shimin Li และเพื่อนร่วมงานที่มหาวิทยาลัยเจียงซูในปี 2020 SMA เกิดขึ้นจากสาขาการคำนวณแบบชีวเลียน (biomimetic computing) โดยได้รับแรงบันดาลใจจากการสังเกตพฤติกรรมจริงของเมือก physarum อัลกอริทึมได้รับการตรวจสอบบนฟังก์ชันเกณฑ์มาตรฐานมาตรฐานและงานการปรับให้เหมาะสมทางวิศวกรรม ความเรียบง่ายและประสิทธิภาพของมันนำไปสู่การยอมรับอย่างรวดเร็วในโดเมนการใช้งานที่หลากหลาย โดยมีรูปแบบและส่วนปรับปรุงมากมายที่เผยแพร่ตามมา

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

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

SMA เหมาะสมสำหรับการแก้ปัญหาการปรับให้เหมาะสมแบบมีเงื่อนไขหรือไม่

ใช่ SMA สามารถจัดการกับเงื่อนไขได้ผ่านวิธีการฟังก์ชันลงโทษ (penalty function methods) หรือเทคนิคการจัดการเงื่อนไข โซลูชันที่ไม่เป็นไปตามเงื่อนไขจะได้รับค่าความเหมาะสมลดลง ซึ่งนำทางการค้นหาไปยังบริเวณที่เป็นไปตามเงื่อนไข

ฉันควรกำหนดขนาดประชากรสำหรับปัญหาของฉันอย่างไร

เริ่มต้นด้วยขนาดประชากรที่สัมพันธ์กับมิติของปัญหา โดยทั่วไปคือ 20-50 ตัว การมีประชากรมากขึ้นช่วยเพิ่มการค้นหาทั่วโลก แต่เพิ่มต้นทุนการคำนวณ ใช้การทดสอบเชิงประจักษ์กับปัญหาเฉพาะของคุณเพื่อหาความสมดุล

พฤติกรรมการบรรจบกันทั่วไปของ SMA เป็นอย่างไร

SMA มักแสดงการปรับปรุงอย่างรวดเร็วในรอบแรกๆ เนื่องจากการสำรวจที่แข็งแกร่ง ตามด้วยการปรับปรุงเมื่อกลไกน้ำหนักนำโซลูชันไปยังตำแหน่งที่ดีที่สุดที่พบมากขึ้นเรื่อยๆ

SMA มักแสดงการปรับปรุงอย่างรวดเร็วในรอบแรกๆ เนื่องจากการสำรวจที่แข็งแกร่ง ตามด้วยการปรับปรุงเมื่อกลไกน้ำหนักนำโซลูชันไปยังตำแหน่งที่ดีที่สุดที่พบมากขึ้นเรื่อยๆ

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

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

  1. Li, S., Chen, H., Wang, M., Heidari, A. A., & Chakraborty, S. (2020). Slime mould algorithm: A new method for stochastic optimization. Future Generation Computer Systems, 111, 300-323.

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