遺傳演算法

9.1 遺傳演算法介紹。

遺傳演算法 (GA) 是一種受到自然選擇過程啟發的優化與搜索方法， 模擬生物進化的過程。

遺傳演算法用於解決複雜問題，尤其是在傳統方法可能無效的情況下。 這些演算法使用選擇、交叉和突變機制來進化解決方案。

工作原則：

1. 初始化：

創建一個初始可能解的族群（染色體）。每個解以字符串的形式編碼 （比如二進制字符串、字符字符串或其他結構）。

2 適應度函數 (fitness function):

評估族群中每個解的質量。

3. 評估：

使用適應度函數評估每個解（個體），以確定解決問題的效果。

4. 選擇：

適應度更高的解更有可能被選中進行繁殖。 常用的選擇方法包括輪盤選擇法、錦標賽選擇法和排名選擇法。

5. 交叉：

選中的解（父母）被組合以創造新解（後代）。交叉可以是單點、多點或減少多點。

6. 突變：

在新解中應用隨機更改（突變）以增加多樣性。 這有助於演算法避免落入局部最小值。

7. 替換：

新族群替代舊族群，過程重複直到滿足停止條件 （例如，達到特定的代數或特定的適應度）。

優勢和劣勢

優勢：

• 多種應用：可以用於解決各種問題，包括分析方法失效的問題。
• 全域優化：在多維及複雜的空間中找到全域最優。
• 靈活性：可以用於任何適應度函數。

劣勢：

• 高計算成本：需要大量計算資源，尤其是對於大族群及複雜問題。
• 參數調整困難：設定參數（族群大小、突變率及交叉率）可能很困難， 且對性能有很大影響。
• 缺乏最優解保證：無法保證找到的解是全域最優。

實際上，遺傳演算法是一種高效的啟發式方法。 即使擁有所有數據，也無法保證找到最佳解。 但在處理複雜情況及海量數據時，它能夠迅速提供接近理想的解。

9.2 應用範例

我們來看看遺傳演算法用於優化函數的範例。

import random

# 遺傳演算法參數設定
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# 定義適應度函數
def fitness_function(x):
    return -x**2 + 10*x
            
# 初始化族群
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# 選擇（錦標賽選擇）
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# 交叉（一點交叉）
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# 突變
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# 遺傳演算法主迴圈
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# 輸出最佳解
best_individual = max(population, key=fitness_function)
print("最佳解:", best_individual)
print("函數值:", fitness_function(best_individual))
            
        

優勢和劣勢

9.3 多維函數優化

問題：

找到多維函數的最小值。

解決方案：

使用之前的範本

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# 使用範例：
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"最佳解: {best_solution}")