---
title: "遺伝的アルゴリズムとは？交叉・突然変異の仕組みとPython実装、収束を早める設定"
url: "https://www.issoh.co.jp/tech/details/3556/"
published: 2024-09-11
updated: 2026-11-02
categories: ["AI"]
publisher: "株式会社一創"
---

# 遺伝的アルゴリズムとは？交叉・突然変異の仕組みとPython実装、収束を早める設定

遺伝的アルゴリズム（GA：Genetic Algorithm）は、解の候補を「個体」として集団で持ち、良い個体を選ぶ（選択）、2つを掛け合わせる（交叉）、一部を書き換える（突然変異）を世代ごとに繰り返して、答えを少しずつ改良する最適化手法です。微分を使わないため、目的関数がシミュレーションの結果でしか得られない問題や、組み合わせが多すぎて総当たりできない問題に使えます。この記事では3つの操作の仕組みを整理したうえで、PythonのDEAPとPyGADで動くコードを示し、選択方式・交叉方式・突然変異率・個体数を変えると収束までの世代数がどう変わるかを、各30試行の実測値で示します。

## まとめ

- 遺伝的アルゴリズムは**選択→交叉→突然変異→評価**を1世代として繰り返す探索手法です。最適解の保証はありませんが、微分できない問題や組み合わせが爆発する問題でも実用的な解に届きます。
- 交叉は集団に既にある良い部分を組み合わせ、突然変異は集団に無い値を持ち込みます。**突然変異を切ると、100ビットのOneMax問題で30試行すべてが最適解に届きませんでした**（平均13.1か所の遺伝子が集団全体で0に固定）。
- 100ビットのOneMax（mutpb=0.2）で収束を早める効果が大きかったのは、**交叉方式を二点交叉から一様交叉へ替える（中央値64.5世代→31.5世代）**、交叉率を0.5から0.8へ上げる（→44.0世代）、遺伝子ごとの反転確率indpbを0.01〜0.02にする、の順でした。indpbを0.1にすると30試行中27回が400世代以内に解けません。
- 個体数を増やすと世代数は減りますが、**適応度の評価回数はむしろ増えます**（個体数50で3,049回、400で7,992.5回）。評価が重い問題では世代数ではなく評価回数で比べます。
- PythonではDEAP 1.4.4（2026年4月18日公開・日本時間）かPyGAD 3.9.2（2026年10月17日公開・日本時間）を使います。**DEAPのeaSimpleはエリート保存をしませんが、PyGADは既定で最良の1個体を次世代へ残します**。
- 制約を数式で書けて厳密な最適解が要るなら、GAではなく[数理最適化](/tech/details/2976/)のソルバを使います。

## 遺伝的アルゴリズムの仕組みと処理の流れ

### 選択・交叉・突然変異を繰り返す1世代の流れ

遺伝的アルゴリズムは、ジョン・ホランドが1975年の著書『Adaptation in Natural and Artificial Systems』で体系化しました。解の候補を「個体」、その集まりを「集団」、候補の良さを表す数値を「適応度」と呼び、次の流れを1世代として繰り返します。

1. 初期集団の生成：解の候補をランダムに複数作る
2. 適応度の評価：それぞれの候補がどれだけ良いかを数値にする
3. 選択：適応度の高い個体を優先して親に選ぶ
4. 交叉：2つの親の遺伝子を組み替えて子を作る
5. 突然変異：子の遺伝子の一部を確率的に書き換える
6. 2に戻る（世代数の上限に達するか、解が十分良くなるまで）

3つの操作は役割が違います。選択は集団を良い方向へ寄せる力、交叉は別々の個体が持つ良い部品をまとめる力、突然変異は集団に無い値を持ち込む力です。ビット列を位置ごとに交換する交叉だけでは、突然変異が無いと各位置で初期集団に存在しない値を生成できません。また、突然変異が強すぎると見つけた良い解が毎世代壊されてランダム探索に近づきます。この均衡が後で示すパラメータ調整の中身です。

### 進化的アルゴリズム・メタヒューリスティックとの関係

生物の進化を模した最適化手法の総称が進化的アルゴリズム（進化計算）で、GAはその一手法です。同じ系統に、解を木構造のプログラムとして進化させる遺伝的プログラミング、連続値を正規分布で変異させる進化戦略、個体間の差分ベクトルで変異を作る差分進化法があります。さらに広い分類ではGAは[メタヒューリスティック](/column/details/3530/)に属し、焼きなまし法や粒子群最適化と同じく、最適性の保証と引き換えに現実的な時間で十分良い解を狙います。

「GAはAIか」という問いには、データから学習する機械学習ではなく探索の手法だ、と答えるのが正確です。ただし機械学習と組み合わせる場面は多く、ハイパーパラメータ探索や、Sakana AIが言語モデルの統合に進化的手法を使った[CycleQD](/tech/details/4577/)のような例があります。

### スキーマ定理と積み木仮説：交叉が効く理由

