熱力学的遺伝アルゴリズムモドキで巡回セールスマンを解いてみた

####モドキを作った理由
熱力学的遺伝アルゴリズムの計算コストを小さくしたかった。
親集団と子集団が同じ数でも世代交代に10秒ほど時間がかかり、
一様交叉と突然変異、淘汰のみの比較的シンプルなGAだと1秒で何世代も進む

####ソースコード
https://github.com/2a3oiUA3zfDtr3py/Misc/tree/master/GA_TSP
全ての乱数はrand()の代わりに/dev/urandomから取得

####アルゴリズム
遺伝子は都市の訪問順に記録する
評価関数をこんな感じにしたいため

距離 = 0;
for(i=0;i<(都市の数-1);i++)
{
  距離 += 都市と都市の距離を求める関数なり二次元配列なり(遺伝子[i+1],遺伝子[i]);
}
距離 += 都市と都市の距離(遺伝子[0],遺伝子[都市の数-1]);

これにより交叉や初期集団の生成に、同じ都市に2度行く遺伝子や一度も行かない都市がある様な遺伝子が発生しない様にする必要がある。

Step 1
温度Tに初期値T0を代入する
親集団のサイズを都市の数のα倍にする
子集団のサイズを親集団のβ倍にする
子集団と同じ数の初期集団をランダムに生成し子集団に入れる

Step2
親集団は空にしておく
二都市間の経路の出現回数を記録する領域を用意し0で初期化する

Step2-1
子集団の全ての個体のエントロピーモドキを計算する
エントロピーモドキの計算方法は
Pxは親集団における 二都市間の経路 xの出現回数
エントロピーモドキS = -log( (Px + 1) / 親集団のサイズ)

Step2-2
エントロピーモドキが大きい順に個体をγ個子集団から取り出し親集団に入れる

親集団が満たされるまで、Step2-1 Step2-2を繰り返す

Step3
親集団の移動距離を計算する
親集団の個体の順位を移動距離で決める

Step4 (子集団の生成)
Step4-1 (交叉)
ルーレット選択で親を二つ選ぶ
遺伝子と同じ長さの乱数を取得し2の剰余を計算する
それに基づいて片方の遺伝子を子の遺伝子にコピー
参考

for(i=0;i<遺伝子長;i++)
{
  if(乱数[i] % 2 == 0)
  {
    子遺伝子[i] = 親遺伝子[i]
  }
}

子遺伝子の残りをもう一方の親遺伝子から出現順序に基づいてコピー
ただしすでに子遺伝子に有るものはスキップ

Step4-2 (突然変異)
適当な乱数に基づいて確率δの割合で
生成された子遺伝子の一部の訪問順序を逆にし
確率εの割合で生成された子遺伝子の一部の訪問順序をデタラメに並べ替える

Step4-1 Step4-2を子集団が満たされるまで繰り返す

Step5
親集団は空にしておく
二都市間の経路の出現回数を記録する領域を用意し0で初期化する
Step5-1
Step2-1と同様に子集団のエントロピーモドキSを計算し
子集団の各個体の移動距離Dを計算する
そして全ての個体の
自由エネルギーモドキF = D - T*S
を計算する

Step5-2
自由エネルギーモドキが小さい順に個体をγ個子集団から取り出し親集団に入れる

親集団が満たされるまで、Step5-1 Step5-2を繰り返す

Step6
温度Tを更新する
T = T * ζ

Step7
終了条件を判定する
終わっていないならStep3へ

####結果
2次元空間上に配置した100都市では、貪欲法+2-OPTより良い結果になる。
2次元空間上に配置した500都市では、貪欲法+2-OPTより悪い結果になる。
8次元空間上に配置した200都市では、貪欲法+2-OPTより悪い結果になる。

2次元空間上に配置した100都市で温度を常に0にして通常の遺伝アルゴリズムとして動作させても上手いこと行かなかった事を考えると
多様性の維持に成功しているっぽい？

そしてモドキでは無い熱力学的遺伝アルゴリズムを2時間かけて1回だけ回した結果は貪欲法よりマシで貪欲法+2optより悪い

####改良
モドキの改良によって上手いこと探索できる確率が上がった

t2 = parent_distance[0];
while(1)
    {
        sort(index,parent_distance,num_parent);//Step3
        evaluate_entropy(parent_gene,&t1,num_parent);//親集団のエントロピーを取得
        printf("%f\n",t1);
        if(Entropy < t1)
        {
            Entropy = t1;
        }
        Entropy *= 0.999;
        if(Entropy * 0.8 > t1)
        {
            Temperature *= 1.05;
        }
        else if(t2 - 0.001 >= parent_distance[index[0]])
        {
            Temperature *= 0.99;
        }
        else
        {
            Temperature *= 1.005;
        }
//Step4以後が続く

Step7を消してStep3の後に温度を動的に決める仕組みを組み込んだら貪欲法より悪い答えになる確率が下がった