遺伝的アルゴリズム

9.1 遺伝的アルゴリズム入門

遺伝的アルゴリズム（GA）は、自然選択のプロセスに触発され、 生物学的進化プロセスを模倣した最適化と探索の方法です。

遺伝的アルゴリズムは、従来の方法が効果的でない複雑な問題を解決するために使用されます。 これらのアルゴリズムは、選択、交差（クロスオーバー）、および突然変異のメカニズムを使用して解決策を進化させます。

動作原理：

1. 初期化：

可能な解決策（染色体）の初期集団が作成されます。 各解決策は、ビット列、文字列、または他の構造としてコード化されます。

2 適合度関数 (fitness function) ：

集団の各解決策の品質を評価します。

3. 評価：

各解決策（個体）は、適合度関数（fitness function）を使用して評価され、 解決策が問題をどれだけうまく解決しているかが判断されます。

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}")