這一節的標題是
9.4 Coding the Genetic Algorithm
因為方格子標題字數限制，所以沒完整顯現
這一節要來實作GA的程式。寫程式的時候，根據上一節的說明，我們把GA的執行過程區分為下列步驟：
- 初始化(initialization)： 造出含有N個元素的起始族群，而這些元素都具有隨機產生的DNA。
- 挑選(selection)： 計算族群中每個元素的適應度，並建立一個交配群。
- 繁殖(reproduction)：重複N次。每次繁殖包含下列步驟
- 根據由元素適應度所計算出來的機率，挑出兩個元素來繁殖下一代。
- 交配(crossover)：結合挑選出來作為父母的兩個元素的DNA，製作其子代的DNA。
- 突變(mutation)：根據給定的機率來修改子代的DNA。
- 把新孕育出來的子代加入新的族群中。
- 用新的族群取代舊的族群，並回到步驟2。
接下來，就根據這些步驟來寫程式。
Step 1: Initialization
在初始化這個步驟中，最主要的是要造出含有N個元素的族群。先前提到過，在GA中，個體、染色體、DNA都是指同樣的東西。所以，我們就來設計一個叫做DNA的類別，用來描述族群中的元素。先前也提到過，DNA中含有基因，所以在設計DNA類別時，我們會把DNA看成是由基因所組成的東西。這也就是說，基因的個數，實際上也就會是DNA的長度。假設DNA的長度是length，我們就用一個相同長度，名稱為genes的list來存放基因這個屬性。初步設計出來的DNA類別會長這樣：
class DNA:
def __init__(self, length):
self.length = length
self.genes = [ ?????????? ]
在這個初步的設計中，並未設定屬性genes的初始值，因為這會隨著要處理的問題不同而有不同的設定。以電腦猴打字的例子來說，電腦猴所打出來的字串是DNA，而字串中的一個個字元，就是基因。在初始化這個步驟中所造出來的元素，其DNA必須是隨機的，這也就是說，在電腦猴打字這個例子中，genes這個list裡頭所放的，必須是隨機產生的字元，這樣才能製造出隨機的DNA。
那實際上要怎麼做，才能產生隨機的字元呢？方法其實挺簡單的，在ASCII (American Standard Code for Information Interchange)中隨機取出字元就可以了。因為我們最終的目標是要讓GA演化出「to be or not to be」這個字串，而在ASCII編號32～127這個範圍中，就包含了大、小寫的英文字母、數字、標點符號、特殊符號等字元。所以，要設定genes的初始值，只要在這個範圍內隨機選取一個數字，並用chr()轉成字元放到genes裡頭就可以了。這個隨機選取字元的功能可以寫成如下的函數：
def random_character():
return chr(random.randint(32, 127))
利用這個函數，設定genes初始值的程式可以這樣寫：
self.genes = [random_character() for _ in range(self.length)]
在這裡，我們之所以把字串拆成一個一個的字元放在list中，而不是直接把整個字串放在一個變數中，是因為這樣處理起來比較方便；畢竟在python中，字串是immutable，沒法改變，這在後面要執行突變步驟時，會是個麻煩。
有了DNA這個類別之後，就可以來製造族群了。假設族群的元素有150個，演化目標是產生「to be or not to be」這個字串，則製造初始族群的程式可以這樣寫：
target = 'to be or not to be'
dna_length = len(target)
population_size = 150
population = [DNA(dna_length) for _ in range(population_size)]
初始化這個步驟的程式到此算是完成了。不過要注意的是，DNA這個類別現在只是個初步的成品，還不完整；在寫後續步驟的程式時，還會再加入新的屬性及方法。
Step 2: Selection
在挑選這個步驟中要做兩件事：計算族群中每個元素的適應度，以及根據適應度挑出適合的元素來建立交配群。先來看看計算元素適應度的程式要怎麼寫，然後再來寫建立交配群的程式。
先前在計算電腦猴所打出字串的適應度時，是去數有幾個正確的字元在正確的位置上。在這裡，我們改變計算方式，改用在正確位置上的正確字元數量的比率來當作適應度。所以，適應度函數會變成
fitness = 在正確位置上的正確字元數量 / 總字元數量
假設正確的字串是放在target這個變數裡頭，則計算DNA適應度的方法可以這樣寫：
def calculate_fitness(self, target):
score = 0
for i in range(self.length):
if self.genes[i] == target[i]:
score += 1
self.fitness = score/len(target)
在DNA類別加入calculate_fitness()方法之後，計算族群中所有元素適應度的程式就可以這樣寫：
for dna in population:
dna.calculate_fitness(target)
算出族群中所有元素的適應度之後，接下來是建立交配群。
在建立交配群時，我們希望適應度越高的元素被挑中的機率越大；要達到這個目的，可以使用輪盤挑選法(roulette wheel selection)。
輪盤挑選法的概念很簡單：在一個大轉輪上塗有不同的顏色，每個顏色代表族群中的一個元素。轉動輪盤，射出飛鏢。被飛鏢射中的顏色所對應的元素，就是被挑中的元素。很顯然的，佔有輪盤面積越大的顏色，就越容易被飛鏢射中。這也就是說，每個顏色所佔有的面積比率，就是那個顏色會被飛鏢射中的機率，也就是那個顏色所對應的元素會被挑中的機率。
那程式要怎麼寫呢？其實挺簡單的。假設有個list裡頭放了30個A、40個B、5個C、10個D、15個E，那隨機從中選出一個字母時，選中A的機率會是0.3，選中B的機率是0.4，以此類推；這個list就相當於是輪盤，而字母的數量比率，就相當於是佔有輪盤面積的比率。依照這樣子的方式，利用輪盤挑選法來成立交配群的程式，可以這樣寫：
min_fitness = min([dna.fitness for dna in population])
scale_up = int(1+1/min_fitness)
mating_pool = []
for dna in population:
n = int(scale_up*dna.fitness)
for _ in range(n):
mating_pool.append(dna)
這裡要注意的是，每個元素放進交配群的數量，也就是n，的計算方式。因為元素的適應度是小於1的浮點數，所以必須把這個數字放大，這樣才能得到可以使用的整數。那要放大多少呢？要放大到所有的元素都能夠出現在交配群中才行。原書是直接寫死，放大100倍，但這並不能保證所有的元素都能夠出現在交配群中。事實上，不管放大多少倍，直接寫死的方式，並不能保證所有的元素都能夠出現在交配群中；而且放大倍數越大，代表交配群會越大，變數mating_pool佔用的記憶體也會越多。上面那段程式中放大倍數sacle_up的算法，除了能確保所有的元素都能夠出現在交配群中之外，也比較節省記憶體。
交配群成立之後，隨機從mating_pool中所選出的元素，就會是符合要求的元素。所以，如果要挑出兩個元素來交配，程式可以這樣寫：
[parentA, parentB] = random.choices(mating_pool, k=2)
除了輪盤挑選法之外，還有一種接力賽法(relay race method)也可以讓適應度越高的元素被挑中的機率越大。這個方法的概念很簡單，就隨機挑選一段賽跑的距離，然後讓族群中所有的元素依序跑一段距離，而這段距離和元素正規化後的適應度大小相同。在跑的過程中，誰先抵達終點就挑誰；如果都沒有人抵達終點，那就再從頭依序跑一次，直到有人抵達終點為止。把接力賽法寫成函數，會長這樣：
def weighted_selection(population):
fitness_sum = sum([dna.fitness for dna in population])
start = random.random()
idx = -1
while start>0:
idx += 1
start = start - population[idx].fitness/fitness_sum
return population[idx]
接力賽法會比輪盤挑選法節省記憶體，但因為每次挑選時，就要重新跑一次，所以計算量會比較大。
除了原書上介紹的這兩種方法外，也可以直接就使用random module中的choices()函數來寫。寫法很簡單，就這樣：
weights = [dna.fitness for dna in population]
[parentA, parentB] = random.choices(population, weights, k=2)
參數weights是權重而不是機率，所以不需將適應度正規化。
Exercise 9.2
def accept_reject(population):
fitness_sum = sum([dna.fitness for dna in population])
probabilities = [dna.fitness/fitness_sum for dna in population]
while True:
idx = random.randint(0, len(population)-1)
p = random.random()
if p < probabilities[idx]:
return population[idx]
Exercise 9.3
population.sort(key=lambda dna: dna.fitness)
for i in range(population_size):
population[i].fitness = 1 + 0.01*i
關於挑選，有個地方要注意的是，我們在挑選時並未排除相同的元素被重複挑出的可能性；這也就是說，有可能挑出來的父、母，其實是同一個元素。如果要的話，也可以限制父、母一定是由不同的元素所組成；不過這樣做，對最後的結果應該不會有什麼太大的影響。
Exercise 9.4
挑選出一個元素之後，把該元素從配對群中去除，這樣再從配對群中挑選出來的元素，就保證不會是相同的元素。程式如下：
mating_pool = make_mating_pool(population)
parentA = random.choice(mating_pool)
# 從配對群中去除parentA
mating_pool = [dna for dna in mating_pool if dna is not parentA]
parentB = random.choice(mating_pool)
Step 3: Reproduction (Crossover and Mutation)
挑選出作為父、母的兩個元素之後，接下來就是要用這兩個元素的DNA來產生下一代的DNA，然後讓下一代的DNA產生突變；寫成程式就是
child = parentA.crossover(parentB)
child.mutate(mutation_rate)
當然，這兩行程式要能執行，必須先在DNA類別中加入crossover()和mutate()這兩個方法。先來看看crossover()方法要怎麼寫。
根據上面程式中呼叫crossover()方法的寫法，crossover()方法會接收一個DNA物件引數，然後傳回一個DNA物件。所以，crossover()方法就設計成這樣：
def crossover(self, partner):
child = DNA(self.length)
crossover_point = random.randint(0, self.length)
# 在crossover_point之前的基因來自此DNA，之後的基因則來自partner這個DNA
for i in range(self.length):
if i < crossover_point:
child.genes[i] = self.genes[i]
else:
child.genes[i] = partner.genes[i]
return child
這個寫法是隨機選取下刀的地方將child的DNA區分成兩部分，並讓前面那部份的基因來自parentA，而後面那部分則來自parentB。
Exercise 9.5
def crossover_coin_flipping(self, partner):
child = DNA(self.length)
for i in range(self.length):
if random.randint(0, 1):
child.genes[i] = self.genes[i]
else:
child.genes[i] = partner.genes[i]
return child
接下來是mutate()方法。mutate()方法很單純，就只是針對genes這個list中的每個元素，根據設定好的突變率來決定，是不是要用隨機選取的字元來取代它；程式如下：
def mutate(self, mutation_rate):
self.genes = [random_character() if random.random()<mutation_rate else c for c in self.genes]
Putting It All Together
把前面的東西整合起來，並加入用來取出DNA字串的get_phrase()方法，可以得到如下的DNA類別：
class DNA:
def __init__(self, length):
self.length = length
self.genes = [random_character() for _ in range(self.length)]
self.fitness = 0
def calculate_fitness(self, target):
score = 0
for i in range(self.length):
if self.genes[i] == target[i]:
score += 1
self.fitness = score/len(target)
def crossover(self, partner):
child = DNA(self.length)
crossover_point = random.randint(0, self.length)
# 在crossover_point之前的基因來自此DNA，之後的基因則來自partner這個DNA
for i in range(self.length):
if i < crossover_point:
child.genes[i] = self.genes[i]
else:
child.genes[i] = partner.genes[i]
return child
def mutate(self, mutation_rate):
self.genes = [random_character() if random.random()<mutation_rate else c for c in self.genes]
def get_phrase(self):
return ''.join(self.genes)
在下面的範例中，我們就利用DNA類別以及random_character()函數，根據GA的步驟，以演化出「to be or not to be」這個句子為目標，讓族群進行演化。
Example 9.1: Genetic Algorithm for Evolving Shakespeare
# python version 3.10.9
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Example 9.1: Genetic Algorithm for Evolving Shakespeare")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 640, 400
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
target = 'to be or not to be'
# Step 1: 初始化
population_size = 150
dna_length = len(target)
population = [DNA(dna_length) for _ in range(population_size)]
mutation_rate = 0.01
font = pygame.font.SysFont('courier', 12)
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
screen.fill(WHITE)
for dna in population:
dna.calculate_fitness(target)
weights = [dna.fitness for dna in population]
next_generation = []
for i in range(population_size):
# Step 2: 挑選
[parentA, parentB] = random.choices(population, weights, k=2)
# Step 3: 繁殖
child = parentA.crossover(parentB)
child.mutate(mutation_rate)
next_generation.append(child)
# Step 4
population = next_generation
# 顯示個體DNA字串；4欄，每欄30筆
row = 0
for i in range(0, population_size, 4):
string = ''
for j in range(4):
if (i+j) < population_size:
string += population[i].get_phrase() + ' '
text = font.render(string, True, (0, 0, 0))
screen.blit(text, (30, (row%30)*15))
row += 1
pygame.display.update()
frame_rate.tick(FPS)
Exercise 9.6
class Population:
def __init__(self, population_size, mutation_rate, target):
self.population_size = population_size
self.mutation_rate = mutation_rate
self.target = target
self.dna_length = len(self.target)
self.population = [DNA(self.dna_length) for _ in range(population_size)]
self.generations = 0
self.best = ''
self.target_score = 1
self.finished = False
def calculate_fitness(self):
for dna in self.population:
dna.calculate_fitness(self.target)
def evolve(self):
weights = [dna.fitness for dna in self.population]
next_generation = []
for i in range(self.population_size):
[parentA, parentB] = random.choices(self.population, weights, k=2)
child = parentA.crossover(parentB)
child.mutate(self.mutation_rate)
next_generation.append(child)
self.population = next_generation
self.generations += 1
def evaluate(self):
scores = [dna.fitness for dna in self.population]
max_score = max(scores)
idx = scores.index(max_score)
self.best = self.population[idx].get_phrase()
if max_score >= self.target_score:
self.finished = True
def get_best(self):
return self.best
def is_finished(self):
return self.finished
def get_generations(self):
return self.generations
def get_average_fitness(self):
scores = [dna.fitness for dna in self.population]
return sum(scores)/self.population_size
def get_all_phrases(self):
phrases = []
for dna in self.population:
phrases.append(dna.get_phrase())
return phrases
主程式
# python version 3.10.9
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Exercise 9.6")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 650, 450
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
target = 'to be or not to be'
population_size = 150
mutation_rate = 0.01
population = Population(population_size, mutation_rate, target)
population.calculate_fitness()
font10 = pygame.font.SysFont('courier', 10)
font12 = pygame.font.SysFont('courier', 12)
font18 = pygame.font.SysFont('courier', 18)
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
screen.fill(WHITE)
if not population.is_finished():
population.evolve()
population.calculate_fitness()
population.evaluate()
best_phrase = population.get_best()
average_fitness = population.get_average_fitness()
generations = population.get_generations()
# 顯示演化資料
text = font12.render('Best phrase:', True, (0, 0, 0))
screen.blit(text, (5, 5))
text = font18.render(population.get_best(), True, (0, 0, 0))
screen.blit(text, (5, 35))
string = f'{"total generations:":<20}{population.get_generations():>10}'
text = font12.render(string, True, (0, 0, 0))
screen.blit(text, (5, 80))
string = f'{"average fitness:":<20}{population.get_average_fitness():>10.2}'
text = font12.render(string, True, (0, 0, 0))
screen.blit(text, (5, 105))
string = f'{"total population:":<20}{population_size:>10}'
text = font12.render(string, True, (0, 0, 0))
screen.blit(text, (5, 130))
string = f'{"mutation rate:":<20}{mutation_rate:>10.0%}'
text = font12.render(string, True, (0, 0, 0))
screen.blit(text, (5, 155))
# 顯示個體DNA字串；3欄，每欄30筆
row = 0
for i in range(0, population_size, 3):
phrases = population.get_all_phrases()
string = ''
for j in range(3):
if (i+j) < population_size:
# string += population.population[i].get_phrase() + ' '
string += phrases[i] + ' '
text = font10.render(string, True, (0, 0, 0))
screen.blit(text, (250, 10+(row%30)*15))
row += 1
pygame.display.update()
frame_rate.tick(FPS)
Exercise 9.7
使用下列動態突變率公式來計算突變率：
mutation_rate = 0.05*(1-0.5*(parentA.fitness+parentB.fitness))
當父母的適應度平均值是0.8時，算出來的突變率是0.01。所以，使用這條公式意味著以0.8為分水嶺，當父母的適應度平均值高於0.8時，突變率會低於0.01；反之，當父母的適應度平均值低於0.8時，突變率會高於0.01。
把evolve()方法改成使用動態突變率
def evolve_dynamic_mutation_rate(self):
weights = [dna.fitness for dna in self.population]
total_weights = sum(weights)
next_generation = []
for i in range(self.population_size):
[parentA, parentB] = random.choices(self.population, weights, k=2)
child = parentA.crossover(parentB)
mutation_rate = 0.05*(1-0.5*(parentA.fitness+parentB.fitness))
child.mutate(mutation_rate)
next_generation.append(child)
self.population = next_generation
self.generations += 1
分別使用定值突變率0.01及動態突變率跑10次，比較其平均適應度及平均世代數如下：
突變率0.01 動態突變率
平均適應度 0.799 0.849
平均世代數 1475.2 798.9
從這結果看起來，使用動態突變率的效果比較好。但是，這就只是這個例子、這個動態突變率公式所看到的結果而已。如果把動態突變率的公式改成
mutation_rate = 0.03*(1-0.5*(parentA.fitness+parentB.fitness))
結果平均適應度是0.889，而平均世代數則為1810.3；雖然平均適應度更高，但平均世代數則比使用定值突變率0.01時差。所以，動態突變率不見得一定就比定值突變率好，這很難去比較。事實上，光就定值突變率來說，想找出能夠得到最好效果的數值，恐怕都是件不可能的任務，更何況是計算公式可以有各式各樣定法的動態突變率了。
