การเพิ่มประสิทธิภาพ

กำหนดขั้นตอนวิธีเชิงพันธุกรรม

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

วิธีขั้นตอนเชิงพันธุกรรมอยู่บนพื้นฐานของทฤษฎีการคัดเลือกตามธรรมชาติ ทฤษฎีนี้ระบุว่าเฉพาะปัจเจกที่แข็งแกร่งที่สุดเท่านั้นที่จะอยู่รอดเพื่อการสืบพันธุ์ในรุ่นต่อไป

ในการปรับค่าที่เหมาะสมของ cBot แต่ละการผ่านการปรับค่าที่เหมาะสมถือเป็นหนึ่งปัจเจก เพื่อประเมินการผ่านแต่ละครั้ง ขั้นตอนวิธีเชิงพันธุกรรมจะคำนวณคะแนนความเหมาะสมสำหรับแต่ละการผ่านและเปรียบเทียบคะแนนนี้กับการผ่านอื่นๆ ทั้งหมด

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

ขั้นตอนของขั้นตอนวิธีเชิงพันธุกรรม

ขั้นตอนวิธีเชิงพันธุกรรมใดๆ มีขั้นตอนดังต่อไปนี้

graph TB
  B([การคัดเลือก]) ==> C([การผสมข้าม]);
  C ==> D([การกลายพันธุ์]);
  D ==> B;

ขั้นตอนต่างๆ มีคำอธิบายดังนี้

การคัดเลือก

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

การข้ามสายพันธุ์

หลังจากค้นพบการผ่านการปรับค่าที่เหมาะสมที่สุดสองอัน ขั้นตอนวิธีจะใช้สิ่งเหล่านี้เพื่อสร้างการผ่านรุ่นลูก (หรือรุ่นสืบทอด) ใหม่โดยใช้การผสมผสานค่าพารามิเตอร์ของการผ่านรุ่นพ่อแม่ทั้งสอง

การกลายพันธุ์

ในขั้นตอนนี้ ขั้นตอนวิธีจะทำให้การผ่านรุ่นลูกกลายพันธุ์โดยการแก้ไขค่าพารามิเตอร์หนึ่งหรือหลายค่าแบบสุ่ม

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

มิฉะนั้น ขั้นตอนวิธีจะเพิ่มตัวนับการหยุดนิ่ง หากตัวนับการหยุดนิ่งถึงค่าของพารามิเตอร์ช่วงเวลาการหยุดนิ่งของขั้นตอนวิธี กระบวนการปรับค่าที่เหมาะสมจะถูกหยุดโดยอัตโนมัติ

พารามิเตอร์ของขั้นตอนวิธีเชิงพันธุกรรม

ขั้นตอนวิธีเชิงพันธุกรรมมีพารามิเตอร์หลายตัวที่ใช้ในระหว่างช่วงชีวิตของมัน พารามิเตอร์เหล่านี้ไม่สามารถเปลี่ยนแปลงได้