GAが機能する理由の古典的な説明が、ホランドのスキーマ定理と、ゴールドバーグが1989年の著書で広めた積み木仮説です。スキーマとは「1\*\*0\*」のように一部の遺伝子だけを固定した型のことです。スキーマ定理は、適応度比例選択などの前提のもとで、交叉と突然変異による破壊を考慮し、次世代に残るスキーマの個体数の期待値に下限を与えます。短い定義長と少ない固定位置は破壊されにくさに関係しますが、各世代での増加を保証するものではありません。積み木仮説は、そうした短い良い部品（積み木）を交叉が組み合わせることで全体の良い解ができる、と考えます。

実務での読み方は、**部分解を足し合わせると全体解になる問題ほど交叉が効く**、です。後の実測で交叉率0.8が交叉率0の3分の1以下の世代数で解けたのは、OneMaxが「各ビットを1にする」部分解の足し算だからです。

## 選択の方式：ルーレット・トーナメント・エリート保存

選択方式で結果がどれだけ変わるかを、100ビットのOneMax問題（全ビットを1にする問題。最適値100）で選択方式だけを入れ替えて30試行ずつ測りました。個体数100・二点交叉・交叉率0.5・mutpb=0.2・indpb=0.01・上限400世代です。

| 選択方式                | 到達    | 世代数の中央値           |
| ------------------- | ----- | ----------------- |
| ルーレット選択             | 0/30  | 400世代で未到達         |
| 確率的普遍抽出（SUS）        | 30/30 | 138.0             |
| トーナメント（tournsize=3） | 30/30 | 64.5              |
| トーナメント3＋エリート1       | 30/30 | 63.0              |
| トーナメント3＋エリート5       | 30/30 | 62.0              |
| トーナメント3＋エリート10      | 30/30 | 66.5              |
| ルーレット＋エリート1         | 6/30  | 381.0（到達した6試行のみ）  |
| ルーレット＋エリート5         | 29/30 | 189.0（到達した29試行のみ） |

### ルーレット選択とSUS：適応度比例の選択確率

