Python Genetic Algorithm - เลือกทำเลร้านขายลูกชิ้นในม็อบด้วย AI 😂
Tags: python, tutorial, machinelearning, datascience
Published: 2020-10-25 12:09:48

ขอเริ่มจากเล่านิทานก่อนนะครับ 555 _สมมุติว่าเราอยู่ในองค์กรสายลับระดับชาติในชื่อ **"ภาคีลูกชิ้นทอด"** ที่กำลังวางแผนแทรกซึมเข้าไปในม็อบเพื่อขายลูกชิ้นและไก่ทอดในม็อบให้ได้มากที่สุด แน่นอนว่าเมื่อเราส่งสายลับมืออาชีพของเราลงไปแล้ว ไม่ว่าใครก็ต้องอดใจไม่ไหว ด้วยลูกชิ้นทอดและน้ำจิ้มสูตรเด็ด ที่ส่งกลิ่นหอมแพร่กระจายออกไปเป็นกิโล **ทำให้ผู้ร่วมชุมนุมที่อยู่ในรัศมีทุกคนจะตามกลิ่นมาซื้ออย่างแน่นอน!**_

_เนื่องจากองค์กรได้รับข้อมูลจากสายสืบถึงพื้นที่ที่มีความเป็นไปได้ที่จะจัดตั้งม็อบก่อนใครเสมอ จึงสามารถคาดเดาตำแหน่งของคนที่เข้าร่วมชุมนุมล่วงหน้าได้อย่างแม่นยำ โดยเราได้รับมอบหมายให้หาจุดที่จะส่งสายลับลูกชิ้นทอดทั้ง 10 คน **เข้าไปประจำการล่วงหน้าตามจุดต่าง ๆ 10 จุด ที่จะสามารถทำยอดขายรวมได้ที่สุด** ชะตากรรมของทั้งประเทศอยู่ในมือของเราแล้ว!!_

_โชคดีที่เรารู้จักเทคนิคที่เรียกว่า **Genetic Algorithm** จึงสามารถนำมาใช้หาตำแหน่งที่ดีได้เสมอ ทำให้องค์กรสามารถทำภารกิจแทรกซึมได้สำเร็จทุกครั้งไป..._

...ในบทความนี้ มาดูกันว่า Genetic Algorithm คืออะไร แล้วมันจะช่วยองค์กรได้อย่างไรนะครับ??

