這一節的標題是
9.6 Evolving Forces: Smart Rockets
因為方格子標題字數限制，所以沒完整顯現
因超過方格子內容長度限制，故分成上、下兩部分
這一節要用GA來設計一款具有演化功能的智慧火箭。
原書作者提到，之所以會選定火箭這個主題，主要是受到Jer Thorp於2009年在他的部落格所發表的〈Smart Rockets〉這個GA範例的啟發。Thorp提到，美國太空總署NASA使用演化式運算來解決各式各樣的問題；這些問題從衛星天線的設計到火箭的點火模式都有。這促使他用Flash的ActionScript寫了個範例來示範GA，而這個範例的主角，就是會不斷進行演化的智慧火箭。
在Thorp的範例中，一群火箭由畫面底部發射，目的是擊中位於畫面頂部的目標物。在火箭和目標物之間有許多障礙物，所以火箭沒辦法以直線的方式朝目標物飛過去；換句話說，火箭發射之後，必須先閃過障礙物之後才能擊中目標。所幸，這些火箭每個都配備有可以改變強度和方向的推進器，因此可以改變飛行方向來閃過障礙物。這些推進器不會同時作動，也不會持續作動，而是會依照設定好的順序，一個接一個的接續作動。不像Thorp使用那麼複雜的火箭，為了簡化問題，我們使用的是比較簡單，就只配備一具理想化推進器的火箭。這具理想化的推進器在現實中不可能存在，因為它可以朝任何方向，以任何需要的強度作動。
Developing the Rockets
要設計智慧火箭，第一步當然是要先設計用來描述智慧火箭的類別。這個類別不用從頭設計，把先前設計過的如Mover、Vehicle等類別拿來改即可。
我們把描述智慧火箭的類別叫做Rocket，初步設計成這樣：
class Rocket:
def __init__(self, x, y):
# 火箭的初始位置、初始速度、初始加速度
self.position = pygame.Vector2(x, y)
self.velocity = pygame.Vector2(0, 0)
self.acceleration = pygame.Vector2(0, 0)
def apply_force(self, force):
self.acceleration += force/self.mass
def update(self):
self.velocity += self.acceleration
self.position += self.velocity
self.acceleration *= 0
要使用GA讓火箭進行演化，必須考慮如何設計上一節提到的三個關鍵部分：族群規模和突變率、適應度函數、基因型與表現型。
在族群規模和突變率部分，因為只是在初步設計的階段，所以就先不要花太多的心思在這兩個參數上，暫時用個看起來合理的數字就可以了；族群規模先使用50，而突變率則使用1%。
在適應度函數方面，因為目的是要讓火箭擊中目標，所以火箭距離目標越近，適應度應該要越高。因此，適應度函數就設計成讓適應度和火箭與目標物間的距離成反比就可以了；這樣子距離越小，適應度會越大，而距離越大，適應度則會越小。
Rocket類別要增加計算適應度的功能，首先在__init__()方法新增一個fitness屬性：
def __init__(self, x, y):
# 火箭的初始位置、初始速度、初始加速度
self.position = pygame.Vector2(x, y)
self.velocity = pygame.Vector2(0, 0)
self.acceleration = pygame.Vector2(0, 0)
self.fitness = 0
接下來要新增一個計算適應度的方法。之所以會把計算適應度的方法放在Rocket類別中，是因為就只有Rocket物件才會知道它和目標物之間的距離，所以也只有它才能利用這個距離來計算它的適應度。假設target向量表示目標物的向量位置，則計算適應度的方法可以設計成這樣：
def calculate_fitness(self, target):
distance = self.position.distance_to(target)
self.fitness = 1/distance
如果想要讓適應度為二次增長，則可以寫成
def calculate_fitness(self, target):
distance = self.position.distance_to(target)
self.fitness = 1/(distance*distance)
在基因型與表現型部分，要考慮的是它們之間的關聯性。表現型，很顯然是Rocket這個類別。那基因型呢？該用什麼當基因型呢？
因為我們的目的是要讓火箭擊中目標，所以火箭在飛行途中，勢必得改變行進的方向來避開障礙物。那火箭要怎麼改變行進的方向呢？因為火箭只有一具推進器，所以唯一能讓火箭改變方向的，就只有推進器所提供的推力。推力是力，具有方向和大小，可以用向量來描述。這也就是說，我們可以用向量來描述推進器的作用，而火箭的行為，也就是飛行方向和速度，也就取決於這個向量的大小和方向。因此，將描述推進器推力的向量作為基因型，會是挺合適的做法。
將推進器所提供的推力作為基因型，這意味著DNA類別中，genes這個list裡頭所放的，會是描述推力的向量。那genes裡頭會有多少個元素呢？在我們的模擬世界中，時間是以一幀一幀的畫面來推移的，所以當火箭發射之後，在每幀畫面中，都會有一個推力向量作用在火箭上；這也就是說，火箭飛行了多少幀畫面，就會有多少個推力向量作用在火箭上。因此，genes這個list裡頭的元素數量，就會等於火箭飛行所歷經的畫面幀數。
確立了基因型之後，DNA類別的__init__()方法就設計成這樣：
def __init__(self, length):
self.length = length
self.max_force = 0.1
self.genes = []
for _ in range(self.length):
r = random.uniform(0, self.max_force)
theta = random.uniform(0, 360)
# 大小介於0～最大出力，方向為任意方向的推力
thrust = pygame.Vector2.from_polar((r, theta))
self.genes.append(thrust)
設計時，我們加了個用來限制最大推力的max_force屬性，以避免過大的推力讓火箭飛得太快而影響模擬效果。另外，在設定genes的初始值時，我們並不是寫成
thrust_x = random.uniform(-1, 1)
thrust_y = random.uniform(-1, 1)
thrust = pygame.Vector2(thrust_x, thrust_y)
因為這樣的寫法所產生的推力，在不同的方向，其最大強度會有所不同。例如，在0°方向，也就是thrust_y=0時，最大的推力，也就是thrust這個向量的最大值，是1；然而，在45°方向，也就是thrust_x和thrust_y的值相同時，最大的推力，則會是⎷2。說得更精確一點，這樣子的寫法所產生的所有可能推力向量，會形成一個填滿的正方形。所以，為了避免這種情況，我們的寫法是在圓上取點，然後用極座標轉成直角座標，這樣不同方向的推力就會有相同的最大強度，而所產生的所有可能推力向量，則會形成一個圓。
DNA類別的__init__()方法修改完之後，mutate()方法也須跟著修改。當產生突變時，代表火箭推進器提供的推力要重置，所以程式修改成
def mutate(self, mutation_rate):
for i in range(self.length):
if random.random() < mutation_rate:
# 產生突變；推力重置
r = random.uniform(0, self.max_force)
theta = random.uniform(0, 360)
# 大小介於0～最大出力，方向為任意方向的推力
thrust = pygame.Vector2.from_polar((r, theta))
self.genes[i] = thrust
完整的DNA類別程式碼如下：
class DNA:
def __init__(self, length):
self.length = length
self.max_force = 0.1
self.genes = []
for _ in range(self.length):
r = random.uniform(0, self.max_force)
theta = random.uniform(0, 360)
# 大小介於0～最大出力，方向為任意方向的推力
thrust = pygame.Vector2.from_polar((r, theta))
self.genes.append(thrust)
def crossover(self, partner):
child = DNA(self.length)
crossover_point = random.randint(0, self.length-1)
# 在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):
for i in range(self.length):
if random.random() < mutation_rate:
# 產生突變；推力重置
r = random.uniform(0, self.max_force)
theta = random.uniform(0, 360)
# 大小介於0～最大出力，方向為任意方向的推力
thrust = pygame.Vector2.from_polar((r, theta))
self.genes[i] = thrust
基因型和表現型都有了，那要怎麼把他們聯繫起來呢？要達到這個目的，首先要讓Rocket類別知道有DNA類別的物件存在；這個修改一下__init__()方法，新增一個dna參數就可以了。另外，在dna的genes這個list中，存放著火箭發射之後在每幀畫面中推進器所提供的推力。所以，我們加入變數gene_counter來計數火箭發射之後已經歷經了多少幀畫面，以便從genes中取出對應的火箭推力，將其施加在火箭上：
def __init__(self, x, y, dna):
:
:
self.dna = dna
self.gene_counter = 0
def run(self):
self.apply_force(self.dna.genes[self.gene_counter])
self.gene_counter += 1
self.update()
self.show()
完整的Rocket類別程式碼如下：
class Rocket:
def __init__(self, x, y, dna, size=24, mass=1):
# 取得顯示畫面
self.screen = pygame.display.get_surface()
# 讓傳遞進來的數值來決定火箭的質量
self.mass = mass
# 火箭的大小，長 x 寬 = size x size/2
self.size = size
# 火箭的初始位置、初始速度、初始加速度
self.position = pygame.Vector2(x, y)
self.velocity = pygame.Vector2(0, 0)
self.acceleration = pygame.Vector2(0, 0)
self.dna = dna
self.fitness = 0
self.gene_counter = 0
# 設定火箭所在surface的格式為per-pixel alpha，並在上面畫出火箭
self.surface = pygame.Surface((self.size, self.size/2), pygame.SRCALPHA)
rocket_color = (100, 100, 100, 200)
body = [(self.size//5, 0), (self.size//5, self.size//2), (self.size, self.size//4)]
pygame.draw.polygon(self.surface, rocket_color, body)
# 推進器圖案座標為(0, self.size//4-self.size//8), (0, self.size//4+self.size//8),
# (self.size//5+self.size//4, self.size//4)]
thruster = [(0, self.size//8), (0, 3*self.size//8), (9*self.size//20, self.size//4)]
pygame.draw.polygon(self.surface, rocket_color, thruster)
def apply_force(self, force):
self.acceleration += force/self.mass
def update(self):
self.velocity += self.acceleration
self.position += self.velocity
self.acceleration *= 0
def show(self):
# 旋轉surface，讓火箭面朝前進方向
heading = math.atan2(self.velocity.y, self.velocity.x)
rotated_surface = pygame.transform.rotate(self.surface, -math.degrees(heading))
rect_new = rotated_surface.get_rect(center=self.position)
# 把火箭所在的surface貼到最後要顯示的畫面上
self.screen.blit(rotated_surface, rect_new)
def calculate_fitness(self, target):
distance = self.position.distance_to(target)
self.fitness = 1/(distance*distance)
def run(self):
self.apply_force(self.dna.genes[self.gene_counter])
self.gene_counter += 1
self.update()
self.show()
Managing the Population
將基因型和和表現型聯繫起來之後，再來就是寫個Population類別來管理由火箭所組成的族群。這個Population類別不用從頭寫，把電腦猴打字那個例子中的程式拿來改會比較省事一點。不過，要特別注意的是，這兩者之間有個很大的差別：在電腦猴打字那個例子中，每一代的演化，都會在一幀畫面中完成；而在智慧火箭這個例子中，卻是在火箭飛行了一段時間之後，才會進行演化而產生下一代。換句話說，在電腦猴打字的例子中，個體的生命週期是1幀畫面；而在智慧火箭的例子中，個體的生命週期，則是火箭的飛行時間。
在模擬世界中，可以用畫面的幀數來當作時間的計數單位。所以，火箭的飛行時間，也就順理成章地用畫面幀數來衡量。在這裡，我們就用life_span這個變數來存放火箭飛行所歷經的畫面幀數，也就是火箭的飛行時間。
先前提到過，DNA類別中的genes這個list，其長度，也就是元素的數量，會等於火箭飛行所歷經的畫面幀數。所以，在Population類別的__init__()方法中，我們設定
self.dna_length = life_span
來滿足這個要求。
電腦猴打字和智慧火箭這兩者之間，還有另一個比較大的差別：在電腦猴打字的例子中，基因型和表現型是相同的，都是DNA類別；但在智慧火箭的例子中，基因型和表現型是不同的類別，基因型是DNA類別，而表現型則是Rocket類別。所以，智慧火箭Population類別的evolve()方法中，parentA和parentB交配產生子代的寫法，必須改成
child = parentA.dna.crossover(parentB.dna)
這樣才不會出現錯誤。
完整的Population類別程式碼如下：
class Population:
def __init__(self, population_size, mutation_rate, life_span):
self.population_size = population_size
self.mutation_rate = mutation_rate
self.dna_length = life_span
# 發射場位置
screen = pygame.display.get_surface()
self.width, self.height = screen.get_size()
self.launch_site = pygame.Vector2(self.width//2, self.height+20)
self.population = [Rocket(self.launch_site.x, self.launch_site.y, DNA(self.dna_length)) for _ in range(population_size)]
self.generations = 0
def calculate_fitness(self, target):
for rocket in self.population:
rocket.calculate_fitness(target)
def evolve(self):
weights = [rocket.fitness for rocket in self.population]
next_generation = []
for i in range(self.population_size):
[parentA, parentB] = random.choices(self.population, weights, k=2)
child = parentA.dna.crossover(parentB.dna)
child.mutate(self.mutation_rate)
next_generation.append(Rocket(self.launch_site.x, self.launch_site.y, child))
self.population = next_generation
self.generations += 1
def get_generations(self):
return self.generations
def live(self):
for rocket in self.population:
rocket.run()
設計好Population、Rocket、DNA這三個類別之後，在接下來的範例中就來看看，智慧火箭是如何藉由演化來找出擊中目標物的路徑。
Example 9.2: Smart Rockets
因為火箭在存活一段時間之後才會進行演化而產生下一代，所以程式流程會是這樣的：
- 製造火箭族群。
- 讓火箭存活N幀畫面。
- 演化產生下一代。
- 回到步驟2。
這裡的N就是life_span。
從下面兩張執行時的截圖可以看到，一開始的時候，火箭漫無目標四處亂竄，但在經過幾代演化之後，就都逕朝目標飛過去；顯然GA成功地發揮了它的作用。
主程式如下，執行時，按滑鼠左鍵可更動目標物位置至滑鼠指標處，藉此來觀察火箭透過演化來適應環境變化的過程。
# python version 3.10.9
import math
import random
import sys
import pygame # version 2.3.0
pygame.init()
pygame.display.set_caption("Example 9.2: Smart Rockets")
WHITE = (255, 255, 255)
screen_size = WIDTH, HEIGHT = 640, 240
screen = pygame.display.set_mode(screen_size)
FPS = 60
frame_rate = pygame.time.Clock()
# 製造火箭族群
population_size = 50
mutation_rate = 0.01
life_span = 250
population = Population(population_size, mutation_rate, life_span)
font14 = pygame.font.SysFont('courier', 14)
target = pygame.Vector2(320, 24)
life_counter = 0
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
screen.fill(WHITE)
pygame.draw.circle(screen, (100, 100, 100), target, 12)
# 火箭存活life_span幀畫面之後才會進行演化
if life_counter < life_span:
population.live()
life_counter += 1
else:
life_counter = 0
population.calculate_fitness(target)
population.evolve()
string = f'{"Generation #:"}{population.get_generations():>3}'
text = font14.render(string, True, (0, 0, 0))
screen.blit(text, (5, 20))
string = f'{"Cycles left:"}{life_span-life_counter:>4}'
text = font14.render(string, True, (0, 0, 0))
screen.blit(text, (5, 40))
# 按滑鼠左鍵可更動目標物位置至滑鼠指標處
if pygame.mouse.get_pressed()[0]:
target = pygame.Vector2(pygame.mouse.get_pos())
pygame.display.update()
frame_rate.tick(FPS)
