ล งก ข ามภาษา ในบทความน ม ไว ให ผ อ านและผ ร วมแก ไขบทความศ กษาเพ มเต มโดยสะดวก เน องจากว ก พ เด ยภาษาไทยย งไม ม บทความด

ขั้นตอนวิธีเชิงพันธุกรรม (อังกฤษ: 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) ของโครโมโซมในโครโมโซมที่ได้เลือกออกมาโดยจะเป็นการสุ่มหลังจากที่เสร็จเรียบร้อยแล้วก็จะนำพันธุกรรมที่ได้ไปวนเข้ากระบวนการเดิมต่อไปเพื่อให้ได้โครโมโซมที่มีคุณภาพที่ดีที่สุดออกมา โดยขั้นตอนวิธีเชิงพันธุกรรมนั้นจำเป็นต้องมี

(genetic representation)
(fitness function)

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

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

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

การคัดเลือก

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

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

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

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

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

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

รหัสเทียม

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

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

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

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

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

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

อ้างอิง

Yaeger, Larry (2011). (PDF). Indiana University. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2012-06-16. สืบค้นเมื่อ 13 Sep 2011.
Banzhaf, Wolfgang (1998). Genetic programming: an introduction on the automatic evolution of computer. The Morgan Kaufmann. ISBN .
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. {{}}: ไม่รู้จักพารามิเตอร์ |coauthors= ถูกละเว้น แนะนำ (|author=) ((help))
Marczyk, Adam (2011). "Genetic Algorithms and Evolutionary Computation" (HTML).

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

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

บทความคอมพิวเตอร์ อุปกรณ์ต่าง ๆ หรือเครือข่ายนี้ยังเป็น คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล

[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 .

[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. {{}}: ไม่รู้จักพารามิเตอร์ |coauthors= ถูกละเว้น แนะนำ (|author=) ((help))

[4] Marczyk, Adam (2011). "Genetic Algorithms and Evolutionary Computation" (HTML).