![cover.jpeg](https://dev-to-uploads.s3.amazonaws.com/i/chjb3jbk54q6hd48xxaf.jpeg)
_จาก [https://mgronline.com/live/detail/9630000108268](https://mgronline.com/live/detail/9630000108268)_

_note: สำหรับท่านที่งง ๆ ว่าลูกชิ้นทอดเกี่ยวอะไร ลองอ่านเนื้อเรื่องเพิ่มเติมได้ครับ 5555: [เปิดใจ CIA หน่วยเคลื่อนที่เร็วประจำม็อบ “ลูกชิ้นทอด-ไก่ทอด” ยอดขายพุ่งเฉียดวันละหมื่น!
](https://positioningmag.com/1302924)_

#Genetic Algorithm
พักเรื่องนิทานเอาไว้สักครู่ มารู้จักกับ Genetic Algorithm กันก่อน Genetic Algorithm (GA) เนี่ยก็เป็น algorithm อย่างหนึ่งที่เอาไว้ใช้หาคำตอบ (solution) ที่ให้ค่าของผลลัพธ์มากที่สุด จริง ๆ มันก็คือ algorithm สำหรับการทำ optimization อย่างหนึ่งนั่นเองครับ

#ตัวอย่าง Use Case
**การหาเส้นทางนำของคลังสินค้าไปส่งตามจุดต่าง ๆ โดยใช้ต้นทุนน้อยที่สุด** 
เราก็จะนิยามโจทย์ให้ Genetic Algorithm (GA) ว่าให้หา **คำตอบ (solution)** ซึ่งก็คือลำดับการเดินทาง เช่น [คลังสินค้า, ร้าน1, ร้าน7, ร้าน3, คลังสินค้า, ร้าน5, ...] ออกมา โดยต้องเป็นคำตอบที่ใช้ **ต้นทุน (cost)** หรือ objective value น้อยที่สุด ซึ่งอาจจะเป็นค่าน้ำมันหรือเวลา ก็ตามแต่ที่เราจะกำหนด จากนั้น GA ก็จะไปทำการลองผิดลองถูกเพื่อหาคำตอบที่ดีที่สุดที่มันหาได้มาให้เราครับ

![example-routing.png](https://dev-to-uploads.s3.amazonaws.com/i/njhunpz0z4mfhrz48ur5.png)
_จาก [https://zenodo.org/record/1247385#.X5QTB50zZD8](https://zenodo.org/record/1247385#.X5QTB50zZD8)_

ลองมาดูตัวอย่างที่ให้ความรู้สึกเป็น AI มากขึ้นหน่อยดีกว่าครับ

**MarI/O bot เล่นเกม Mario** 
ความน่าสนใจของงานนี้อยู่ตรงที่ว่า คนสร้างไม่ได้สอนตัว AI เลยแม้แต่น้อย ว่ากดปุ่มอะไรแล้วจะเกิดอะไร หรือกลไกของเกมส์ Mario เป็นอย่างไร หรือโดนโจมตี/เก็บของแล้วจะเป็นอะไร นั่นคือเริ่มต้นมา AI ไม่รู้อะไรเลย แต่มันจะค่อย ๆ ลองเล่น ลองผิดลองถูกไปเรื่อย ๆ จนเก่งขึ้นตามภาพครับ

![example-mario.gif](https://dev-to-uploads.s3.amazonaws.com/i/x4rpwnmqvxxhbzbb512i.gif)
_จาก [https://www.youtube.com/watch?v=qv6UVOQ0F44](https://www.youtube.com/watch?v=qv6UVOQ0F44)_

เบื้องหลังความเทพของ bot ตัวนี้ก็คือ **Genetic Algorithm** นี่แหละ เอาไปรวมกับ **Neural Network** เพื่อให้มันสามารถอ่าน input จาก pixel บนหน้าจอ แล้วทำหน้าที่เป็นเหมือนกับสมองในการสั่งการตัว Mario ว่าเมื่อเห็นภาพบนหน้าจอแบบนี้ แล้วจะต้องกดปุ่มอะไรต่อ

การนิยามโจทย์สำหรับ GA ก็จะเป็นว่า **คำตอบ (solution) ที่ต้องการก็คือ โครงสร้างของ Neural Network ที่สามารถควบคุม Mario ได้ดีที่สุด** ทำให้ Mario สามารถเดินทางไปได้ **เป็นระยะทางไกลที่สุด (objective value)** นั่นเองครับ

แล้วก็ยังมีตัวอย่างน่าสนใจอีกมาก ที่ GA สามารถทำได้ ถ้าสนใจลองหาเพิ่มเติมได้ครับ
keywords: `genetic algorithm`, `evolutionary algorithm`
อันนี้ลองหาใน Youtube มาไว ๆ ครับ

{% youtube zIkBYwdkuTk %}

{% youtube Aut32pR5PQA %}

{% youtube W15wZaWj6hk %}


จะเห็นได้ว่า GA สามารถเอาไปประยุกต์ใช้กับปัญหาได้หลากหลายมาก ถ้าเราสามารถนิยามปัญหาของเราเป็นการหาคำตอบที่ดีที่สุด (เท่าที่จะหาได้) จากบรรดาคำตอบที่เป็นไปได้ทั้งหมด (search space) เช่น ใช้ต้นทุนน้อยสุด หรือให้ค่าความเหมาะสม (fitness) มากที่สุด

#Genetic Algorithm ทำงานอย่างไร
ทีนี้ แล้วอะไรล่ะที่ทำให้ GA มันเทพขนาดนั้น ถึงขนาดนำมาควบคุม Mario หรือช่วยสายลับลูกชิ้นทอดของเราได้เลย ...เริ่มจากมาทำความเข้าใจหลักการทำงานของ algorithm กันก่อนนะครับ

_Genetic Algorithm (GA) จะใช้แนวคิดคล้าย ๆ กับการวิวัฒนาการของสิ่งมีชีวิตเลยครับ คือเป็น Natural Selection สิ่งมีชีวิตที่อ่อนแอจะถูกกำจัด ตัวที่แข็งแกร่งจะอยู่รอด และได้สืบพันธุ์ต่อไป แล้วก็จะมีกลไกของการกลายพันธุ์ (mutate) ของ Gene ทีละนิดในแต่ละครั้งที่สืบพันธุ์ เหมือนเป็นการลองผิดลองถูก คล้าย ๆ กับที่มนุษย์ค่อย ๆ มีการกลายพันธุ์/วิวัฒนาการ ให้หางของเราหายไปทีละนิดจนเป็นมนุษย์อย่างในปัจจุบัน คือค่อย ๆ สร้างความแตกต่างออกไปจากพ่อ-แม่ ของมัน เพื่อสร้างความหลากหลายครับ_

_มาทบทวนวิชาชีวะมัธยมกันสักหน่อยนะครับ 555_

###โครโมโซม (Chromosome)
โดยสิ่งมีชีวิตแต่ละตัวจะมี **สารพันธุกรรม (Chromosome)** อยู่ครับ สิ่งนี้จะเป็นตัวกำหนดลักษณะของมัน ซึ่งสิ่งนี้ สำหรับใน GA ก็คือตัว **คำตอบ** ที่เราจะให้มันหานั่นเองครับ เราอยากให้ Algorithm มันค่อย ๆ พัฒนา Chromosome ของมันไปเรื่อย ๆ จนในท้ายที่สุดจะได้ Chromosome ที่แข็งแกร่งที่สุดที่อยู่รอดออกมาเป็นคำตอบ ก็คือ Chromosome ที่ทำให้ได้ cost ต่ำที่สุด หรือมีค่า fitness สูงสุด ตามที่เราคุยกันไปตอนต้นนั่นเองครับ

ถ้าเป็นโจทย์การหาเส้นทางฯ Chromosome 1 อันก็อาจจะเป็น
**ลำดับของการเดินทาง 1 รอบ [คลังสินค้า, ร้าน1, ร้าน2, คลังสินค้า, ร้าน3]**

หรือถ้าเป็นโจทย์เกมส์ MarI/O Chromosome 1 อันก็อาจจะเป็น **โครงสร้าง Neural Network แบบหนึ่ง** อย่างนี้เป็นต้น

###การคัดเลือกโดยธรรมชาติ (Natural Selection)
ทีนี้ในการทำ GA เราก็จะมีกลไกในการคัดเลือกตัวที่เก่งที่สุดอยู่ครับ โดยเราสร้าง **ประชากร** ของสิ่งมีชีวิตขึ้น แบ่งเป็น *รุ่น (generation)* เริ่มจากรุ่น 0 หรือ generation 0 เราจะสร้าง Chromosome ขึ้นมาเยอะ ๆ แบบสุ่มมั่ว ๆ เลยนะครับ สมมุติว่าสร้างมา 500 Chromosomes โดย Chromosome แต่ละอันก็จะแทนสิ่งมีชีวิต 1 ตัว ที่เกิดมาแบบสุ่ม อาจจะมีทั้งตัวที่แข็งแกร่ง และตัวที่อ่อนแอปน ๆ กันอยู่

จากนั้นเราก็จะทำการคำนวนครับว่า Chromosome แต่ละอันมีความแข็งแกร่ง หรือ **ความเหมาะสม (Fitness)** มากแค่ไหน ออกมาเป็นตัวเลข 1 ตัวสำหรับแต่ละอัน เช่น Mario ตัวนี้เดินไปได้ไกล 50 เมตร แบบนี้เป็นต้น

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

พอเรากำจัดตัวที่อ่อนแอออกไปแล้ว เราก็จะให้ตัวที่เหลือรอดเนี่ย ได้มาทำการ **สืบพันธุ์** เพื่อสร้างลูกหลานและส่งต่อ Chromosome ที่ดีต่อไปครับ (เดี๋ยวจะอธิบายในส่วนของการสืบพันธุ์เพิ่มเติมครับ)

แล้วเราก็จะทำอย่างนี้ไปเรื่อย ๆ ใน generation ต่อ ๆ ไป ทำให้ Chromosome หรือคำตอบที่ดีแต่ละอันที่สุ่มมาได้เกิดการผสมกันไปมา ถ้าผสมแล้วไม่ดีก็จะถูกกำจัดออก แล้วเหลือไว้แต่อันที่ดี เพื่อไปผสมกันให้ดีขึ้นไปอีกเรื่อย แล้วสุดท้ายคำตอบที่ดีที่สุดที่เราได้จาก Algorithm ก็คือ Chromosome ที่ให้ค่า Fitness ดีที่สุดใน **generation สุดท้าย** นั่นเองครับ

![natural-selection.png](https://dev-to-uploads.s3.amazonaws.com/i/ire19k55210d60w3iutb.png)
_ภาพการเกิด Natural Selection โดยยีราฟตัวที่มี Chromosome คอสั้นจะโดนแย่งอาหาร และค่อย ๆ อดอาหารตายไป ทำให้ยีราฟที่มี Chromosome คอยาวอยู่รอด และสืบพันธุ์ส่งต่อ "ความคอยาว" ให้รุ่นลูกหลานถัดไป จนยีราฟทุกตัวใน generation หลังก็จะคอยาวกันหมด จาก [https://www.toppr.com/content/story/amp/natural-selection-and-polymorphism-73211/](https://www.toppr.com/content/story/amp/natural-selection-and-polymorphism-73211/)_

###การสืบพันธุ์ และการกลายพันธุ์ (Reproduction and Mutation)
การสืบพันธุ์ (Reproduction) ถ้าเป็นตามที่เราเรียนมาก็คือเราจะเอา Chromosome จากพ่อกับแม่ มา crossover กัน โดยสลับหน่วยย่อยของ Chromosome กันบางส่วนเพื่อแลกเปลี่ยนสารพันธุกรรมกัน ก่อนจะส่งต่อไปให้กับรุ่นลูกใช่ไหมครับ

![crossover.jpeg](https://dev-to-uploads.s3.amazonaws.com/i/qajsakrvl1hfjq28m8pn.jpeg)
_Chromosomes Crossing Over จาก [https://ib.bioninja.com.au/standard-level/topic-3-genetics/33-meiosis/crossing-over.html](https://ib.bioninja.com.au/standard-level/topic-3-genetics/33-meiosis/crossing-over.html)_

ใน Genetic Algorithm เราก็จะทำเช่นเดียวกันครับ คือเราเอาตัวที่แข็งแกร่ง 2 ตัวมาทำการแลกเปลี่ยนบางส่วนของคำตอบกัน โดยคาดหวังว่ามันอาจจะได้ Combination ที่ดีขึ้นออกมาในรุ่นลูกครับ

![reproduction.jpg](https://dev-to-uploads.s3.amazonaws.com/i/ilozhusqghonh3r9bj3o.jpg)
_ภาพการ cross chromosomes แบบหนึ่ง ใน GA จาก [https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.htm](https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.htm)_

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

![mutation-swap.jpg](https://dev-to-uploads.s3.amazonaws.com/i/mgssre2w3cs7jvn6e8ko.jpg)
_ภาพ Swap Mutation จาก [https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm](https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm)_

###สรุปกระบวนการ Genetic Algorithm
1. เริ่มจากสร้างประชากร Chromosomes ขึ้นมาแบบสุ่ม สมมุติ 500 ตัว
2. คำนวนค่า Cost หรือ Fitness ของ Chromosome แต่ละตัว
3. ถ้าเงื่อนไขในการหยุดเป็นจริง ให้หยุดทำงาน ถ้ายังไม่จริงก็ทำต่อ
4. กำจัดตัวที่อ่อนแอออกไป สมมุติครึ่งหนึ่ง ก็จะเหลือตัวที่แข็งแกร่งอยู่ 250 ตัว
5. เอาตัวที่เหลืออยู่มาสืบพันธ์และสุ่มกลายพันธุ์ เพื่อเพิ่มจำนวนของประชากรให้ Chromosomes ทั้งหมดกลับมามีจำนวน 500 เท่าเดิม
6. ทำซ้ำตั้งแต่ข้อ 2

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xtfrtm512jyhv22aco7c.png)
_จาก [https://www.researchgate.net/figure/Genetic-algorithm-flowchart_fig2_263224226](https://www.researchgate.net/figure/Genetic-algorithm-flowchart_fig2_263224226)_

_ผมละรายละเอียดบางส่วนเอาไว้ คิดว่าไปดูในโค้ดน่าจะเห็นภาพมากกว่าครับ_

#แล้วจะขายลูกชิ้นที่ไหนดี...
ก่อนที่ภาคีลูกชิ้นทอดของเราจะรอนานไปมากกว่านี้ ถ้าพอจะเข้าใจแนวคิดของ Genetic Algorithm คร่าว ๆ แล้ว เรามาเริ่มเขียนโค้ดเพื่อช่วยองค์กรหาตำแหน่งขายลูกชิ้นกันดีกว่าครับ

โค้ดเต็ม ๆ ทั้งหมดดูได้ใน Google Colab ตามลิ้งนี้เลยครับ สามารถเปิดขึ้นลองรันดู ไปพร้อม ๆ กับอ่านบทความได้เลยครับ [https://colab.to/1K6qosp_HcGmgBy8dVqSlpooYLBSeEnbA](https://colab.to/1K6qosp_HcGmgBy8dVqSlpooYLBSeEnbA)

ก่อนอื่นกำหนดค่าคงตัวต่าง ๆ กันก่อน
- _POPULATION_SIZE:_ ให้ในหนึ่ง Generation มีประชากรเป็น **500 chromosomes**
- _N_SHOPS:_ ให้ Chromosome 1 ตัว หรือก็คือ คำตอบ 1 คำตอบที่เราต้องการหา ประกอบด้วยตำแหน่ง xy ของร้านค้า จำนวน **10 ร้านค้า** เพราะเรามีสายลับทั้งหมด 10 คน
- _EFFECT_RADIUS:_ ให้รัศมีของกลิ่นหอมกระจายไปไกล เป็นระยะทาง **1.0 หน่วย** (Euclidean Distance = 1.0)
- _CAPACITY:_ ให้ร้านค้า 1 ร้าน สามารถขายให้ได้แค่ **ไม่เกิน 150 คนเท่านั้น**

##ข้อมูลที่อยู่ของคนในม็อบ
เนื่องจากเราไม่มีข้อมูลจริง ก็จะเริ่มจากสร้างข้อมูลตำแหน่งของคนในม็อบขึ้นมาก่อนได้เป็นแบบนี้นะครับ สมมุติว่า 1 จุดแทน 1 คนยืนอยู่เลย จะมีอยู่ 3 กลุ่ม clusters ขนาดเล็ก กลาง ใหญ่ รวมทั้งหมด 1,250 คนครับ

![colab-mobdata.png](https://dev-to-uploads.s3.amazonaws.com/i/k8jtzfour2u3gd3dmmf4.png)

_note: รายละเอียดว่าสร้างออกมาแบบนี้ได้ยังไงไม่ได้น่าสนใจมากขออนุญาตข้ามนะครับ สามารถไปดูได้ในโค้ดเต็มครับ_

##ฟังก์ชันต่าง ๆ
สำหรับ project นี้ไม่ได้ซับซ้อนมากนัก ผมจะขอเริ่มแบบง่าย ๆ โดยการ implement logic ของส่วนต่าง ๆ ที่ยุ่ง ๆ ให้เป็นฟังก์ชันย่อย ๆ  ออกมาตามนี้ครับ
1. ฟังก์ชัน _get_customers(positions, mob)_ สำหรับรับตำแหน่งของร้านค้าและม็อบ เพื่อไปคำนวณว่าเมื่อตั้งร้านตามตำแหน่งต่อไปนี้แล้ว คนไหนบ้างในม็อบจะมาซื้อ และเป็นจำนวนเท่าไหร่ในแต่ละร้าน
2. ฟังก์ชัน _create_initial_population()_ สำหรับสุ่มสร้าง population ของ chromosomes เริ่มต้น
3. ฟังก์ชัน _calculate_objective(mob, population)_ สำหรับคำนวณค่า fitness
4. ฟังก์ชัน _reproduce(parents, count)_ สำหรับนำ population ที่ผ่านการคัดเลือกมาเป็น parents เพื่อทำการสืบพันธุ์และกลายพันธุ์ต่อไป

###_get_customers(positions, mob)_
ฟังก์ชันนี้ใช้สำหรับคำนวณว่าเมื่อตั้งร้านตามตำแหน่ง `positions` แล้วใครในม็อบจะมาซื้อบ้าง (เลข index ของ array mob) และได้จำนวนการขายของแต่ละร้านเท่าไหร่ โดยที่ `mob` คือ array ของตำแหน่ง (x, y) ของคนในม็อบ

![colab-script-get_customers.png](https://dev-to-uploads.s3.amazonaws.com/i/hllpjzqwm9byp1ao281r.png)

1. ผมวนลูปเพื่อเอาตำแหน่งของร้านค้า `p` มาทีละร้าน จาก `positions`
2. คำนวณระยะห่างของแต่ละคนในม็อบกับร้าน `p` (Euclidean Distance)
3. เลือกคนที่อยู่ใกล้ที่สุดมาจำนวนไม่เกิน 150 คน (เท่ากับจำนวนคนที่ร้าน 1 ร้านสามารถขายให้ได้ _CAPACITY = 150_) และอยู่ห่างจากร้าน `p` เป็นระยะทางไม่เกิน 1.0 หน่วย (คือระยะทางที่กลิ่นหอมจากร้าน `p` สามารถลอยไปได้ไกลที่สุด _EFFECT_RADIUS = 1.0_) เราจะนับไปเลยว่าคนพวกนี้จะเข้ามาซื้อร้าน `p` เพราะไม่มีใครทนต่อกลิ่นหอมได้
4. นับจำนวนของคนที่ผ่านเงื่อนไขในข้อ 3 แล้วเพิ่มไปใน customer_counts ของร้าน `p` เพื่อใช้บอกว่าร้าน `p` ได้ลูกค้าไปจำนวนกี่คน
5. ลบคนที่เป็นลูกค้าของร้าน `p` ไปแล้วออกจาก mob นั่นคือเราให้คนคนหนึ่งซื้อลูกชิ้นทอดได้แค่ครั้งเดียว จากร้านเดียวเท่านั้น

หลังจบการทำงาน ฟังก์ชัน _get_customers(positions, mob)_ จะ return output ออกมา 2 อย่าง คือ
- `customer_indexes:` เป็น array 1 มิติ เก็บ index ของคนในม็อบ ที่ได้ซื้อลูกชิ้นทอดจากร้านใดร้านหนึ่งไป
- `customer_counts:` เป็น array 1 มิติ เป็นจำนวนของลูกค้าที่เข้าไปซื้อลูกชิ้นทอดจากร้านแต่ละร้าน มีขนาดเท่ากับจำนวนร้านค้าที่ใส่เข้าไป (`positions`)

เหตุผลที่ผมเริ่มทำฟังก์ชันนี้ก่อน ก็เพื่อให้สามารถเขียนฟังก์ชัน _report(mob, positions)_ ที่จะ report performance ของแต่ละร้านใน `positions` ว่าขายได้เท่าไหร่ และ plot ออกมาเป็นกราฟให้ดูง่าย จะได้เขียนโค้ดให้เห็นภาพได้มากขึ้นครับ

ทดสอบฟังก์ชัน report()

![colab-report-sample.png](https://dev-to-uploads.s3.amazonaws.com/i/zz0v51o1w883dhr64vrv.png)

_จุดสีน้ำเงิน_ คือคนที่ยังไม่ได้เป็นลูกค้าร้านใด
_จุดสีเขียว_ คือคนที่เป็นลูกค้าซื้อไปเรียบร้อยแล้ว
_กากบาทสีแดง_ คือตำแหน่งร้านค้าที่ input เข้าไป (`positions`)
_วงกลมสีแดง_ คือรัศมีของกลิ่นหอมแต่ละร้าน (มีรัศมีเท่ากับ _EFFECT_RADIUS = 1.0_)

###_create_initial_population()_
ฟังก์ชันนี้ใช้สำหรับสร้าง population ของ Chromosomes เริ่มต้นโดยสุ่มค่า xy ขึ้นมา การ implement ก็ค่อนข้างง่าย ก็คือวนลูปเป็นจำนวนเท่ากับจำนวนของประชากรที่เราอยากได้ ซึ่งผมกำหนดไว้เป็น 500 ตัว (_POPULATION_SIZE = 500 Chromosomes_) สำหรับ Chromosome แต่ละตัว ก็จะทำการสุ่มตำแหน่งพิกัด xy ของร้าน 10 ร้าน (_N_SHOPS = 10_) ออกมา แทนคำตอบ 1 คำตอบ โดยใช้ฟังก์ชัน `np.random.uniform()` ของ library NumPy ในการสุ่มเลขแบบ uniform

![colab-script-create_initial_population.png](https://dev-to-uploads.s3.amazonaws.com/i/3jvlupl08fjsrtxhme3g.png)

ตัวอย่าง Chromosomes 5 ตัวแรกใน `population` ก็คือเป็น array ของ (x, y) ทั้งหมด 10 ตัว

![colab-population-sample.png](https://dev-to-uploads.s3.amazonaws.com/i/zc44o37ybsmnbhf5p963.png)

ลองเอา population ที่สร้างได้ ตัวที่ 0 กับตัวที่ 1 มา plot ดู ก็จะเห็นว่า แต่ละตัวมีตำแหน่งของร้านจำนวน 10 ร้าน และกระจายกันแบบมั่ว ๆ

![colab-chromosomes-sample.png](https://dev-to-uploads.s3.amazonaws.com/i/x6yh9oe35oxpn3d559lo.png)

###_calculate_objective(mob, population)_
ฟังก์ชันนี้ใช้สำหรับคำนวณค่า Fitness ของ Chromosome แต่ละตัวจากใน population ซึ่ง Fitness ของ Chromosome แต่ละตัว ก็คือยอดขายรวมของแต่ละร้านใน Chromosome นั้นนั่นเอง

เนื่องจากเรามีฟังก์ชัน _get_customers()_ ที่สามารถคำนวณ `customer_counts` ของร้านค้าแต่ละร้านใน 1 Chromosome ได้อยู่แล้ว จึงสามารถเอามาใช้ได้ตามนี้ครับ

![colab-script-calculate_objective.png
](https://dev-to-uploads.s3.amazonaws.com/i/i35qqm0cz8suztf3o2db.png)

ไป ๆ มา ๆ เหมือนว่าฟังก์ชันที่ยากที่สุดจะเป็น _get_customers()_ นี่แหละครับ 555

###_reproduce(parents, count)_
สุดท้ายก็คือฟังก์ชัน _reproduce()_ ครับ โดยฟังก์ชันนี้มี 2 ขั้นตอนคือขั้นตอนการสุ่ม crossover chromosomes ทีละคู่ และขึ้นตอนของการสุ่มกลายพันธุ์ ผมจึงสร้าง 2 ขั้นตอนนั้นออกมาเป็นอีก 2 ฟังก์ชันย่อย ๆ คือ _cross_chromosome(a, b)_ และ _mutate_population(population, prob, scale)_ ตามนี้ครับ

####_cross_chromosome(a, b)_
สุ่มตำแหน่งที่จะทำการ cross โดยใช้ `np.random.choice()` โดยผลลัพธ์จะออกมาเป็น array ของค่า Boolean True หรือ False อย่างใดอย่างหนึ่ง โดยในตำแหน่งร้านที่ `will_cross` เป็น True ก็จะถูกสลับระหว่าง chromosome a และ chromosome b

![colab-script-cross_chromosome.png](https://dev-to-uploads.s3.amazonaws.com/i/vqfn4uglpth9z7oj1sx5.png)

ตัวอย่างผลลัพธ์การ cross ระหว่าง chromosome a และ b
![colab-crossing-sample.png](https://dev-to-uploads.s3.amazonaws.com/i/apzsu7rlwpmcxnbvkmp9.png)

####_mutate_population(population, prob, scale)_
ในส่วนของการกลายพันธุ์ ผมใช้แบบง่าย ๆ คือเป็นการเลื่อนตำแหน่ง (x, y) ของร้านค้าแบบสุ่ม
ขั้นแรกผมสุ่มก่อนว่าจะให้เกิดการกลายพันธุ์ที่ Chromosome ตัวไหนบ้างจากใน `population` โดยมีความน่าจะเป็นของการกลายพันธุ์เท่ากับ `prob` (_default `prob` = 0.2_)

จากนั้นก็สุ่ม `noise` ขึ้นมา คือเป็นค่าสุ่มเล็ก ๆ ที่จะเอาไปบวกกับ (x, y) ของร้านใน `population` โดยใช้ `np.random.normal` ที่จะสุ่มค่าตัวเลขออกมาจาก normal distribution โดยใช้ `scale` = 0.3 (ยิ่งเยอะ ยิ่งมีโอกาสที่ค่าที่สุ่มออกมาจะเลขใหญ่ ๆ) โดย `noise` ในตำแหน่งที่เราเลือกว่าจะไม่กลายพันธุ์ ก็จะ set ให้เป็น 0 ไป จากนั้นก็เอา `noise` ไปบวกเข้ากับ `population` 

![colab-script-mutate_population.png](https://dev-to-uploads.s3.amazonaws.com/i/uv7mwd2ot7y1kon9k9o1.png)

ตัวอย่างของ chromosome ที่ถูกทำให้กลายพันธุ์ จะเห็นว่าบางร้านก็ถูกเลื่อนออกไปไกลจากเดิม แต่บางร้านก็ไม่ไกล คละกันไป

![colab-mutation-sample.png](https://dev-to-uploads.s3.amazonaws.com/i/n42ephenap0x1ic0iv2j.png)

####ฟังก์ชันหลัก _reproduce(parents, count)_
เมื่อเราได้ฟังก์ชันย่อยทั้งสองครบแล้ว ตอนนี้เราก็สามารถเขียน _reproduce()_ ได้ดังนี้

![colab-script-reproduce.png](https://dev-to-uploads.s3.amazonaws.com/i/03r43u4wh32xytyo63z6.png)

ก็คือวนลูปเพื่อสุ่มหยิบ chromosomes มาทีละคู่ จาก `parents` เอามา cross กันด้วย _cross_chromosome()_ จากนั้นก็เก็บผลลัพธ์ไว้ใน `children` จนได้จำนวนตามที่ต้องการคือเท่ากับ `count`

จากนั้นก็เอา `children` ไปสุ่มกลายพันธุ์ด้วย _mutate_population()_ ที่เราสร้างเอาไว้ แล้วก็ return `children` ซึ่งเป็น array ของลูกที่ได้กลับไป

เท่านี้เราก็ได้ฟังก์ชันทั้งหมดที่ต้องการเรียบร้อยแล้ว เขียนไปเขียนมาก็เริ่มยาวแล้วเหมือนกัน 555 ต่อไปก็จะเขียนโค้ดการทำงานหลักที่ใช้หาคำตอบกันครับ

##เขียนโค้ดการทำงานหลักเพื่อหาคำตอบ...สักที
เมื่อยึดตามกระบวนการทำงานของ Genetic Algorithm ที่เราสรุปเอาไว้ด้านบน เราก็พอจะร่างโครงขึ้นมาเป็น outline ได้ประมาณนี้

```python
# 1. สร้าง population เริ่มต้น

generation = 0
while True:
    # 2. คำนวณ fitness
    objective = ...

    # 3. ตรวจสอบเงื่อนไขการหยุดการทำงาน

    # 4. กำจัดตัวที่อ่อนแอ คัดเลือกตัวที่แข็งแกร่ง
    population = ...

    # 5. สืบพันธุ์ และกลายพันธุ์
    population = ...

    print(f'generation {generation:2}: {objective.max()}')
    generation += 1
```

ทีนี้เราก็เติมโค้ดแต่ละส่วนลงไปด้วยฟังก์ชันที่เราเขียนเอาไว้แล้ว ตามนี้
1. ใช้ฟังก์ชัน _create_initial_population()_
2. ใช้ฟังก์ชัน _calculate_objective()_
3. ...ขออนุญาตข้ามไปก่อน
4. ให้ใช้ค่า fitness จากตัวแปร `objective` ในการเรียงลำดับจากมากไปน้อย แล้วตัดให้เหลือแค่ครึ่งแรก ที่มีค่า fitness สูง
5. ใช้ฟังก์ชัน _reproduce()_ ได้ `children` ออกมา จากนั้นเอา `children` ไปรวมกับ `population` ที่เหลืออยู่

ได้เป็นโค้ดที่สมบูรณ์มากขึ้นดังนี้

```python
# 1. สร้าง population เริ่มต้น
np.random.seed(random_state)
population = create_initial_population()

generation = 0
while True:
    # 2. คำนวณ fitness
    objective = calculate_objective(mob, population)

    # 3. ตรวจสอบเงื่อนไขการหยุดการทำงาน

    # 4. กำจัดตัวที่อ่อนแอ คัดเลือกตัวที่แข็งแกร่ง
    rank_indexes = (-objective).argsort()[:int(POPULATION_SIZE/2)]
    population = population[rank_indexes]

    # 5. สืบพันธุ์ และกลายพันธุ์
    children = reproduce(population, count=POPULATION_SIZE/2)
    population = np.vstack((population, children))

    print(f'generation {generation:2}: {objective.max()}')
    generation += 1
```
ซึ่งจริง ๆ โค้ดด้านบนนี้ก็สามารถรันได้จริงแล้วนะครับ ทำงานได้ถูกต้องทุกอย่าง ปัญหาอย่างเดียวก็คือมันไม่รู้ว่าจะต้องหยุดทำงานเมื่อไหร่ ถ้าลองสั่งรันดูมันก็จะทำงานไปเรื่อย ๆ ครับ 555

ดังนั้นเราต้องเขียนส่วนที่ 3 ที่เราได้ข้ามไป เพื่อบอกมันว่าเมื่อไหร่ถึงจะหยุดได้
ซึ่งจริง ๆ สามารถทำได้หลายวิธีมากครับ เราอาจจะบอกว่าให้มันทำไปเป็นจำนวน 100 generations แล้วหยุดก็ได้
วิธีที่ผมชอบใช้ก็คือ ให้มันทำงานไปเรื่อย ๆ **จนกว่ามันจะไม่สามารถหา chromosome ที่ดีขึ้นได้เป็นระยะเวลาหนึ่ง** เช่นไม่เพิ่มเป็นจำนวน 10 generation ก็ให้หยุดนั่นเองครับ

_**พูดอีกอย่างก็คือเมื่อเราไม่สามารถหา chromosome ที่ดีขึ้นได้ ภายใน 10 generations ก็ให้หยุดการทำงาน**_

โดยผมจะเพิ่มตัวแปรที่ใช้จำค่า objective ที่ดีที่สุดเอาไว้ ชื่อ `max_so_far` และก็มีตัวแปรที่คอยนับ `n_not_improve` ถ้า ค่า objective ที่ดีสุดของ generation ปัจจุบัน _ไม่ได้ดีกว่า_ objective ที่ดีที่สุดที่เราเคยเจอ ตัว `n_not_improve` นี้ก็จะบวกค่าเพิ่มไปทีละ 1 ครับ

ถ้าเจอค่า objective ที่ดีที่สุดอันใหม่ `n_not_improve` ก็จะถูก reset กลับเป็น 0 แต่ถ้า `n_not_improve` ถึง 10 เมื่อไหร่ นั่นคือมันไม่ได้เกิดการ improve เป็นเวลานานเกินไปแล้ว ก็จะ break ออกจากลูปแล้วจบการทำงานของโปรแกรมครับ

โค้ดในส่วนที่เพิ่มเข้ามาก็จะเป็นประมาณนี้
```python
...

max_so_far = float('-inf')
n_not_improve = 0

generation = 0
while True:
    ...

    # 3. ตรวจสอบเงื่อนไขการหยุดการทำงาน
    max_local = objective.max()
    if max_local > max_so_far:
        max_so_far = max_local
        n_not_improve = 0
    else:
        n_not_improve += 1
        if n_not_improve >= 10:  # ถ้าไม่มี improvement เป็นจำนวน 10 gen
            break
    ...
    print(f'generation {generation:2}: {objective.max()}')
    generation += 1
```
_ขออนุญาตลงแบบย่อ เนื่องจากรู้สึกว่าโค้ดเต็ม ๆ ใหญ่ไปหน่อยครับ 55 สามารถดูทั้งหมดจากใน Colab ได้ครับ_

เท่านี้โค้ด Genetic Algorithm ของเราก็สมบูรณ์แล้วครับ ถ้าลองกดรันดู แต่ละ generation มันก็จะ print ค่าของ fitness (ยอดขาย) ของตัวที่เก่งที่สุดใน generation นั้นออกมา ก็จะเห็นว่ามันค่อย ๆ เพิ่มขึ้นทีละนิด แล้วไปหยุด generation 78 ซึ่งได้ยอดขายรวมเป็น 1235 คน จาก 1250 คน คิดเป็น 98.8%!

จาก report คำตอบที่ดีที่สุด จะเห็นว่าเหลือแค่ 15 คนเท่านั้นนะครับที่ไม่ซื้อลูกชิ้นทอดของเรา 55
![colab-best-solution.png](https://dev-to-uploads.s3.amazonaws.com/i/uyqntvxz7fqq81uuqmof.png)

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

#ดูพัฒนาการของคำตอบในแต่ละ generation
นอกจากจะได้คำตอบสุดท้ายแล้ว เรายังสามารถแก้โค้ดนิดหน่อยเพื่อให้มันเก็บคำตอบที่ดีที่สุดของแต่ละ generation เอาไว้มา plot เพื่อดูความเร็วของการเข้าใกล้คำตอบสุดท้ายได้ครับ
 
![colab-evolution.png](https://dev-to-uploads.s3.amazonaws.com/i/9irjv7a60nshf08xdehs.png)

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

#Summary
ถ้าอ่านมาจนถึงตรงนี้คิดว่าน่าจะพอเข้าใจเกี่ยวกับ Genetic Algorithm และปัญหาที่สามารถนำไปประยุกต์ใช้ได้ประมาณหนึ่งแล้ว ซึ่งจริง ๆ Genetic Algorithm ที่นำไปใช้กันจริง ๆ อาจจะแตกต่างจากนี้ได้หลายรูปแบบมากครับ แล้วแต่กรณีที่นำไปใช้ แต่แนวคิดหลักก็จะไม่ต่างกันมาก คือใช้การคักเลือกโดยธรรมชาติ (Natural Selection) มีการสืบพันธุ์ (Reproduction) และการกลายพันธุ์ (Mutation) เพื่อค้นหาคำตอบที่ดีที่สุด

ซึ่ง Genetic Algorithm ก็เป็นแค่ algorithm หนึ่งที่ใช้ในการหาคำตอบของปัญหาประเภท Search Problem คือเป็นปัญหาที่ให้ algorithm หาคำตอบ จาก set ของคำตอบที่เป็นไปได้ออกมา ที่ satisfy เงื่อนไขบางอย่างที่เรากำหนดเอาไว้ ซึ่งยังมี algorithm อื่น ๆ อีกมาก ถ้าสนใจศึกษาเพิ่มเติมอาจจะเริ่มจากการ search โดยดูตาม [link นี้](https://www.tutorialspoint.com/artificial_intelligence/artificial_intelligence_popular_search_algorithms.htm) เป็น guide ก็ได้ครับ 

ถ้ามีเรื่องไหนที่สนใจเพิ่มเติมสามารถ comment เอาไว้ได้นะครับ

FB Page: [Copy Paste Engineer](https://www.facebook.com/CopyPasteEng)

<center>**- ขอบคุณที่อ่านครับ -**</center>