??遺傳算法是一種受生物進化理論啟發的隨機優化算法，其核心思想是模擬自然界中 “物競天擇、適者生存” 的進化過程，通過對候選解的迭代優化，找到問題的最優解。

一、核心思想

??遺傳算法將優化問題的候選解視為生物群體中的“個體”，每個個體的“基因”對應解的參數。通過模擬生物進化中的選擇、交叉、變異等過程，讓群體中 “適應性強”（即更接近最優解）的個體保留并繁衍，“適應性弱” 的個體被淘汰，最終使群體逐漸逼近最優解。

二、算法步驟

1. 編碼：將問題解轉化為“基因”形式

??首先需要將實際問題的候選解編碼為計算機可處理的字符串（如二進制串、實數編碼等），這個字符串稱為 “染色體”，其中的每個元素（如二進制位）稱為 “基因”。

??例如：若優化問題是求“x 在 [0,31] 范圍內使函數 f (x)=x2 最大的解”，可將 x 用 5 位二進制編碼（如 x=5 對應染色體“00101”）。

2. 初始化群體

??隨機生成一定數量的染色體，組成初始 “群體”（個體數量稱為 “種群規模”）。

??例如：隨機生成 4 個 5 位二進制串，組成初始群體：00101、11011、01001、10010。

3. 適應度評估：衡量個體的 “優劣”

??定義“適應度函數”，計算每個個體的適應度值，值越高表示該個體（解）越優。

??例如：對上述問題，適應度函數可直接用 f (x)=x2，將染色體轉為十進制后計算：
??????00101（x=5）→ 適應度 = 25；
??????11011（x=27）→ 適應度 = 729（最優）。

4. 遺傳操作：模擬進化過程

??通過選擇、交叉、變異，生成下一代群體：

??選擇（Selection）：從當前群體中篩選出適應度高的個體，使其有更高概率繁衍后代（類似 “適者生存”）。
??常用方法：輪盤賭選擇（適應度越高的個體，被選中的概率越大）。例如：適應度為 729 的個體被選中的概率遠高于25的個體。

??交叉（Crossover）：將兩個選中的個體（父代染色體）按一定概率（交叉概率）交換部分基因，生成新個體（子代染色體），增加群體多樣性。

??例如：對父代11011和10010，隨機選擇交叉點（如第 3 位后），交換后半部分：
??????父代 1：110 | 11 → 子代 1：11010；
??????父代 2：100 | 10 → 子代 2：10011。

??變異（Mutation）：對子代染色體的基因按一定概率（變異概率）隨機改變（如二進制位 0 變 1 或 1 變 0），避免群體陷入局部最優。

??例如：對子代11010的第 4 位進行變異（1→0），得到11000。

5. 終止條件

??重復步驟 3 和 4，直到滿足終止條件（如迭代次數達到上限、最優個體的適應度不再提升等），最終輸出適應度最高的個體作為最優解。

三、算法特點

??魯棒性：對問題的數學性質要求低，可處理非線性、多峰等復雜問題。
??并行性：群體中的多個個體可同時優化，適合并行計算。
??隨機性：通過隨機操作探索解空間，但通過適應度評估引導優化方向，兼顧 “探索” 與 “利用”。

四、應用場景

??遺傳算法廣泛用于函數優化、機器學習（如神經網絡參數優化）、組合優化（如旅行商問題、背包問題）、工程設計（如電路布局）等領域。

五、Python實現示例

??現尋找函數$f(x)=?x^2+10$在區間$[?10,10]$內的最大值。理論上，當$x=0$時函數取得最大值 $f(0)=10$。運行該程序后，可以觀察算法如何逐步逼近這個最優解。

