จากตอนที่ 1 และตอนที่ 2 ทำให้เข้าใจที่มาของแนวคิดและภาพรวมของ GA ไปแล้ว ในตอนนี้จะแสดงให้เห็นตัวอย่างการนำเอา GA ไปใช้ในการสร้างโปรแกรมคอมพิวเตอร์กัน
1. กำหนดคำเป้าหมาย เช่น "Genetic Algorithm"
2. เนื่องจากเป็นเกมส์ทายคำ ดังนั้น Sample space ที่จะใช้ได้ทั้งหมดก็คือตัวอักษรและตัวเลข
gene_set = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_ 0123456789')
target = list('Genetic Algorithm')
3. สร้าง class Individual
import numpy as np
class Individual():
def __init__(self):
self.chromosome = []
def fitness(self,target_chromosome):
pass
ภายใน Individual มีส่วนที่ใช้แทน solution ของการแก้ปัญหาเก็บไว้ในตัวแปร chromosome และ การแก้ปัญหาในโจทย์นี้คือการสร้างลำดับของตัวอักษรที่ตรงกับเป้าหมายคือ "Genetic Algorithm" ในตอนแรกของการสร้างแต่ละ Individual เราจะกำหนดชุดตัวอักษรขึ้นมาแบบสุ่มก่อน แต่ให้จำนวนตัวอักษรเท่ากับจำนวนอักษรของคำเป้าหมาย เราจะเพิ่ม code ดังนี้
class Individual():
def __init__(self):
self.chromosome = []
c = np.random.choice(gene_set,size=len(target))
self.chromosome = c
def fitness(self):
pass
ส่วนสำคัญอีกอันของ Individual คือ fitness function ทำหน้าที่ระบุว่า chromosome อยู่ห่างจาก target เท่าไหร่ ซึ่งสามารถหาได้โดยใช้หลักการวัดความต่างของข้อมูล [1] ในที่นี้เลือกใช้ Manhattan \[d(x,y) = \sum_{i=1}^n \mid x_i - y_i \mid \]
class Individual():
def __init__(self):
self.chromosome = []
c = np.random.choice(gene_set,size=len(target))
self.chromosome = c
def fitness(self):
fit = 0.0
for g,t in zip(self.chromosome,target):
if g == t :
fit += 1
return fit
4. สร้าง Genetic Algorithm class
class GA():
def __init__(self):
pass
def select(self):
pass
def crossover(self,ind1,ind2):
pass
def mutate(self,ind):
pass
def sort(self):
pass
def elitism(self):
pass
def evolute(self):
pass
โครงสร้างของ class GA ถูกวางไว้ตามแนวของขั้นตอนการทำงานใน GA ที่กล่าวไว้ในตอนที่ 2 และเพิ่มเติมมาอีก 2 functions เพื่อความสะดวกในการทำงานมากขึ้น คือ sort และ evolute
4. 1 initiation จะมีงานย่อยคือ
สร้าง populaion สำหรับ generation แรก หรือ G(0) และการกำหนด hyper parameters ที่จำเป็น
def __init__(self,pop_size):
self.population = []
self.pop_size = pop_size
for _ in range(pop_size) :
ind = Individual()
self.population.append(ind)
จาก code จะเห็นว่า population คือ list ของ Individual ซึ่งแต่ละ Individual บรรจุ solution ที่สร้างขึ้นมาแบบสุ่ม เพื่อเป็นการง่ายในการเลือกเอา Individual ที่ดี เราต้องการ function ที่ใช้เรียงลำดับ Individual โดยอิงกับค่า fitness
def sort(self):
self.population = sorted(self.population,key=lambda x : x.fitness())
ในขั้นตอนของ initiation หลังจากสร้าง population ชุดแรกเสร็จแล้วก็ต้องทำการ sort population นั้นเพื่อเป็นการ evaluate
def __init__(self,pop_size):
self.population = []
self.pop_size = pop_size
for _ in range(pop_size) :
ind = Individual()
self.population.append(ind)
self.sort()
4.2 select มีหน้าที่คัดเลือก Individual จาก population ออกมาแบบสุ่ม โดยในตัวอย่างนี้จะใช้วิธี roulette selection โดยกำหนดให้โอกาสในการถูกเลือกของสมาชิกใน population มีเท่ากันหมด (uniform distribution)
def select(self):
p = np.random.choice(self.population)
return p
4.3 crossover เป็นกระบวนแลกเปลี่ยน gene ระหว่าง 2 individual ที่ถูกเลือกมาแบบสุ่ม ในตัวอย่างนี้จะใช้ แบบ single point crossover
def crossover(self,ind1,ind2):
# select crossover point
l = min(len(ind1.chromosome),len(ind2.chromosome))
cp = np.random.randint(0,l-1)
#swap gene
new_chromosome = []
new_chromosome.extend(ind1.chromosome[cp:])
new_chromosome.extend(ind2.chromosome[:cp])
offspring = Individual()
offspring.chromosome = new_chromosome
return offspring
 |
