最初の記事を読んでいない人は、それが続きであり、決して独立した記事ではないので、それを読むことをお勧めします。
1.Antアルゴリズム、別名Ant Colony Optimization（ACO）
このアルゴリズムのアイデアは、1992年にこのアルゴリズムを提案したMarco Dorigoが最初に思いつきました。
このアルゴリズムは、メタヒューリスティック最適化と呼ばれます。
アルゴリズムのアイデア
幼少期にアリを見ましたか？ まあ、少なくとも一度は？ アリは通常、食べ物に行きます。 遠い。 しかし、彼らはどのように食べ物をどこに行けばいいのでしょうか？ 結局、昨日どこかでアリ（リンゴなど）が見つかった場合、毎回再度検索することは有益ではありません。 リンゴを見つけたアリは、家に帰る途中でフェロモンで道路をマークします。 だから、少しだけ、彼はただ一人です。 翌日、n匹のアリがそこに行き、誰もが食べ物を見つけ、道をマークします。 トラックにはより多くのフェロモンがあり、次のアリがそれに沿って移動する可能性が増加していますが、フェロモンは蒸発し、数日後にはトラックに痕跡が残りません。そして、トラックが長くなるほど、速く崩壊します。 この事実に基づいて、このアルゴリズムはアリの生活から構築されています。
単位時間あたりの最短経路に沿ってより多くのアリが走り、最終的には他のすべてのフェロモンが蒸発するという事実の例ですが、これではコロニー全体の経路になります。
これを巡回セールスマンの問題に適用する方法は？
最初の記事で説明したブランチアンドバウンドメソッドを使用して、次の変更を行います。
1）選択ツリーでエッジを取得する/取得しない場合、パスの1つに沿って、ルートからこの頂点までのパスに特定の数のフェロモンを「配置」します。
2）各エッジで、このエッジを通るすべてのパスのフェロモンが加算されます。
3）アルゴリズムの各反復で、各パスのフェロモンの数は特定の割合で減少します。
4）次のピークを選択するとき、コストの見積もりだけでなく、その途中のフェロモンの数によってもガイドされます。
このアルゴリズムは、大きなグラフでのハミルトニアンサイクルの正値に対して最も効果的な多項式アルゴリズムの1つと見なされます。
枝と境界線の書かれた方法があるので、アリのコロニーの最も単純なバージョンをそれに固定するのは非常に簡単です。難易度は、蒸発率、合格した場合に入れるフェロモンの数などの定数の正しい選択にあります
欲張りからの利益は〜17％で、作業時間は約1時間です。
遺伝的アルゴリズム
アルゴリズムのアイデア
このアルゴリズムのアイデアの主な源は、生物学的進化です。
このアルゴリズムの主な重点は、いわゆるクロスオーバー演算子に置かれています。これは、候補解の再結合を生成します。
1）主な要件は、ソリューションを何か（ビット、数字、記号）のベクトルとして保存することです
この問題では、このi番目のセルから移動する頂点の番号をi番目のセルに格納します。
2）交配のためのソリューションから選択する新しいソリューションは、古いソリューションとクロスの突然変異の結果として受け取られます。
3）突然変異は、一部の遺伝子（この例ではアレイ細胞）をランダムに変更する関数として定義され、結果は多くのソリューションに組み込まれています。
4）交配は、前の反復からのいくつかの最良の解の遺伝子の組み合わせ（ランダム）として定義されます。
5）各段階で、不適切な解決策-些細なハミルトニアンサイクルではない解決策をスローする必要があります（たとえば、サイズ250の2つのサイクルが含まれています）。
6）突然変異の解は、ある程度の確率でランダムに選択されます。
7）異種交配の解は再びランダムに選択されますが、この反復で得られた最良の解（サイクルの重みがより小さい）がより高い可能性があります。
各段階で記憶に不満を感じている場合は、適応した最悪の解決策を捨てることができます。
このようなアルゴリズムを実行する最も簡単な方法は、最初にいくつかの正しい解決策を提供することです。たとえば、異なる頂点から走っている貪欲な女性によって私たちに与えられます。
停止状態-アルゴリズムのいくつかのパラメーター。カウントを終了する時間であり、答えを表示する必要があることを示します（現時点での最良の解決策）
私の場合、停止パラメーターは時間制限でした。
最も単純な実装は2時間で機能し、貪欲な人からわずか4％しか勝ちません
これは主に最も単純な実装によるものであることに注意する価値があります。多くの情報源は、遺伝的アルゴリズムが最良ではないとしても最高の1つであると主張しています。
これには多くの問題があります。 情報源の半分は、記録保持者が現時点でACOであると言い、半分はその遺伝学です。
ps継続は主に最初の記事へのコメントのおかげで書かれました。これは、少なくともこれらのアルゴリズムの最も単純な実装を書くことを奨励しました。