The Nature of Code閱讀心得與Python實作：9.7 Interactive Selection

Karl Sims是位以在電腦動畫中使用粒子系統及人工生命而聞名的數位媒體藝術家及視覺特效軟體開發人員，他設計了互動媒體裝置Galápagos；這個裝置可藉由與觀賞者的互動，讓顯示在12台螢幕上的影像，依循GA的挑選、繁殖等步驟，隨著時間的流逝而進行演化。

互動式挑選的概念其實挺簡單的，重點就在於要怎麼產生適應度值。接下來就用個簡單的例子來介紹互動式挑選實際上是怎麼做的；在這個例子中，構成GA族群的，是一朵朵的花朵，而花朵的適應度，則由使用者透過滑鼠來設定。

先來設計基因型，也就是DNA類別。每朵花都由花瓣、花苞、花莖所構成，其尺寸、數量為：

• 花瓣：數量2～16；直徑4～24像素。
• 花苞：直徑24～48像素。
• 花莖：長度50～100像素。

至於花的顏色，則是由r、g、b所組成。另外，當花瓣數量比較多時會重疊，所以讓花瓣的顏色具有透明度，這樣比較能看出一瓣一瓣的花瓣。這些屬性總共有14個，以下列順序放在genes這個list中：

• genes[0]～genes[3]：花瓣顏色r、g、b、a
• genes[4]：花瓣尺寸
• genes[5]：花瓣數量
• genes[6]～genes[8]：花苞顏色r、g、b
• genes[9]：花苞尺寸
• genes[10]～genes[12]：花莖顏色r、g、b
• genes[13]：花莖長度

不過要注意的是，為了處理方便，genes的元素值全部都設定成0～1的浮點數，在使用時，再根據實際上的需要，使用0.4節介紹過的轉換公式，映射到需要的範圍中。

設計好的DNA類別長這樣：

class DNA:
    def __init__(self):
        self.length = 14
        self.genes = [None]*self.length
        for i in range(self.length):
            self.genes[i] = random.uniform(0, 1)
        
    def crossover(self, partner):
        child = DNA()
        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:
                self.genes[i] = random.uniform(0, 1)

要注意一下，取亂數時，這裡用的是random.uniform(0, 1)而不是random.random()；這兩者的主要差異，在於亂數上限值不同。在計算花的顏色、數量、尺寸時，必須依據亂數產生器所產生的亂數範圍來調整所使用的計算式。

接下來來設計表現型，也就是用來描述花朵的Flower類別。這個類別挺單純的，就長這樣：

class Flower:
    def __init__(self, dna, x, y):
        # 取得顯示畫面
        self.screen = pygame.display.get_surface()
        
        self.dna = dna
        
        # 方框中心點位置
        self.x, self.y = x, y
        # 方框大小
        self.w, self.h = 70, 140
        
        # 設定所在surface的格式為per-pixel alpha
        self.surface = pygame.Surface((self.w, self.h+20), pygame.SRCALPHA)
        
        self.bounding_box = self.surface.get_rect()
        self.bounding_box.h -= 20
        self.rect = self.bounding_box.copy()
        
        self.bounding_box.center = (self.x, self.y)        
        
        self.fitness = 1
        
        self.rollover_on = False
        
        self.font = pygame.font.SysFont('courier', 14)
        
    def show(self):
        genes = self.dna.genes
        
        # 花瓣顏色、半徑、數量
        petal_color = [int(255*genes[i]) for i in range(4)]
        petal_size = 20*genes[4] + 4
        petal_count = int(14*genes[5] + 2)
                
        # 花苞顏色、半徑
        center_color = [int(255*genes[i]) for i in range(6, 9)]
        center_size = 24*genes[9] + 24
        
        # 花莖顏色、長度
        stem_color = [int(255*genes[i]) for i in range(10, 13)]
        stem_length = 50*genes[13] + 50

        self.surface.fill((255, 255, 255))
        
        # 滑鼠選中的花朵，方框內的底色由白轉灰
        if self.rollover_on:
            pygame.draw.rect(self.surface, (220, 220, 220, 230), self.rect)

        # 長方形外框
        pygame.draw.rect(self.surface, (0, 0, 0), self.rect, 1)
        
        # 畫花莖
        stem_start, stem_end = (self.w/2, self.h), (self.w/2, self.h-stem_length)
        pygame.draw.line(self.surface, stem_color, stem_start, stem_end, 5) 
        
        # 畫花瓣
        for i in range(petal_count):
            angle_rad = i*2*math.pi/petal_count
            petal_x = stem_end[0] + petal_size*math.cos(angle_rad)
            petal_y = stem_end[1] + petal_size*math.sin(angle_rad)
            
            # 將花瓣畫在個別的surface上，這樣才能看出透明度的效果
            surf = pygame.Surface((petal_size, petal_size), pygame.SRCALPHA)
            surf_rect = surf.get_rect(center=(petal_x, petal_y))
            pygame.draw.circle(surf, petal_color, (petal_size/2, petal_size/2), petal_size/2)
            self.surface.blit(surf, surf_rect)
                    
        # 畫花苞
        pygame.draw.circle(self.surface, center_color, stem_end, center_size/2)
        
        # 顯示適應度
        text = self.font.render(f'{int(self.fitness)}', True, (0, 0, 0))
        text_rect = text.get_rect(center=(self.w/2, self.h+10))
        self.surface.blit(text, text_rect)
        
        self.screen.blit(self.surface, self.bounding_box)
        
    def rollover(self):
        x, y = pygame.mouse.get_pos()
        if self.bounding_box.collidepoint(x, y):
            self.rollover_on = True
            self.fitness += 0.25
        else:
            self.rollover_on = False

