ตอนที่แล้ว ได้พูดถึงแนวคิด GA

แนวคิดเบื้องหลัง GA ก็คือ การตัดต่อพันธุกรรม

ลองดูนะครับ สมมติว่าผมมีสูตรอาหาร 4 สูตร

ผมต้องมองว่า สูตรแต่ละสูตร ก็เปรียบเสมือนสายพันธุกรรม 

ในทุกสูตร บรรทัดแรก ให้หมายถึงใช้วัตถุดิบบางอย่างให้เหมือน ๆ กันทั้งหมด

เช่น บรรทัดแรก อาจหมายถึง พริกขี้หนูสวน

บรรทัดที่สอง อาจหมายถึง น้ำปลา

เช่น ในสูตร ผมอาจใส่เข้าไป 12 ชนิด (ก็คือ เกิดข้อมูล 12 บรรทัด)

แต่ละสูตร ดูตามแถวยืนนะครับ

สีต่าง ๆ ให้หมายถึงปริมาณ 

เมื่อลองปรุงอาหารตามสูตรเหล่านี้ แล้วก็ลองหาใครก็ได้ ให้มาลองชิมดู แล้วให้โหวต

ชอบ 2 สูตรไหนที่สุด ก็ให้สองสูตรที่ชอบที่สุด มาแต่งงานกัน เพื่อเกิดรุ่นลูก ซึ่งจะดึงยีนจากรุ่่นต้นตอไปคลุกเคล้ากัน

ดูข้างล่างสิครับ เราเปลี่ยนสูตรอาหารให้กลายเป็นสายพันธุกรรมไปแล้ว 

เป็นการเปลี่ยนโจทย์วิจัย ไปเป็นโจทย์พันธุกรรม

 

GA1 

สมมติว่า สูตรที่ 3 กับ 4 เป็นสูตรที่ดีที่สุด

จับสองสูตรนี้มาแต่งงานกัน แล้วเกิดรุ่นลูกหลายสุตร ซึ่งยีนของรุ่นลูก ต้องมาจากสูตรที่ 3 และ 4 เท่านั้น

(ข้อยกเว้นมีได้ครับ คือเมื่อเกิดการกลายพันธุ์ แต่ตอนนี้ จะยังไม่นำเรื่องนั้นมาปน) 

GA2 

ลองดูสีของรุ่นลูก ก็ล้วนแต่มาจากสูตร 3 และ 4 ของรุ่นก่อนหน้า 

เป็นไปได้ว่า รุ่นลูกจะออกมาดีกว่ารุ่นเดิม เราก็จะทำการทดลองแบบนี้ซ้ำต่อไป  

ตัวอย่าง

ถ้าผมลองสูตรทำเครื่องแกงสัก 15 สูตร แล้วพบว่า สูตรที่ 7 กับ 11 มีคุณภาพดี ผมก็ลองเอาสูตรที่ดีนี่มาลองคลี่ดู ซึ่งรายละเอียดในนั้นคงใส่ไปหลายอย่างมาก แต่เวลาดู เรามาดูทีละประเด็น

เช่น พอมาดู เอ๊ะ สูตรดีที่ว่า คือ สูตรที่ 7 ใช้พริกขี้หนูสวน 3 ขีด และสูตรที่ 11 ใช้พริกขี้หนูสวน 5 ขีด

ก็แสดงว่า พันธุกรรมที่ดี เกิดจากพริกขี้หนูสวน 3 ขีด หรือ 5 ขีด ก็ได้

ดังนั้น รุ่นลูก เราก็จะตะบี้ตะบันใช้แต่พริกขี้หนูสวน 3 หรือ 5 ขีดนี้เท่านั้น

ทั้งรุ่นต้นตอ และรุ่นลูกของสูตร 7-11 นี่ พอรวมกันเข้า ก็จะเหมือนเป็นสายตระกูลหนึ่งทีเดียว

แต่ไม่ใช่ว่า สูตรที่ดี จะต้องมีพริกมาก อาจมีสูตรที่ดีบางสูตร ไม่ต้องใส่พริกเลย เป็นอีกสายตระกูลหนึ่งออกไป โดยมีความโดดเด่นทัดเทียมกันก็ได้

คุณภาพของสูตร เป็นเรื่องของความลงตัวอย่างเหมาะเจาะของทุกอย่างที่เราใส่เข้าไป ไม่ใช่ว่าดีเพราะมีตัวใดตัวหนึ่งอยู่โดดเดี่ยวมาเป็นตัวกำหนด

ดังนั้น ในระยะยาว ก็อาจเป็นสองค่าย ค่ายหนึ่ง ไม่เผ็ดเลย ก็จะมีสูตรออกไปแนวนึง

อีกค่ายที่เผ็ด ก็จะมีสูตรออกไปอีกแนวนึง

โดยรายละเอียดทั้งสองค่าย อาจไม่มีส่วนคล้ายกันเลยก็ได้

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

นั่นคือ เขานำแนวคิดเรื่องการผสมคัดพันธุ์ต้นไม้หรือปศุสัตว์มาใช้อย่างเป็นระบบ

แบบนี้ มีข้อที่ดีมาก ๆ คือ ไม่ต้องเขียนโปรแกรม ไม่ต้องใช้คอมพิวเตอร์