ルーレット選択は、適応度に比例した確率で親を選ぶ方式です。DEAPでは`tools.selRoulette`で、ドキュメントには[最小化問題や適応度が0以下になる問題には使えない](https://deap.readthedocs.io/en/master/api/tools.html)と明記されています。確率的普遍抽出（SUS、`tools.selStochasticUniversalSampling`）は同じ比率を、等間隔の針で一度に抜き出して偶然の偏りを減らした方式です。

OneMaxでは、ルーレット選択は30試行すべてが400世代で最適値に届かず（最良値の平均83.2）、SUSは全試行で届いたものの中央値138世代と、トーナメント選択の倍以上かかりました。原因は適応度の「比」で選ぶ仕組みにあります。適応度が平均約80の集団（各ビットが確率0.8で1）に200回ずつ選択をかけて比べると、選ばれた個体の平均はルーレットもSUSも80.15〜80.16で、集団平均79.94からほとんど上がりません。76点と84点の比は1.1倍しかないからです。トーナメント選択（tournsize=3）は83.37まで上がりました。

ルーレットとSUSの差は偶然の偏りです。1回の選択で一度も選ばれない個体は、ルーレットで平均37.0個、SUSで2.1個でした。ルーレットは選択圧がほとんど無いまま毎世代4割近い個体をランダムに捨てるので、良い遺伝子も偶然に失われます。適応度の差が小さくなる終盤ほどこの傾向が強まるため、ルーレット選択を使うなら適応度を順位に置き換える（ランキング選択）か、トーナメント選択を使うほうが安全です。

### トーナメント選択：tournsizeによる選択圧の調整

トーナメント選択は、集団からtournsize個をランダムに取り出して最良の1個体を親にする方式で、適応度の値の大きさではなく順位だけを使います。tournsizeを上げるほど選択圧が強まり、OneMaxでは2で76.5世代、3で64.5世代、5で54.5世代、10で53.0世代でした。5を超えると頭打ちです。

「選択圧を上げると多様性が失われ、局所解に陥る」とよく説明されますが、局所解の多いRastrigin関数（10次元・最小値0）で測ると、少なくとも突然変異が十分効いている設定では逆の結果でした。

```
import random, math, statistics
from deap import base, creator, tools, algorithms

DIM = 10

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

def rastrigin(individual):
    return (10 * DIM + sum(x * x - 10 * math.cos(2 * math.pi * x)
                           for x in individual),)

def run(tournsize, seed, ngen=200):
    random.seed(seed)
    tb = base.Toolbox()
    tb.register("attr_float", random.uniform, -5.12, 5.12)
    tb.register("individual", tools.initRepeat, creator.Individual,
                tb.attr_float, n=DIM)
    tb.register("population", tools.initRepeat, list, tb.individual)
    tb.register("evaluate", rastrigin)
    tb.register("mate", tools.cxBlend, alpha=0.5)
    tb.register("mutate", tools.mutGaussian, mu=0, sigma=0.5, indpb=0.2)
    tb.register("select", tools.selTournament, tournsize=tournsize)
    pop = tb.population(n=100)
    hof = tools.HallOfFame(1)
    algorithms.eaSimple(pop, tb, cxpb=0.7, mutpb=0.3, ngen=ngen,
                        halloffame=hof, verbose=False)
    unique = len({tuple(round(v, 3) for v in ind) for ind in pop})
    return hof[0].fitness.values[0], unique

for tournsize in (2, 3, 5, 10, 20):
    results = [run(tournsize, seed) for seed in range(60)]
    best = statistics.median(r[0] for r in results)
    uniq = statistics.median(r[1] for r in results)
    print(f"tournsize={tournsize:2d} 最良値の中央値={best:6.3f} ユニーク個体数の中央値={uniq:5.1f}")
```

| tournsize | 最良値の中央値（0が最適） | 最終世代のユニーク個体数 |
| --------- | ------------- | ------------ |
| 2         | 4.634         | 96/100       |
| 3         | 4.002         | 35/100       |
| 5         | 1.749         | 28.5/100     |
| 10        | 0.696         | 29.5/100     |
| 20        | 0.107         | 29/100       |

各tournsizeについて、乱数シード0〜59の60試行の中央値です。初期値は各次元−5.12〜5.12から生成しますが、交叉・突然変異後の値をこの範囲に戻す境界処理は入れていません。tournsize=2は多様性を最もよく保つ（100個体中96個がユニーク）のに最良値は最下位で、tournsize=20は多様性が3割まで落ちても最良値は0.107と最も最適に近づきました。mutGaussianのsigma=0.5・indpb=0.2で新しい値の供給が続くため、多様性の低下がそのまま失敗にはつながっていません。多様性の指標だけを見て選択圧を下げると、この比較では最良目的関数値の中央値が0.107から4.634へ、約43倍に増えます。判断は到達した適応度で行い、自分の問題では同じ形で測り直してください。

### エリート保存：DEAPのeaSimpleには無くPyGADは既定で1

エリート保存は、各世代の最良の数個体を交叉や突然変異にかけずに次世代へそのまま残す仕組みで、同じ評価基準のもとで、最良値が世代を追って悪化しないようにします。注意したいのは、ライブラリによって既定の扱いが違う点です。DEAPの`algorithms.eaSimple`は[子の集団で親の集団を丸ごと置き換え](https://deap.readthedocs.io/en/master/api/algo.html)、引数の`halloffame`は最良個体を記録するだけで集団には戻しません。一方PyGADは`keep_elitism`の既定値が1で、何も指定しなくても最良の1個体が残ります。同じ設定のつもりで両者を比べると、この差だけで結果が変わります。

上の表のとおり、エリート保存の効き方は選択方式で大きく違いました。トーナメント選択ではエリートを1〜10個残しても中央値62.0〜66.5世代で、無しの64.5世代とほぼ同じです（評価回数はエリートを再評価しない分だけ4,005回から3,639.5〜3,815.5回に減ります）。一方ルーレット選択では、エリート無しで0試行だった到達が、エリート1で6試行、エリート5で29試行まで増えました。偶然の偏りで良い個体を失いやすい選択方式ほど、エリート保存が効きます。

DEAPでエリート保存を入れるには、世代ループを自前で書いて次の3行を足します。

```
elites = list(map(tb.clone, tools.selBest(pop, elite)))
offspring = algorithms.varAnd(tb.select(pop, len(pop) - elite), tb, cxpb, mutpb)
# 子の評価のあと
pop = elites + offspring
```

## 交叉と突然変異の方式と選び方

### 解の表現（エンコーディング）と演算子の対応

実装で最初に決めるのは、解を何の並びで表すかです。ビット列（特徴選択やナップサック問題の採用・不採用）、実数列（連続値のパラメータ）、順列（巡回路や作業順序のように要素を重複なく1回ずつ並べる）の3つが基本で、表現が決まると使える交叉・突然変異が絞られます。順列では要素の重複を防ぐ演算子を選びます。例えばDEAPのcxOrderedを使う30都市の巡回路は、0〜29の整数を1回ずつ並べた個体で表します。

### 交叉：一点・二点・一様・ブレンド・順序交叉

| 方式     | DEAPの関数    | 必須引数  | 動作            | 適する表現    |
| ------ | ---------- | ----- | ------------- | -------- |
| 一点交叉   | cxOnePoint | なし    | 1か所で切って入れ替え   | ビット列・実数列 |
| 二点交叉   | cxTwoPoint | なし    | 2か所で切り中間を入れ替え | ビット列・実数列 |
| 一様交叉   | cxUniform  | indpb | 遺伝子ごとに確率で入れ替え | ビット列・実数列 |
| ブレンド交叉 | cxBlend    | alpha | 親の値の内分・外分点を取る | 実数列      |
| 順序交叉   | cxOrdered  | なし    | 重複を作らず順序を継承   | 順列       |

表の「必須引数」は個体以外に演算子が要求する引数です。ここでは`toolbox.register`で固定し、省略したまま演算子を呼ぶとTypeErrorになります。巡回セールスマン問題のような順列に二点交叉を使うと、同じ都市が2回現れる不正な個体ができます。順列には順序交叉（cxOrdered）か部分写像交叉（cxPartialyMatched）を使います。DEAPのこれらの実装では、要素を0〜n−1の整数に対応付け、各整数を1回ずつ並べます。

ビット列の3方式をOneMaxで比べると、世代数の中央値は一点交叉71.5、二点交叉64.5、一様交叉（indpb=0.5）31.5で、一様交叉が半分以下でした（30試行すべて到達）。一点・二点交叉は隣り合う遺伝子をまとめて受け継ぐので、良い遺伝子の隣にある悪い遺伝子も一緒に残ります。各ビットが独立に効くOneMaxでは、この「まとめて受け継ぐ」性質が足かせになります。逆に、隣り合う遺伝子が組で意味を持つ問題（工程の連続した並びなど）では、一様交叉はその組を壊すので有利とは限りません。

### 突然変異：mutpbとindpbの2つの確率

突然変異も表現に合わせ、ビット列には`mutFlipBit`、実数列には`mutGaussian`（mu・sigma・indpbが必須）、順列には`mutShuffleIndexes`を使います。DEAPで混同しやすいのが2つの確率です。`mutpb`はその個体に突然変異をかけるかどうかの確率、`indpb`はかけた個体の中で各遺伝子を書き換える確率です。100ビットでmutpb=0.2・indpb=0.01なら、個体の2割が対象になり、対象の個体では平均1ビットが反転します。交叉側の`cxpb`は、並んだ2個体のペアごとに交叉するかどうかの確率です（[varAndの仕様](https://deap.readthedocs.io/en/master/api/algo.html)）。

## 適応度関数の設計で押さえる3つの判断

適応度関数は候補の良さを数値で返す関数で、数理最適化でいう[目的関数と制約条件](/tech/details/8321/)を1つの評価値にまとめたものです。探索で何を優先するかはここで決まり、到達する解の質や評価回数は選択・交叉・突然変異の設定にも左右されます。

- **違反量に比例したペナルティにする**：制約を1つでも破ったら適応度0、とすると集団のほとんどが0になり選択が働きません。違反が少ない個体ほど点が高くなる形にします。
- **評価回数を見積もる**：OneMaxの基準設定でも中央値4,005回の評価が要りました。1回の評価に10秒かかるシミュレーションなら、それだけで11時間を超えます。重い場合は[サロゲートモデル](/tech/details/16830/)での近似か、`toolbox.register("map", ...)`での並列化を検討します。
- **単位の違う目的は正規化して重み付けするか、多目的化する**：コストと納期を重み付き和にすると、結果を決めるのは重みの設定です。DEAPは`weights=(-1.0, -1.0)`で複数の目的を持て、`tools.selNSGA2`を使う進化ループで、パレート最適解集合の近似を探索できます。

## PythonでGAを実装する：DEAPとPyGAD

### DEAP 1.4.4のインストールと構成

DEAPはDistributed Evolutionary Algorithms in Pythonの略で、最新版は[PyPIの1.4.4](https://pypi.org/project/deap/)（2026年4月17日UTC公開）です。今回はPython 3.13.14で動作を確認しました。

```
python -m pip install deap==1.4.4 numpy==2.5.4
```

`creator`で適応度クラスと個体クラスを作り、`base.Toolbox`に交叉・突然変異・選択・評価の関数を名前で登録し、`tools`の既製の操作と`algorithms`の進化ループを組み合わせる、という分担です。なお`pip show deap`は1.4.4と表示する一方、`deap.__version__`は”1.4″を返します。版の判定には`importlib.metadata.version("deap")`を使ってください。

### OneMax問題のコードと実行結果

OneMaxは最適値が100と分かっているので、探索がどこまで進んだかを一目で判断できます。適応度関数がタプル`(sum(individual),)`を返す点に注意してください。DEAPは多目的を前提に作られているため、目的が1つでもタプルで返します。

```
import random
from deap import base, creator, tools, algorithms

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

def eval_onemax(individual):
    return (sum(individual),)

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_bool, n=100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", eval_onemax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.01)
toolbox.register("select", tools.selTournament, tournsize=3)

random.seed(42)
pop = toolbox.population(n=100)
hof = tools.HallOfFame(1)
algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=40,
                    halloffame=hof, verbose=False)
print("40世代後の最良適応度:", hof[0].fitness.values[0])
```

```
40世代後の最良適応度: 97.0
```

入門記事でよく使われる40世代という設定では、最適値の100に届かず97で止まりました。後述の実測では、この設定で最適値に届くまで中央値64.5世代かかります。

### 巡回セールスマン問題（順序交叉）と2-optでの仕上げ

順列を扱う例として30都市の巡回セールスマン問題を解きます。`weights=(-1.0,)`で最小化にし、交叉に`cxOrdered`、突然変異に`mutShuffleIndexes`を使います。

```
import random, math
from deap import base, creator, tools, algorithms

random.seed(1)
N_CITY = 30
cities = [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(N_CITY)]

def total_distance(order):
    d = 0.0
    for i in range(len(order)):
        x1, y1 = cities[order[i - 1]]
        x2, y2 = cities[order[i]]
        d += math.hypot(x2 - x1, y2 - y1)
    return (d,)

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Route", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(N_CITY), N_CITY)
toolbox.register("individual", tools.initIterate, creator.Route, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", total_distance)
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

random.seed(42)
pop = toolbox.population(n=300)
hof = tools.HallOfFame(1)
algorithms.eaSimple(pop, toolbox, cxpb=0.8, mutpb=0.2, ngen=300,
                    halloffame=hof, verbose=False)
print("初期ルート(0番から順に巡回):", round(total_distance(list(range(N_CITY)))[0], 1))
print("GA最良ルート:", round(hof[0].fitness.values[0], 1))
```

```
初期ルート(0番から順に巡回): 1855.2
GA最良ルート: 523.6
```

番号順に回る初期ルートの1855.2に対し、300世代後の最良ルートは523.6でした。出発点を固定しても巡回路は29!通り（約8.8×10の30乗）ありますが、GAは76,041回の評価でこの水準に届いています。個体数×世代数の90,000回＋初期300回より少ないのは、eaSimpleが適応度を無効化された個体だけを再評価するためです。varAndは交叉・突然変異を適用すると適応度を無効化し、結果として遺伝子が変わらなかった個体も再評価します。

ただし、この523.6はまだ局所的に改善できる解です。辺を2本つなぎ替える2-opt法を最後にかけると、さらに短くなりました。

```
def two_opt(route):
    best = list(route)
    improved = True
    while improved:
        improved = False
        for i in range(1, N_CITY - 1):
            for j in range(i + 1, N_CITY):
                new = best[:i] + best[i:j + 1][::-1] + best[j + 1:]
                if total_distance(new)[0] < total_distance(best)[0] - 1e-9:
                    best, improved = new, True
    return best

print("GA解に2-optをかけた後:", round(total_distance(two_opt(hof[0]))[0], 1))
```

```
GA解に2-optをかけた後: 511.6
```

GAは大域的に良い領域を見つけるのは得意でも、最後の細かい詰めは遅い手法です。組合せ問題では、GAの解に局所探索をかけて仕上げる組み合わせ（メメティックアルゴリズム、memetic algorithmと呼ばれます）がよく使われます。

### PyGAD 3.9.2によるOneMaxの実装

PyGADは1つの`pygad.GA`クラスに引数を並べるだけで動く、APIが簡素なライブラリです（[PyPIの最新版は3.9.2](https://pypi.org/project/pygad/)）。上と同じOneMaxを書くと次のとおりです。

```
python -m pip install pygad==3.9.2 numpy==2.5.4
```

```
import numpy as np
import pygad

def fitness_func(ga_instance, solution, solution_idx):
    return float(np.sum(solution))

ga = pygad.GA(
    num_generations=400,
    num_parents_mating=50,
    sol_per_pop=100,
    num_genes=100,
    gene_type=int,
    gene_space=[0, 1],
    fitness_func=fitness_func,
    parent_selection_type="tournament",
    K_tournament=3,
    crossover_type="two_points",
    mutation_type="random",
    mutation_probability=0.01,
    keep_elitism=1,
    stop_criteria="reach_100",
    random_seed=0,
)
ga.run()
solution, fitness, _ = ga.best_solution()
print("最良適応度:", fitness)
print("要した世代数:", ga.generations_completed)
```

```
最良適応度: 100.0
要した世代数: 39
```

`stop_criteria="reach_100"`で適応度100に届いた時点で止まり、39世代でした。PyGADの`mutation_probability`は各遺伝子を変異対象にする確率です。DEAPのmutpbとindpbによる二段階の判定とは異なり、mutpbを省いて同じ数値を渡しても変異頻度はそろいません。また`keep_elitism`を書かなくても既定で1になります。両者の数字を直接比べるときは、エリート保存と突然変異の確率の意味をそろえてください。順列の交叉や多目的最適化まで細かく組みたいならDEAP、数行で試したいならPyGAD、が使い分けの目安です。多目的に特化したライブラリとしてはpymoo（最新版0.6.2）もあります。

## 遺伝的アルゴリズムの収束を早める設定（実測）

ここからは、OneMaxで最適値100に届くまでの世代数を、パラメータを1つずつ変えて測った結果です。乱数シード0〜29の30試行、上限400世代、基準は個体数100・cxpb=0.5・mutpb=0.2・indpb=0.01・tournsize=3です。

```
import random, statistics
from deap import base, creator, tools, algorithms

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)

def eval_onemax(individual):
    return (sum(individual),)

def build(indpb, tournsize):
    tb = base.Toolbox()
    tb.register("attr_bool", random.randint, 0, 1)
    tb.register("individual", tools.initRepeat, creator.Individual,
                tb.attr_bool, n=100)
    tb.register("population", tools.initRepeat, list, tb.individual)
    tb.register("evaluate", eval_onemax)
    tb.register("mate", tools.cxTwoPoint)
    tb.register("mutate", tools.mutFlipBit, indpb=indpb)
    tb.register("select", tools.selTournament, tournsize=tournsize)
    return tb

def gens_to_solve(pop_size, indpb, tournsize, cxpb, mutpb, seed, max_gen=400):
    random.seed(seed)
    tb = build(indpb, tournsize)
    pop = tb.population(n=pop_size)
    nevals = 0
    for ind in pop:
        ind.fitness.values = tb.evaluate(ind)
        nevals += 1
    for gen in range(1, max_gen + 1):
        offspring = algorithms.varAnd(tb.select(pop, len(pop)), tb, cxpb, mutpb)
        for ind in offspring:
            if not ind.fitness.valid:
                ind.fitness.values = tb.evaluate(ind)
                nevals += 1
        pop = offspring
        if max(ind.fitness.values[0] for ind in pop) >= 100:
            return gen, nevals
    return None, nevals

results = [gens_to_solve(100, 0.01, 3, 0.5, 0.2, seed) for seed in range(30)]
solved = [r for r in results if r[0] is not None]
print("到達:", len(solved), "/ 30")
print("世代数の中央値:", statistics.median(g for g, _ in solved))
print("評価回数の中央値:", statistics.median(n for _, n in solved))
```

```
到達: 30 / 30
世代数の中央値: 64.5
評価回数の中央値: 4005.0
```

### 交叉率：OneMaxでの0.8と0.95の比較

| cxpb | 世代数の中央値 | 評価回数の中央値 |
| ---- | ------- | -------- |
| 0.0  | 150.0   | 3,118.5  |
| 0.3  | 77.0    | 3,495    |
| 0.5  | 64.5    | 4,005    |
| 0.8  | 44.0    | 3,774    |
| 0.95 | 43.0    | 4,243    |

交叉率0でも150世代で解けますが、0.8で44世代と3分の1以下になり、0.95に上げても43世代で変わりません。この結果は部分解の足し算で全体解になるOneMaxでのものです。ただし評価回数で見ると順位が入れ替わり、交叉率0が3,118.5回で最も少なくなりました。交叉率0では、mutpb=0.2で突然変異の適用対象になった個体だけが適応度を無効化されるため、1世代あたりの評価対象は平均で約2割になります。遺伝子が実際に反転したかどうかは再評価の判定に使いません。評価が重い問題では、世代数の短さだけで交叉率を上げないでください。参考までに、MATLABの`ga`は[CrossoverFractionの既定値が0.8](https://www.mathworks.com/help/gads/ga.html)、Optuna 5.0.0の多目的サンプラー`NSGAIISampler`は`crossover_prob=0.9`で、既定の交叉は一様交叉です。

### 突然変異率：100ビットのOneMaxでのindpb比較

| indpb | 400世代以内に到達 | 世代数の中央値          |
| ----- | ---------- | ---------------- |
| 0.005 | 30/30      | 72.0             |
| 0.01  | 30/30      | 64.5             |
| 0.02  | 30/30      | 56.0             |
| 0.05  | 30/30      | 118.0            |
| 0.1   | 3/30       | 305.0（到達した3試行のみ） |

遺伝子長が100なので、indpb=0.01は「対象個体で平均1ビット反転」です。2ビット相当（0.02）で56世代まで縮みましたが、5ビット相当（0.05）では倍以上かかり、10ビット相当（0.1）では27試行が届きませんでした（届かなかった試行の平均最良値は98.1で、あと2ビットで足踏み）。変異による破壊が改善を上回った状態です。今回の100ビット・mutpb=0.2の比較では、indpb=0.02が試した値の中で最も少ない世代数で到達しました。この結果は他の遺伝子長や問題に共通する上限を示すものではなく、変異率が高い場合もランダム探索と同じ挙動になるとは限りません。Optunaの`NSGAIISampler`も既定ではパラメータ数の逆数（1.0 / パラメータ数）を突然変異確率に使います。

### 個体数：OneMaxでの到達世代数と評価回数の比較

| 個体数 | 世代数の中央値 | 評価回数の中央値 |
| --- | ------- | -------- |
| 30  | 174.0   | 3,162.5  |
| 50  | 99.0    | 3,049    |
| 100 | 64.5    | 4,005    |
| 200 | 41.0    | 5,167.5  |
| 400 | 31.5    | 7,992.5  |

個体数を30から400へ増やすと、世代数は174から31.5へ5.5分の1になります。一方で実際の計算コストである評価回数は3,162.5回から7,992.5回へ2.5倍に増えました。最も少なかったのは個体数50（3,049回）です。1回の評価にシミュレーションや実機測定を伴うなら、個体数は小さめから試します。

### 世代数の目安と打ち切り条件

世代数に固定の目安はありません。同じOneMaxでも、設定次第で31.5世代から、400世代回しても届かない場合まで幅がありました。実務では「最良適応度がN世代続けて改善しなければ停止」という条件を自前のループに入れます。eaSimpleは世代数固定なので、この場合は上の計測コードのようにループを書きます。

## 早期収束とヒッチハイキング：GAが止まる2つの原因

GAが途中で改善しなくなる典型は2つです。1つは**早期収束（初期収束）**で、序盤に偶然強い個体が現れ、その遺伝子が集団に広がって探索が早い段階で固まる現象です。もう1つは**ヒッチハイキング**で、良い遺伝子の隣にある悪い遺伝子が、交叉でまとめて受け継がれて生き残る現象です。

早期収束がどう起きるかは、突然変異を切る（mutpb=0）とよく分かります。基準設定のままmutpbだけ0にすると、**30試行すべてが400世代以内に最適値へ届かず、最良値は平均86.9で止まりました**。止まった時点の集団を調べると、平均13.1か所の遺伝子が全個体で0にそろっていました。全員が0を持つ位置は交叉では1に戻せないため、その時点で最適解への道が断たれています。突然変異が「集団に無い値を持ち込む」役割だというのは、この状態を防ぐという意味です。

対処は原因で分けます。

- 集団の遺伝子が固まる（早期収束）：突然変異率や個体数を変えて比較します。今回の100ビットのOneMaxでは、mutpb=0.2のもとでindpb=0.01〜0.02が試す候補になります。選択圧を下げる手もありますが、上のRastriginの実測のように最良値を悪化させることがあるので、到達した適応度で確かめてから決めます。
- 良い遺伝子の周りに悪い遺伝子が残る（ヒッチハイキング）：遺伝子どうしが独立に効く問題なら一様交叉に替える（前述の比較で二点交叉の半分以下の世代数）。
- 改善が止まったまま世代を重ねる：打ち切り条件を入れ、乱数シードを変えて複数回走らせ、最良を採ります。

## 他の最適化手法との使い分け

### 勾配法・数理最適化ソルバ・ベイズ最適化との違い

| 手法        | 必要な前提              | 最適性            | 向く場面           |
| --------- | ------------------ | -------------- | -------------- |
| 勾配法       | 勾配を計算・近似可能         | 収束・最適性は追加条件に依存 | 連続で山が1つの問題     |
| 数理最適化ソルバ  | ソルバが扱う数理モデルで定式化可能  | 許容誤差内で最適性を確認可能 | 制約を式で書ける計画問題   |
| ベイズ最適化    | 評価値を取得可能・評価予算が限られる | 保証なし           | 1回の評価が重い調整     |
| 遺伝的アルゴリズム | 適応度が計算できればよい       | 保証なし           | ブラックボックス・組合せ問題 |

分かれ目は「問題を数式の制約として書けるか」です。対応する数理モデルで定式化できるなら、まずソルバを検討します。ただし計算時間は問題の規模や構造に依存し、最適性を確認できるかは終了状態と許容誤差にも依存します。GAの出番は、目的関数がシミュレータや実測でしか得られない、あるいは制約が複雑で線形式に落とせない場合です。どの手法もあらゆる問題で他より優れることはない、というのがWolpertとMacreadyの[No Free Lunch定理](https://ieeexplore.ieee.org/document/585893)（1997年）で、手法選びは問題の性質で決まります。

### 遺伝的アルゴリズムを選ぶべきでない場面

- **厳密な最適解が必要**：GAは最適解に届いたかを自分で判定できません。OneMaxで「到達した」と言えたのは正解が100と分かっていたからです。監査や契約で最適性の根拠が要るなら、[Gurobi](/tech/details/2756/)のような数理最適化ソルバの証明付きの解を使います。
- **1回の評価が重い**：数千回の評価が前提です。1回10分の構造解析なら、評価回数を数十〜数百回に抑えるよう設計されたベイズ最適化を先に検討します。
- **再現性と説明責任が重い**：乱数に依存するため、シードを固定しない限り実行ごとに違う解が出ます。Rastriginの実験でも同じ設定の60試行で結果に幅があり、中央値で比べました。

## 実務での応用例：設計・シフト作成・配送計画・ハイパーパラメータ探索

### 新幹線の先頭形状とNASAのアンテナ

評価をシミュレーションでしか得られない設計問題は、GAの実績が多い分野です。N700系新幹線の先頭形状「エアロ・ダブルウィング」は、JR東海の技術者が[「遺伝的アルゴリズムを用いた先頭車両形状設計」](https://www.sice.or.jp/org/hokuriku/H21files/091104%5Fspk.pdf)と題して講演しており、走行抵抗の低減とトンネル微気圧波の対策を目的に形状を設計しました。NASAの小型衛星Space Technology 5のXバンドアンテナは、進化的アルゴリズムで自動設計され、[委託先が人手で設計したアンテナを上回った](https://doi.org/10.1162/EVCO%5Fa%5F00005)と報告されています（Hornbyら、Evolutionary Computation誌 2011年）。

### シフト・勤務表の自動作成

希望休、資格要件、連続勤務の上限といった条件を適応度のペナルティとして表します。ただし、必ず守る資格要件などと、調整可能な希望条件は区別します。例えば「各シフトに有資格者を1人以上配置」を必須条件とするなら、違反した案は採用せず、GAの出力を別途検証します。製品側での使われ方は[シフト管理システムのAI](/column/details/15897/)で整理しています。

### 配送ルートの最適化

上で実装した巡回セールスマン問題の拡張で、車両台数・積載量・時間指定が加わる配送計画では、規模や制約の組み合わせによって厳密解法の計算時間が増えるため、GAを含むメタヒューリスティックや厳密解法との併用を検討します。配送計画を自社の業務に組み込むなら、[物流システム開発](/service/business%5Fsystem/logistics/)として配車ロジックと既存の受注・在庫データの連携まで設計することになります。

### 機械学習のハイパーパラメータ探索

学習率などの連続値と、層の数などの離散値が混在するハイパーパラメータの調整に使えます。学習率については、学習過程を微分して調整する手法もあります。ただし1回の評価が学習1回分なので、評価回数の少ない手法が選ばれる場面も多くあります。[Optuna](/tech/details/18671/)は[5.0.0で多目的の既定サンプラーをNSGA-IIからTPEへ変えて](https://github.com/optuna/optuna/releases/tag/v5.0.0)おり、GA系のNSGAIISamplerは明示して使う形になりました。手法の選び方は[ハイパーパラメータ探索](/tech/details/16351/)の解説を参照してください。

## よくある質問

### 遺伝的アルゴリズムの収束を早めるには何を変えればよいですか？

100ビットのOneMax問題の実測では、二点交叉を一様交叉に替える（中央値64.5世代→31.5世代）、交叉率を0.5から0.8に上げる（→44.0世代）、トーナメントサイズを3から5に上げる（→54.5世代）が効きました。今回の100ビット・mutpb=0.2の比較では、遺伝子ごとの反転確率indpb=0.01〜0.02が有効でした。indpb=0.1では30試行中27回が400世代以内に解けませんでした。一様交叉が効くのは各遺伝子が独立に効く問題の場合です。

### 交叉と突然変異はそれぞれ何のためにあるのですか？

交叉は集団に既にある良い部分どうしを組み合わせ、突然変異は集団に無い値を持ち込みます。実測では、交叉率0でも150世代で解けた一方、突然変異を切ると30試行すべてが最適解に届かず、平均13.1か所の遺伝子が集団全体で0に固定されていました。

### 世代数と個体数はどのくらいに設定すればよいですか？

固定の目安はありません。個体数を増やすと世代数は減りますが評価回数は増え、OneMaxでは個体数50で3,049回、400で7,992.5回でした。今回のOneMaxでは個体数50の評価回数が最少でしたが、実務の初期個体数は評価予算から決めます。「N世代改善が無ければ停止」に加え、評価回数や時間の上限も設定します。

### DEAPとは何の略ですか？

Distributed Evolutionary Algorithms in Pythonの略で、遺伝的アルゴリズムを含む進化計算のPythonライブラリです。最新版は1.4.4（2026年4月18日公開・日本時間）で、`pip install deap`で入り、Python 3.13.14で動作を確認しました。

### 遺伝的アルゴリズムはAIですか？機械学習とどう違いますか？

データから学習して予測や分類をする機械学習とは違い、遺伝的アルゴリズムは評価関数を最大化・最小化する解を探す最適化手法です。両者は競合せず、機械学習モデルのハイパーパラメータ探索やニューラルネットワークの構造探索にGAを使う、という組み合わせ方をします。

## 関連記事

- [数理最適化とは？最適化アルゴリズムの種類と最適化モデルの作り方をPythonで解説](/tech/details/2976/)
- [ヒューリスティックとは？アルゴリズムとの違いと代表手法を実測で解説](/column/details/3530/)
- [決定変数・目的関数・制約条件とは？違いと定式化の手順を例題で解説](/tech/details/8321/)
- [ハイパーパラメータ探索とは？手法の選び方と打ち切り設計を実装目線で解説](/tech/details/16351/)
- [Gurobiとは？Pythonでの使い方・インストール・ライセンスと価格【gurobipy 13.0】](/tech/details/2756/)

---

出典: [遺伝的アルゴリズムとは？交叉・突然変異の仕組みとPython実装、収束を早める設定](<https://www.issoh.co.jp/tech/details/3556/>)（株式会社一創）