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

ในศาสตร์ของปัญญาประดิษฐ์ นั้น ขั้นตอนวิธีเชิงวิวัฒนาการ (evolutionary algorithm) เป็นหนึ่งในเรื่องของการคำนวณเชิงวิวัฒนาการ (evolutionary computation) ที่ใช้ฐานประชากรโดยทั่วไปของขั้นตอนวิธีแบบเมตาฮิวริสติกที่เหมาะสมที่สุด (metaheuristic optimization algorithm) โดยขั้นตอนวิธีเชิงวิวัฒนาการนั้น ใช้กระบวนการที่ได้รับแรงบันดาลใจมาจากการวิวัฒนาการทางชีววิทยา^[1] อันได้แก่ การสืบพันธุ์ (reproduction) การกลายพันธุ์ (mutation) การแลกเปลี่ยนยีน (recombination) และการคัดเลือก (selection) โดยจะมีผลเฉลยที่สามารถเลือกได้ (candidate solution) แทนประชากร และฟังก์ชันคุณภาพ (quality function) ในการคัดเลือกประชากรที่เหมาะสมตามสภาพแวดล้อมที่กำหนดไว้^[2]^[3] ขึ้นตอนวิธีเชิงวิวัฒนาการนี้มักจะใช้ได้ดีสำหรับการหาผลเฉลยของปัญหาในทุกๆ ด้าน เนื่องจากสามารถพัฒนาผลเฉลยที่มีไปยังผลเฉลยที่ถูกต้องได้อย่างรวดเร็ว ทำให้มันประสบความสำเร็จในหลายๆ ด้านของปัญหา เช่น วิศวกรรม ศิลปกรรม ชีวภาพ เศรษฐศาสตร์ การตลาด พันธุศาสตร์ การค้นคว้าวิจัย การออกแบบหุ่นยนต์ วิทยาศาสตร์ด้านสังคม ฟิสิกส์ รัฐศาสตร์ และ เคมี

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

กระบวนการในการออกแบบ

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

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

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

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

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

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

รหัสเทียม

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

รูปแบบต่างๆ ของขั้นตอนวิธีเชิงวิวัฒนาการ

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

ขั้นตอนวิธีเชิงพันธุกรรม (Genetic algorithm) - เป็นขั้นตอนวิธีเชิงวิวัฒนาการที่ถูกใช้อย่างแพร่หลายที่สุด เป็นขั้นตอนวิธีในการหาผลเฉลยจากสายของตัวเลข (strings of numbers) โดยการใช้ตัวดำเนินการเช่นการผสมพันธุ์ และ การกลายพันธุ์ ขั้นตอนวิธีเชิงวิวัฒนาการนี้มักใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด
การโปรแกรมเชิงพันธุกรรม (Genetic programming) - เป็นการหาผลเฉลยที่เป็นโปรแกรมคอมพิวเตอร์ที่มีความเหมาะสมที่สุดในการแก้ไขปัญหาทางคอมพิวเตอร์
การโปรแกรมเชิงวิวัฒนาการ (Evolutionary programming) - เช่นเดียวกันกับการโปรแกรมเชิงพันธุกรรม แต่โครงสร้างของโปรแกรมจะไม่เปลี่ยนแปลง และตัวแปรที่เป็นตัวเลขมีสิทธิ์ที่จะวิวัฒน์ได้
กลยุทธ์เชิงวิวัฒนาการ (Evolution strategy) - ทำงานร่วมกับเวกเตอร์ของจำนวนจริงโดยเป็นตัวแทนของผลเฉลย โดยใช้การกลายพันธุ์แบบปรับตัวเอง (self-adaptive mutation)
ข่ายประสาทวิวัฒน์ (Neuroevolution) - มีลักษณะคล้ายกับการโปรแกรมเชิงพันธุกรรม แต่จีโนมเป็นตัวแทนของโครงข่ายประสาทเทียม (artificial neural network) โดยอธิบายถึงโครงสร้างและการเชื่อต่อ
ความฉลาดแบบกลุ่ม (Swarm Intelligence) - มีการใช้การกลายพันธุ์ในการแปลงผลเฉลย และชักนำไปยังคำตอบที่ดีที่สุดภายใต้สภาพแวดล้อมเงื่อนไขที่ต่างๆ กัน เช่น ขั้นตอนวิธีหาค่าเหมาะสมที่สุดด้วยระบบอาณาจักรมด (Ant colony optimization) ขั้นตอนวิธีหาค่าเหมาะสมที่สุดด้วยระบบที่มีประจุ (Charged system search) เป็นต้น
วิธีการลอกแบบ (Memetic Algorithm) - เป็นอีกแนวคิดหนึ่งในการวิวัฒนาการ แต่จะใช้การส่งผ่านหรือการเลียนแบบองค์ประกอบแทนวิธีการทางพันธุกรรม

อ้างอิง

↑ J. Clune, C. Ofria, and R. T. Pennock, “How a generative encoding fares as problem-regularity decreases,” in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008.
↑ G.S. Hornby and J.B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3):223–246, 2002.
↑ Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding". Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.

อ่านเพิ่มเติม

Ashlock, D. (2006), Evolutionary Computation for Modeling and Optimization, Springer, ISBN 0-387-22196-4.
Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford Univ. Press.
Bäck, T., Fogel, D., Michalewicz, Z. (1997), Handbook of Evolutionary Computation, Oxford Univ. Press.
Eiben, A.E., Smith, J.E. (2003), Introduction to Evolutionary Computing, Springer.
Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor
Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2016-05-27. สืบค้นเมื่อ 2011-09-29.{{cite book}}: CS1 maint: multiple names: authors list (ลิงก์)
Ingo Rechenberg (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
Hans-Paul Schwefel (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
Michalewicz Z., Fogel D.B. (2004). How To Solve It: Modern Heuristics, Springer.
Price, K., Storn, R.M., Lampinen, J.A., (2005). "Differential Evolution: A Practical Approach to Global Optimization", Springer.
Yang X.-S., (2010), "Nature-Inspired Metaheuristic Algorithms", 2nd Edition, Luniver Press.

[1] J. Clune, C. Ofria, and R. T. Pennock, “How a generative encoding fares as problem-regularity decreases,” in PPSN (G. Rudolph, T. Jansen, S. M. Lucas, C. Poloni, and N. Beume, eds.), vol. 5199 of Lecture Notes in Computer Science, pp. 358–367, Springer, 2008.

[2] G.S. Hornby and J.B. Pollack. Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8(3):223–246, 2002.

[3] Jeff Clune, Benjamin Beckmann, Charles Ofria, and Robert Pennock. "Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding". Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway.

[1]

[2]

[3]