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

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

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

## อ้างอิง

## อ่านเพิ่มเติม
* 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
* 
* 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.

หมวดหมู่:การหาค่าเหมาะที่สุดทางคณิตศาสตร์
หมวดหมู่:การวิจัยดำเนินการ
หมวดหมู่:การเรียนรู้ของเครื่อง
หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:ขั้นตอนวิธีเชิงวิวัฒนาการ