Pythonではじめる遺伝的アルゴリズム入門

最適化問題は、工学、金融、情報科学といった多様な分野において、実用上極めて重要な課題です。しかし、問題が複雑化し、探索すべき解の候補が膨大になるにつれて、従来型の数学的な手法で厳密な最適解を求めることは困難になります。特に、組み合わせ最適化問題のように、無数の選択肢の中から最良のものを発見する必要がある場合、その計算コストは現実的ではありません。

このような背景から、生物の進化プロセスにヒントを得たメタヒューリスティック・アルゴリズムの一つである「遺伝的アルゴリズム(Genetic Algorithm, GA)」が、有効な解決策として注目されています。遺伝的アルゴリズムは、解の候補群を「個体」の集団とみなし、選択・交叉・突然変異といった遺伝的な操作を模したプロセスを繰り返すことで、優れた解へと効率的に進化させていくアプローチです。

本記事では、この遺伝的アルゴリズムが機能する基本的な仕組みと、その挙動を決定づける重要な構成要素を詳細に解説します。さらに、古典的な組み合わせ最適化問題を題材に、Pythonを用いた実装例を示し、そのアルゴリズムの具体的な動作と有用性を実践的に探ります。

遺伝的アルゴリズムの概要

遺伝的アルゴリズム(Genetic Algorithm, GA)は、生物の進化の仕組みを模倣することで、問題に対する最適解を探索する計算手法です。具体的には、解の候補となる集団の中から、環境に適した(=評価の高い)個体を優先的に選択し、それらの個体が持つ要素を組み換えたり(交叉)、一部を変化させたり(突然変異)することで、世代交代を繰り返しながら、より優れた解を発見していきます。

基本用語

アルゴリズムを理解するために、まずはアルゴリズムの基本となる要素を確認しましょう。

用語説明生物の進化での例え
個体 (Individual)1つの「解の候補」を指します。1匹の生物
遺伝子 (Gene)個体を構成する最小単位の情報です。問題のパラメータなどが該当します。目の色や髪の色を決める遺伝子
染色体 (Chromosome)遺伝子の集合体です。多くの場合、「個体」と同義で用いられます。遺伝子情報全体が記録された設計図
集団 (Population)複数の個体から成る集まりです。多様な解の候補を同時に扱います。ある地域に生息する生物の群れ
世代 (Generation)アルゴリズムの繰り返し処理(ループ)1回分を指す単位です。親の世代、子の世代
適応度 (Fitness)個体が解としてどれほど「優秀か」を示す評価値です。この値が高いほど良い解であることを意味します。生存能力や繁殖能力の高さ

アルゴリズムの流れ

遺伝的アルゴリズムは、主に以下の5つのステップを繰り返すことで、解の最適化を進めていきます。

  1. 初期集団の生成 (Initialization): 最初に、多数の個体(解の候補)をランダムに生成し、進化の起点となる最初の集団を作成します。


  2. 適応度評価 (Evaluation): 集団内の各個体が、設定された問題に対してどれほど優れているかを「適応度関数」を用いて評価し、適応度を算出します。


  3. 選択 (Selection): 適応度が高い優秀な個体を、次世代に遺伝情報を引き継ぐ親として選び出します。適応度が高いほど選択される確率が高くなるように設計されます。


  4. 交叉 (Crossover): 選択された2つの親個体が持つ遺伝子(染色体)の一部を交換し、新たな子個体を生成します。これにより、両親の優れた特性を組み合わせた、より良い解が生まれることが期待されます。


  5. 突然変異 (Mutation): 一定の低い確率で、個体の遺伝子の一部をランダムに変更します。これは、探索が局所的な最適解に陥ることを防ぎ、集団の多様性を維持するために不可欠な操作です。

遺伝的アルゴリズムの詳細

遺伝的アルゴリズムの性能は、その挙動を決定づける各要素(遺伝子表現、適応度関数、選択、交叉、突然変異)をいかに問題に合わせて設計するかに大きく依存します。ここでは、これらの構成要素について、その役割と代表的な手法を解説します。

1. 遺伝子の表現方法

遺伝的アルゴリズムを適用する上で最初のステップは、問題における「解の候補」をアルゴリズムが扱える形式、すなわち「遺伝子(染色体)」として表現することです。この表現方法は問題の性質によって異なり、適切な設計が探索効率を大きく左右します。

