私は、遺伝的アルゴリズム (GA) を使用して巡回セールスマン問題 (TSP) を解決するための小さな学術課題に取り組んでいます。私は、都市とツアーを配列に格納する非常に単純な古典的な表現に従っています。たとえば、10 都市のツアーは 9-1-0-4-3-8-6-5-2-7 のように表すことができます。GA のかなり基本的な知識があるので、TSP にさまざまなタイプのミューテーションを適用するためにどのようなアプローチに従うかについて、少し混乱しています。ルートが route として表され、突然変異率が変数 m_rate で表されているとしましょう。
[1] 単純挿入変異
1-2-3-4-5-6-7-8-9 があるとします。次に、たとえばインデックス 5 のランダムな都市を選択し、2 などのランダムな挿入インデックスを選択すると、突然変異した染色体は 1-2-6-3-4-5-7-8-9 になります。
ここで、突然変異を適用するために私がやっていることは次のとおりです。
for (int i=0; i<route.length; i++) {
if (m_rate<Math.random()) {
// Pick a random city
int randomCity = 0 + (int)(Math.random() * ( ((route.length-1) - 0) + 1));
// Do the insertion and shift the array where appropriate
}
}
つまり、ルート内のすべての都市をループして、突然変異条件 (m_rate>Math.random()) が成立するかどうかを確認します。成立する場合は、そのインデックスで停止し、次を使用せずに挿入ポイントをランダムに選択します。突然変異確率変数。配列の最後に到達しない限り、残りのすべての都市またはインデックスに同じことを適用し続けます。これは正しいアプローチですか？最初のミューテーションを適用したら、ループを停止または中断する必要がありますか? 挿入点の選択に突然変異確率を何らかの形で関与させる必要がありますか? それは私にはあまり意味がないように思えますが。染色体やルートに複数の都市が変異している可能性がある場合、染色体が再変異している可能性はありますか? 言い換えれば、2 番目または 3 番目の突然変異を行って、染色体を最初の形に反転させた場合 (突然変異前) はどうなるでしょうか?
[2] 相互交換突然変異。
染色体のランダムな都市を選択してから、2 つ目のランダムな都市を選択し、2 つを交換します。たとえば、ルート 1-5-2-8-0-9-3-7-4-6。最終的にインデックス 2 とインデックス 7 を選択すると、突然変異した染色体は 1-5-7-8-0-9-3-2-4-6 になります。
上記の挿入突然変異と同様のアプローチに従っています。ルート内のすべての都市をトラバースし、確率条件を確認してから、突然変異率を適用せずに交換するランダムな都市を直接選択します。上記と同じ種類の質問がここに適用されます..
[3] 反転突然変異。
これは最もトリッキーなものです。1-2-3-4-5-6-7-8-9 のような染色体が与えられた場合、インデックス 2 からインデックス 5 への突然変異カットを選択し、そのサブルートを逆にします ==> 1-2-6-5- 4-3-7-8-9。
しかし、これをどのように適用しますか？ルートをループしてから、突然変異率に基づいて都市を選択し、サブルートの長さを決定するために別のインデックスを直接選択しますか? 一度変更して終了しますか？この種の実装では、変異カットが 0-9 または 0-(length-1) になる場合、染色体全体またはルート全体を変異させて全体を反転させることはできますか? この場合、実際の突然変異率の値は? 私はここでちょっと迷っています...
これが長すぎることを前もってお詫びします..しかし、これらの問題に関するコメントをいただければ幸いです. 私は数多くの研究論文を見てきましたが、この種の詳細や詳細にアプローチしたものは多くありません。
ありがとうございました。