import matplotlib
matplotlib.use('TkAgg')import numpy as np
import matplotlib.pyplot as plt# 目標函數：尋找 -x^2 + 10 的最大值
def objective_function(x):return -x ** 2 + 10# 解碼染色體為實際數值
def decode_chromosome(chromosome, min_val, max_val):"""將二進制染色體解碼為區間內的實數值"""binary_str = ''.join(map(str, chromosome))decimal = int(binary_str, 2)max_decimal = 2 ** len(chromosome) - 1return min_val + (max_val - min_val) * decimal / max_decimal# 計算適應度（函數值越大適應度越高）
def calculate_fitness(population, min_val, max_val):fitness = []for chromosome in population:x = decode_chromosome(chromosome, min_val, max_val)fitness.append(objective_function(x))return fitness# 選擇操作（錦標賽選擇）
def tournament_selection(population, fitness, tournament_size=3):selected = []for _ in range(len(population)):# 隨機選擇幾個個體進行比較tournament_indices = np.random.choice(len(population), tournament_size)tournament_fitness = [fitness[i] for i in tournament_indices]# 選擇適應度最高的個體winner_index = tournament_indices[np.argmax(tournament_fitness)]selected.append(population[winner_index])return selected# 交叉操作（單點交叉）
def crossover(parents, crossover_rate=0.8):children = []for i in range(0, len(parents), 2):parent1 = parents[i]parent2 = parents[i + 1] if i + 1 < len(parents) else parents[0]# 以一定概率進行交叉if np.random.random() < crossover_rate:crossover_point = np.random.randint(1, len(parent1))child1 = parent1[:crossover_point] + parent2[crossover_point:]child2 = parent2[:crossover_point] + parent1[crossover_point:]else:child1, child2 = parent1.copy(), parent2.copy()children.extend([child1, child2])# 確保種群大小不變return children[:len(parents)]# 變異操作
def mutate(population, mutation_rate=0.01):for chromosome in population:for i in range(len(chromosome)):if np.random.random() < mutation_rate:chromosome[i] = 1 - chromosome[i]  # 翻轉位return population# 主函數
def genetic_algorithm(pop_size=100, chromosome_length=10, generations=100,min_val=-10, max_val=10):# 初始化種群population = [np.random.randint(0, 2, chromosome_length).tolist() for _ in range(pop_size)]best_fitness_history = []best_solution = Nonebest_x = Nonefor generation in range(generations):# 計算適應度fitness = calculate_fitness(population, min_val, max_val)# 記錄最佳解best_idx = np.argmax(fitness)best_fitness_history.append(fitness[best_idx])if best_solution is None or fitness[best_idx] > calculate_fitness([best_solution], min_val, max_val)[0]:best_solution = population[best_idx]best_x = decode_chromosome(best_solution, min_val, max_val)# 選擇parents = tournament_selection(population, fitness)# 交叉children = crossover(parents)# 變異population = mutate(children)# 打印進度if generation % 10 == 0:print(f"Generation {generation}: Best fitness = {best_fitness_history[-1]:.4f}, Best x = {best_x:.4f}")# 繪制適應度進化曲線plt.figure(figsize=(10, 6))plt.plot(best_fitness_history)plt.title('Best Fitness Over Generations')plt.xlabel('Generation')plt.ylabel('Fitness')plt.grid(True)plt.savefig('figure/fitness_evolution.png')return best_solution, best_x, objective_function(best_x)# 運行算法
best_chromosome, best_x, best_fitness = genetic_algorithm()print("\n優化結果:")
print(f"最佳染色體: {best_chromosome}")
print(f"最優解 x = {best_x:.6f}")
print(f"最大值 f(x) = {best_fitness:.6f}")

??示例通過模擬生物進化過程來尋找函數的最優解。流程包括：
????初始化種群：隨機生成一組二進制編碼的染色體
????評估適應度：計算每個染色體對應的函數值
????選擇操作：使用錦標賽選擇法選出較優個體
????交叉操作：對選中的個體進行基因重組
????變異操作：引入隨機變異增加多樣性
????迭代進化：重復上述過程直到滿足終止條件

??通過模擬生物進化的“優勝劣汰”機制，遺傳算法能在復雜解空間中高效搜索最優解，是啟發式優化算法中的經典方法之一。

End.