【Pythonコラム】Pythonで始める遺伝的アルゴリズム：最適解を"進化"させる魔法

Pythonで始める遺伝的アルゴリズム：最適解を"進化"させる魔法

遺伝的アルゴリズム（Genetic Algorithm, GA）は、生物の進化の仕組みを模倣した、問題解決のための強力なアルゴリズムです。特に、複雑な問題を効率的に解決したり、厳密解を求めるのが難しい場合に有効です。この記事では、Pythonを使って遺伝的アルゴリズムの基本的な考え方と実装について、初心者にもわかりやすく解説します。

遺伝的アルゴリズムの基本

遺伝的アルゴリズムは、以下のステップを繰り返すことで、より良い解を探索していきます。

1. 初期集団の生成: 解となりうる候補（個体）をランダムに複数生成します。これらの個体が集まったものを「集団」と呼びます。
2. 適応度評価: 各個体がどれだけ良い解であるか評価します。この評価値を「適応度」と呼びます。例えば、ある関数の最大値を求める問題であれば、関数の出力値が適応度になります。
3. 選択: 適応度の高い個体ほど、次世代に子孫を残しやすくなるように選択します。ルーレット選択やトーナメント選択などの方法があります。
4. 交叉: 選択された個体同士を交配させ、新しい個体（子）を生成します。これにより、親の持つ良い特徴を組み合わせることを目指します。
5. 突然変異: 生成された個体の一部をランダムに変化させます。これにより、局所最適解に陥るのを防ぎ、多様性を維持します。
6. 世代交代: 新しく生成された個体（子）と、元の個体（親）の中から、適応度の高い個体を選び、次世代の集団を構成します。
7. 終了判定: 指定した世代数に達した、または一定の適応度を持つ個体が見つかった場合に、アルゴリズムを終了します。

Pythonでの実装例：ナップサック問題

遺伝的アルゴリズムを理解するために、有名な「ナップサック問題」を例に、Pythonで実装してみましょう。

ナップサック問題とは、容量が決まっているナップサックに、価値と重さが異なる複数の品物を詰め込む際に、価値の合計を最大化する組み合わせを見つける問題です。

import random

# 品物クラス
class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

# 個体クラス
class Individual:
    def __init__(self, genes):
        self.genes = genes
        self.fitness = 0  # 適応度は後で計算

    def calculate_fitness(self, items, capacity):
        total_weight = 0
        total_value = 0
        for i, gene in enumerate(self.genes):
            if gene == 1:
                total_weight += items[i].weight
                total_value += items[i].value

        if total_weight > capacity:
            self.fitness = 0 # 容量オーバーの場合は適応度を0にする
        else:
            self.fitness = total_value

# 遺伝的アルゴリズムのメイン関数
def genetic_algorithm(items, capacity, population_size, generations, mutation_rate):
    # 1. 初期集団の生成
    population = []
    num_items = len(items)
    for _ in range(population_size):
        genes = [random.randint(0, 1) for _ in range(num_items)] # 各遺伝子は0または1
        individual = Individual(genes)
        individual.calculate_fitness(items, capacity) # 初期適応度を計算
        population.append(individual)

    # 世代交代
    for generation in range(generations):
        # 2. 選択 (ルーレット選択)
        fitness_sum = sum([individual.fitness for individual in population])
        if fitness_sum == 0:
            # すべての個体の適応度が0の場合、ランダムに選択
            selected_parents = random.choices(population, k=population_size)
        else:
            probabilities = [individual.fitness / fitness_sum for individual in population]
            selected_parents = random.choices(population, weights=probabilities, k=population_size)

        # 3. 交叉 (一点交叉)
        offspring = []
        for i in range(0, population_size, 2):
            parent1 = selected_parents[i]
            parent2 = selected_parents[i+1] if i+1 < population_size else selected_parents[0] # 偶数でない場合、最初の個体と交配

            crossover_point = random.randint(1, num_items - 1)
            child1_genes = parent1.genes[:crossover_point] + parent2.genes[crossover_point:]
            child2_genes = parent2.genes[:crossover_point] + parent1.genes[crossover_point:]

            child1 = Individual(child1_genes)
            child2 = Individual(child2_genes)
            offspring.append(child1)
            offspring.append(child2)

        # 4. 突然変異
        for individual in offspring:
            for i in range(num_items):
                if random.random() < mutation_rate:
                    individual.genes[i] = 1 - individual.genes[i] # 0と1を反転

        # 適応度計算
        for individual in offspring:
            individual.calculate_fitness(items, capacity)

        # 5. 世代交代 (エリート選択) - 親世代から上位の個体を残す
        population.sort(key=lambda x: x.fitness, reverse=True) # 適応度で降順ソート
        offspring.sort(key=lambda x: x.fitness, reverse=True)
        new_population = population[:population_size // 2] + offspring[:population_size - population_size // 2]
        population = new_population

        # 現在の最適解を表示
        best_individual = max(population, key=lambda x: x.fitness)
        print(f"世代 {generation + 1}: 最適な価値 = {best_individual.fitness}")

    # 最終的な最適解を返す
    best_individual = max(population, key=lambda x: x.fitness)
    return best_individual, population

# メイン処理
if __name__ == '__main__':
    # 品物の定義 (重さ, 価値)
    items = [
        Item(10, 60),
        Item(20, 100),
        Item(30, 120)
    ]
    capacity = 50  # ナップサックの容量
    population_size = 50  # 集団のサイズ
    generations = 100  # 世代数
    mutation_rate = 0.01  # 突然変異率

    best_individual, population = genetic_algorithm(items, capacity, population_size, generations, mutation_rate)

    print("\n最終結果:")
    print("最適な価値:", best_individual.fitness)
    print("選択された品物:", [i for i, gene in enumerate(best_individual.genes) if gene == 1])

このコードは、ナップサック問題に対する遺伝的アルゴリズムの基本的な実装例です。 ItemクラスとIndividualクラスで品物と個体を表し、genetic_algorithm関数が主要な処理を行います。 ルーレット選択、一点交叉、突然変異といった基本的な操作が含まれています。

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

遺伝的アルゴリズムは、以下のような様々な問題に応用できます。

• 関数最適化
• 機械学習のパラメータ調整
• スケジューリング問題
• 経路最適化問題（巡回セールスマン問題など）
• ロボットの制御

まとめ

遺伝的アルゴリズムは、生物の進化の仕組みを応用した強力な問題解決手法です。 Pythonを使えば、比較的簡単に実装でき、複雑な問題を解決するための強力なツールとなります。 今回の例を参考に、様々な問題に挑戦してみてください。