ขอเริ่มจากเล่านิทานก่อนนะครับ 555 สมมุติว่าเราอยู่ในองค์กรสายลับระดับชาติในชื่อ "ภาคีลูกชิ้นทอด" ที่กำลังวางแผนแทรกซึมเข้าไปในม็อบเพื่อขายลูกชิ้นและไก่ทอดในม็อบให้ได้มากที่สุด แน่นอนว่าเมื่อเราส่งสายลับมืออาชีพของเราลงไปแล้ว ไม่ว่าใครก็ต้องอดใจไม่ไหว ด้วยลูกชิ้นทอดและน้ำจิ้มสูตรเด็ด ที่ส่งกลิ่นหอมแพร่กระจายออกไปเป็นกิโล ทำให้ผู้ร่วมชุมนุมที่อยู่ในรัศมีทุกคนจะตามกลิ่นมาซื้ออย่างแน่นอน!
เนื่องจากองค์กรได้รับข้อมูลจากสายสืบถึงพื้นที่ที่มีความเป็นไปได้ที่จะจัดตั้งม็อบก่อนใครเสมอ จึงสามารถคาดเดาตำแหน่งของคนที่เข้าร่วมชุมนุมล่วงหน้าได้อย่างแม่นยำ โดยเราได้รับมอบหมายให้หาจุดที่จะส่งสายลับลูกชิ้นทอดทั้ง 10 คน เข้าไปประจำการล่วงหน้าตามจุดต่าง ๆ 10 จุด ที่จะสามารถทำยอดขายรวมได้ที่สุด ชะตากรรมของทั้งประเทศอยู่ในมือของเราแล้ว!!
โชคดีที่เรารู้จักเทคนิคที่เรียกว่า Genetic Algorithm จึงสามารถนำมาใช้หาตำแหน่งที่ดีได้เสมอ ทำให้องค์กรสามารถทำภารกิจแทรกซึมได้สำเร็จทุกครั้งไป...
...ในบทความนี้ มาดูกันว่า Genetic Algorithm คืออะไร แล้วมันจะช่วยองค์กรได้อย่างไรนะครับ??
จาก https://mgronline.com/live/detail/9630000108268
note: สำหรับท่านที่งง ๆ ว่าลูกชิ้นทอดเกี่ยวอะไร ลองอ่านเนื้อเรื่องเพิ่มเติมได้ครับ 5555: เปิดใจ CIA หน่วยเคลื่อนที่เร็วประจำม็อบ “ลูกชิ้นทอด-ไก่ทอด” ยอดขายพุ่งเฉียดวันละหมื่น!
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 ก็จะไปทำการลองผิดลองถูกเพื่อหาคำตอบที่ดีที่สุดที่มันหาได้มาให้เราครับ
จาก https://zenodo.org/record/1247385#.X5QTB50zZD8
ลองมาดูตัวอย่างที่ให้ความรู้สึกเป็น AI มากขึ้นหน่อยดีกว่าครับ
MarI/O bot เล่นเกม Mario
ความน่าสนใจของงานนี้อยู่ตรงที่ว่า คนสร้างไม่ได้สอนตัว AI เลยแม้แต่น้อย ว่ากดปุ่มอะไรแล้วจะเกิดอะไร หรือกลไกของเกมส์ Mario เป็นอย่างไร หรือโดนโจมตี/เก็บของแล้วจะเป็นอะไร นั่นคือเริ่มต้นมา AI ไม่รู้อะไรเลย แต่มันจะค่อย ๆ ลองเล่น ลองผิดลองถูกไปเรื่อย ๆ จนเก่งขึ้นตามภาพครับ
จาก 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 มาไว ๆ ครับ
จะเห็นได้ว่า 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 โดยยีราฟตัวที่มี Chromosome คอสั้นจะโดนแย่งอาหาร และค่อย ๆ อดอาหารตายไป ทำให้ยีราฟที่มี Chromosome คอยาวอยู่รอด และสืบพันธุ์ส่งต่อ "ความคอยาว" ให้รุ่นลูกหลานถัดไป จนยีราฟทุกตัวใน generation หลังก็จะคอยาวกันหมด จาก https://www.toppr.com/content/story/amp/natural-selection-and-polymorphism-73211/
การสืบพันธุ์ และการกลายพันธุ์ (Reproduction and Mutation)
การสืบพันธุ์ (Reproduction) ถ้าเป็นตามที่เราเรียนมาก็คือเราจะเอา Chromosome จากพ่อกับแม่ มา crossover กัน โดยสลับหน่วยย่อยของ Chromosome กันบางส่วนเพื่อแลกเปลี่ยนสารพันธุกรรมกัน ก่อนจะส่งต่อไปให้กับรุ่นลูกใช่ไหมครับ
Chromosomes Crossing Over จาก https://ib.bioninja.com.au/standard-level/topic-3-genetics/33-meiosis/crossing-over.html
ใน Genetic Algorithm เราก็จะทำเช่นเดียวกันครับ คือเราเอาตัวที่แข็งแกร่ง 2 ตัวมาทำการแลกเปลี่ยนบางส่วนของคำตอบกัน โดยคาดหวังว่ามันอาจจะได้ Combination ที่ดีขึ้นออกมาในรุ่นลูกครับ
ภาพการ cross chromosomes แบบหนึ่ง ใน GA จาก https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_crossover.htm
จากนั้นโดยทั่วไป เขาก็ใส่จะกลไกการกลายพันธุ์เข้าไปเล็กน้อย เช่นลองแก้ค่าบางค่าของ Chromosome จาก 0 เป็น 1 ดูแบบสุ่ม หรือลองสลับค่าบางค่าดู เป็นต้น เพื่อทำให้เกิดความหลากหลายของ Chromosome มากขึ้นครับ ก็เหมือนกับการลองผิดลองถูก คือแก้แล้วอาจจะทำให้คำตอบดีขึ้นหรือแย่ลงก็ได้ แต่ยิ่งลองผิดลองถูกมากก็ยิ่งมีโอกาสเจอคำตอบที่ดีมากขึ้นใช่ไหมครับ
ภาพ Swap Mutation จาก https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm
สรุปกระบวนการ Genetic Algorithm
- เริ่มจากสร้างประชากร Chromosomes ขึ้นมาแบบสุ่ม สมมุติ 500 ตัว
- คำนวนค่า Cost หรือ Fitness ของ Chromosome แต่ละตัว
- ถ้าเงื่อนไขในการหยุดเป็นจริง ให้หยุดทำงาน ถ้ายังไม่จริงก็ทำต่อ
- กำจัดตัวที่อ่อนแอออกไป สมมุติครึ่งหนึ่ง ก็จะเหลือตัวที่แข็งแกร่งอยู่ 250 ตัว
- เอาตัวที่เหลืออยู่มาสืบพันธ์และสุ่มกลายพันธุ์ เพื่อเพิ่มจำนวนของประชากรให้ Chromosomes ทั้งหมดกลับมามีจำนวน 500 เท่าเดิม
- ทำซ้ำตั้งแต่ข้อ 2
จาก https://www.researchgate.net/figure/Genetic-algorithm-flowchart_fig2_263224226
ผมละรายละเอียดบางส่วนเอาไว้ คิดว่าไปดูในโค้ดน่าจะเห็นภาพมากกว่าครับ
แล้วจะขายลูกชิ้นที่ไหนดี...
ก่อนที่ภาคีลูกชิ้นทอดของเราจะรอนานไปมากกว่านี้ ถ้าพอจะเข้าใจแนวคิดของ Genetic Algorithm คร่าว ๆ แล้ว เรามาเริ่มเขียนโค้ดเพื่อช่วยองค์กรหาตำแหน่งขายลูกชิ้นกันดีกว่าครับ
โค้ดเต็ม ๆ ทั้งหมดดูได้ใน Google Colab ตามลิ้งนี้เลยครับ สามารถเปิดขึ้นลองรันดู ไปพร้อม ๆ กับอ่านบทความได้เลยครับ 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 คนครับ
note: รายละเอียดว่าสร้างออกมาแบบนี้ได้ยังไงไม่ได้น่าสนใจมากขออนุญาตข้ามนะครับ สามารถไปดูได้ในโค้ดเต็มครับ
ฟังก์ชันต่าง ๆ
สำหรับ project นี้ไม่ได้ซับซ้อนมากนัก ผมจะขอเริ่มแบบง่าย ๆ โดยการ implement logic ของส่วนต่าง ๆ ที่ยุ่ง ๆ ให้เป็นฟังก์ชันย่อย ๆ ออกมาตามนี้ครับ
- ฟังก์ชัน get_customers(positions, mob) สำหรับรับตำแหน่งของร้านค้าและม็อบ เพื่อไปคำนวณว่าเมื่อตั้งร้านตามตำแหน่งต่อไปนี้แล้ว คนไหนบ้างในม็อบจะมาซื้อ และเป็นจำนวนเท่าไหร่ในแต่ละร้าน
- ฟังก์ชัน create_initial_population() สำหรับสุ่มสร้าง population ของ chromosomes เริ่มต้น
- ฟังก์ชัน calculate_objective(mob, population) สำหรับคำนวณค่า fitness
- ฟังก์ชัน reproduce(parents, count) สำหรับนำ population ที่ผ่านการคัดเลือกมาเป็น parents เพื่อทำการสืบพันธุ์และกลายพันธุ์ต่อไป
get_customers(positions, mob)
ฟังก์ชันนี้ใช้สำหรับคำนวณว่าเมื่อตั้งร้านตามตำแหน่ง positions แล้วใครในม็อบจะมาซื้อบ้าง (เลข index ของ array mob) และได้จำนวนการขายของแต่ละร้านเท่าไหร่ โดยที่ mob คือ array ของตำแหน่ง (x, y) ของคนในม็อบ
- ผมวนลูปเพื่อเอาตำแหน่งของร้านค้า
pมาทีละร้าน จากpositions - คำนวณระยะห่างของแต่ละคนในม็อบกับร้าน
p(Euclidean Distance) - เลือกคนที่อยู่ใกล้ที่สุดมาจำนวนไม่เกิน 150 คน (เท่ากับจำนวนคนที่ร้าน 1 ร้านสามารถขายให้ได้ CAPACITY = 150) และอยู่ห่างจากร้าน
pเป็นระยะทางไม่เกิน 1.0 หน่วย (คือระยะทางที่กลิ่นหอมจากร้านpสามารถลอยไปได้ไกลที่สุด EFFECT_RADIUS = 1.0) เราจะนับไปเลยว่าคนพวกนี้จะเข้ามาซื้อร้านpเพราะไม่มีใครทนต่อกลิ่นหอมได้ - นับจำนวนของคนที่ผ่านเงื่อนไขในข้อ 3 แล้วเพิ่มไปใน customer_counts ของร้าน
pเพื่อใช้บอกว่าร้านpได้ลูกค้าไปจำนวนกี่คน - ลบคนที่เป็นลูกค้าของร้าน
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()
จุดสีน้ำเงิน คือคนที่ยังไม่ได้เป็นลูกค้าร้านใด
จุดสีเขียว คือคนที่เป็นลูกค้าซื้อไปเรียบร้อยแล้ว
กากบาทสีแดง คือตำแหน่งร้านค้าที่ 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
ตัวอย่าง Chromosomes 5 ตัวแรกใน population ก็คือเป็น array ของ (x, y) ทั้งหมด 10 ตัว
ลองเอา population ที่สร้างได้ ตัวที่ 0 กับตัวที่ 1 มา plot ดู ก็จะเห็นว่า แต่ละตัวมีตำแหน่งของร้านจำนวน 10 ร้าน และกระจายกันแบบมั่ว ๆ
calculate_objective(mob, population)
ฟังก์ชันนี้ใช้สำหรับคำนวณค่า Fitness ของ Chromosome แต่ละตัวจากใน population ซึ่ง Fitness ของ Chromosome แต่ละตัว ก็คือยอดขายรวมของแต่ละร้านใน Chromosome นั้นนั่นเอง
เนื่องจากเรามีฟังก์ชัน get_customers() ที่สามารถคำนวณ customer_counts ของร้านค้าแต่ละร้านใน 1 Chromosome ได้อยู่แล้ว จึงสามารถเอามาใช้ได้ตามนี้ครับ
ไป ๆ มา ๆ เหมือนว่าฟังก์ชันที่ยากที่สุดจะเป็น 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
ตัวอย่างผลลัพธ์การ cross ระหว่าง chromosome a และ b
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
ตัวอย่างของ chromosome ที่ถูกทำให้กลายพันธุ์ จะเห็นว่าบางร้านก็ถูกเลื่อนออกไปไกลจากเดิม แต่บางร้านก็ไม่ไกล คละกันไป
ฟังก์ชันหลัก reproduce(parents, count)
เมื่อเราได้ฟังก์ชันย่อยทั้งสองครบแล้ว ตอนนี้เราก็สามารถเขียน reproduce() ได้ดังนี้
ก็คือวนลูปเพื่อสุ่มหยิบ chromosomes มาทีละคู่ จาก parents เอามา cross กันด้วย cross_chromosome() จากนั้นก็เก็บผลลัพธ์ไว้ใน children จนได้จำนวนตามที่ต้องการคือเท่ากับ count
จากนั้นก็เอา children ไปสุ่มกลายพันธุ์ด้วย mutate_population() ที่เราสร้างเอาไว้ แล้วก็ return children ซึ่งเป็น array ของลูกที่ได้กลับไป
เท่านี้เราก็ได้ฟังก์ชันทั้งหมดที่ต้องการเรียบร้อยแล้ว เขียนไปเขียนมาก็เริ่มยาวแล้วเหมือนกัน 555 ต่อไปก็จะเขียนโค้ดการทำงานหลักที่ใช้หาคำตอบกันครับ
เขียนโค้ดการทำงานหลักเพื่อหาคำตอบ...สักที
เมื่อยึดตามกระบวนการทำงานของ Genetic Algorithm ที่เราสรุปเอาไว้ด้านบน เราก็พอจะร่างโครงขึ้นมาเป็น outline ได้ประมาณนี้
# 1. สร้าง population เริ่มต้น
generation = 0
while True:
# 2. คำนวณ fitness
objective = ...
# 3. ตรวจสอบเงื่อนไขการหยุดการทำงาน
# 4. กำจัดตัวที่อ่อนแอ คัดเลือกตัวที่แข็งแกร่ง
population = ...
# 5. สืบพันธุ์ และกลายพันธุ์
population = ...
print(f'generation {generation:2}: {objective.max()}')
generation += 1
ทีนี้เราก็เติมโค้ดแต่ละส่วนลงไปด้วยฟังก์ชันที่เราเขียนเอาไว้แล้ว ตามนี้
- ใช้ฟังก์ชัน create_initial_population()
- ใช้ฟังก์ชัน calculate_objective()
- ...ขออนุญาตข้ามไปก่อน
- ให้ใช้ค่า fitness จากตัวแปร
objectiveในการเรียงลำดับจากมากไปน้อย แล้วตัดให้เหลือแค่ครึ่งแรก ที่มีค่า fitness สูง - ใช้ฟังก์ชัน reproduce() ได้
childrenออกมา จากนั้นเอาchildrenไปรวมกับpopulationที่เหลืออยู่
ได้เป็นโค้ดที่สมบูรณ์มากขึ้นดังนี้
# 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 ออกจากลูปแล้วจบการทำงานของโปรแกรมครับ
โค้ดในส่วนที่เพิ่มเข้ามาก็จะเป็นประมาณนี้
...
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
เท่านี้เราก็สามารถช่วยเหลือองค์กรของเราให้แทรกซึมเข้าไปในม็อบได้สำเร็จอย่างมีประสิทธิภาพสูงสุดแล้วครับ
ดูพัฒนาการของคำตอบในแต่ละ generation
นอกจากจะได้คำตอบสุดท้ายแล้ว เรายังสามารถแก้โค้ดนิดหน่อยเพื่อให้มันเก็บคำตอบที่ดีที่สุดของแต่ละ generation เอาไว้มา plot เพื่อดูความเร็วของการเข้าใกล้คำตอบสุดท้ายได้ครับ
จะเห็นได้ว่าตั้งแต่สุ่ม population ออกมาใน generation แรก ก็ได้ยอดขายค่อนข้างเยอะอยู่แล้ว อาจจะเป็นเพราะว่าจำนวนประชากร POPULATION_SIZE ของเราเยอะมาก ทำให้มีโอกาสโชคดีสุ่มแล้วเจอคำตอบดี ๆ แต่แรกแบบนี้ หรือไม่ก็เป็นเพราะว่าข้อมูลตำแหน่งม็อบของเรามันกระจุกมากเกินไปก็ได้ครับ ถ้าสนใจก็สามารถลองแก้โค้ดปรับตัวแปรต่าง ๆ เล่นดูเพิ่มเติม แล้วเอาผลลัพธ์มาแชร์กันได้นะครับ
Summary
ถ้าอ่านมาจนถึงตรงนี้คิดว่าน่าจะพอเข้าใจเกี่ยวกับ Genetic Algorithm และปัญหาที่สามารถนำไปประยุกต์ใช้ได้ประมาณหนึ่งแล้ว ซึ่งจริง ๆ Genetic Algorithm ที่นำไปใช้กันจริง ๆ อาจจะแตกต่างจากนี้ได้หลายรูปแบบมากครับ แล้วแต่กรณีที่นำไปใช้ แต่แนวคิดหลักก็จะไม่ต่างกันมาก คือใช้การคักเลือกโดยธรรมชาติ (Natural Selection) มีการสืบพันธุ์ (Reproduction) และการกลายพันธุ์ (Mutation) เพื่อค้นหาคำตอบที่ดีที่สุด
ซึ่ง Genetic Algorithm ก็เป็นแค่ algorithm หนึ่งที่ใช้ในการหาคำตอบของปัญหาประเภท Search Problem คือเป็นปัญหาที่ให้ algorithm หาคำตอบ จาก set ของคำตอบที่เป็นไปได้ออกมา ที่ satisfy เงื่อนไขบางอย่างที่เรากำหนดเอาไว้ ซึ่งยังมี algorithm อื่น ๆ อีกมาก ถ้าสนใจศึกษาเพิ่มเติมอาจจะเริ่มจากการ search โดยดูตาม link นี้ เป็น guide ก็ได้ครับ
ถ้ามีเรื่องไหนที่สนใจเพิ่มเติมสามารถ comment เอาไว้ได้นะครับ
FB Page: Copy Paste Engineer
Top comments (0)