はじめに

遺伝的アルゴリズム（Genetic Algorithm、GA）は、進化の過程を模倣した強力な最適化手法です。このアルゴリズムは、生物の進化のプロセスである選択、交叉、突然変異といったメカニズムを応用し、最適解を探索します。GAは特に、大規模かつ複雑な最適化問題に対して有効であり、様々な応用分野で使われています。この記事では、Pythonを用いて遺伝的アルゴリズムを実装し、最適化問題を解決する具体的な方法を紹介します。

遺伝的アルゴリズムとは？

遺伝的アルゴリズム（GA）は、進化論に基づいた最適化アルゴリズムです。GAは、解の候補となる個体群（ポピュレーション）を生成し、その中から適応度の高い個体を選び、新たな世代を作り出しながら最適な解を探索します。この進化の過程で、交叉（クロスオーバー）や突然変異を適用し、より良い解に近づけていきます。

GAの基本ステップ

  1. 初期化: ランダムに初期集団を生成します。
  2. 選択: 適応度（評価値）が高い個体を次世代に選びます。
  3. 交叉: 親個体の遺伝情報を組み合わせて新しい子個体を生成します。
  4. 突然変異: 遺伝子の一部をランダムに変更し、多様性を保ちます。
  5. 適応度評価: 新しい世代の個体を評価し、目的に最も適した解を選びます。
  6. 停止条件: 最適解が見つかるか、世代数が規定に達したらアルゴリズムを終了します。 これらのステップを繰り返すことで、最適解を探索します。

Pythonでの遺伝的アルゴリズムの実装

ここでは、簡単な例を通して遺伝的アルゴリズムの実装を解説します。例として、関数の最小化問題を解決します。目標は、与えられた数式の最小値を見つけることです。

例題: 関数の最小化

対象となる関数は次のような単純な2変数の関数とします。

f(x, y) = x^2 + y^2

この関数の最小値を求めることが目標です。この場合、$f(x, y)$は、$x = 0$かつ$y = 0$で最小値0を取ります。

ステップ1: 初期化

まず、個体（解の候補）を表現するためのデータ構造を定義し、初期集団を生成します。ここでは、個体を2つの変数（$x$と$y$）として表現します。

import random
# 個体をランダムに生成する関数
def create_individual():
    return [random.uniform(-10, 10), random.uniform(-10, 10)]
# 初期集団を生成する関数
def create_population(size):
    return [create_individual() for _ in range(size)]
# 集団の初期化
population_size = 100
population = create_population(population_size)

ステップ2: 適応度評価

次に、各個体の適応度（フィットネス）を評価するための関数を定義します。ここでは、目的関数$f(x, y) = x^2 + y^2$の値が小さいほど、適応度が高いとします。

# 適応度関数（評価関数）
def fitness(individual):
    x, y = individual
    return x2 + y2

ステップ3: 選択

次に、遺伝的アルゴリズムの選択ステップを実装します。ここでは、ルーレット選択を使用して、適応度の高い個体が選ばれる確率が高くなるようにします。

# ルーレット選択を実装する関数
def select(population):
    fitness_values = [fitness(ind) for ind in population]
    total_fitness = sum(fitness_values)
    selection_probs = [f / total_fitness for f in fitness_values]
    return population[random.choices(range(len(population)), weights=selection_probs, k=1)[0]]

ステップ4: 交叉（クロスオーバー）

交叉では、親個体の遺伝子を交ぜ合わせて新しい子個体を生成します。ここでは、1点交叉を用います。

# 1点交叉を実装する関数
def crossover(parent1, parent2):
    crossover_point = random.randint(0, 1)
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2

ステップ5: 突然変異

突然変異は、個体の一部をランダムに変異させて、集団の多様性を保ちます。突然変異の確率は低めに設定します。

# 突然変異を実装する関数
def mutate(individual, mutation_rate=0.01):
    if random.random() < mutation_rate:
        mutation_index = random.randint(0, 1)
        individual[mutation_index] = random.uniform(-10, 10)

ステップ6: 世代更新

最後に、各世代で選択、交叉、突然変異を行い、新しい世代を生成します。一定回数の世代が進化するまでこのプロセスを繰り返します。

# 新しい世代を生成する関数
def evolve(population, mutation_rate=0.01):
    new_population = []
    for _ in range(len(population) // 2):
        # 選択
        parent1 = select(population)
        parent2 = select(population)
        # 交叉
        child1, child2 = crossover(parent1, parent2)
        # 突然変異
        mutate(child1, mutation_rate)
        mutate(child2
, mutation_rate)
        new_population.extend([child1, child2])
    return new_population
# 進化の実行
generations = 100
for generation in range(generations):
    population = evolve(population)
    best_individual = min(population, key=fitness)
    print(f"Generation {generation}: Best Fitness = {fitness(best_individual)}")

コードの解説

  • select(): ルーレット選択で適応度に応じた個体を選びます。
  • crossover(): 親個体の一部を交差させて新しい子個体を生成します。
  • mutate(): 一部の遺伝子をランダムに変更し、集団の多様性を確保します。
  • evolve(): 次の世代の個体を生成し、進化を繰り返します。 このアルゴリズムを実行すると、各世代で個体が進化し、目的関数の最小値に向かって収束していく様子が確認できます。

遺伝的アルゴリズムの応用

遺伝的アルゴリズムは、以下のような様々な分野で応用されています。

  • スケジューリング: 工場や学校のスケジュール最適化。
  • 経路探索: 物流や旅行の最短経路問題の解決。
  • パラメータ最適化: 機械学習モデルのハイパーパラメータチューニング。

まとめ

遺伝的アルゴリズム（GA）は、進化論に基づいた強力な最適化アルゴリズムで、複雑な最適化問題に対しても有効です。この記事では、Pythonを用いたGAの基本的な実装を通して、最適化問題の解決方法を解説しました。GAは非常に柔軟で、様々な問題に適用可能です。Pythonのシンプルさを活かしながら、ぜひ自分のプロジェクトでも試してみてください。

参照:

Genetic Algorithms with `Python` | Real `Python`