すべての読者への挨拶。 今日は、自然なアルゴリズムに焦点を当てたかなり珍しい一連の記事を続けてみます。 特に、この記事では、Max-Min Ant System（MMAS）として知られるantアルゴリズムの変更に焦点を当てます。 従来のantアルゴリズムとの違いと、そのような変更を行う理由について説明します。 カットの下の詳細。
序文の代わりに
数年前、記事
「Ant Algorithms」がHabréで公開されました。これは、Dorigo（Dorigo）の元のantアルゴリズムを十分に詳細に説明しています。 アルゴリズムに慣れていない人のために、この記事を読むことをお勧めします。 次に、巡回セールスマン問題に対する約束されたMMASアルゴリズムについて少し説明します。
アイデア
MMASアルゴリズムは、ACOアルゴリズムに対する一種のアドオンです（Ant Colony Optimization、Dorigo and Stutzle、2004）。 ACOアルゴリズムによれば、蟻は独立したエージェントであり、蟻の経路（グラフの端）にあるフェロモンを介してのみ相互作用します。 最初の開始時に、最初の量のフェロモンが各エッジに適用され、アリがエッジを通過する頻度に応じて変化します。フェロモンの量は、式に従って変化します。
pはフェロモン蒸発係数、Fは最適なソリューションのコストの逆数です。 そして、実際には、アルゴリズムの修正：フェロモンの量はギャップにあります
。
さらに、アリに最も魅力のないvisit骨を訪問する機会を提供するために、古典的なアリアルゴリズムからの次の式が適用されます。
antアルゴリズムに精通している読者には、この式に新しいものはないはずですが、残りをもう一度送信して、古典的なアルゴリズム
に関する記事を読みます。
次に、DorigoとGambardellaによって提案された別の変更を追加しましょう（Dorigo and Gambardella、1997）。
ここでもう少し詳しく説明します。 より良いパスを維持するために、グラフでは「貪欲な」アリが使用されます。 アリの総数に占める割合は
qに等しく、つまり、アリが進む経路は式（3）によって決定されます。 アリがさらに進むピークは、その魅力が最大になるように、すべての隣接する非訪問ピークから選択されます。 したがって、0 <
q <1は、現在のアリが貪欲である確率であり、1-
qの確率では
、アリは標準的な方法で動作します。 係数
qは 、他のすべてと同様に、実験的に決定されます。
説明
アルゴリズム自体と同様に、フェロモン制限に関連する変更は、自然の自然法則に非常によく適合しています。 直観的に、実際の状態のフェロモンの量は絶えず成長することはできません。 ある時点で、フェロモンの蒸発速度はフェロモンのフットプリントの更新速度に等しく、フェロモンの量の変化率は一定ではありませんが、この関数を使用すると実行時間が大幅に増加するため、フェロモン量の最大値を単純に設定するのが最適です。 同様の状況は、フェロモンの量の低いバーです。 さらに、制限の値はアルゴリズムの効率に影響し、ご想像のとおり、実験的に選択されます。
ご清聴ありがとうございました。
文学
Dorigo M.、Stutzle T.（2004）Ant Colony Optimization。 MIT Press、ケンブリッジ、MA
Pellegrini P.、Stutzle T、およびBirattari M.（2011）アントコロニー最適化におけるパラメーター適応の重要な分析。 IRIDIA-テクニカルレポートシリーズ