遺伝的アルゴリズム

遺伝的アルゴリズム（ TSP，関数の最大値への応用）

[巡回セールスマン問題]

test ケーススタディファイル名   // C/C++，C#，VB の場合
Java Test ケーススタディファイル名   // Java の場合
PHP test.php ケーススタディファイル名   // PHP の場合
Ruby test.rb ケーススタディファイル名   // Ruby の場合
py -3 test.py ケーススタディファイル名   // Python の場合

と入力してやれば実行できます．ケーススタディファイル，たとえば data_ct は，同じ問題を乱数の初期値や問題を変えて実行したいような場合に効果的であり，たとえば以下のような形式で作成します．

3
data1_s.txt data1_t.txt
data1_s.txt data1_t.txt
data1_s.txt data1_t.txt

　　最初の数字はケーススタディの数（この場合は 3 ケース）であり，2 行目以降が各ケーススタディのデータになります．各行の最初が Species 記述ファイル名，2 番目が TSP 記述ファイル名です．

　　Specific 記述ファイルは，遺伝的アルゴリズムに対する基本事項を記述するためのファイルであり，たとえば以下のように記述します．

対立遺伝子上限 9 対立遺伝子下限 0
最大遺伝子長 10 最小遺伝子長（負の時は，最大遺伝子長で固定） -1
遺伝子の重複 0 個体の重複（同じ染色体の個体） 0
集団サイズ 10 子供 10

　　日本語で記述した部分（「対立遺伝子上限」，「対立遺伝子下限」等）は，次に続くデータの説明ですのでどのように修正しても構いませんが，削除したり，または，複数の文（間に半角のスペースを入れる）にするようなことはしないでください．また，以下の説明においても同様ですが，入力データによっては，そのケースには不必要なデータが現れることがあります．その場合においても，データの説明とデータは削除せず残しておいてください（内部的には，使用されません）．各データの意味は以下に示す通りです．

対立遺伝子上限と対立遺伝子下限: 　　説明通り，対立遺伝子上限と対立遺伝子下限を入力します．プログラム内では，初期集団の発生や突然変異操作の中で使用されます．たとえば，染色体を 0 と 1 の組み合わせで表現したいときは，1 と 0 を入力します．また，TSP のような場合で，かつ，標準的な初期集団発生手続きを使用する場合は，上限と下限の間の数字（上限と下限を含む）の数が，都市の数と一致する必要がある点に注意してください．なお，一つの遺伝子の値に対して int を使用していますので，int で表現できない上限や下限を入力しないでください．
最大遺伝子長と最小遺伝子長（負の時は，最大遺伝子長で固定）: 　　このプログラムでは，可変長の染色体を使用できます．そのような場合，遺伝子長の上限と下限を入力します．最小遺伝子長に負の値を入力すると，最大遺伝子長で与えた固定長の染色体となります．
遺伝子の重複: 　　一つの染色体の中に同じ遺伝子を複数個含むことができるか否かを入力します．1 を入力すると可能になり，0 を入力すると不可能になります．TSP のような場合は，0 を入力します．
個体の重複（同じ染色体の個体）: 　　個体集団の中に同じ遺伝子の並びを持った個体が複数存在することを許すか否かを入力します．1 を入力すると許し，0 を入力すると許しません．
集団サイズ: 　　集団サイズを入力します．このプログラムでは，集団サイズは固定です．
子供: 　　交叉により発生させる子供の数を入力します．たとえば，1 点交叉のように，2 つの親から 2 つの子供を生成する交叉においては，ここで入力された値の半分の回数だけ交叉が実行されます．

　　TSP 記述ファイルは，TSP を解くために必要なデータ（クラス TSP に関するデータ）を記述するファイルであり，たとえば以下のように記述します．なお，クラス TSP は，クラス Species の導出クラスになっています．Species で定義した値と矛盾しないように注意してください．たとえば，都市の数は，最大遺伝子長と等しくなければなりません．なお，9 行目，及び，10 行目は，Java のプログラムを実行する場合だけに必要とします．他の言語のプログラムを実行する際には，9 行目，及び，10 行目を削除してください．

出力レベル(負はファイル) 10 出力方法(0:適応度＋順番，1:適応度) 0
出力ファイル名 result\kekka 表示間隔 10
交叉方法 1 交叉確率 1.0 点 5 位置 0 方法 1 バイアス 0 ステップ 1
突然変異方法 1 突然変異率 0.03 幅 1 平均 0.0 標準偏差 1.0
エリート 2 方法 1 バイアス 0 ステップ 1
都市数 10 最大世代交代数 2000
近傍探索(0:行わない，1:行う) 0 近傍（2or3） 2
選択方法(0:最良，1:最初) 1
図示(0:しない，1:結果，2:初期状態と結果，3:ステップ) 3
都市番号 0 図の大きさ（幅，高さ） 1000 750
-58 37
55 -19
6 -79
27 -30
44 -94
33 -58
-94 87
-9 3
33 69
43 -57

