前回の記事では、ニューロエボリューションの動機と進化的アルゴリズム(EA)の基本構成要素について説明しました。 本記事では、進化的アルゴリズムのいくつかの種類と進化計算への他のアプローチについて取り上げます。

遺伝的アルゴリズム

遺伝的アルゴリズム(GA)は1970年代に初めて導入された進化的アルゴリズムの一種で、 特に離散的または組み合わせ最適化問題において最も広く使用されるアルゴリズムの一つです。 GAは、ニューラルネットワークグラフの重み付き隣接行列など、適切な遺伝子表現を使用して候補解を表現し、 選択された個体に対して突然変異(通常は固定された低い突然変異率)と交叉操作を適用します。 GAは通常、ルーレット選択(より優れた個体がより高い確率で選択される確率的選択)、 トーナメント選択(ランダムに選択された小グループ内で最良の個体を選択)、 ランクベース選択(ランクに応じて割り当てられた確率でランク付けされた個体を選択)、 および切り捨て選択(上位K個の最適個体を選択)を使用します。

上は、生存率50%の切り捨て選択を使用して、2次元SchafferおよびRastrigin関数上で200座標を20世代にわたって進化させたものを示しています。 この設定では、遺伝子型が表現型と同じである直接符号化が使用されています。 突然変異と交叉(xとy値がランダムに選択された異なる親から選ばれる)は90%の突然変異率と20%の交叉率で実行され、 初期集団は多変量ガウス分布からサンプリングされています。使用された単純なGAの実装は付録で確認できます。 上から、単純なGAが20世代で大域最適解に収束したことが観察できますが、 より高次元で複雑な適応度地形における局所最適解への早期収束の可能性も示唆しています。

進化戦略

進化戦略(ES)は、連続的で実数値の数値最適化のために設計され、1973年に提唱された、 もう一つの広く使用される進化的アルゴリズムの一種です。ESは、解のパラメータに対応する実数値ベクトルで各個体を表現します。 ESは主に切り捨て選択を利用し、選択された個体を保持するか、次世代で子孫のみを使用するかのいずれかで、 これらはそれぞれ($\mu + \lambda$)-ESと($\mu, \lambda$)-ESに分類されます。 ($\mu$は子孫を生成するために使用される選択された個体を表し、$\lambda$は子孫を示します。)

上は、$\mu=1$の単純な($\mu + \lambda$)-ESを使用して、2次元SchafferおよびRastrigin関数上で200座標を20世代にわたって進化させたものを示しています。 初期集団は多変量ガウス分布(平均ベクトル[1.0, 2.0]と対角値が固定分散または突然変異力0.5に設定された共分散行列)からサンプリングされています。 使用された単純なESの実装は付録で確認できます。単純なESが共分散を同じに保ちながら最良個体を使用して平均をシフトすることで、 徐々に大域最大値に近づいていく様が観察できます。

CMA-ES

単純なGAとESの両方において、突然変異のためのノイズをサンプリングする際、固定分布の使用に制限されていました(GAでは一様分布、ESでは正規分布)。 これは、進化的探索中に突然変異の程度を調整するために観測値を活用できないことを意味していました。 そこで、共分散行列適応進化戦略(CMA-ES)は、その名前が示すように、より良い観測値の活用のためにノイズの共分散行列を適応的に調整します。 共分散行列は、平均ベクトルと同様に、前世代からの選択された個体を使用して計算されます。

上は、($\mu + \lambda$)選択を用いたCMA-ES(生存率は25%に設定)を使用して、 2次元SchafferおよびRastrigin関数上で200座標を20世代にわたって進化させたものを示しています。 平均と共分散の計算はNumPyによって提供される関数を使用して行われたため、共分散行列の実行時計算量は$O(N^2)$となります(ここで$N$は変数の数(この場合は2))。 です。したがって、CMA-ESは通常、少数のパラメータ(〜10K)の最適化に使用されます。 使用されたCMA-ESの実装は付録で確認できます。ここでは、CMA-ESが分布の楕円を適応的に変化させることが観察できますが、 アルゴリズムが過度に活用的であるため、高度に欺瞞的なRastrigin関数において局所最大値への早期収束を引き起こしました。

OpenAI-ES

OpenAI進化戦略(OpenAI-ES)は、小さく固定された多変量ガウス分布からのサンプルを使用してパラメータの勾配を推定し、 勾配上昇を実行することで、進化戦略をより活用的にする別の技術です。 具体的には、平均ゼロで対角分散$\sigma$を持つ多変量ガウス分布から$N$個のノイズ$\epsilon$をサンプリングし、 $\sum_i^N F(\theta+\sigma\epsilon_i)\epsilon_i/N\sigma$を計算することで$\theta$の勾配を推定します。 勾配を解析的に計算しないため、OpenAI-ESは微分不可能でノイズのある関数に適用できます。 また、重みを推定するための適応度計算は、マルチプロセッシングやベクトル化を使用して並列化できるため、 大量のパラメータを最適化するアルゴリズムとして人気があります。