แต่ต้องจดครับ

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

แนวคิดทางพันธุกรรมเขาใช้กันมานมนานหลายอย่างที่ได้ผลดี ก็สามารถปรับใช้ได้กับวิธีนี้ เช่น

-ยอมให้มีการผ่าเหล่าบ้าง แบบนาน ๆ ครั้ง (เช่น ลองเปลี่ยนเป็นใช้พริกขี้หนูสวน 10 ขีด หรือไม่ใส่พริกขี้หนูสวน)

-ไม่แต่งอยู่แต่ในวงศ์เดียวกัน ต้องมีข้ามไปแต่งข้ามตระกูลบ้าง

-โคลนนิงเป็นการย่ำอยู่กับที่ เพราะจะไม่มีโอกาสวิวัฒนาการเลย

-บางครั้ง ต้องยอมให้มีสายพันธุ์ที่ไม่น่าสนใจ ได้มีโอกาสแทรกเข้ามาบ้าง เพื่อเพิ่มความหลากหลายทางพันธุกรรม

ฯลฯ 

ลองมาอธิบายในมุมมองของการทำ optimization ทางคณิตศาสตร์กันบ้าง ว่าวิธีที่ดูพื้น ๆ นี้ จริง ๆ แล้วลึกซึ้ง

 

ถ้าไม่สนใจทฤษฎี หยุดอ่านแค่ตรงนี้เลยครับ

 

การหาสูตรตำรับ จัดเป็นปัญหาหนึ่งในตระกูล optimization โดยตัวที่ต้องจูนหา เรียกว่า parameter ซึ่งช่วงที่เป็นไปได้ทั้งหมดที่จะต้องจูนหาเพื่อให้ได้ระบบที่ลงตัวที่สุด (global optima) เรียกว่าอยู่ใน parameter space หรือ search space

วิธีการจูนมีคนคิดมากมาย โดยมักอิงอุปมาจากปรากฎการณ์ธรรมชาติ เอามาแปลงเป็นแนวคิดคณิตศาสตร์

เหมือนกันเปี๊ยบ กับที่พวกหนังจีนกำลังภายใน ใช้ปรากฎการณ์ธรรมชาติมาแปลงเป็นกระบวนท่าวิทยายุทธ

ปรกติแล้วการทำ optimization ที่ต้อง search ใน parameter space มักใช้กลยุทธอยู่ 2 แนว คือ จะจำผลการค้นครั้งเก่า หรือจะลืม

วิธีที่ลืมผลเก่า ๆ ก็ได้แก่การทำ random search (จะเป็นวิธีการเชิงสุ่มล้วน ๆ) ซึ่งไม่จำอะไรเลย

วิธีที่เหลือ จะจำอดีตได้ ซึ่งมีทั้งจำแบบระยะสั้น ระยะกลาง และจำยาวแบบติดแน่นตรึงตรา

จำติดแน่นก็ได้แก่ taboo search

จำระยะปานกลางได้แก่ ant algorithm ซึ่งใช้วิธี "ทิ้งฟีโรโมน" ไว้เป็นเบาะแสโดยให้ "กลิ่นจางเมื่อเวลาผ่านไป"

จำระยะสั้น ได้แก่วิธี deterministic ทั้งหลาย เช่น gradient search ซึ่งเอาข้อมูลล่าสุดมาเล็งทิศและกำหนดการย่างก้าวการค้นหาครั้งใหม่

หรือจะแบ่งตามนิสัยใจกว้าง-ใจแคบก็ได้

วิธีแบบ deterministic ส่วนใหญ่ มักใจแคบ ซึ่งมักเรียกกันว่า วิธีการเชิงละโมภ คือถ้าเห็นตำแหน่งไหนดี ก็วนเวียนย่ำอยู่แถว ๆ นั้น ไม่ไปไหนแล้ว คือปักธงว่าตรงไหนดี ก็เกาะธงไว้ไม่ยอมเขยื้อนไปไหนแม้แต่ก้าวเดียว

 เหมือนโยนลูกบอลล์ลงแอ่ง ท้ายสุด จะกลิ้งไปกองที่เดียวกันเสมอ ซึ่งน่าจะต่ำสุด

แต่ต่ำสุดในแอ่ง เป็นคนละเรื่องกับต่ำสุดนอกแอ่งที่อยู่ไกลออกไป 

(ตำแหน่งที่ดีที่ว่านี้ จะดีที่สุดในละแวกนั้น แต่จะดีที่สุดในโลกหรือไม่ ไม่มีใครรับประกัน ซึ่งมีชื่อเรียกเฉพาะว่า local optima) 

ส่วนกลุ่มวิธีที่ใจกว้าง เช่น simulated annealing หรือ  quantum tunneling จะใจถึงกว่า  ใจกว้างกว่า คือบางครั้ง สูตรแย่ลงกว่าเดิมนิดหน่อย ก็หยวน ๆ ยอมรับได้ว่าเป็นพัฒนาการรูปแบบหนึ่ง ที่ดีกว่าเดิม คือยอมทิ้งของดีในมือ ไปตั้งต้นใหม่อย่างระมัดระวัง

ดูเผิน ๆ เหมือนโง่ ไม่รู้จักเก็บของดีไว้ในมือ ช่างไม่รักดีเอาเสียเลย

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

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

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

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