ga

遺伝的アルゴリズムによるパラメタ探索

日本語 | English

概要

遺伝的アルゴリズム (GA: Genetic Algorithm) による壺モデルのパラメタ探索を行うソースコード一式が含まれています。

実際に行われていること

大まかな流れ

遺伝的アルゴリズムによるパラメタ探索は、以下のような手順で行われます。

1. パラメタを表すベクトル: (rho, nu, recentness, frequency) を各個体とする集団をランダムに生成する
2. パラメタをもとに壺モデルを実行、その結果から適合度を算出し、これを記録する
3. 適合度をもとに、集団の進化計算を行う a. 適合度が高い個体を選択し、交叉を行う b. 一定の確率で突然変異を行う c. 次世代の集団を生成する
4. 2に戻る。ただし、一定の世代数が経過したら終了する

適合度の計算

特に2で（各個体ごとに）求められる適合度は、具体的には以下のようにして求められます。

1. (rho, nu, recentness, frequency) というパラメタをもとに、壺モデルを実行する
2. 壺モデルの実行によって生成された「相互やり取りの履歴」を記録する
3. 2で記録した履歴を用いて、ネットワークの特徴を示す10個のメトリクスを計算する
4. ターゲットとしているネットワークのメトリクスと、3で計算したメトリクスとの間の差分を計算し、これに-1をかけたものを適合度とする a. より正確には2つのメトリクスの差分を $d$ とすると、$d = \sum_{i=1}^{10} |m_i - m_i'|$ として計算できる．ただし、$m_i$ はターゲットとしているネットワークのメトリクス、$m_i'$ は3で計算したメトリクスである。 b. 適合度 $f$ は $f = -d$ として計算できる。

実行方法

本実験

このディレクトリ（/ga）に移動した上で、main.py を実行してください。

$ cd ga
$ pwd # => /path/to/ga
$ python main.py <population_size> <mutation_rate> <cross_rate> <target_data>  [rho] [nu] [s]

各引数の詳細などは python main.py -h あるいは python main.py --help で確認できます。

実行を行うと、./results/<target_data> 以下に結果が保存されます。より正確には、./results/<target_data> にディレクトリが作成され、その中に各世代ごとのアーカイブデータと、最終的な結果（最も適合度の高い個体のデータと、その個体によって生成されたネットワークのメトリクス）が保存されます。

グリッドサーチ

ターゲットデータごとに適した個体数、突然変異率、交差率を探索するためにグリッドサーチを行う場合は、grid_search.pyを実行してください。

$ pwd # => /path/to/ga
$ python grid_search.py <target_data>  [rho] [nu] [s]

結果はresults/grid_search/以下にjson形式で保存されます。grid_search.pyの実行にはMac Book Pro(M1 Pro, 32GB)で1つのターゲットデータに対して丸1日程度かかるので注意してください。

グリッドサーチの結果から最適な個体数、突然変異率、交差率を見つけるには、search_best.pyを実行してください。

$ pwd # => /path/to/ga
$ python search_best.py <target_data>  [rho] [nu] [s]