上は、2次元SchafferおよびRastrigin関数において、平均ベクトル(固定分散付き)に対しOpenAI-ESを使用して、 200座標を20世代進化させた結果を示しています。使用されたOpenAI-ESの実装は付録で確認できます。 平均ベクトルの代わりに、ランダムに選択された初期集団メンバーを最適化するモデルのパラメータとして扱うこともでき、 これは実際にこの場合において平均ベクトルを最適化するよりも良い結果をもたらします。 (練習として初期集団の最適化を実装し、結果を確認してみてください。)この特定の実装では、 より良い勾配推定のためにより小さい分散$\sigma$を使用するため、適応度計算が2回実行されています。 しかし、勾配推定では100個のサンプルのみが選択され、適応度関数が両方とも欺瞞的であるため、 アルゴリズムは大域最適値に向かって移動することに失敗しました。

その他のアプローチ

議論され実験された上の技術に加えて、様々な異なる戦略を持つ他のアプローチがあります。 例えば、非支配ソート遺伝的アルゴリズムII(NSGA-II)は、多目的最適化に使用される遺伝的アルゴリズムの例であり、 パレートフロント上の多様な解集合の発見を行います(パレートフロントは、 他の実行可能解が一つを悪化させることなく複数の目的のいずれかでより良い結果を達成できないパレート最適解の集合であり、 複数の目的間の潜在的なトレードオフを示します)。NSGA-IIは、 パレート最適解を保存するために親と子孫の全体から最高ランクの個体を選択するエリート主義を使用し、 高速非支配ソート(記録管理を伴って非支配解を反復的に特定し、それに応じてランク付けする)を利用し、 疎な領域を優先し多様性を保持するために混雑距離を使用します。

遺伝的プログラミング(GP)は、ニューロエボリューションで探求される別のアプローチで、 最適プログラムのオープンエンドな発見のために可変長で実行可能なツリー構造プログラムを進化させます。 GPは、ニューロエボリューションの文脈でニューラルネットワークアーキテクチャ、 ハイパーパラメータなどの構築ルールを最適化するために使用されます。 デカルト遺伝的プログラミング(CGP)は、ニューラルネットワークを含むグラフへのGPの効率的で単純な適用のために、 プログラムをツリーではなく有向非環グラフ(DAG)として表現する遺伝的プログラミングの例です。 対し、進化プログラミング(EP)は、ESに似ているが異なるアプローチで、表現型適応に焦点を当て、 通常確率的選択を使用します。

他にも、(鳥の群れのような)動物の社会行動にインスパイアされた粒子群最適化(PSO)や、 フェロモン痕跡を使って食料源への経路を見つける実際のアリのコロニーを模倣したグラフトラバーサルの最適化のためのアリコロニー最適化(ACO)など、 自然に強くインスパイアされた異なるアプローチもあります。一方で、 より情報に基づいた活用的候補サンプリングのために統計モデルを利用する分布推定アルゴリズム(EDA)や、 シンプルで効果的であることが証明されている特定の変分演算子(3個体を使用した突然変異と変異体と非変異体ベクトル間の交叉) と貪欲選択を使用する差分進化(DE)など、より確率的、機械的なアプローチがあります。 上の議論が暗に示すように、進化的アルゴリズム自体の進歩はニューロエボリューションの分野に影響を与える可能性が非常に高いため、 進化的アルゴリズムに関する広範な研究が強く推奨されます。

結論

本記事では、GA、ES、CMA-ES、およびOpenAI-ESについて議論し、 ニューロエボリューションで使用できる他のアプローチ(NSGA-II、GP、CGP、EP、PSO、ACO、EDA、およびDE)を簡潔に紹介しました。 一部の進化的アルゴリズムは特定のタスクを実行するように設計されていますが、 個々のタスクに対するEAの有効性はハイパーパラメータに非常に敏感で、事実上予測不可能であるため、 実験が必要です。次の記事では、ついにEAを用いてニューラルネットワークを進化し始めます。

付録

以下は、本記事の図の作成に使用した進化的アルゴリズムと関数のPython実装です。 これらの実装は、高速で並列化可能な計算のためにJAXを利用しています。 (これらのアルゴリズムの理解を深めるために、ご自身で実装してみることを強くお勧めします。)

リソース

• Risi, S. et al. 2025. Neuroevolution: Harnessing Creativity in AI Agent Design. Neuroevolution.