Evolutionary Algorithms

進化的アルゴリズム（EA）は、自然選択を模倣する最適化アルゴリズムの一群です。候補解の集団を維持し、それぞれを適応度関数で評価し、優れた候補から交叉とランダムな突然変異によって子孫を生成します。これを何世代も繰り返し、集団をより良い解へと導きます。EAでは候補を評価するだけでよく、勾配を計算する必要はありません。そのため、離散的な選択、微分不可能またはノイズのある目的関数、局所最適解が多数存在する起伏の激しい探索空間など、勾配降下法では扱えない問題にも適しています。このため、EAはハイパーパラメーター調整、ニューラルアーキテクチャ探索、エンジニアリング設計、スケジューリングの標準的な手法です。

進化的アルゴリズムの仕組み#

すべてのEAは、次の要素で構成されます。

1. 表現: 各候補は、ビット列、実数ベクトル、プログラム木などのゲノムとしてエンコードされます。
2. 初期化: 最初の世代は通常ランダムに生成され、既知の良好な解を初期値として使う場合もあります。
3. 適応度評価: 適応度関数が、最適化対象の目的に基づいて各候補を評価します。
4. 選択: 適応度の高い候補ほど親として選ばれやすくなります。たとえば、トーナメント選択ではランダムに選んだ複数の候補から優れたものを選び、エリート選択では最良の候補を変更せずに次世代へ引き継ぎます。
5. 変異: 交叉では2つの親の要素を組み合わせ、突然変異では小さな変更をランダムに加えて、集団が探索を続けられるようにします。

機械学習（ML）では、適応度関数に精度や平均適合率（mAP）などの検証指標を使うことがよくあります。そのため、候補を評価するにはモデルを学習してテストする必要があり、これが圧倒的にコストの高いステップです。予算が尽きるか、適応度の改善が止まるまで、次のループを繰り返します。

選択圧と突然変異の強さによって、活用と探索のバランスが決まります。選択圧が強く突然変異が小さいと、すぐに収束しますが、局所最適解に陥る可能性があります。一方、選択圧が弱く突然変異が大きいと、広範囲を探索しますが、評価を無駄にすることがあります。

進化的アルゴリズムの主な種類#

• 遺伝的アルゴリズム（GA）: 候補を文字列、通常はビット列としてエンコードし、主に交叉を利用します。John Hollandは1975年の著書Adaptation in Natural and Artificial Systemsで、この手法を体系化しました。
• 進化戦略（ES）: 実数ベクトルを最適化し、実行中にステップサイズを適応させるガウス突然変異を使用します。突然変異分布の共分散全体を学習するCMA-ESは、連続値のブラックボックス問題に対する最も強力な汎用手法の1つです。
• 遺伝的プログラミング: 木構造で表現したプログラムや数式を進化させます。記号回帰やプログラムの自動設計に使われます。
• ニューロエボリューション: ニューラルネットワークの重み、場合によっては構造も進化させます。OpenAIは2017年、1,000を超える並列ワーカーで実行する進化戦略を使い、3Dヒューマノイドに10分で歩行を学習させました。これは強化学習に代わるスケーラブルな手法です。

コードで見る遺伝的アルゴリズム#

ナップサック問題では、重量制限を超えずに総価値を最大化するため、どの品物を詰めるかを決めます。これは勾配のない離散問題です。このNumPyを使った遺伝的アルゴリズムは、品物ごとに1ビットを割り当てた50個のビット列ゲノムを進化させます。トーナメント選択、一様交叉、ビット反転突然変異、エリート選択を使い、1,048,576通りすべての選択肢と答えを照合します。

import itertools

import numpy as np

rng = np.random.default_rng(0)
# Knapsack problem: pick from 20 items to maximize total value within a weight limit of 200
values, weights, limit = rng.integers(10, 100, 20), rng.integers(5, 50, 20), 200


def fitness(pop):
    """Return each selection's total value, or 0 if it exceeds the weight limit."""
    return np.where(pop @ weights <= limit, pop @ values, 0)