　　各データの意味は，以下に示すとおりです．

出力レベル(負はファイル)

　　結果の出力方法を入力します．

=0 : 最終結果だけを出力します．

=n : n 回毎に出力します．なお，n が負の場合は，-n 回毎に，ファイルに追加形式（ append ）で出力されます．n が正の場合は，出力するたびに，出力を行うか否か，および，どこに出力するかを聞いてきます．したがって，この段階において，出力先をファイルに変更することも可能です（ n = 0 の場合も同様）．

出力方法(0:適応度＋順番，1:適応度)

　　結果の出力方法を入力します．

=0 : 経路長と巡回する都市の順番を出力します．

=1 : 得られた経路長だけを出力します．ただし，最終結果だけは，都市の順番も出力します．

出力ファイル名

　　結果を保存するファイル名です．

表示間隔

　　計算がどこまで進んでいるのかを示すため，結果の概略を画面に表示しますが，それを何世代毎に行うのかを入力します．

交叉方法

　　交叉方法を入力します．以下の方法から選択できます．内容の詳細については，クラス Species の対応するメンバー関数を参照してください．

=-1 : 交叉を使用しない

=0 : 親のコピー

=1 : 循環交叉

=2 : 部分的交叉

=3 : 順序交叉

=4 : 一様順序交叉

=5 : 一様位置交叉

=6 : エッジ組み替え交叉

=7 : サブツアー交叉

　　その他，このプログラムでは使用していませんが，クラス Species には以下の交叉方法も定義してあります．

多点交叉
一様交叉
平均化交叉

交叉確率

　　交叉確率を入力します．

点

　　多点交叉の場合は何点交叉かを（たとえば，1 点交叉の場合は 1 ），また，サブツアー交叉の場合は，1 つのペアーに対する交叉回数を入力します．それ以外の場合は，利用されません．

位置

　　多点交叉の場合だけに利用され，2 つの親の交叉点を同じにするか否かを示します．0 を入力すると同じ，また，1 を入力すると異なる交叉点が使われます．交叉点が異なる場合，子供の遺伝子長が可変になりますので，Species 記述ファイルにおいて遺伝子長を可変長にしておいてください（ TSP の場合はあり得ませんが）．

方法

　　このデータを含め以下，3 つのデータ（「ステップ」までのデータ）は，サブツアー以外の交叉において利用されます．まず，このデータは，交叉における親の選択方法を指定します．

=-1 : ランダムに選択

=0 : 適応度に比例した確率で選択

=1 : 最小値からの差（ただし，α以下の場合はα）に比例した確率で選択

=2 : 評価値に順位をつけ，適応度の値を減少率βで線形化し，その値に応じた確率で選択

バイアス

　　方法が 1 の場合はα，また，方法が 2 の場合は初期値

ステップ

　　方法が 2 の場合においてβ

突然変異方法

　　突然変異方法を入力します．以下の方法から選択できます．内容の詳細については，クラス Species の対応するメンバー関数を参照してください．

=-1 : 突然変異を使用しない

=0 : 移動

=1 : 逆位

=2 : スクランブル

=3 : 転座

　　その他，このプログラムでは使用していませんが，クラス Species には以下の突然変異方法も定義してあります．

対立遺伝子への置換
重複
摂動
挿入
削除

突然変異率

　　突然変異率を入力します

幅

　　突然変異方法が，スクランブル，転座，重複，挿入，および，削除であるとき利用され，突然変異を起こす幅（染色体の部分列であり，遺伝子長より短い必要がある）を入力します．0 を入力すると幅がランダムに決められます．

　　また，突然変異方法が摂動であるときは，摂動の確率分布を入力します．0 のときは正規分布，また，1 のときは一様分布となります．

平均

　　突然変異方法として摂動を使用するとき利用されます．正規分布の時は平均，また，一様分布の時は分布の下限を入力します．

標準偏差

　　突然変異方法として摂動を使用するとき利用されます．正規分布の時は標準偏差，また，一様分布の時は分布の上限を入力します．

エリート

　　このプログラムでは，エリート選択とルーレット選択を利用しています．つまり，エリート選択によってここで指定した数だけの個体を選択した後，残りをルーレット選択で選択します．

方法

　　ルーレット板の作成方法を入力します．

=-1 : ランダムに選択

=0 : 適応度に比例した確率で選択

