Genetic Algorithm: เครื่องมือวิจัยสำหรับชาวบ้าน (3) - จบ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

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

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

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

 

ลองดูสีของรุ่นลูก ก็ล้วนแต่มาจากสูตร 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) ด้วยวิธีนี้ได้ผลมาตลอด แล้วทำไมคนจะหยิบยืมแนวคิดนี่ไปแก้ปัญหาขี้ผงขนาดไม่กี่สิบตัวแปรไม่ได้ ?

[Genuine]

สวัสดีค่ะอาจารย์

ตามอ่านบันทึกของอาจารย์แบบเงียบ ๆ ไร้ร่องรอยมานาน เจอบันทึก GA สามตอนที่เอา GA มาทำสูตรอาหาร :D 

หลาย ๆ ครั้งที่ mutation เป็นสิ่งที่ดีและทำให้เกิดสิ่งมีชีวิตใหม่ขึ้นมา mutant พวกนี้ก็ต้องไปแข่งขันกันต่อใน natural selection เราก็จะได้ผู้ชนะขยายเผ่าพันธุ์ต่อไป

สำหรับ GA ถ้าเข้าใจไม่ผิด (ถ้าผิดพลาดอย่างไรขออาจารย์แก้ไขด้วยนะคะ) หลักการของ GA คือการ sampling จาก population ต่อด้วย mutation เพื่อให้เกิด variation ซึ่งจะทำให้ natural selection ทำงานได้เต็มที่ สุดท้ายเราจะได้ optima เป็นผลลัพธ์ แต่ optima ตัวนี้ก็ต้องถูกส่งกลับไปใน population pool และผ่านระบบ GA ต่อไป

ขอบคุณสำหรับบันทึกดี ๆ ที่ทำให้ได้ทบทวนเรื่อง GA ค่ะ ^__^

 

[wwibul]

สวัสดีครับคุณ ณิชนันทน์

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

[Thomas]

Hi!

I am currently writing a (free and open) e-book called "Global Optimization - Theory and Application". It is about genetic algorithms, evolutionary algorithms, evolution strategy, leaning classifier systems, simulated annealing, and so on. I hope that I can make this topic more interesting for students and fellow researchers and help people to get started with it. Of course, the book is still very incomplete and probably has also errors, but I try to improve it very much.

You can find it at http://www.it-weise.de/projects/book.pdf, I will update it regularly.

Constructive criticism is always welcom, as well as new suggestions on what to include in the book.

Kind regards,
Thomas.

[wwibul]

Thanks for your invaluable link.

Read I will. Criticize I try.

[wwibul]

ดูแวบแรกนึกว่าโฆษณาขายของ "แหกด่าน" หลุดมาอาละวาด  แต่กลายเป็นโฆษณาหนังสือตำรา

ลองเข้าไปดูตามลิงค์ เอ๊ะ หนังสือเขาไม่เลวแฮะ

ใครสนใจก็รีบโหลดนะครับ ตามลิงค์ที่เขาทิ้งไว้... 

 

[wwibul]

สำหรับผู้สนใจ KM เรื่องการตลาดเชิงรุก...

• โฆษณาภาษาอังกฤษข้างบนนี้ ผมมองว่า น่าสนใจ
• น่าสนใจว่าเขาสามารถข้ามกำแพงวัฒนธรรมเรื่องภาษา  มาหาคนที่เขาไม่เคยรู้จัก และอ่านภาษาของอีกฝ่ายแทบไม่ออกได้อย่างไร ?
• ผมเดาว่า เขาคงใช้ตัวค้นเช่นกูเกิลมาช่วย
• แต่แม้กระนั้น ยิ่งคิด ก็ยิ่งทึ่งครับ ว่าเขาเจาะจงทะลวงเข้ามาตรงนี้ได้อย่างไร ?
  

 

[wwibul]

ต่อครับ

• ผมลองพลิก ๆ ดูหัวข้อที่เขาเขียน ผมว่าเป็นที่เปิดหูเปิดตามาก บังเอิญผมเคยใช้เทคนิคบางอย่างที่เขาไม่ได้อ้างอิงถึง ซึ่งอาจเป็นงานวิจัยที่หลงหูหลงตาเขาไปหน่อย (อยู่ในวารสารของทางวิศวเคมี) ก็เลยอีเมล์ไปหาเมื่อคืนวันที่ 28 มิ.ย.
• ปรากฎว่า เขาปรับเพิ่มเนื้อหาขึ้นมาหนึ่งบทเต็มในหัวข้อดังกล่าว และเจาะลึกสืบสาวต่อได้อย่างน่าทึ่ง ปรับแก้เพิ่มเติมเสร็จใน 3-4 วัน
• เห็นแล้วยิ่งทึ่งครับ ว่าเขาทำได้ยังไง...
  

 

[นิสิตป.โท]

ขอคารวะและขอบคุณมากๆสำหรับบทความและหนังสือ กำลังจะสอบ Data mining ค่ะ (ได้อ่านก่อนสอบ โชคดีจริงๆ เย้)

Hi Mr.Thomas, I am studying on MIS. I would like to say thank you for sharing the book!! very useful :D

[chakrit]

ตามมาอ่านครับ

อ่านแล้วได้ประโยชน์ในการที่จะทำ e-book ซึ่งผมก็อยากจะทำเหมือนกัน

ช้าไปหน่อย แต่ก็ดีกว่าไม่ได้เริ่มต้นครับ