遺伝子表現主な対象問題
バイナリ表現選択・不選択を決定する問題(ナップサック問題など)[0, 1, 1, 0, 1]
順序表現順序が重要な問題(巡回セールスマン問題など)[3, 1, 4, 2, 0]
実数値表現連続値パラメータを扱う問題(関数最適化など)[0.23, 1.87, -0.54]
  • バイナリ表現 (Binary Encoding): 各遺伝子を 01 で表現する最も基本的な方法です。ある要素を「含めるか(1)」「含めないか(0)」といった、組み合わせ最適化問題で多用されます。
  • 順序表現 (Permutation Encoding): 訪問する都市のリストなど、要素の「順序」が解の意味を持つ問題に用いられます。各遺伝子は重複なく並べられた要素のインデックスで表現されます。
  • 実数値表現 (Real-Coded GA): 関数のパラメータやAIモデルの重みなど、連続的な値を直接遺伝子として扱います。現実世界の多くの問題に直感的に適用できます。

2. 適応度の設計

適応度(Fitness)は、各個体(解の候補)がどれだけ優れているかを示す評価スコアであり、アルゴリズムの探索方向を導く羅針盤の役割を果たします。この適応度を計算する関数を「適応度関数」と呼び、その設計は「何を最大化(または最小化)したいか」という問題の目的そのものを定義する、極めて重要なプロセスです。

例えば、巡回セールスマン問題であれば「移動距離の短さ」が適応度の高さに対応します。この場合、目的関数である総移動距離が小さいほど、適応度は高くなるように設計します(例: 適応度 = 1 / 総移動距離 )。

3. 選択 (Selection) の手法

選択は、適応度の高い個体を優先的に次世代の親として選び出す操作です。「適者生存」の原則に基づき、優れた遺伝子を後世に伝えることで、集団全体の質を向上させる役割を担います。

手法メリットデメリット/注意点主な用途
エリート選択最良解が失われないことを保証単体では多様性が失われる他の手法と併用される
ルーレット選択直感的で理解しやすい適応度の差が大きいと優れた個体に選択が集中しすぎる教育用やシンプルな問題
トーナメント選択高速で実装が容易、選択圧の調整が可能トーナメントサイズの調整が必要最も一般的で実用的
順位選択適応度の差が激しくても安定した選択が可能ソート処理の計算コストがかかる多様性を維持したい場合

4. 交叉 (Crossover) の手法

交叉は、選択された2つの親個体から遺伝子を組み合わせて、新たな子個体を生成する操作です。両親の持つ優れた部分を継承することで、親を超える性能を持つ子が生まれる可能性を秘めており、探索空間における「探索(Exploration)」の役割を担います。この操作は、遺伝子の表現方法と密接に関連しています。

遺伝子表現代表的な交叉手法
バイナリ/実数値一点交叉, 二点交叉, 一様交叉, ブレンド交叉(BLX-α)
順序表現順序交叉(OX), 部分マップ交叉(PMX)
  • 一点交叉 (Single-Point Crossover): 染色体上に一点の交叉点を定め、それ以降の遺伝子を親同士で入れ替える、最もシンプルな手法です。
  • ブレンド交叉 (BLX-α): 主に実数値表現で用いられ、2つの親の遺伝子値の間の値をランダムに生成することで、より連続的な探索を可能にします。

5. 突然変異 (Mutation) の手法

突然変異は、子個体の遺伝子を低い確率でランダムに変化させる操作です。この操作は、探索が局所的な最適解(局所最適解)に停滞してしまうことを防ぎ、集団の多様性を維持することで、探索の「多様性(Diversity)」を確保する重要な役割を果たします。突然変異率(Mutation Rate)は、通常1%以下といった低い値に設定されます。

遺伝子表現代表的な突然変異手法
バイナリビット反転突然変異 (Bit Flip Mutation)
実数値ガウス突然変異 (Gaussian Mutation)
順序表現交換突然変異 (Swap Mutation), 逆位突然変異 (Inversion Mutation)
  • ビット反転突然変異: バイナリ表現において、遺伝子の一部(ビット)を 0 から 1 へ、または 1 から 0 へと反転させます。
  • 交換突然変異: 順序表現において、染色体上の2つの遺伝子の位置を入れ替えます。

Pythonによる実装例

ここでは、これまでに解説した遺伝的アルゴリズムの各要素をPythonで実装し、具体的な問題を解決するプロセスを示します。題材として、古典的な組み合わせ最適化問題である「数分割問題 (Number Partitioning Problem)」を取り上げます。

