ขั้นตอนวิธีเชิงพันธุกรรม
ขั้นตอนวิธีเชิงพันธุกรรม (อังกฤษ: 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) โดยจะทำการคัดเลือกยีนออกมาเป็นคู่ๆแล้วทำวิธีดังที่ได้กล่าวมา ซึ่งตามทฤษฎีแล้วจะต้องได้ค่าเฉลี่ยของคุณภาพของยีนที่ดีขึ้นเนื่องจากได้ทำการคัดเลือกยีนที่มีคุณภาพดีจากรุ่นที่แล้วมาใช้นั้นเองจากการผลิตรุ่นถัดไปด้วยวิธีนี้จะทำให้ได้ยีนที่แตกต่างจากยีนเดิมและยังมีคุณภาพเฉลี่ยที่ดีขึ้นอีกด้วย วิธีการนำยีนสองตัวนั้นมาผลิตรุ่นถัดไปนั้นเป็นวิธีการเลียนแบบทางชีววิทยาแต่จากการวิจัยพบว่าถ้าใช้หลายๆยีนมาผลิตรุ่นถัดไปพบว่ามีประสิทธิภาพที่ดีกว่าแบบคู่อีกด้วย
การจบการทำงาน
กระบวนการข้างต้นนี้จะวนซ้ำไปเรื่อยๆจนกว่าจะถึงเงื่อนไขในการจบการทำงานโดยส่วนใหญ่จะเป็นดังนี้
- พบผลลัพธ์ที่อยู่ในเกณฑ์พอใจแล้ว
- ถึงรุ่นสุดท้ายที่ได้กำหนดไว้แล้ว
- ทรัพยากรที่ใช้ในการคำนวณหมดแล้ว
- พบคำตอบที่มีความเหมาะสมอยู่ในระดับสูงสุดแล้ว
- ตรวจสอบด้วยผู้ควบคุมเอง
- การนำเงื่อนไขต่างๆด้านบนต่างๆมาประยุกต์รวมกัน
รหัสเทียม
- เลือกค่าเริ่มต้นของประชากรแต่ละตัว
- คำนวณค่าความเหมาะสมของประชากรแต่ละตัว
- ทำการคำนวณซ้ำในรอบนี้ไปเรื่อยๆจนกว่าจะเลิกการทำงาน (ทรัพยากรหมด,ถึงค่าที่พอใจ,อื่นๆ)
- เลือกยีนที่มีความเหมาะสมอยู่ในระดับที่ต้องการจากรุ่นปัจจุบัน
- ทำการผลิตรุ่นใหม่โดยใช้วิธีการกลายพันธ์หรือการไขว้เปลี่ยนกับยีนที่ได้เลือกมา
- คำนวณค่าความเหมาะสมของยีนที่จะเป็นรุ่นถัดไป
- แทนค่าของยีนรุ่นถัดไปกับรุ่นเดิม
ขั้นตอนวิธีที่เกี่ยวข้อง
ขั้นตอนวิธีเชิงวิวัฒนาการ
(อังกฤษ: Evolutionary algorithm) เป็นส่วนหนึ่งของการคำนวณโดยการวิวัฒนาการ และมีขั้นตอนวิธีเชิงพันธุกรรมเป็นส่วนย่อย
ความฉลาดแบบกลุ่ม
(อังกฤษ: Swarm intelligent) เป็นส่วนหนึ่งของการคำนวณโดยการวิวัฒนาการ จะเป็นการสังเกตจากสิ่งมีชีวิตที่ดำรงชีวิตเป็นฝูงหรือกลุ่ม ตัวอย่างเช่น ระบบอาณาจักรมด (Ant colony system) ซึ่งได้รับการดลใจจากการหาอาหารของมด, หน้าที่ต่างๆ ของมัน โดยใช้สารเคมีในตัวมันที่ทิ้งไว้, การทำให้เหมาะสมแบบกลุ่มอนุภาค (Particle Swarm Optimization) ซึ่งได้รับการดลใจจาก การหาอาหารของฝูงนก หรือ ฝูงปลา
แหล่งข้อมูลอื่น
- En.Wikipedia
- Obitko.com
- Imperial College เก็บถาวร 2011-09-28 ที่ เวย์แบ็กแมชชีน