這裡頭有個rollover()方法，其主要功能是當滑鼠指標移到某朵花上時，那朵花的適應度值會增加；使用者可藉此來設定花朵的適應度值。

至於Population類別，稍微修改一下並新增一個rollover()方法就可以了：

class Population:
    def __init__(self, population_size, mutation_rate):
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        
        self.population = [None]*population_size
        for i in range(self.population_size):
            self.population[i] = Flower(DNA(), 40+i*80, 120)

        self.generations = 0
        
    def rollover(self):
        for flower in self.population:
            flower.rollover()

    def evolve(self):
        weights = [flower.fitness for flower 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(Flower(child, 40+i*80, 120))
            
        self.population = next_generation   
        self.generations += 1
        
    def get_generations(self):
        return self.generations
    
    def show(self):
        for flower in self.population:
            flower.show()

Example 9.4: Interactive Selection

實際執行的結果長這樣：

主程式

# 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.4: Interactive Selections")

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 = 8
mutation_rate = 0.05
population = Population(population_size, mutation_rate)

font = pygame.font.SysFont('courier', 16)
button_caption = font.render('evolve new generation', True, (0, 0, 0), (200, 200, 200))
button = button_caption.get_rect()
button.topleft = (15, 15)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()           
        elif event.type == pygame.MOUSEBUTTONDOWN:
            if event.button == 1:
                x, y = event.pos
                if button.collidepoint(x, y):
                    population.evolve()

    screen.fill(WHITE)
    
    population.show()
    population.rollover()
        
    screen.blit(button_caption, button.topleft)  

    string = f'{"Generation "}{population.get_generations():<3}'
    text = font.render(string, True, (0, 0, 0))
    screen.blit(text, (5, HEIGHT-25))          
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 9.13

將DNA類別genes屬性的元素數量由14個增加到19個；最後5個就存放花朵專屬的背景聲：

def __init__(self):
    self.length = 19
    :
    :

在Flower類別新增play_sound()方法：

def play_sound(self):        
    freqs = [1047, 1175, 1319, 1397, 1568, 1760, 1976, 2093]     
    tone_idx = [int(8*self.dna.genes[i]) for i in range(14, 19)]
    for idx in tone_idx:
        winsound.Beep(freqs[idx], 10)  

修改Flower類別的rollover()方法，當滑鼠移至某朵花時，就播放一次其背景聲：

def rollover(self):
    x, y = pygame.mouse.get_pos()
    if self.bounding_box.collidepoint(x, y):
        # 滑鼠選中花朵時，播放一次背景聲
        if not self.rollover_on:
            self.play_sound()
        
        self.rollover_on = True
        self.fitness += 0.25
    else:
        self.rollover_on = False

Exercise 9.14

參考Karl Sims的論文〈Evolving Virtual Creatures〉，用segment組合成一棵樹。每個segment有兩個連接點，突變會發生在segment的顏色上，以及連接點參數所控制的segment特性如位置、方位、長度及寬度的縮放比例等。

程式如下：

class Population:
    def __init__(self, population_size, mutation_rate):
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        
        self.population = [None]*population_size
        for i in range(self.population_size):
            self.population[i] = Tree(DNA(), 90+150*(i//2), 120+180*(i%2))

        self.generations = 0
        
    def rollover(self):
        for tree in self.population:
            tree.rollover()

    def evolve(self):
        weights = [tree.fitness for tree 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)
            # 有些segment可能會脫離連接點，故全部重新接合
            child.re_connect()
            next_generation.append(Tree(child, 90+150*(i//2), 120+180*(i%2)))
            
        self.population = next_generation   
        self.generations += 1
        
    def get_generations(self):
        return self.generations
    
    def show(self):
        for tree in self.population:
            tree.show()


class DNA:
    def __init__(self):
        scale_w = random.uniform(1, 2)
        scale_h = random.uniform(1, 2)
        orientation = random.uniform(-120, -60)
        connection = Connection(pygame.Vector2(70, 140), orientation, scale_w, scale_h)
        
        segment_root = Segment()
        segment_root.connect_to = (0, 0)
        segment_root.connect(connection)
                
        self.genes = [segment_root]
        # 生成整棵樹
        self.generate(segment_root, 4, self.genes)
        
        self.length = len(self.genes)
        
    def crossover(self, partner):
        child = DNA()
        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] = copy.deepcopy(self.genes[i])
            else:
                child.genes[i] = copy.deepcopy(partner.genes[i])
                
        return child

    def mutate(self, mutation_rate):    
        for segment in self.genes:
            # 顏色突變
            color = list(segment.color)
            for i in range(3):
                if random.random() < mutation_rate:
                    color[i] = random.randint(0, 255)

            segment.color = tuple(color)                
            
            # 連接點突變
            for i in range(2):
                if random.random() < mutation_rate:
                    segment.connections[i].orientation += random.uniform(-5, 5)
            
                if random.random() < mutation_rate:
                    segment.connections[i].scale_width += random.uniform(-0.1, 0.1)
            
                if random.random() < mutation_rate:
                    segment.connections[i].scale_height += random.uniform(-0.1, 0.1)
            
    def generate(self, segment, level, genes):
        if level == 0:
            return 
        
        idx = genes.index(segment)
        
        segment1 = Segment()
        segment1.connect_to = (idx, 0)
        segment1.connect(segment.connections[0])
        
        segment2 = Segment()
        segment2.connect_to = (idx, 1)
        segment2.connect(segment.connections[1])
        
        genes.extend([segment1, segment2])
        
        self.generate(segment1, level-1, genes)
        self.generate(segment2, level-1, genes)
        
    def re_connect(self):
        for i in range(1, self.length):
            idx, site = self.genes[i].connect_to
            self.genes[i].connect(self.genes[idx].connections[site])


class Tree:
    def __init__(self, dna, x, y):
        # 取得顯示畫面
        self.screen = pygame.display.get_surface()
        
        self.dna = dna
        
        # 方框中心點位置
        self.x, self.y = x, y
        # 方框大小
        self.w, self.h = 140, 140
        
        # 設定所在surface的格式為per-pixel alpha
        self.surface = pygame.Surface((self.w, self.h+20), pygame.SRCALPHA)
        
        self.bounding_box = self.surface.get_rect()
        self.bounding_box.h -= 20
        self.rect = self.bounding_box.copy()
        
        self.bounding_box.center = (self.x, self.y)        
        
        self.fitness = 1
        
        self.rollover_on = False
        
        self.font = pygame.font.SysFont('courier', 14)
        
        for segment in self.dna.genes:
            direction = pygame.Vector2(1, 0).rotate(segment.orientation)
            segment.end_pos = segment.start_pos + segment.height*direction
        
    def show(self):
        genes = self.dna.genes
        length = self.dna.length
            
        self.surface.fill((255, 255, 255))        
        
        # 滑鼠選中的樹，方框內的底色由白轉灰
        if self.rollover_on:
            pygame.draw.rect(self.surface, (220, 220, 220, 230), self.rect)

        # 長方形外框
        pygame.draw.rect(self.surface, (0, 0, 0), self.rect, 1)

        # 樹
        for segment in genes:
            pygame.draw.line(self.surface, segment.color, segment.start_pos, segment.end_pos, int(segment.width+1))
            
        # 顯示適應度
        text = self.font.render(f'{int(self.fitness)}', True, (0, 0, 0))
        text_rect = text.get_rect(center=(self.w/2, self.h+10))
        self.surface.blit(text, text_rect)
        
        self.screen.blit(self.surface, self.bounding_box)
        
    def rollover(self):
        x, y = pygame.mouse.get_pos()
        if self.bounding_box.collidepoint(x, y):
            self.rollover_on = True
            self.fitness += 0.25
        else:
            self.rollover_on = False


class Segment:
    def __init__(self, width=5, height=20):
        self.width = width
        self.height = height
        
        # 寬度變動範圍為30%
        variation = self.width*0.3
        self.width_range = [self.width-variation, self.width+variation]
        
        # 高度變動範圍為30%
        variation = self.height*0.3
        self.height_range = [self.height-variation, self.height+variation]
        
        self.start_pos = pygame.Vector2() 
        self.end_pos = pygame.Vector2() 
        self.orientation = 0
        
        r, g, b = random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)
        self.color = (r, g, b)
        
        # (a, b)表編號為a的segment之b連接點
        self.connect_to = (0, 0)

        self.connections = [None]*2
        for i in range(2):
            orientation = random.uniform(-150, -30)
            scale_w = random.uniform(0.8, 1.2)
            scale_h = random.uniform(0.8, 1.2)
            self.connections[i] = Connection(self.end_pos, orientation, scale_w, scale_h)
        
    def connect(self, connection):
        self.start_pos = connection.position
        self.orientation = connection.orientation
 
        new_width = self.width*connection.scale_width
        if new_width < self.width_range[0]:
            self.width = self.width_range[0]
        elif new_width > self.width_range[1]:
            self.width = self.width_range[1]
        else:    
            self.width = new_width
        
        new_height = self.height*connection.scale_height
        if new_height < self.height_range[0]:
            self.height = self.height_range[0]
        elif new_height > self.height_range[1]:
            self.height = self.height_range[1]
        else:    
            self.height = new_height
        
        direction = pygame.Vector2(1, 0).rotate(self.orientation)
        self.end_pos = self.start_pos + self.height*direction
        
        self.connections[0].position = self.end_pos.copy()
        self.connections[1].position = self.end_pos.copy()

                
class Connection:
    def __init__(self, position, orientation, scale_width, scale_height):
        # 向量        
        self.position = position
        
        # 單位：度
        self.orientation = orientation
        
        self.scale_width = scale_width
        self.scale_height = scale_height

                
# python version 3.10.9
import copy
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Exercise 9.14")

WHITE = (255, 255, 255)
BLACK = (0, 0, 0)

screen_size = WIDTH, HEIGHT = 640, 420
screen = pygame.display.set_mode(screen_size)

FPS = 60
frame_rate = pygame.time.Clock()

population_size = 8
mutation_rate = 0.05
population = Population(population_size, mutation_rate)

font = pygame.font.SysFont('courier', 16)
button_caption = font.render('evolve new generation', True, BLACK, (200, 200, 200))
button = button_caption.get_rect()
button.topleft = (20, 15)

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()           
        elif event.type == pygame.MOUSEBUTTONDOWN:
            if event.button == 1:
                x, y = event.pos
                if button.collidepoint(x, y):
                    population.evolve()

    screen.fill(WHITE)
    
    population.show()
    population.rollover()
        
    screen.blit(button_caption, button.topleft)  

    string = f'{"Generation "}{population.get_generations():<3}'
    text = font.render(string, True, BLACK)
    screen.blit(text, (20, HEIGHT-25))          
    
    pygame.display.update()
    frame_rate.tick(FPS)