数分割問題 (Number Partitioning Problem) とは

数分割問題とは、「与えられた数の集合を2つの部分集合に分割し、それぞれの部分集合の合計値の差を可能な限り小さくする」という問題です。例えば、{10, 8, 7, 6, 4} という数の集合がある場合、これを {10, 7} (合計17) と {8, 6, 4} (合計18) に分けると、差は |17 - 18| = 1 となり、これが最適解となります。

この問題は、組み合わせの数が膨大になる典型的なNP困難問題であり、遺伝的アルゴリズムの適用例として非常に適しています。

対象の問題を実装

まず、解決したい問題そのものを定義するクラスを作成します。このクラスは、分割対象となる数のリストを保持し、ある分割パターン(染色体)が与えられたときに、その評価値(2つの部分集合の合計値の差)を計算する役割を持ちます。この評価値が、個体の適応度を計算する際の基準となります。

import numpy as np

class NumberPartitioningProblem:
    def __init__(self, n_numbers: int, low: float = 0.0, high: float = 100.0) -> None:
        np.random.seed(123)
        self._numbers = np.random.uniform(low, high, n_numbers)

    def __call__(self, chromosome: np.ndarray) -> float:
        return self.score(chromosome)

    def score(self, chromosome: np.ndarray) -> float:
        sum0 = sum(self._numbers[chromosome == 0])
        sum1 = sum(self._numbers[chromosome == 1])
        return abs(float(sum0 - sum1))

個体を定義するクラス

次に、遺伝的アルゴリズムにおける「個体」を表現するクラスを定義します。各個体は、問題の解候補となる「染色体(chromosome)」と、その解の優秀さを示す「適応度(fitness)」を属性として保持します。今回の数分割問題では、染色体は各数値をどちらのグループに割り振るかを示すバイナリ配列(例: [0, 1, 0, 1, ...])で表現されます。

from collections.abc import Callable, Sequence

class Individual:
    def __init__(self, chromosome: np.ndarray, problem: Callable) -> None:
        self.chromosome = chromosome
        self.problem = problem
        self.fitness = self._calculate_fitness()

    def _calculate_fitness(self) -> float:
        return self.problem(self.chromosome)

    @classmethod
    def from_random_population(
        cls, n_individuals: int, n_features: int, n_classes: int, problem: Callable
    ) -> Sequence["Individual"]:
        population = []
        for _ in range(n_individuals):
            chromosome = np.random.randint(0, n_classes, n_features)
            population.append(cls(chromosome, problem))
        return population

アルゴリズムの実装

最後に、遺伝的アルゴリズムの本体を実装します。このクラスは、個体の集団(population)を管理し、「選択」「交叉」「突然変異」といった操作をメソッドとして定義します。run メソッドを実行することで、設定された世代数にわたって進化のシミュレーションを繰り返し、最適解を探索します。

import random

