本記事は、遺伝的アルゴリズム（GA）とニューラルネットワーク（NN）を組み合わせた手法であるNEATについて、公式ドキュメントを読んでいきながら理解を深めていく勉強メモです。
ここでは、特にPythonを用いて記述しているNEAT-Pythonについて取り上げてみていこうと思います。
なお、今回はNEAT-Pythonの公式ドキュメントが英語であるため、適宜引用しながらChatGPTを用いて日本語に変換しています。そのため、時折進化計算や機械学習の分野で使用される語彙とは異なる単語が出力されます。これを踏まえて、なるべく適切な単語に変換してメモするようにしています。
NEATとは
NEAT is a method developed by Kenneth O. Stanley for evolving arbitrary neural networks. NEAT-Python is a pure Python implementation of NEAT, with no dependencies other than the Python standard library.
NEATは、Kenneth O. Stanleyによって開発された、任意のニューラルネットワークを進化させるための方法です。NEAT-Pythonは、NEATの純粋なPython実装であり、Python標準ライブラリ以外の依存関係はありません。
NEAT (NeuroEvolution of Augmenting Topologies) is an evolutionary algorithm that creates artificial neural networks.
NEAT（NeuroEvolution of Augmenting Topologies）は、人工ニューラルネットワークを生成する進化アルゴリズムです。
これらの部分より、NEATとは任意の人工ニューラルネットワークを進化させていくアルゴリズムであることが分かります。
NEATの概要
In the current implementation of NEAT-Python, a population of individual genomes is maintained. Each genome contains two sets of genes that describe how to build an artificial neural network:
1. Node genes, each of which specifies a single neuron.
2. Connection genes, each of which specifies a single connection between neurons.NEAT-Pythonの現在の実装では、個々のゲノムの集団が維持されています。各ゲノムには、人工ニューラルネットワークを構築する方法を記述する2つの遺伝子セットが含まれています:
1. ノード遺伝子: それぞれが単一のニューロンを指定します。
2. 接続遺伝子: それぞれがニューロン間の単一の接続を指定します。
ここで重要なのは、NEATでは2つの遺伝子を用いるということです。1つ目はノード遺伝子で、2つ目は接続遺伝子です。ニューラルネットワークをイメージしてもらえれば分かりやすいと思います。
なお、ゲノムとは遺伝子情報を保持するリストやデータ構造となります。そして、このゲノムに格納された情報を元にしてニューラルネットワーク1個体が構築されることとなります。
To evolve a solution to a problem, the user must provide a fitness function which computes a single real number indicating the quality of an individual genome: better ability to solve the problem means a higher score. The algorithm progresses through a user-specified number of generations, with each generation being produced by reproduction (either sexual or asexual) and mutation of the most fit individuals of the previous generation.
問題の解を進化させるために、ユーザは個別のゲノムの品質を示す単一の実数を計算する適応度関数を与える必要があります。問題を解決する能力が高いほど高いスコアが得られます。アルゴリズムは、ユーザが指定した世代数を進行し、各世代は前の世代の最も適応度の高い個体の繁殖（性的または無性のいずれか）と突然変異によって生成されます。
進化計算でいうところの評価の部分だと思われます。先述したノード遺伝子と接続遺伝子の品質を表すための評価関数を、私たちユーザ自身が与える必要があります。
つまり、
1. 各個体のゲノムごとに、適応度関数を用いて評価を実行
2. その評価を元にして、親となるような個体を選択し、交叉と突然変異を通じて新たな子個体を生成
3. この1, 2の進化のサイクルを、与えた世代数分実行する
という流れです。
The reproduction and mutation operations may add nodes and/or connections to genomes, so as the algorithm proceeds genomes (and the neural networks they produce) may become more and more complex. When the preset number of generations is reached, or when at least one individual (for a fitness criterion function of max; others are configurable) exceeds the user-specified fitness threshold, the algorithm terminates.
繁殖および突然変異の操作は、ゲノムにノードと接続を追加する場合があり、アルゴリズムが進行するにつれて、ゲノム（およびそれらが生成するニューラルネットワーク）はますます複雑になる可能性があります。指定された世代数に達するか、少なくとも1つの個体（最大の適応度基準関数の場合；その他は設定可能）がユーザ指定の適応度の閾値を超えた場合、アルゴリズムは終了します。
交叉や突然変異により、ニューラルネットワークにノードや接続が追加されたりします。これにより、ネットワークは進化を重ねるごとにどんどん複雑になっていくため、あらかじめ適応度の閾値を定めておくことで、ネットワーク自体が複雑になりすぎる前にアルゴリズムを終了させることができます。
以上までで、進化のサイクルの終了条件は2つ存在することが分かります。1つ目は、設定した世代数分進化が実行されることです。2つ目は、適応度の閾値を設定し、その閾値を超えた場合に終了することです。
One difficulty in this setup is with the implementation of crossover - how does one do a crossover between two networks of differing structure? NEAT handles this by keeping track of the origins of the nodes, with an identifying number (new, higher numbers are generated for each additional node). Those derived from a common ancestor (that are homologous) are matched up for crossover, and connections are matched if the nodes they connect have common ancestry. (There are variations in exactly how this is done depending on the implementation of NEAT; this paragraph describes how it is done in this implementation.)
この設定における1つの困難な点は、交叉（crossover）の実装です。異なる構造を持つ2つのネットワークの間でどのように交叉を行うのでしょうか？ NEATは、ノードの起源を識別する番号（新しい、より高い番号は各追加のノードごとに生成されます）を追跡することでこれに対処します。共通の祖先から派生したノード（同源のもの）は、交叉のために対応させられ、接続は、接続するノードが共通の起源を持つ場合に対応させられます。（NEATの実装によって、これがどのように行われるかにはさまざまなバリエーションがあります；この段落は、この実装での方法を説明しています。）
さて、先述した説明で、交叉によりノードや接続の追加を行うと分かりました。しかし、この交叉をプログラミングでどのように実装するかが問題点となります。特に、2つのそれぞれ異なる構造を持つニューラルネットワークを親としたとき、どのように交叉を行うようにするべきかを考える必要があります。
NEATでは、この問題に対処するため、ノードの起源を識別するような番号を用いるようにしています。これにより、例えば共通の祖先から派生したノードは、交叉のために対応させられることとなります。また、その接続は、そのようなノード同士を対応する際に使用されます。
交叉をプログラミングでどのように実装するか
ノードの起源を識別するような番号を用いる
Another potential difficulty is that a structural mutation - as opposed to mutations in, for instance, the weights of the connections - such as the addition of a node or connection can, while being promising for the future, be disruptive in the short-term (until it has been fine-tuned by less-disruptive mutations). How NEAT deals with this is by dividing genomes into species, which have a close genomic distance due to similarity, then having competition most intense within species, not between species (fitness sharing). How is genomic distance measured? It uses a combination of the number of non-homologous nodes and connections with measures of how much homologous nodes and connections have diverged since their common origin. (Non-homologous nodes and connections are termed disjoint or excess, depending on whether the numbers are from the same range or beyond that range; like most NEAT implementations, this one makes no distinction between the two.)
もう1つの潜在的な困難は、接続の重みなどの突然変異とは異なり、ノードや接続の追加などの構造的な変異は将来有望である一方で、短期間では混乱を引き起こす可能性があります（それがより混乱を引き起こさない突然変異によって微調整されるまで）。NEATがこれに対処する方法は、ゲノムを種に分けることで、類似性による遺伝的距離が近い種内で最も競争が激しい状況を作り出し、種間では競争が起こらないようにすることです（適応度共有）。遺伝的距離はどのように測定されるのでしょうか？ それは、同源ノードと接続が共通の起源からどれだけ分かれたかを示す尺度と、同源ノードと接続の数と、それらが同じ範囲からの数かそれを超える数かに基づく、非同源ノードと接続の数の組み合わせを使用します（非同源ノードと接続は、同じ範囲からの数かそれを超える数かに応じて、分離または余剰と呼ばれます；ほとんどのNEATの実装と同様に、この実装ではこれらの2つを区別しません）。
問題点はもう1つあります。それは、ノードや接続の追加などのネットワークの構造的な変異が行われると、変異後すぐの状態では適応度が低くなることが考えられるということです。そして適応度が低くなると、仮に進化を重ねることで将来的には優れた評価を出すようなものに対しても、淘汰されてしまう可能性があります。
これに対処するため、NEATでは種分化という方法を用います。これは、遺伝子を遺伝的距離の近いもの同士で種ごとに分けて、その種の中で競争を行うようにする代わりに、種同士の間では競争が起こらないようにするというものです。
（例えば、似たネットワークを持つ個体同士は同じ種と見る、違うネットワークを持つ個体同士は別の種と見る、といったことを想像してください。このようにグループごとに分けることにより、多様性を確保するようになっています。）
ネットワークの構造的な変異後すぐは、適応度が低くなりやすい
種分化の実施
概要まとめ
というわけで、以上をまとめていきます。
- NEATは、任意の人工ニューラルネットワークを進化させていくアルゴリズムである
- NEATは、ノード遺伝子と接続遺伝子の2つの遺伝子を用いる
- ユーザが評価関数を与えることで、ノード遺伝子と接続遺伝子の適応度を評価する
- ユーザは、あらかじめ適応度の閾値を定めておくことで、複雑になりすぎる前にアルゴリズムを終了させることもできる
- ニューラルネットワークを進化させていく際の問題点は2つ存在する
- 交叉をプログラミングでどのように実装するか
- ネットワークの構造的な変異後すぐは、適応度が低くなりやすい
- ノードの起源を識別するような番号を用いる
- 種分化の実施
インストール
ここからは, NEAT-Pythonのインストールを実行していきます.
なお, インストールするにあたり実行環境を記述しておきます.
Python 3.9.9
pip 21.2.4
OS: Microsoft Windows 10 Pro
CPU: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
RAM: 8.00 GB
NEAT-Pythonのインストール方法は2つあります.
1. Install neat-python from PyPI using pip
2. Install neat-python from source using setup.py
すなわち, 次の2つですね.
1. pipコマンドを使用して, PyPIからインストールする
2. setup.pyを使用して, sourceからインストールする
これらの何が違うかというと, 1はpipコマンドを使用するのに対し, 2はGithubからリポジトリをダウンロードして, その中にあるsetup.pyを実行するというものになります. 慣れている方法どちらかで行ってください.
今回は, 1のpipコマンドを使用してインストールするようにします.
pip install neat-python
エラーが出なければ, これでインストールは完了です.
次