Python實現遺傳算法代碼詳解

一、什麼是遺傳算法

遺傳算法（Genetic Algorithm）是一種基於生物進化中“適者生存”的思想而開發出來的一種優化算法，是模擬自然界中優勝劣汰的進化過程。它通過將問題轉化為基因與適應度的優化問題，並在種群中進行基因的交叉、變異、選擇等操作，來搜索最優解。遺傳算法廣泛應用於各種複雜的非線性優化問題。

二、遺傳算法基本操作

遺傳算法的基本操作包括：初始化種群、計算適應度、選擇、交叉、變異等。其中，初始化種群是指隨機生成一組可能的解決方案，計算適應度是指對種群的每個個體進行評估，選擇是指對適應度高的個體進行保留，交叉是指將適應度高的個體結合後生成新的個體，變異是指對適應度較差的個體進行隨即變異。

三、如何實現遺傳算法

用Python語言實現遺傳算法可以簡化算法開發流程，同時Python也是強調可讀性和易學性的語言。下面是一個基於Python的遺傳算法示例代碼：

import random

# 初始化種群
def init_population(population_size, chromosome_length):
    population_list = []
    for i in range(population_size):
        population_list.append(
            [random.randint(0, 1) for _ in range(chromosome_length)])
    return population_list

# 計算適應度
def compute_fitness(population_list, target):
    fitness_list = []
    for chromosome in population_list:
        fitness = 0
        for i in range(len(chromosome)):
            if chromosome[i] == target[i]:
                fitness += 1
        fitness_list.append(fitness)
    return fitness_list

# 選擇
def selection(population_list, fitness_list, num_parents):
    parents_list = []
    for i in range(num_parents):
        max_score_index = fitness_list.index(max(fitness_list))
        parents_list.append(population_list.pop(max_score_index))
        fitness_list.pop(max_score_index)
    return parents_list

# 交叉
def crossover(parents_list, offspring_size):
    offspring_list = []
    for i in range(offspring_size):
        offspring = []
        parent1 = random.choice(parents_list)
        parent2 = random.choice(parents_list)
        cross_point = random.randint(0, len(parent1) - 1)
        offspring.extend(parent1[:cross_point])
        offspring.extend(parent2[cross_point:])
        offspring_list.append(offspring)
    return offspring_list

# 變異
def mutation(offspring_list, mutation_rate):
    for offspring in offspring_list:
        for i in range(len(offspring)):
            if random.random() < mutation_rate:
                offspring[i] = (offspring[i] + 1) % 2
    return offspring_list

# 主函數
def main():
    target = [1, 0, 1, 0, 1, 1]

    population_size = 6
    chromosome_length = len(target)
    num_parents = 4
    offspring_size = population_size - num_parents
    mutation_rate = 0.1

    population_list = init_population(population_size, chromosome_length)
    for generation in range(20):
        fitness_list = compute_fitness(population_list, target)
        parents_list = selection(population_list, fitness_list, num_parents)
        offspring_list = crossover(parents_list, offspring_size)
        offspring_list = mutation(offspring_list, mutation_rate)
        population_list = parents_list + offspring_list

    print("Final Population: ", population_list)

if __name__ == '__main__':
    main()

四、代碼解析

這個示例代碼實現了一個二進制向量的遺傳算法，目標是找到一個與給定目標向量匹配的解決方案。下面是對代碼中各個函數的解析：

1. init_population(population_size, chromosome_length)：初始化種群。該函數生成一個由population_size個長度為chromosome_length的隨機二進制向量組成的種群。
2. compute_fitness(population_list, target)：計算適應度。該函數將種群中每個個體與目標進行比較，並返回每個個體的適應度（即匹配的位數）。
3. selection(population_list, fitness_list, num_parents)：選擇。該函數根據適應度從種群中選擇num_parents個適應度最高的個體作為父代。
4. crossover(parents_list, offspring_size)：交叉。該函數隨機選取兩個父代，將它們的染色體交叉，生成offspring_size個新的個體。
5. mutation(offspring_list, mutation_rate)：變異。該函數對每個個體的每個位進行變異以增加種群的多樣性。
6. main()：主函數。該函數初始化各個參數並進行遺傳算法迭代，最終輸出最終種群。

五、總結

本文介紹了遺傳算法的基本思想和Python實現遺傳算法的示例代碼。通過本文的介紹，相信讀者可以對遺傳算法有一個更深入的理解，並能夠運用Python語言來實現自己的遺傳算法問題。