Genetic Algorithms คืออะไร??[พร้อมตัวอย่างและโค้ด]
สวัสดีครับวันนี้ผมจะมาเล่าเรื่องของ Genetic Algorithms ให้ทุกคนได้อ่านนะครับ
Genetic Algorithms เป็นหนึ่งในอัลกอรึทึมที่เอาไว้หาค่าที่เหมาะสมที่สุด เช่น จัดตารางงาน ตารางเวลาหรือหาสูตรการทำเค้กให้อร่อยที่สุด เจ้า Genetic Algorithms ก็สามารถหาให้เราได้55555
โดยเจ้า Genetic Algorithms นั้นจะประกอบไปด้วย Chromosome ซึ่งมี concept การทำงานง่ายๆคือ โครโมโซมตัวไหนแข็งแกร่งที่สุดจะเป็นผู้อยู่รอดและสามารถมีลูกหลานได้ ส่วนตัวไหนอ่อนแอก็จะไม่ได้ไปสู่รุ่นถัดไป!!
ซึ่งในวันนี้ผมจะมาอธิบายการทำงานของเจ้าอัลกอรึทึมตัวนี้ว่า เราจะวัดความแข็งแกร่งของโครโมโซมและหาค่าที่เหมาะสมที่สุดได้ยังไง
ตัวอย่างของเราวันนี้ก็คือ ใช้ Genetic Algorithms —
หาค่า a, b, c, dจาก สมการ 2a+4b+3c-2d=41
ซึ่งโดยปกติแล้วเราจะคุ้นชินกับการหาค่า n ตัวแปร n สมการ จากการที่เอาสมการมาบวกลบกันแล้วค่อยๆแก้หาไปทีละตัวแปร หรือใช้กฎของ cramer ก็สามารถทำได้
แต่!! ถ้าหากเรามี 4ตัวแปรแล้วมีเพียง 1 สมการละ? หากจะนั่งเดาตัวเลขไปเรื่อยๆคงเสียเวลามากแน่ๆ ฉะนั้นเราจึงต้องเรียก Genetic Algorithms เข้ามาช่วย
ซึ่งวิธีการทำงานของ เจ้า Genetic algotithms มีดังนี้
ขั้นที่ 1 Initialization
การ Initialization คือการสร้าง Population(ประชากร) รุ่นที่ 1 ขึ้นมาก่อน ซึ่งการสร้างประชากรนั้นก็อยู่ที่ปัญหาว่าจะออกแบบให้ประชากรของเรานั้นเป็นแบบไหน
โดยในตัวอย่างนี้จะสร้างประชากร เป็นดังนี้
{[a1, b1, c1, d1], [a2, b2, c2, d2], [a3, b3, c3, d3], [a4, b4, c4, d4]}
เราจะเรียกสมาชิกใน Population ว่า Chromosome และ เรียกสมาชิกใน Chromosome ว่า Gene
ซึ่งตัวแปรทุกตัวเราจะทำการสุ่มขึ้นมาในครั้งแรกโดยเราอาจจะกำหนดขอบเขตของการสุ่มเพื่อกำหนดขอบเขตของคำตอบที่เราอยากจะได้ เช่น ให้
สมมติว่าเราสุ่มได้ดังนี้
{[1, 4, 5, 2], [2, 6, 1, 9], [7, 13, 3, 6], [4, 7, 1, 9]}
พอเรา Initial Population เริ่มต้นแล้ว เราจะส่ง Population นี้ไปทำการ Selection&Evaluation เพื่อหาว่า Chromosome ไหนที่ควรจะอยู่รอดต่อไป
ขั้นที่ 2 Selection&Evaluation
ก่อนที่เราจะหาค่าความแข็งแกร่งของแต่ละ Chromosome เราจะต้องมี Objective function มาวัดมันซะก่อน ซึ่งฟังก์ชันนี้เราก็ต้องเป็นคนออกแบบขึ้นมาเอง ซึ่งถ้าดูจากปัญหาที่เรามีแล้ว การหา Objective function ของ Chromosome ก็คงจะต้องเป็น Chromosome ตัวที่มีคำตอบเข้าใกล้ 41 ที่สุด เพื่อให้ง่ายต่อความเข้าใจ เราจึงย้าย 41 ไป ลบ และเนื่องจากเราไม่สนใจทิศทาง แต่เราอยากรู้แค่ว่า เมื่อเราแทน a, b, c, d ลงไปในสมการแล้วอยู่ห่างจาก 41 ขนาดไหน ดังนั้นเราจึงใส่ absolute เข้าไปด้วย ซึ่งเราจะได้ Objective function ดังนี้ f(a, b, c, d) = abs(2a+4b+3c-2d-41)
จากฟังก์ชันที่ได้ มีความหมายว่า ถ้าเราแทน a, b, c, d เข้าไป แล้วมีคำตอบเข้าใกล้ 0 มากที่สุด Chromosome ตัวนั้นจะเป็น Chromosome ที่แข็งแรงที่สุด
จาก Population ด้านบนที่เราเพิ่งสุ่มมาจะได้ว่า
Objective function ของ Chromosome ตัวที่ 1 : a = 1, b = 4, c = 5, d = 2
ดังนั้นเราจะได้ f(1, 4, 5, 2) = abs(2*1+4*4+3*5-2*2–41)=12
และเราจะหา Objective function ของ Chromosome ทุกตัวจะได้ดังนี้
Objective function ของ Chromosome ตัวที่ 2: f(2, 6, 1, 9) = 28
Objective function ของ Chromosome ตัวที่ 3: f(7, 13, 3, 6) = 22
Objective function ของ Chromosome ตัวที่ 4: f(4, 7, 1, 9) = 20
เขียนแทนด้วย
F_obj[0] = 12
F_obj[1] = 28
F_obj[2] = 22
F_obj[3] = 20
หลังจากนั้นเราจะมาหาความน่าจะเป็นของ Chromosome ตัวไหนที่ควรจะอยู่รอดในรุ่นถัดไป ซึ่ง Chromosome ตัวที่แข็งแรงที่สุด(The Fittest Chromosomes)ก็จะมีโอกาสอยู่รอดในรุ่นถัดดไปมากที่สุด ก่อนที่เราจะไปหา ความน่าจะเป็น เราต้องหาค่า Fitness ของ Chromosome แต่ละตัวก่อน ซึ่งมีสมการดังนี้
ที่เราต้องบวก1 เข้าไปที่ตัวส่วนเพื่อป้องกันไม่ให้ส่วนเป็น 0 (กรณีที่ F_obj เป็น 0) และหากเราวิเคราะห์สมการคร่าวๆเราก็จะได้ว่า หาก F_obj ของเราเป็น 0 ค่า Fitness ของเราก็จะได้ 1 พอดี แต่ถ้าหาก ค่า F_obj ของเรามีค่ามากเท่าไหร่ ค่า Fitness ของ F_obj ตัวนั้นก็จะยิ่งเข้าใกล้ 0 มากขึ้น ซึ่งมันบอกเราได้ว่า ยิ่งค่า Fitness เข้าใกล้ 1 มากเท่าไหร่ Chromosome ตัวนั้นก็ยิ่งแข็งแรงมากขึ้นเท่านั้น แต่หากค่า Fitness เข้าใกล้ 0 มากเท่าไหร่ Chromosome ตัวนั้นก็อ่อนแอมากเท่านั้น และหาก Fitness ได้ 0 พอดี ก็จะหมายความว่า Chromosome ตัวนั้นคือคำตอบที่เราต้องการ
ซึ่งเราคำนวณค่า Fitness ของแต่ละ Chromosome ได้ดังนี้
Fitness[0] = 1/(1+12) = 0.0769
Fitness[1] = 1/(1+28) = 0.0345
Fitness[2] = 1/(1+22) = 0.0435
Fitness[3] = 1/(1+20) = 0.0476
เมื่อเราได้ค่า Fitness มาแล้วต่อไปเราจะมาหาความน่าจะเป็นที่จะอยู่รอดของแต่ละ Chromosome ได้จาก P[i] = Fitness[i]/total ซึ่งจะได้
P[0] = 0.0769/0.2025 = 0.3798
P[1] = 0.0345/0.2025 = 0.1704
P[2] = 0.0435/0.2025 = 0.2148
P[3] = 0.0476/0.2025 = 0.2351
และเนื่องจากการ Selection เราจะใช้ roulette wheel ในการเลือกดังนั้นสิ่งที่เราต้องมีคือค่าความน่าจะเป็นสะสม(cumulative probability values) ซึ่งจะได้
C[0] = 0.3798
C[1] = 0.3798+0.1704 = 0.5502
C[2] = 0.3798+0.1704+0.2148=0.765
C[3] = 0.3798+0.1704+0.2148+0.2351 = 1.0
เมื่อได้ค่าความน่าจะเป็นสะสมแล้ว roulette wheel ต้องการอีกอย่างคือ ค่า R ทีเกิดจากการสุ่มที่อยู่ในช่วง [0, 1]
R[0] = 0.145
R[1] = 0.932
R[2] = 0.633
R[3] = 0.347
ถ้าหาก R[i] มีค่ามากกว่า C[k] และ มีค่าน้อยกว่า C[k+1] เราจะเลือก C[k+1] เป็น Chromosome ในรุ่นถัดไป
มาถึงตรงนี้แล้วพอจะรู้กันหรือยังครับ ว่าทำไม Chromosome ที่แข็งแรงที่สุดถึงมีโอกาสอยู่รอดในรุ่นถัดไปมากที่สุด
หากยังไม่รู้ละก็ ผมจะอธิบายเป็นรูปภาพให้ผู้อ่านได้เข้าใจกันง่ายขึ้นนะครับ
หากเราวาดค่า C[i] ลงบนเส้นจำนวนจะเห็นได้ว่าค่าระหว่าง 0 ถึง C[0] มีความยาวกว้างเยอะที่สุดก็จะทำให้เวลาสุ่มค่า R แล้วจะทำให้มีโอกาสที่จะอยู่ในช่วงนี้มากขึ้นไปด้วย ซึ่งในที่นี้นอกจาก Chromosome[0] จะอยู่รอดในรุ่นถัดไปแล้ว ก็เพิ่มจำนวนตัวเองอีกด้วย(เก่งจริงๆ Chromosome ตัวนี้55555) ซึ่งก็เป็นเพราะว่าค่า Fitness[0] มีค่ามากที่สุด หรือ Chromosome[0] แข็งแรงมากที่สุดนั่นเอง ก็เป็นที่มาที่ทำให้เราสรุปได้ว่า ยิ่งค่า Fitness มาก Chromosome ตัวนั้นก็จะยิ่งมีโอกาสรอดสู่รุ่นถัดไปมากยิ่งขึ้นนั่นเอง อีกจุดที่น่าสังเกตคือ Chromosome[1] ไม่ได้ไปสู่รุ่นถัดไปนั่นเพราะค่า Fitness ของ Chromosome[1] มีค่าน้อยจึงทำให้เมื่อสุ่มค่า R ก็ทำให้มีโอกาสในการไปตกช่วงที่ 2 (ระหว่าง C[0] และ C[1])น้อยลงด้วย(อ่อนแอก็ต้องแพ้ไปจริงๆ TT)
ดังนั้นเราจะได้
NewChromosome[0] = Chromosome[0]
NewChromosome[1] = Chromosome[3]
NewChromosome[2] = Chromosome[2]
NewChromosome[3] = Chromosome[0]
Population ใหม่ของเราจะกลายเป็น
Chromosome[0] = [1, 4, 5, 2]
Chromosome[1] = [4, 7, 1, 9]
Chromosome[2] = [7, 13, 3, 6]
Chromosome[3] = [1, 4, 5, 2]
เมื่อเราได้ Population ใหม่แล้ว เราก็จะเอา Population นี้ไปทำการ Crossover และ Mutation ต่อไป
ขั้นที่ 3 Crossover
เหตุผลของการทำ Crossover คือ ในเมื่อเราได้ Poplation ใหม่ที่ได้มา มีแต่ตัวที่แข็งแกร่งทั้งนั้น เราลองเอามันมาผสมพันธ์กันซะหน่อย เผื่อจะได้ลูกที่แข็งแกร่งกว่าเดิม
ซึ่งวิธีการก็คือ เราจะต้องตั้ง Crossover rate ขึ้นมาก่อน ในตัวอย่างนี้เราจะใช้ 25% และหลังจากนั้นเราจะทำการสุ่ม ค่า R ที่อยู่ในช่วง [0, 1] ขึ้นมา สุ่มมาเท่ากับจำนวน Chromosome ใน Population ของเรา ก็จะได้ดังนี้
R[0] = 0.12
R[1] = 0.34
R[2] = 0.21
R[3] = 0.23
และหาก R[i] ≤ 0.25 เราจะนำ C[i] ไป ทำการ Crossover จากด้านบนเราก็จะได้ว่า
Chromosome[0] x Chromosome[2]
Chromosome[2] x Chromosome[3]
Chromosome[3] x Chromosome[0]
เมื่อเราได้ Chromosome ที่จะนำมาทำการ Crossover กันแล้ว เราจะต้องหาตำแหน่งที่จะให้มัน Crossover กันด้วย(Crossover point) ซึ่งตำแหน่งเราก็จะทำการสุ่มขึ้นระหว่าง [1, ความยาวของ Chrosmosome-1] เนื่องจาก Chromosome เรานั้นยาว 4 ดังนั้น ตำแหน่งที่เราจะสุ่มจะอยู่ในช่วงของ [1,3] นั้นเอง สมมติว่าเราสุ่มได้ดังนี้
C[0] = 2
C[1] = 1
C[2] = 3
ซึ่งการ Crossover ของ Chromosome ตัวที่ 0, 2, 3 ก็จะตัด ณ ตำแหน่งที่ 2, 1, 3 จากที่สุ่มได้ ตามลำดับ
หากเราสังเกต Chromosome ที่ได้มาใหม่นั้น เราจะสังเกตได้ว่า สมาชิกของ Chromosome ก็วนกันอยู่แค่นั้น เราจำเป็นต้องมีการกลายพันธ์ุ(Mutation)เพื่อเพิ่มความหลากหลายแก่ประชากร และอีกหนึ่งจุดที่น่าสนใจคือ หากเราสังเกตที่ Chromosome[3] หลังจาก Crossover เสร็จแล้วก็ยังได้ตัวเดิม นี่เป็นเหตุผลหนึ่งที่ทำให้เราต้องมีการ Mutation ก็เพื่อป้องกันไม่ให้ Chromosome วนไปวนมาซึ่งทำให้เราไปไม่ถึงคำตอบที่เราต้องการซักทีนั่นเอง
ขั้นที่ 4 Mutation
ก่อนที่เราจะทำการกลายพันธ์ุ เราต้องกำหนด Mutation rate ก่อน สมมติว่าเรากำหนดให้ Mutation rate = 20%
ขั้นตอนแรกของการ Mutation คือ เราจะต้องหาจำนวน Gene ทั้งหมดใน Population ก่อน ซึ่งจะได้ว่า
total_gene = ความยาวของ Chromosome * จำนวนของ Chromosome
total_gene = 4*4 = 16
จากนั้นเราจะหาว่าเราจะ Mutation ทั้งหมดกี่ตัวจาก
total_gene*Mutation rate = 16*0.2=3.2 (ปัดลงให้เป็น 3)
เราจะได้ว่าจำนวน Gene ที่เราจะ Mutation มี 3 ตัว
หลังจากนั้น เราจะ random ตัวเลขที่มีค่าระหว่าง [1,16] เป็นจำนวน 3 ตัวเพื่อเป็นตำแหน่งในการ Mutation สมมติว่า random ได้ 13, 2, 8 หลังจากนั้น 3 ตำแหน่งนี้จะถูกแทนที่ด้วยค่าที่เรา random ตัวเลขระหว่าง [1,41] อีก 3 ตัว สมมติว่าเราได้ 7, 12, 2
เราจะเอา 7, 12, 2 ไปแทนค่าเดิม ณ ตำแหน่งที่เราสุ่มได้มา
หลังจากที่เรา Mutation เสร็จแล้ว เราก็จะเอา Population นี้ไปหาค่าความแข็งแกร่งอีกครั้ง หา F_obj หา Fitness กันต่อไป เราจะวนทำซ้ำไปเรื่อยๆจนกว่าเราจะได้คำตอบ หรือจนกว่า ค่า F_obj ของเราจะเป็น 0 นั้นเอง
จากผลที่ได้เราจะเห็นว่าคำตอบของทั้ง 2 ครั้งนั้นไม่เท่ากันแต่ให้ผลลัพธ์เดียวกันคือสามารถหา a, b, c, d ที่ทำให้สมการ 2a+4b+3c-2d=41เป็นจริงได้
จากข้างบนเราก็จะเห็นว่า มีค่า a, b, c, d หลายชุดที่เป็นผลเฉลยของสมการนี้ ซึ่งเราจะเสียเวลาหากจะมานั่งลองแทนค่าทีละตัว แต่เจ้า Genetic Algorithms บอกเราได้โดยใช้เวลาไม่นาน
เป็นยังไงบ้างครับ สำหรับเจ้า Genetic Algorithms ไม่ยากและไม่ง่ายจนเกินไปใช่ไหมครับ
ครั้งหน้าผมจะมาเล่าเรื่องอะไรให้ฟัง ฝากติดตามกันด้วยนะครับ
แล้วเจอกันใหม่ในตอนหน้า สวัสดีครับ :)
ตัวอย่างโค้ดของเจ้า Genetic Algorithms
github: https://github.com/krittametproject/ga_for_solving_simpleEq
อ้างอิง
[1] https://arxiv.org/pdf/1308.4675.pdf
