กระบวนการในการออกแบบ ของ ขั้นตอนวิธีเชิงวิวัฒนาการ

ในการวิวัฒนาการทางธรรมชาติ กลุ่มของประชากรที่เป็นอิสระจากกันผ่านสภาพแวดล้อมที่มีสภาพกดดันจนทำให้เกิดการคัดเลือกทางธรรมชาติ (natural selection) แล้วเกิดการคัดเลือกประชากรที่เหมาะสม เช่นเดียวกับขั้นตอนวิธีเชิงวิวัฒนาการ เราจะสุ่มผลเฉลยที่สามารถเลือกได้ (candidate sulotion) เช่น สมาชิกของโดเมนในฟังก์ชัน ขึ้นมา แล้วใช้ฟังก์ชันคุณภาพ (quality function) เป็นตัวคัดเลือกคำตอบที่เหมาะสม ยิ่งฟังก์ชันมีมาตรฐานสูงยิ่งดี โดยเทียบจากมาตรฐานนี้ บางส่วนของผลเฉลยที่ดีกว่าจะถูกเลือกไปเป็นเมล็ดพันธุ์สำหรับรุ่นถัดไป โดยประยุกต์รูปแบบของการสืบพันธุ์ การกลายพันธุ์ให้กับมัน โดยการสืบพันธุ์นั้น ผลเฉลยที่ถูกเลือกสองตัวหรือมากกว่า (หรือเรียกได้ว่าเป็นบรรพบุรุษ) จะถูกนำมาดำเนินการ และให้ผลออกมาเป็นผลเฉลยรุ่นใหม่ (หรือเรียกได้ว่าเป็นลูก) ส่วนการกลายพันธุ์นั้น จะถูกใช้กับผลเฉลยเพียงหนึ่งตัว และผลที่ได้คือผลเฉลยรุ่นใหม่ การสืบพันธุ์และกลายพันธุ์นี้จะนำไปสู่เซ็ตของผลเฉลยรุ่นใหม่ ที่มีมาตรฐานใหม่ที่ดีกว่ารุ่นเก่า กระบวนการเหล่านี้จะถูกดำเนินการไปจนกว่าจะพบผลเฉลยที่ดีที่สุด หรือที่ถูกต้อง หรือจนกว่าการคำนวณจะถึงขอบเขตสิ้นสุด

ในกระบวนการข้างต้นนั้น มีแรงพื้นฐานสองแรงในการสร้างรากฐานให้กับระบบของการวิวัฒนาการ

  • ตัวดำเนินการที่เปลี่ยนแปลงได้ (variation operator) สำหรับการสืบพันธุ์และการกลายพันธุ์ ซึ่งจะทำการสร้างความหลากหลายและความแปลกใหม่ที่จำเป็น ระหว่างที่
  • การคัดเลือก (selection) ทำหน้าที่เป็นแรงที่ผลักดันคุณภาพ

ในการผสมผสานโปรแกรมประยุกต์ (application) ของความหลากหลาย (variation)และการคัดเลือก (selection) มักนำไปสู่การพัฒนาของค่าความเหมาะสม (fitness value) ในประชากรที่ต่อเนื่องกัน (consecutive population) มันง่ายที่จะเห็นว่ากระบวนการวิวัฒนาการนี้ ถูกใช้งานอย่างเหมาะสม หรืออย่างน้อย ใกล้เคียง โดยจะเห็นถึงการเข้าใกล้ค่าที่ถูกต้องเหมาะสมทุกๆ รอบของการวิวัฒนาการ

แต่อย่าลืมว่า ส่วนประกอบส่วนมากของขึ้นตอนวิธีเชิงวิวัฒนาการเป็นแบบสุ่ม ระหว่างการตัดเลือก ประชากรที่เหมาะสมกว่าจะมีโอกาสที่จะถูกเลือกมากกว่าประชากรที่ไม่เหมาะสม แต่อย่างไรก็ตาม ประชากรที่ไม่เหมาะสมก็มีโอกาสที่จะถูกเลือกมาเป็นบรรพบุรุษ หรืออยู่รอดต่อไป สำหรับการผสมใหม่ (recombination) นั้น แต่ล่ะชิ้นส่วนจะถูกนำมาผสมกันใหม่อย่างสุ่ม เช่นเดียวกันกับการกลายพันธุ์ แต่ล่ะชิ้นส่วนที่ถูกกลายพันธุ์และการวางทับในผลเฉลยจะถูกเลือกมาอย่างสุ่ม

ขั้นตอนวิธีโดยทั่วไปของขั้นตอนวิธีเชิงวิวัฒนาการสามารถดูได้จากรหัสเทียมด้านล่าง

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธี ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของเบลแมน-ฟอร์ด