=1 : 最小値からの差（ただし，α以下の場合はα）に比例した確率で選択

=2 : 評価値に順位をつけ，適応度の値を減少率βで線形化し，その値に応じた確率で選択

バイアス

　　方法が 1 の場合はα，また，方法が 2 の場合は初期値

ステップ

　　方法が 2 の場合においてβ

都市数

　　都市の数を入力します．Species 記述データで指定した最大遺伝子長と一致する必要があります．

最大世代交代数

　　最大世代交代数を入力します．

近傍探索(0:行わない，1:行う)

　　1 を入力すると，各世代の各個体に対して，逐次改善法により近似解を求めます．なお，この場合は，個体の重複を許すように設定しておいた方が安全だと思います（許さないようにすると，指定した集団サイズだけの個体が存在しなくなる可能性があります）．また，0 を入力すると近似解を求める操作を行いません．

近傍（2or3）と選択方法(0:最良，1:最初)

　　逐次改善法においては，λ近傍（λの値が近傍に対する入力値）に含まれる（λ本の）枝を入れ替えるという作業を距離の改善がなされなくなるまで続けることによって，解を求めます．各ステップにおいて，どのλ本の枝を入れ替えるかを探索していきますが，選択方法に 0 を入力すると，λ本の枝を入れ替えるすべての組み合わせの内，最も改善度が高いものを選択します．また，1 を入力すると，最初に見つかったλ本の枝をすぐ入れ替えます．通常，1 で良いと思います．

図示(0:しない，1:結果，2:初期状態と結果，3:ステップ)

　　Java においては，結果の図示が可能です．ここでは，結果を図示するか否かを入力します．ただし，図示しない場合においても，入力データの 5 行目は必ず記述してください．

=0 : 図示しない

=1 : 最終結果だけを図示

=2 : 初期状態と最終結果を図示

=3 : 初期状態，最終結果，および，出力レベルで指定した回数毎に中間結果を図示します．

都市番号

　　都市番号を表示する際，その字の大きさを入力します．0 を入力すると都市番号を表示しません．

図の大きさ（幅，高さ）

　　図の幅と高さの最大値を入力します．実際に表示される図の大きさは，これらの値と都市座標の分布状況によって，上下，左右の縮尺が等しくなるように決められます．

-58 37

55 -19

　･････

　　以下，各都市の x 座標と y 座標です．都市の数だけ必要になります．この入力された順番が，その都市の都市番号になります（ 0 から始まる）．

　　なお，Java において，結果を図示する場合，対応する図が表示される毎に，コマンドプロンプトの画面に

　　図を確認したらreturnキーを押してください

のようなメッセージが出力されますので，メッセージに従い return を押して継続してください．すべての処理が終了すると，return を押しても応答しなくなりますが，表示されている図を削除するとプログラムが終了します．

[関数の最大値]

　　この例の場合における Species 記述ファイルは，たとえば，以下のようになります．
対立遺伝子上限 1 対立遺伝子下限 0 最大遺伝子長 15 最小遺伝子長（負の時は，最大遺伝子長で固定） -1 遺伝子の重複 1 個体の重複（同じ染色体の個体） 0 集団サイズ 20 子供 20

　　データの意味は TSP の場合とほぼ同様ですので省略します．x の値が染色体に対応し，15 ビットのビット列で表現している点に注意してください．クラス TSP の代わりに，関数の最適値を求めるためのクラス Function （ PHP の場合はクラス Func ）を利用していますので，ケーススタディファイルにおいて，TSP 記述ファイル名の代わりに関数記述ファイル名を入力します．関数記述ファイルは，たとえば，以下のようになります．
出力レベル(負はファイル) 20 出力方法(0:すべて，1:最大) 0 出力ファイル名 result\kekka 表示間隔 1 交叉方法 1 交叉確率 1.0 点 2 位置 0 方法 1 バイアス 0 ステップ 1 突然変異方法 0 突然変異率 0.05 幅 1 平均 0.0 標準偏差 1.0 エリート 2 方法 1 バイアス 0 ステップ 1 最大世代交代数 200

　　データの意味については，TSP の場合とほぼ同様ですが，交叉方法および突然変異方法に対して選択できる方法が異なってきます．交叉方法に対しては，

=-1 : 交叉を使用しない
=0 : 親のコピー
=1 : 多点交叉
=2 : 一様交叉
=3 : 平均化交叉

の中から選択でき，また，突然変異に方法に対しては，

=-1 : 突然変異を使用しない
=0 : 対立遺伝子への置換
=1 : 移動
=2 : 逆位
=3 : スクランブル
=4 : 転座
=5 : 重複
=6 : 摂動

の中から選択できます．