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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

ที่มา[แก้]

ส่วนที่ถูกค้นพบมาในช่วงแรกสุดของสื่งที่เราเรียกในทุกวันนี้ว่าขั้นตอนวิธีเชิงพันธุกรรม[4] นั้นเกิดในช่วงปลายปี 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). "Intro to Genetic Algorithms" (PDF). Indiana University. สืบค้นเมื่อ 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.; Matthew F.,Muldoon; Bruce G.,Pollock; Steven,Manuck; Gwenn,Smith;Mark E.,Sale (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. 
  4. Marczyk, Adam (2011). "Genetic Algorithms and Evolutionary Computation" (HTML). 

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