遺傳演算法

核心步驟

1. 選擇 (Selection)：適應度越高的個體越容易被選中
2. 交叉 (Crossover)：兩個父代交換基因產生子代
3. 突變 (Mutation)：隨機改變基因，維持多樣性

Vibe Prompt

「幫我用遺傳演算法解決 TSP（20 個城市）。種群 100，迭代 200 代，用 Matplotlib 動畫顯示最佳路線的演化過程。」

import random, math

def genetic_algorithm(cities, pop_size=100, generations=200, mutation_rate=0.01):
    n = len(cities)
    def dist(i, j):
        return math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    def fitness(route):
        return -sum(dist(route[i], route[(i+1)%n]) for i in range(n))
    
    # 初始化種群
    pop = [random.sample(range(n), n) for _ in range(pop_size)]
    
    for gen in range(generations):
        # 計算適應度
        scores = [(fitness(ind), ind) for ind in pop]
        scores.sort(reverse=True)
        pop = [ind for _, ind in scores]
        
        # 菁英保留
        next_pop = pop[:2]
        
        while len(next_pop) < pop_size:
            p1, p2 = random.choices(pop[:pop_size//2], k=2)
            # OX 交叉
            a, b = sorted(random.sample(range(n), 2))
            child = [-1] * n
            child[a:b] = p1[a:b]
            remaining = [x for x in p2 if x not in child]
            for i in range(n):
                if child[i] == -1:
                    child[i] = remaining.pop(0)
            # 突變
            if random.random() < mutation_rate:
                i, j = random.sample(range(n), 2)
                child[i], child[j] = child[j], child[i]
            next_pop.append(child)
        pop = next_pop
    
    return pop[0], -fitness(pop[0])