私は遺伝的アルゴリズムを学び、巡回セールスマン問題の練習をしています。
GAが実際に何ができると期待すべきか疑問に思っています。
私はここで15都市と48都市の問題を試しましたTSPサンプル問題
私のGAは、15都市の問題の正確な解決策を非常に迅速に見つけます。しかし、それは48都市の問題に苦しんでいます。人口規模の子供の数についてさまざまな仕様を試しましたが、結果はおおよそ次のようになります。
正しいソリューションの最小距離：33,551
私のGAソリューションの距離：〜39,000
ランダムルート距離：〜140,000
GAが正確な解決策を提供することは保証されていませんが、基本的に起こっていることである、近い解決策のみを提供することを理解しています。
私の質問は次のとおりです。私は48の都市の問題について、GAアルゴリズムで問題がないのか、それとも何か間違ったことをしていて、GAにいくつかの大きな改善が必要なのか。
前もって感謝します
都市の数が多いほど、問題は難しくなります。これは、検索スペースが大きいだけでなく、通常、コスト関数がより複雑になるためです。
ヒューリスティックがどれだけうまく機能するかを言うのは（不可能ではないにしても）常に難しいですが（GAだけでなく、すべてのGA）、16％オフはかなりのように思えます。演算子を変更してパラメータを少しいじると、パフォーマンスが向上する可能性があると思います。
すべてのオペレーターには、結果に関する制限と期待があります。たとえば、クロスオーバー演算子（以前の投稿で述べたように）は、同じサブパスを持つ染色体の数を増やす傾向があり、遺伝的収束につながります。使用した突然変異演算子は、最も攻撃的なものの1つではありません。エルゴ、他の演算子を使用して、パフォーマンスが向上するかどうかを確認することをお勧めします。以前の回答にあるすべての参照を使用して、それらを適切に理解できます。理解すれば簡単なので、実装はそれほど難しくありません。
絶対に改善できると思います。できれば 5% 以下の誤差を目指します~1%。