class GeneticAlgorithm:
    def __init__(
        self,
        problem: Callable,
        n_individuals: int,
        n_features: int,
        n_classed: int = 2,
        n_parents: int = 6,
        n_generations: int = 1000,
        mutation_rate: float = 0.01,
    ):
        self.problem = problem
        self.n_individuals = n_individuals
        self.n_features = n_features
        self.n_classed = n_classed
        self.n_parents = n_parents
        self.n_generations = n_generations
        self.mutation_rate = mutation_rate
        self.population: Sequence[Individual] = []

    def select_parents(self, population: Sequence[Individual], tournament_size: int = 4) -> Sequence[Individual]:
        parents = []

        sorted_population = sorted(population, key=lambda x: x.fitness)
        parents.extend(sorted_population[: self.n_parents // 2])

        # トーナメント方式
        for _ in range(self.n_parents // 2):
            # 集団からトーナメントサイズ分の個体をランダムに選ぶ
            tournament_contenders = random.sample(population, tournament_size)

            # トーナメント出場者の中から最も適応度の高い個体を勝者とする
            winner = min(tournament_contenders, key=lambda x: x.fitness)
            parents.append(winner)

        return parents

    def crossover(self, parents: Sequence[Individual]) -> Sequence[Individual]:
        population = []
        population.extend(parents)

        n_crossovers = (self.n_individuals - len(parents)) // 2

        for _ in range(n_crossovers):
            parent1, parent2 = random.sample(parents, 2)

            # 交叉点をランダムに決定 (遺伝子の間を選ぶので 1 から size-1)
            crossover_point = random.randint(1, len(parent1.chromosome) - 1)

            # 親1の遺伝子を交叉点までの部分とそれ以降の部分に分割
            parent1_part1 = parent1.chromosome[:crossover_point]
            parent1_part2 = parent1.chromosome[crossover_point:]

            # 親2の遺伝子を交叉点までの部分とそれ以降の部分に分割
            parent2_part1 = parent2.chromosome[:crossover_point]
            parent2_part2 = parent2.chromosome[crossover_point:]

            # 子の遺伝子を作成
            child1 = np.concatenate((parent1_part1, parent2_part2))
            child2 = np.concatenate((parent2_part1, parent1_part2))

            population.append(Individual(child1, self.problem))
            population.append(Individual(child2, self.problem))

        return population

    def mutate(self, population: Sequence[Individual]) -> Sequence[Individual]:
        for individual in population[self.n_parents :]:
            for i in range(len(individual.chromosome)):
                if random.random() < self.mutation_rate:
                    individual.chromosome[i] = 1 - individual.chromosome[i]
            individual.fitness = individual._calculate_fitness()

        return population

    def run(self):
        # 初期世代
        self.population = Individual.from_random_population(
            self.n_individuals, self.n_features, self.n_classed, self.problem
        )

        for i in range(self.n_generations):
            parents = self.select_parents(self.population)
            self.population = self.crossover(parents)
            self.population = self.mutate(self.population)

            best_individual = min(self.population, key=lambda x: x.fitness)
            print(f"第{i + 1}世代の最適解: {best_individual.fitness}")

実行例

最終的に、これまでに定義したクラスを使い、問題をインスタンス化し、遺伝的アルゴリズムのパラメータ(集団サイズ、世代数など)を設定して、探索を実行します。

if __name__ == "__main__":
    n_numbers = 100
    problem = NumberPartitioningProblem(n_numbers=n_numbers)

    ga = GeneticAlgorithm(
        problem,
        n_individuals=1000,
        n_features=n_numbers,
        n_classed=2,
        n_parents=6,
        n_generations=1000,
        mutation_rate=0.01,
    )
    ga.run()

おわりに

本記事では、生物の進化という自然界のメカニズムに着想を得た最適化手法「遺伝的アルゴリズム」について、その基本的な概念から各構成要素の役割、そしてPythonによる具体的な実装例までを解説しました。

遺伝的アルゴリズムは、今回取り上げた数分割問題だけでなく、スケジューリング、パラメータ最適化、巡回セールスマン問題など、厳密な解法が困難な多種多様な問題に対して強力な解法となり得ます。その最大の魅力は、問題の数学的な性質に深く踏み込むことなく、探索的なアプローチで実用的な解を見つけ出せる柔軟性にあります。

今回実装したコードは、遺伝的アルゴリズムの基本を理解するための一例です。ぜひ、各パラメータを調整したり、選択や交叉の手法を別のものに入れ替えたりして、その挙動の変化を観察してみてください。そして、ご自身の興味のある問題にこのアルゴリズムを適用し、その可能性を体験していただければ幸いです。

More Information

  • arXiv:2007.12673, Tanweer Alam, Shamimul Qamar, Amit Dixit, Mohamed Benaida, 「Genetic Algorithm: Reviews, Implementations, and Applications」, https://arxiv.org/abs/2007.12673
  • arXiv:2404.18955, Zhaoning Shi, Meng Xiang, Zhaoyang Hai, Xiabi Liu, Yan Pei, 「GARA: A novel approach to Improve Genetic Algorithms’ Accuracy and Efficiency by Utilizing Relationships among Genes」, https://arxiv.org/abs/2404.18955
  • arXiv:1911.00490, Alison Jenkins, Vinika Gupta, Alexis Myrick, Mary Lenoir, 「Variations of Genetic Algorithms」, https://arxiv.org/abs/1911.00490
  • arXiv:2304.03995, Robert Tjarko Lange, Tom Schaul, Yutian Chen, Chris Lu, Tom Zahavy, Valentin Dalibard, Sebastian Flennerhag, 「Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization」, https://arxiv.org/abs/2304.03995
  • arXiv:2506.02120, Mariana A. Londe, Luciana S. Pessoa, Carlos E. Andrade, José F. Gonçalves, Mauricio G. C. Resende, 「Random-key genetic algorithms: Principles and applications」, https://arxiv.org/abs/2506.02120