population = rng.random((50, 20)) < 0.2  # 50 random genomes, one bit per item
for generation in range(100):
    scores = fitness(population)
    # Tournament selection: each parent is the better of two random genomes
    pairs = rng.integers(50, size=(50, 2))
    parents = population[np.where(scores[pairs[:, 0]] > scores[pairs[:, 1]], pairs[:, 0], pairs[:, 1])]
    # Uniform crossover with the next parent, then flip each bit with probability 0.05
    children = np.where(rng.random((50, 20)) < 0.5, parents, np.roll(parents, 1, axis=0))
    children ^= rng.random((50, 20)) < 0.05
    children[0] = population[scores.argmax()]  # elitism: keep the best genome
    population = children

all_selections = np.array(list(itertools.product([0, 1], repeat=20)))
print(f"GA best: {fitness(population).max()}, true optimum: {fitness(all_selections).max()}")

GA best: 811, true optimum: 811を出力します。このアルゴリズムは、総当たりでは100万通りの選択肢を確認するところを、その約0.5%にあたる5,000回の適応度評価で最適な詰め方を見つけました。

ハイパーパラメーターの進化#

学習率、損失の重み、データ拡張の強度などの学習設定は、どの数式でも予測できない形で相互に影響します。また、候補ごとに学習全体を実行する必要があるため、進化的探索に適しています。Ultralytics YOLOのtune()メソッドは、YOLO26モデルにこの手法を使用します。各イテレーションでは、これまでに得た適応度上位9つの設定から、適応度で重み付けして親を選びます。デフォルトの探索空間にある26個のハイパーパラメーターの約半分を、探索範囲に応じたスケールのガウスステップで変異させ、モデルを学習し、適応度を記録します。物体検出では、適応度にmAP_50-95を使います。30件の結果が得られると、最良の設定上位20%の共分散に基づく突然変異も使用します。これはCMA-ESを取り入れた手法です。ハイパーパラメーター調整ガイドに、探索空間の全容が記載されています。

from ultralytics import YOLO

# 事前学習済みYOLO26 nanoモデルを読み込みます
model = YOLO("yolo26n.pt")

# ハイパーパラメーターを進化させます。30イテレーション実行し、各イテレーションで変異させた設定を1つ選び、10エポック学習します
model.tune(data="coco8.yaml", epochs=10, iterations=30, plots=False)

チューナーは各設定と適応度をtune_results.ndjsonに書き込み、最良の設定をbest_hyperparameters.yamlに保存します。保存した設定は、学習全体の実行にそのまま渡せます。

その他の用途#

• ニューラルアーキテクチャ探索: GoogleのAmoebaNetは、正則化進化から生まれました。これは最悪のモデルではなく最も古いモデルを除外する、トーナメント選択型のEAです。2018年にはImageNetでトップ1精度83.9%を達成しました。
• エンジニアリング設計: NASAのSpace Technology 5ミッションでは、コンピューターで進化させたXバンドアンテナが2006年に飛行しました。形状は不規則な折れ曲がったワイヤーでしたが、従来の設計手法によるアンテナと同等の性能を達成しました。
• アルゴリズム発見: AlphaEvolveは2025年5月にGoogle DeepMindが発表したもので、コードの変更を提案するGeminiモデル、自動評価器、プログラムの進化的データベースを組み合わせています。Googleのデータセンター向けに進化させたスケジューリングヒューリスティックの1つは、同社の世界全体のコンピューティングリソースを平均0.7%回復させます。

進化的アルゴリズムと関連手法の比較#

• 勾配降下法: 微分可能な損失の勾配に従い、数百万個のパラメーターを持つネットワークの重みを学習する場合、はるかに効率的です。EAは、パラメーターが少ない問題、評価コストが高い問題、または勾配がない問題に適しています。
• 群知能: 粒子群最適化などの手法では、検索空間を移動するエージェントの集団を維持します。各エージェントは、自身と近隣の最良の結果を基に位置を調整し、世代交代、交叉、突然変異は行いません。
• ベイズ最適化: 目的関数の確率モデルを構築し、そのモデルが最も大きな改善を見込む場所を次の試行として選択します。小規模で滑らかな探索空間では、EAより少ない評価回数で済みますが、パラメーター数や並列ワーカー数が多い場合にはスケーリングしにくくなります。