遺傳算法：如何用“進化”解決復雜問題？

FairyGirlhub

發布于 2025-6-11 07:29

瀏覽

0收藏

你有沒有想過，大自然是怎么讓生物變得越來越強大的？

比如，為什么長頸鹿的脖子越來越長，為什么鳥兒的翅膀能飛得越來越遠？？

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

其實，大自然有一套神奇的“優化”方法，而科學家們把這個方法用到了計算機里，這就是“遺傳算法”。

接下來，我們將深入探討遺傳算法的設計思想、基本原理和實踐應用，幫助你更好地理解和應用這一強大的優化工具。

1.前言｜什么是遺傳算法？

遺傳算法（Genetic Algorithm，簡稱GA）起源于對生物系統的計算機模擬研究，是一種隨機全局搜索優化方法。

它模擬了生物進化過程中的選擇、交叉和變異等現象，從初始種群出發，通過一系列操作，使群體逐漸進化到搜索空間中更優的區域，最終收斂到一群最適應環境的個體，從而求得問題的優質解。

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

▲ 遺傳算法原理示意圖

簡單來說，它就像大自然一樣，通過“選擇”“交配”和“變異”來找到解決問題的最好方法。

其中一些關鍵術語如下：

??種群（Population） 參與演化的生物群體，即解的搜索空間

??染色體（Chromosome） 對應問題的解向量

?? 基因（Gene） 解向量的一個分量，或者編碼后的解向量的一位

?? 個體（Individual） 種群的每一個成員，對應每一個可能的解

??適應度（Fitness） 體現個體的生存能力，與目標函數相關的函數

??遺傳算子（Operator） 個體的演化操作，包括選擇、交叉、變異

??選擇(Selection) 基于適應度的優勝劣汰，以一定的概率從種群中選擇若干個體

??交叉(Crossover) 兩個染色體進行基因重組

??變異(Mutation)：單個染色體的基因以較低概率發生隨機變化

2.原理｜遺傳算法是怎么工作的？

遺傳算法就像是在玩一個“尋寶游戲”。一開始，我們有很多“尋寶者”（這些“尋寶者”就是算法中的“種群”），它們都在不同的地方尋找寶藏（也就是問題的最優解）。

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

▲ 藏寶圖

每個“尋寶者”都有自己的“地圖”（這個“地圖”就是“基因”，它決定了“尋寶者”的特征和能力）。

遺傳算法也是這樣工作的。

初始種群產生了一系列隨機解，選擇操作保證了搜索的方向性，交叉和變異拓寬了搜索空間，其中交叉操作延續父輩個體的優良基因，變異操作則可能產生比當前優勢基因更優秀的個體。

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

▲ 人類進化演變圖

變異操作有利于跳出局部最優解，同時增加了隨機搜索的概率，即容易發散。因此，遺傳算法需要在過早收斂（早熟）和發散、精度和效率之間平衡。

遺傳算法的核心在于其模擬生物進化過程的幾個關鍵操作：

選擇操作｜Selection

根據個體的適應度，以一定的概率從種群中選擇若干個個體作為下一代的父母。

適應度高的個體有更高的被選中概率，這類似于自然選擇中的“適者生存”。

遺傳算法會挑出那些“表現好”的個體，讓它們有更多的機會繁殖后代。

常見方法：

輪盤賭選擇（Roulette Wheel Selection）根據個體的適應度值分配一個概率區間，適應度高的個體獲得更大的區間。通過隨機選擇，適應度高的個體被選中的概率更高。
錦標賽選擇（Tournament Selection）隨機選擇若干個體進行“比賽”，適應度最高的個體獲勝并進入下一代。
排名選擇（Rank Selection）根據個體的適應度進行排名，排名靠前的個體有更高的選擇概率。這種方法適用于適應度值差異較大的情況。

交叉操作｜Crossover

兩個父本個體的基因在某一位置處被切斷，前后兩串分別交叉組合，形成兩個新的子代個體。這一過程類似于生物的有性繁殖，通過基因重組產生新的變異。

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

▲ 基因交叉組合

兩個“表現好”的個體組合起來，產生新的后代。這個過程就像是生物的有性繁殖，新的后代會繼承父母的優點。

常見方法：

單點交叉（Single-point Crossover）在兩個父代個體的染色體上隨機選擇一個交叉點，將交叉點之后的部分基因片段進行交換。
多點交叉（Multi-point Crossover）選擇多個交叉點進行基因片段的交換。
均勻交叉（Uniform Crossover）隨機決定每個基因位是否交換，使得基因片段的交換更加均勻。

變異操作｜Mutation

對個體的基因序列進行隨機變異，以一定的概率改變某個基因的值。這為種群引入了新的遺傳信息，增加了種群的多樣性，避免算法陷入局部最優。

偶爾，一些后代會發生隨機的變化，這就像生物的基因突變。雖然大多數變異可能沒什么用，但偶爾會有一些變異讓后代變得更強大。

常見方法：

位變異（Bit-flip Mutation）隨機選擇一個基因位，將其值從0變為1或從1變為0（適用于二進制編碼）。
均勻變異（Uniform Mutation）隨機選擇多個基因位進行變異。
高斯變異（Gaussian Mutation）對基因值進行高斯分布的隨機擾動（適用于實數編碼）。

3.應用｜遺傳算法有什么用？

遺傳算法在優化問題、機器學習和工程設計等領域有廣泛應用，

例如在資源分配、路徑規劃、調度問題、特征選擇、神經網絡訓練、超參數優化、結構設計、電路設計和系統優化等方面能夠快速找到接近最優的解。

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片

▲ 梯度下降算法

