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

ขั้นตอนวิธีเชิงพันธุกรรม (อังกฤษ: genetic algorithm) เป็นเทคนิคสำหรับค้นหาผลเฉลย (solutions) หรือคำตอบโดยประมาณของปัญหา โดยอาศัยหลักการจากทฤษฎีวิวัฒนาการจากชีววิทยา และ การคัดเลือกตามธรรมชาติ (natural selection) นั่นคือ สิ่งมีชีวิตที่เหมาะสมที่สุดจึงจะอยู่รอด กระบวนการคัดเลือกได้เปลี่ยนแปลงสิ่งมีชีวิตให้เหมาะสมยิ่งขึ้น ด้วยตัวปฏิบัติการทางพันธุกรรม (genetic operator) เช่น การสืบพันธุ์ (inheritance หรือ reproduction) , การกลายพันธุ์ (mutation) , การแลกเปลี่ยนยีน (recombination)

ขั้นตอนวิธีเชิงพันธุกรรมเป็นการจำลองทางคอมพิวเตอร์ เพื่อแก้ปัญหาหาค่าเหมาะที่สุด (optimal solution) โดยการแทนคำตอบที่มีอยู่ให้อยู่ในลักษณะ โครโมโซม (chromosomes) แล้วปรับปรุงคำตอบแต่ละชุด (เรียกว่า individual) ด้วยวิธีการต่าง ๆ ซึ่งเกี่ยวข้องกับการวิวัฒนาการ (evolutionary operation) การเปลี่ยนแปลงยีนแบบสุ่ม ด้วยตัวปฏิบัติการทางพันธุกรรม (evolutionary operator) เพื่อให้ได้คำตอบที่ดีขึ้น โดยทั่วไปจะแทนคำตอบด้วยเลขฐานสอง (สายอักขระของเลข 0 และ 1) การวิวัฒน์ (evolution) เพื่อหาคำตอบที่เหมาะสมที่สุด (the fitness solution) จะเริ่มจากประชากรที่ได้จากการสุ่มทั้งหมดและจะทำเป็นรุ่น ๆ ในแต่ละรุ่นคำตอบหลายชุดจะถูกสุ่มเลือกขึ้นมาเปลี่ยนแปลง ซึ่งอาจจะทำให้เกิดการกลายพันธุ์ หรือสับเปลี่ยนยีนระหว่างกัน จนได้ประชากรรุ่นใหม่ ที่มีค่าความเหมาะสม (fitness) มากขึ้น การวิวัฒน์นี้จะทำไปเรื่อย ๆ จนกระทั่งพบคำตอบที่มีค่าความเหมาะสมตามต้องการ

ที่มา

ส่วนที่ถูกค้นพบมาในช่วงแรกสุดของสื่งที่เราเรียกในทุกวันนี้ว่าขั้นตอนวิธีเชิงพันธุกรรม นั้นเกิดในช่วงปลายปี 1950 เขียนโดยนักชีววิทยาด้านการวิวัฒนาการโดยที่ต้องการหารูปแบบของการวิวัฒนาการตามธรรมชาติ แต่มันก็ไม่ได้ถูกมองว่าสามารถนำไปใช้สำหรับการแก้ปัญหาในด้านอื่นๆได้ แต่ก็ไม่นานนักในปี 1962 นักวิจัยเช่น G.E.P. Box, G.J. Friedman, W.W. Bledsoe และ H.J. Bremermann ทั้งหมดได้ทำการพัฒนาขั้นตอนวิธี ต่างๆ ในการการเพิ่มประสิทธิภาพของฟังชั่น และ ปัญหาการเรียนรู้ของเครื่องเช่นเดียวกัน แต่งานวิจัยของพวกเค้าก็ได้รับการติดตามที่น้อย งานวิจัยที่ประสบความสำเร็จกว่าคืองานวิจัยในปี 1965 เมื่อ Ingo Rechenberg นำเสนอเทคนิคที่เค้าเรียกว่ากลยุทธ์การวิวัฒนาการถึงแม้ว่ามันจะคล้ายกับขั้นตอนวิธีของนักปีนเขามากกว่าวิธีเชิงพันธุกรรมก็ตาม โดยจะคล้ายคลึงกันแต่จะไม่มีการพลิตจำนวนประชากรออกมามากๆและไม่มีการไขว้เปลี่ยน (cross over) โดยที่รุ่นบรรพบุรุษจะทำการกลายพันธ์ (mutation) ออกมาหนึ่งตัวแล้วจากนั้นจะเลือกตัวที่ดีกว่านำไปเป็นบรรพบุรุษของการการกลายพันธ์ (mutation) ครั่งต่อไป และมีการพัฒนาจนมีการนำวิธีคิดแบบจำนวนประชากรมากๆ นำมาใช้เพื่อให้มีประสิทธิภาพที่ดียิ่งขึ้น

