遺伝的アルゴリズム(Genetic Algorithm, GA)は、生物の進化のメカニズムを模した最適化手法です。解の候補（個体）の集団を、選択・交叉・突然変異の操作を繰り返すことで進化させ、最適解を探索します。
DEAP(Distributed Evolutionary Algorithms in Python)は、Pythonで進化計算を実装するためのフレームワークで、遺伝的アルゴリズムだけでなく遺伝的プログラミングや多目的最適化にも対応しています。
本記事の内容
- 遺伝的アルゴリズムの全体像と各操作の理論
- DEAPの基本的な使い方
- 単目的最適化の実装
- 世代ごとの進化の可視化
遺伝的アルゴリズムの全体像
遺伝的アルゴリズムは以下の4ステップを反復的に実行します。
- 初期集団の生成: ランダムに個体（解の候補）を生成
- 選択(Selection): 適応度の高い個体を優先的に選択
- 交叉(Crossover): 2つの親個体の遺伝子を組み合わせて子個体を生成
- 突然変異(Mutation): 遺伝子の一部をランダムに変更
数学的な定式化
最適化問題を以下のように定式化します。
$$ \min_{\bm{x} \in \mathcal{S}} f(\bm{x}) $$
ここで $\bm{x}$ は個体（解の候補）、$\mathcal{S}$ は探索空間、$f$ は目的関数です。
適応度関数
適応度(fitness)は、各個体がどれだけ「良い」かを数値化する関数です。最小化問題の場合、
$$ \text{fitness}(\bm{x}) = -f(\bm{x}) $$
のように目的関数の負値を使うか、DEAPでは最小化の重み (-1.0,) を設定します。
選択: トーナメント選択
集団からランダムに $k$ 個体を選び、最も適応度の高い個体を選択する方法です。$k$ が大きいほど選択圧が高くなります。
交叉: 一点交叉
2つの親の遺伝子配列を、ランダムに選んだ位置で切断し交換します。
$$ \text{Parent 1}: [a_1, a_2, | a_3, a_4] \quad \text{Parent 2}: [b_1, b_2, | b_3, b_4] $$
$$ \text{Child 1}: [a_1, a_2, b_3, b_4] \quad \text{Child 2}: [b_1, b_2, a_3, a_4] $$
突然変異: ガウス突然変異
実数値の遺伝子に対して、ガウスノイズを加えます。
$$ x_i’ = x_i + \mathcal{N}(0, \sigma^2) $$
DEAPでの実装
Rastrigin関数の最小化問題をDEAPで解きます。Rastrigin関数は多数の局所最適解を持つベンチマーク関数です。
$$ f(\bm{x}) = 10n + \sum_{i=1}^{n}[x_i^2 – 10\cos(2\pi x_i)] $$
import numpy as np
import matplotlib.pyplot as plt
from deap import base, creator, tools, algorithms
import random
random.seed(42)
np.random.seed(42)
# --- Rastrigin関数 ---
def rastrigin(individual):
n = len(individual)
return (10 * n + sum(x**2 - 10 * np.cos(2 * np.pi * x) for x in individual),)
# --- DEAPの設定 ---
# 最小化問題の定義
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
# 遺伝子: [-5.12, 5.12]の実数値
n_dim = 10
toolbox.register("attr_float", random.uniform, -5.12, 5.12)
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_float, n=n_dim)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# 遺伝的操作の登録
toolbox.register("evaluate", rastrigin)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=0.5, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
# --- 遺伝的アルゴリズムの実行 ---
pop_size = 100
n_gen = 200
cx_prob = 0.7 # 交叉確率
mut_prob = 0.2 # 突然変異確率
# 初期集団の生成
pop = toolbox.population(n=pop_size)
# 統計の記録
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)
stats.register("std", np.std)
# 進化の実行
pop, logbook = algorithms.eaSimple(
pop, toolbox,
cxpb=cx_prob,
mutpb=mut_prob,
ngen=n_gen,
stats=stats,
verbose=False
)
# --- 結果の表示 ---
best_ind = tools.selBest(pop, k=1)[0]
print(f"最良個体の適応度: {best_ind.fitness.values[0]:.6f}")
print(f"最良個体の遺伝子（先頭5つ）: {[round(x, 4) for x in best_ind[:5]]}")
print(f"理論的な最小値: 0.0")
# --- 可視化 ---
gen = logbook.select("gen")
min_fits = logbook.select("min")
avg_fits = logbook.select("avg")
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# 適応度の推移
ax1 = axes[0]
ax1.plot(gen, min_fits, 'b-', label='Best')
ax1.plot(gen, avg_fits, 'r-', alpha=0.5, label='Average')
ax1.set_xlabel('Generation')
ax1.set_ylabel('Fitness (Rastrigin)')
ax1.set_title('Fitness Evolution')
ax1.legend()
ax1.grid(True, alpha=0.3)
# Rastrigin関数の形状（2次元断面）
ax2 = axes[1]
x = np.linspace(-5.12, 5.12, 200)
y = np.linspace(-5.12, 5.12, 200)
X, Y = np.meshgrid(x, y)
Z = 20 + X**2 - 10*np.cos(2*np.pi*X) + Y**2 - 10*np.cos(2*np.pi*Y)
ax2.contourf(X, Y, Z, levels=50, cmap='viridis')
ax2.scatter(best_ind[0], best_ind[1], c='red', s=100, marker='*', zorder=5,
label='Best solution')
ax2.set_xlabel('$x_1$')
ax2.set_ylabel('$x_2$')
ax2.set_title('Rastrigin Function (2D slice)')
ax2.legend()
plt.tight_layout()
plt.show()
Rastrigin関数は多数の局所最適解を持ちますが、遺伝的アルゴリズムは集団ベースの探索により、局所最適に陥りにくい性質を持っています。
まとめ
本記事では、DEAPを用いた遺伝的アルゴリズムの実装について解説しました。
- 遺伝的アルゴリズムは選択・交叉・突然変異の進化的操作を繰り返して最適解を探索する
- DEAPフレームワークでは、個体の定義から遺伝的操作の登録まで柔軟に設定できる
- トーナメント選択、ブレンド交叉、ガウス突然変異は実数値最適化で広く使われる
- 多峰性関数（Rastrigin関数など）に対しても、集団ベースの探索で局所最適を回避できる
次のステップとして、多目的最適化（NSGA-II）やパラメータチューニングへの応用も検討してみてください。