其優勢在于全局搜索能力強，可有效避免局部最優；適應性強，適用于非線性、高維度和多峰問題；并行性高，適合并行計算。

旅行推銷員問題（TSP）是遺傳算法的經典應用之一。

TSP問題要求從n個城市中找到一條最短路徑，使推銷員從某城市出發，唯一走遍所有城市后回到起點。

以下是一個用遺傳算法解決TSP問題的Python示例。

import numpy as np
import matplotlib.pyplot as plt
import random
from math import sqrt
from matplotlib.collections import LineCollection


plt.rcParams['font.family'] = ['serif'] # 顯示中文問題
plt.rcParams['font.serif'] = ['SimSun'] # 顯示中文問題


# 生成隨機城市坐標
def generate_cities(num_cities, width=1000, height=1000):
    return [(random.randint(0, width), random.randint(0, height)) for _ in range(num_cities)]


# 計算路徑總距離
def calculate_distance(path, cities):
    distance = 0
    for i in range(len(path)):
        x1, y1 = cities[path[i-1]]
        x2, y2 = cities[path[i]]
        distance += sqrt((x2 - x1)**2 + (y2 - y1)**2)
    return distance


# 初始化種群
def initialize_population(pop_size, num_cities):
    population = []
    for _ in range(pop_size):
        individual = list(range(num_cities))
        random.shuffle(individual)
        population.append(individual)
    return population


# 選擇操作 - 輪盤賭選擇
def selection(population, cities, num_parents):
    fitness_values = [1/calculate_distance(individual, cities) for individual in population]
    total_fitness = sum(fitness_values)
    probabilities = [f/total_fitness for f in fitness_values]
    
    selected_indices = np.random.choice(len(population), size=num_parents, p=probabilities, replace=False)
    return [population[i] for i in selected_indices]


# 交叉操作 - 有序交叉(OX)
def crossover(parent1, parent2):
    size = len(parent1)
    child = [-1] * size
    
    # 選擇交叉點
    start, end = sorted(random.sample(range(size), 2))
    
    # 從parent1復制片段
    child[start:end] = parent1[start:end]
    
    # 從parent2填充剩余城市
    remaining = [city for city in parent2 if city not in child]
    ptr = 0
    for i in range(size):
        if child[i] == -1:
            child[i] = remaining[ptr]
            ptr += 1
    
    return child


# 變異操作 - 交換變異
def mutate(individual, mutation_rate):
    if random.random() < mutation_rate:
        i, j = random.sample(range(len(individual)), 2)
        individual[i], individual[j] = individual[j], individual[i]
    return individual


# 遺傳算法主函數
def genetic_algorithm(cities, pop_size=100, num_generatinotallow=500, mutation_rate=0.01, elitism_ratio=0.1):
    num_cities = len(cities)
    population = initialize_population(pop_size, num_cities)
    best_distance = float('inf')
    best_path = None
    fitness_history = []
    
    num_elites = int(pop_size * elitism_ratio)
    
    for generation in range(num_generations):
        # 評估種群
        distances = [calculate_distance(individual, cities) for individual in population]
        current_best = min(distances)
        fitness_history.append(current_best)
        
        if current_best < best_distance:
            best_distance = current_best
            best_path = population[distances.index(current_best)]
        
        # 選擇精英
        elite_indices = np.argsort(distances)[:num_elites]
        elites = [population[i] for i in elite_indices]
        
        # 選擇父母
        parents = selection(population, cities, pop_size - num_elites)
        
        # 生成下一代
        next_generation = elites.copy()
        
        while len(next_generation) < pop_size:
            parent1, parent2 = random.sample(parents, 2)
            child = crossover(parent1, parent2)
            child = mutate(child, mutation_rate)
            next_generation.append(child)
        
        population = next_generation
    
    return best_path, best_distance, fitness_history


# 繪制路徑
def plot_path(cities, path, title="TSP Path"):
    path_coords = [cities[i] for i in path] + [cities[path[0]]]  # 回到起點
    x, y = zip(*path_coords)
    
    fig, ax = plt.subplots(figsize=(10, 6))
    ax.scatter(x, y, color='red')
    
    # 繪制路徑線
    lines = [[path_coords[i], path_coords[i+1]] for i in range(len(path_coords)-1)]
    lc = LineCollection(lines, colors='blue', linewidths=1)
    ax.add_collection(lc)
    
    ax.set_title(title)
    ax.set_xlabel("X 軸")
    ax.set_ylabel("Y 軸")
    plt.grid()
    plt.show()


# 繪制適應度進化曲線
def plot_fitness_history(fitness_history, title="適應度進化曲線"):
    plt.figure(figsize=(10, 6))
    plt.plot(fitness_history, color='green')
    plt.title(title)
    plt.xlabel("迭代次數")
    plt.ylabel("最優距離")
    plt.grid()
    plt.show()


# 主程序
if __name__ == "__main__":
    # 參數設置
    num_cities = 20
    pop_size = 100
    num_generations = 500
    mutation_rate = 0.02
    
    # 生成城市
    cities = generate_cities(num_cities)
    
    # 運行遺傳算法
    best_path, best_distance, fitness_history = genetic_algorithm(
        cities, pop_size=pop_size, num_generatinotallow=num_generations, mutation_rate=mutation_rate)
    
    print(f"最優距離: {best_distance}")
    print(f"最優路徑: {best_path}")
    
    # 繪制結果
    plot_path(cities, best_path, f"旅行推銷員問題(TSP) (最優距離: {best_distance:.2f})")
    plot_fitness_history(fitness_history)

遺傳算法：如何用“進化”解決復雜問題？-AI.x社區圖片