หลักการออกแบบขั้นตอนวิธี

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

1. วิธีการแทนค่ายีนของผลลัพธ์ (genetic representation)
2. วิธีการหาความเหมาะสม (fitness function)

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

การกำหนดค่าเริ่มต้น

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

การคัดเลือก

ระหว่างรุ่นของยีนแต่ละรุ่นนั้นจะมีการคัดเลือดยีนที่มีความเหมาะสมมากกว่าไปยังยีนรุ่นต่อไปโดยทำอย่างนี้เพื่อให้สามารถเข้าใกล้คำตอบของปัญหาได้มากยิ่งขึ้นโดยการคัดเลือกนั้นจะใช้การคัดเลือกโดยการใช้[ความเหมาะสม] (fitness-base) โดยการใช้ค่าของคุณภาพของยีนแต่ละตัวนำไปหาค่าความเหมาะสมได้จากกระบวนหาความเหมาะสม (fitness-function) ซึ่งจะแตกต่างกันไปตามแต่ละปัญหา หรืออาจจะใช้การสุ่มเพื่อให้เข้าถึงคำตอบได้แต่อาจจะใช้เวลาที่นานมากเกินไป

การผลิตรุ่นถัดไป

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

การจบการทำงาน

กระบวนการข้างต้นนี้จะวนซ้ำไปเรื่อยๆจนกว่าจะถึงเงื่อนไขในการจบการทำงานโดยส่วนใหญ่จะเป็นดังนี้

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

รหัสเทียม

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

ขั้นตอนวิธีที่เกี่ยวข้อง

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

(อังกฤษ: Evolutionary algorithm) เป็นส่วนหนึ่งของการคำนวณโดยการวิวัฒนาการ และมีขั้นตอนวิธีเชิงพันธุกรรมเป็นส่วนย่อย

ความฉลาดแบบกลุ่ม

(อังกฤษ: Swarm intelligent) เป็นส่วนหนึ่งของการคำนวณโดยการวิวัฒนาการ จะเป็นการสังเกตจากสิ่งมีชีวิตที่ดำรงชีวิตเป็นฝูงหรือกลุ่ม ตัวอย่างเช่น ระบบอาณาจักรมด (Ant colony system) ซึ่งได้รับการดลใจจากการหาอาหารของมด, หน้าที่ต่างๆ ของมัน โดยใช้สารเคมีในตัวมันที่ทิ้งไว้, การทำให้เหมาะสมแบบกลุ่มอนุภาค (Particle Swarm Optimization) ซึ่งได้รับการดลใจจาก การหาอาหารของฝูงนก หรือ ฝูงปลา

อ้างอิง

1. Yaeger, Larry (2011). (PDF). Indiana University. คลังข้อมูลเก่า เก็บจาก แหล่งเดิม (PDF) เมื่อ 2012-06-16. สืบค้นเมื่อ 13 Sep 2011.
2. Banzhaf, Wolfgang (1998). Genetic programming: an introduction on the automatic evolution of computer. The Morgan Kaufmann. ISBN 978-1558605107.
3. Bies, Robert R. (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". JOURNAL OF PHARMACOKINETICS AND PHARMACODYNAMICS. 33 (2): 195–221. doi:10.1007/s10928-006-9004-6. Unknown parameter |coauthors= ignored (|author= suggested) (help)
4. Marczyk, Adam (2011). "Genetic Algorithms and Evolutionary Computation" (HTML).

แหล่งข้อมูลอื่น

• En.Wikipedia
• Obitko.com
• Imperial College 2011-09-28 ที่ เวย์แบ็กแมชชีน