4.4 mutation เป็นขั้นตอนการเพิ่ม gene ใหม่เข้าไปใน population เพราะเป็นไปได้ว่าในขั้นตอนการสร้าง generation นั้น มี gene บาง gene ไม่ได้ถูกนำเข้าไปร่วม ซึ่งอาจนำไปสู่การไม่สามารถแก้ปัญหาได้ กระบวน mutation ออกแบบมาเพื่อเพิ่มความสามารถในการแก้ปัญหา แต่มีข้อคิดว่า probability ในการเกิด mutation ไม่ควรมากเกินไปหรือน้อยเกินไป เพราะอาจทำให้เกิดการเปลี่ยนแปลงมากเกินไปก็ได้
def mutate(self,ind,indpb=0.1):
# indpb is chance of mutation happen
for i in range(len(ind.chromosome)):
if np.random.rand() <= indpb:
mt = np.random.choice(gene_set)
ind.chromosome[i] = mt
return ind
จะเห็นได้ว่า mutation ทำให้ gene ในตำแหน่งที่ 2 มีการเปลี่ยนแปลงจากต้นฉบับ
4.5 elitism คือกระบวนการส่งผ่าน individual ที่มี chromosome ที่ดีไปยัง generation ถัดไปโดยไม่ต้องผ่านการ selection, crossover และ mutation เพื่อเป็นการการันตีว่าในประชากรรุ่นถัดไปจะมี chromosome ที่ดีปะปนอยู่
def elitism(self,rate = 0.1):
elites = []
elite_size = round(self.pop_size * rate)
elites.extend(self.population[-elite_size:])
return elites
4.6 evolution เป็นการนำขั้นตอนทั้งหมดที่กล่าวมาแล้ว มาทำงานร่วมกันเพื่อให้เกิดวิวัฒนาการ
def evolute(self):
# get elite
gt = self.elitism()
while len(gt) < self.pop_size :
# select parent
p1 = self.select()
p2 = self.select()
# crossover to get new offspring
offspring = self.crossover(p1,p2)
mutated = self.mutate(offspring,indpd=0.1)
gt.append(mutated)
# move to next generation
self.population = gt
# sort population
self.sort()
ทดสอบ
def get_the_best(pop):
return pop[-1]
def display(ind):
return "{},{}".format (''.join(ind.chromosome),ind.fitness())
pop_size = 100
epochs = 5000
epoch = 0
log = []
ga = GA(pop_size) # create population size 10
best = get_the_best(ga.population)
while not best.chromosome == target and epoch < epochs :
ga.evolute()
best = get_the_best(ga.population)
if epoch % 50 == 0 :
print("Epoch {} : {}".format(epoch,display(best)))
log.append(best.fitness())
epoch += 1
จากผลลัพธ์ที่แสดงในภาพจะเห็นว่าในรอบแรกๆ ของ evolution ค่า fitness ยังคงต่ำอยู่ และ chromosome ที่เก็บตัวอักษรก็แสดงให้เห็นว่าไม่ได้ใกล้เคียงกับ target เลย จนเมื่อจำนวนรอบของการ evolution มากขึ้น ค่า fitness ค่อยๆปรับตัวเพิ่มขึ้นทีละน้อย ชุดตัวอักษรที่เก็บใน chromosome ก็เริ่มแสดงให้เห็นว่ามีความใกล้เคียงกับ target มากขึ้น นี่คือตัวอย่างแรกที่แสดงให้เห็นขั้นตอนการสร้างโปรแกรมด้วย Genetic Algorithm ที่ให้โปรแกรมปรับตัวเองให้เข้าใกล้เป้าหมายทีละน้อย ทำนองเดียวกับที่เกิดขึ้นในสิ่งมีชีวิต
ในตอนต่อไปจะนำเอาตัวอย่างการใช้งานแบบอื่นมาให้ดูกัน รวมถึงการทำ curve fitting ในข้อมูลการระบาดของ Covid-19 ด้วย
เอกสารอ้างอิง
ความคิดเห็น
แสดงความคิดเห็น