アリコロニーアルゴリズムの理論と実践ガイド

[[170615]]

数年前、私が修士号を取得するために勉強していたとき、大学にアリコロニーアルゴリズムを専門とする教授がいました。彼はとても優秀で、私は時々彼について少しずつ学んでいました。感覚も生物学的知能の現れであり、遺伝的アルゴリズムやニューラル ネットワークに似ています。ただ、当時は実際に学ぶ必要がなかったので、勉強しませんでした。最近このような課題があったので、基礎をしっかり勉強し、明確な目標を持って意欲的に学習したので、比較的早く受け入れて理解することができ、あとは実装するためのコードを書いただけです。今日は、TSP 問題とアリコロニーアルゴリズムについて詳しく説明します。

1. 巡回セールスマン問題（TSP）とその派生問題

巡回セールスマン問題 (TSP) は、配車経路問題 (VRP) の特殊なケースです。数学者は TSP 問題が NP 困難問題であることを証明しているため、VRP も NP 困難問題です。巡回セールスマン問題 (TSP) は、巡回セールスマン問題または行商人問題とも呼ばれ、最も基本的な経路問題です。この問題は、1 人の旅行者が出発点から出発し、指定されたすべての需要地点を通過して出発点に戻るまでの最小経路コストを求めます。 ——巡回セールスマン問題事典

もちろん、ノードの数が少ない場合、ほとんどの人は問題は単純で網羅的な列挙によって解決できると考えますが、実際の問題ではノードの数が多く、それが不可能になることがよくあります。たとえば、16 都市のみを対象とする巡回セールスマン問題の場合、網羅的方法を使用して問題の最適解を見つけると、比較する必要がある実行可能な解は次のようになります。15!/2=653,837,184,000。 1993 年、当時のワークステーションを使用して総当たり方式でこの問題を解決するのに 92 時間を要しました。今ではコンピューターは高速化していますが、複雑な問題に直面するとまだ十分ではありません。これはいわゆる「組み合わせ爆発」、つまり指数関数的な成長であり、科学者は、妥当な時間枠内で許容可能な最適解を見つけることを目標に、徐々に近似アルゴリズムまたはヒューリスティックアルゴリズムを探し求めています。

TSP 問題解決アルゴリズムの開発は、次の 3 つの部分に分けられます。

1). 古典的な厳密なアルゴリズム: 網羅的方法、線形計画法アルゴリズム、動的計画法アルゴリズム、分岐限定アルゴリズムなど、オペレーションズ リサーチにおける従来のアルゴリズム。これらのアルゴリズムは一般に非常に複雑で、小規模な問題を解決するのにのみ適しています。

2). 近似アルゴリズム: 問題の規模が大きい場合、必要な時間は指数関数的に増加しますが、これは受け入れられません。アルゴリズムによって解決される問題の規模は大きく制限されます。自然なアイデアは、正確なソリューションの精度を犠牲にして、許容できる適切な時間計算量と許容できるソリューション品質を備えたアルゴリズムを見つけることです。このアイデアに基づいて設計されたアルゴリズムは、総称して近似アルゴリズムと呼ばれます。挿入アルゴリズム、最近傍アルゴリズムなど。

3) インテリジェントアルゴリズム: 科学技術と生産の継続的な発展により、多くの実用的な問題では合理的な時間枠内で全体的な最適解を見つけることができなくなり、現代の最適な問題解決方法の出現が促されました。タブー探索、遺伝的アルゴリズム、シミュレーテッドアニーリングアルゴリズム、人工ニューラルネットワーク、進化戦略、進化プログラミング、粒子群最適化アルゴリズム、蟻コロニー最適化アルゴリズム、免疫コンピューティングなど、さまざまな探索メカニズムを備えたヒューリスティックアルゴリズムの出現により、ヒューリスティックアルゴリズムの研究が最高潮に達しました。

各アルゴリズムの詳細については説明しません。詳細については、関連情報を参照してください。

実際の生産現場では、TSP 問題にはさまざまな実際の環境に起因する多くの派生した古典的な問題があります。車両ルーティング問題 (VRP) は、従来の VRP にさまざまな制約を追加することによって形成されます。例えば、需要制約によるランダム需要の配車問題（SVRP）、時間制約による時間ウィンドウ付き配車問題（VRPTW）、距離制約による距離制約付き配車問題（DVRP）があり、他の条件に応じて、複数の配送センターを持つ配車問題（MDVRP）と分割可能な配車問題（SDVRP）、最初に配達して後で回収する配車問題（VRPB）、配送と回収を行う配車問題（VRPPD）、不完全情報によるファジー配車問題（FVRP）もあります[3]。

2. アリコロニーアルゴリズムの基本原理

2.1 アルゴリズムの概要

VRP 問題の場合、解決アルゴリズムは、正確なアルゴリズムと人工知能アルゴリズムの 2 つのカテゴリに大まかに分けられます。精度アルゴリズムは厳密な数学的手法に基づいており、解決できる場合のソリューションの品質は良好です。しかし、アルゴリズムの厳密さと計算量の大きさのため、大規模な問題を解決することはほぼ不可能です。したがって、その適用範囲は小規模な決定論的問題に限られます。小規模および中規模の問題に直面した場合、人工知能アルゴリズムは精度の点で優位性がありません。しかし、規模が大きくなると、人工知能の手法では基本的に許容できる時間内に許容できる満足のいく解決策を見つけることができますが、これは精密なアルゴリズムでは難しいことです。実際の問題におけるさまざまな制約の複雑さにより、人工知能アルゴリズムは大きな優位性を示しています。まさにこのため、人工知能アルゴリズムは実際のアプリケーションでより広く使用されています。車両経路計画問題を解決するための正確なアルゴリズムには、動的計画法と分岐限定法が含まれます。そして、大規模な実用的な問題に対処するために、許容できる結果をもたらすヒューリスティック アルゴリズムの模索が始まりました。タブー検索アルゴリズム、遺伝的アルゴリズム、人工ニューラル ネットワーク アルゴリズム、そして現在さらに研究が進められているアント コロニー アルゴリズムなど、他の分野からの新世代の最適化アルゴリズムが次々と登場しました。

2.2 アリコロニーアルゴリズムの原理

アリのコロニー アルゴリズムは、実際のアリのコロニーの採餌行動の研究からヒントを得ました。生物学的研究によれば、協力して働くアリの群れは餌と巣の間の最短経路を見つけることができますが、単独のアリでは見つけることができません。生物学者は、多くの注意深い観察と研究を経て、個々のアリの行動が相互作用し、影響し合っていることを発見しました。アリは移動するとき、通った道にフェロモンと呼ばれる物質を残すことがあります。この物質こそが、個々のアリ間の情報伝達やコミュニケーションの媒体なのです。アリは移動するときにこの物質を感知し、それに沿って這うことに慣れており、もちろん這う過程でフェロモンも放出します。経路上のフェロモントレイルが太いほど、他のアリがその経路に沿って移動する可能性が高くなり、経路上のフェロモントレイルが強化されます。したがって、多数のアリで構成されるアリコロニーの集団行動は、正のフィードバック現象を示します。ある道を歩くアリの数が増えるほど、後から来たアリがその道を選ぶ可能性が高くなります。この間接的なコミュニケーションメカニズムを通じて、アリは協力して最短経路を探すという目標を達成します。アリの採餌行動を説明するために例を見てみましょう。

上記の a、b、c の概略図に示すように、

図 a は元の状態です。アリはポイント A から出発します。E に到達するには、途中に障害物があり、目的地に到達するにはそれらを迂回する必要があります。 BC と BH は、障害物を迂回する 2 つのパスです (2 つしかないと仮定)。各パスの距離 d は調整されています。

図 b は、各エッジのフェロモン濃度が等しく、15 であると仮定した場合の、時刻 t = 0 におけるアリの状態を示しています。

図 c は、時刻 t=1 でアリが通過した後の状態を示しています。多数のアリの選択確率が異なるため、各エッジのフェロモン濃度が変化し、選択確率は経路の長さに関係しています。したがって、より短い経路の集中度はますます高くなり、他の経路よりもこの短い経路を通って目的地に到達するアリの数が多くなります。多数のアリがこのように練習すると、最短経路が見つかります。したがって、このプロセスの本質は次のように要約できます。

1. 経路確率選択メカニズム フェロモンの痕跡が濃いほど、選択される確率が高くなります。

2. フェロモン更新メカニズムの経路が短いほど、経路上のフェロモン痕跡は速く成長します。

3. 共同作業メカニズム: 個々のアリはフェロモンを通じて情報を交換します。

アリの採餌の原理から、一個体の行動は非常に単純であることがわかります。アリはフェロモンをたどって這い、フェロモンを放出する方法しか知りませんが、組み合わせた後の集団知能は非常に高いです。アリのコロニーは、複雑な地理的分布条件下でも、アリの巣と食料源の間の最短経路を簡単に見つけることができます。この特性は、メタヒューリスティックアルゴリズムの特性と完全に一致しています。アリコロニー最適化アルゴリズムは、この生態学的現象にヒントを得て、模倣して改良されました。採餌アリは人工アリに置き換えられ、アリが放出するフェロモンは人工フェロモンに変わります。アリの這い回りとフェロモンの蒸発は連続的ではなく、離散的な時間と空間で発生します。

上記の例が理解しにくい場合は、ここにいくつかの PPT を投稿します。個人的にはとても良いと思います。また、多くの情報も見つかりましたが、最も理解しやすいと思います [ソースは大連理工大学の Gu Junfeng です]。次のセクションのダウンロード リンクを参照してください。

より深い意味では、最適化手法の 1 つであるアリコロニーアルゴリズムは、人工群知能の分野に属します。人工群知能は、主に昆虫の群れや動物の群れなどの自然の群知能からヒントを得ています。独自の強力な共同検索機能に加えて、一連のコンピューティング エージェントを使用して問題に対して分散処理を実行することもできるため、検索効率が大幅に向上します。

3. アリコロニーアルゴリズムの基本プロセス

私たちは、大連理工大学の顧俊鋒の PPT を使用して問題を説明したり、スクリーンショットを撮って重要な数式を計算して説明したり、PPT で理解しにくい部分を個別に説明したりしています。

3.1 基本的な数学モデル

まず、基本的な TSP 問題の基本的な数学モデルを見てみましょう。

問題は実はとても単純です。目的関数は、通過する各パスの合計長さです。距離行列の長さは実際の問題によって異なることに注意してください。

3.2 蟻コロニーアルゴリズムの説明

アリコロニーアルゴリズムのプロセスを説明する前に、アルゴリズムの原理と注意すべきいくつかの点について説明します。

1. TSP 問題に対する人工アリコロニーアルゴリズムでは、m 個のアリがグラフ内の隣接するノード間を移動し、それによって協力して非同期的に問題の解決策を取得すると想定されます。各アリのワンステップ転送の確率は、グラフの各エッジ上の 2 種類のパラメータによって決まります。1. フェロモン値 (フェロモン トレースとも呼ばれます)。 2. 可視性、つまり事前の値。

2. フェロモンを更新する方法は 2 つあります。1 つは揮発です。つまり、すべてのパス上のフェロモンが一定の割合で減少し、自然のアリのコロニーで時間の経過とともにフェロモンが揮発するプロセスをシミュレートします。もう 1 つは強化です。これは、「良い」評価値を持つエッジ (アリが歩いたエッジ) にフェロモンを追加します。

3. アリの次のターゲットへの移動はランダム原理によって実現されます。つまり、現在のノードに保存されている情報を使用して、次のノードに到達する確率を計算し、この確率に従って 1 ステップの移動が実現され、このプロセスが何度も繰り返され、最適なソリューションにどんどん近づきます。

4. 検索プロセス中、または解決策を見つけた後、アリは解決策または解決策の一部の最適化度を評価し、関連する接続のフェロモンに評価情報を保存します。

3.3 アリコロニーアルゴリズムのコアステップ

これまでの原則と上記の説明によれば、アリコロニーアルゴリズムの 2 つのコアステップは、パスの構築とフェロモンの更新です。ここでは、これら 2 つのステップについて重点的に説明します。

3.3.1 パスの構築

各アリは開始都市としてランダムに都市を選択し、アリが順番に通過する都市を格納するパス メモリ ベクトルを維持します。道を構築する各ステップで、アリはランダムな比例ルールに従って次に到達する都市を選択します。ランダム確率は次の式に従って計算されます。

上記の式は、現在のポイントから各可能な次のノードまでの確率を​​計算するものです。分子はフェロモンの強度と視認性の積を累乗したもので、分母はすべての分子の合計です。最初は理解しにくいですが、実際の例を計算すると非常に明確にわかり、逆に式を理解できるようになります。ノードを選択するたびに、選択したノードを使用可能なノードから削除する必要があることに注意してください。

3.3.2 フェロモンアップデート

フェロモンの更新は、アリコロニーアルゴリズムの中核です。これはアルゴリズム全体の中核でもあります。このアルゴリズムでは、初期期間の濃度値が固定されています。各反復の後、外に出たすべてのアリが戻ってきて、通ったルートを計算し、対応するエッジのフェロモン濃度を更新します。明らかに、この値はアリが移動した距離に関連しているはずです。繰り返し反復すると、短距離の線の集中度が非常に高くなり、おおよその最適解が得られます。それでは、フェロモンの更新のプロセスを見てみましょう。

フェロモン濃度C(0)を初期化します。小さすぎると、アルゴリズムが早期に成熟しやすくなり、アリはすぐに局所的な最適経路に集まります。ご想像のとおり、C値が小さすぎると、各揮発と増強の値が似通ってしまいます。その後、ランダムな状況下では、いくつかの小さな確率イベントによって、最適でない経路のフェロモン濃度が上昇します。Cが大きすぎると、探索方向におけるフェロモンの誘導役割が低下し、アルゴリズムのパフォーマンスに影響します。一般的に、貪欲アルゴリズムを使用してパス値 Cnn を取得し、アリの数に基づいて C(0) = m/Cnn を計算します。ここで、m はアリの数です。

各ラウンドの終了後、問題空間内のすべてのパス上のフェロモンが蒸発します。その後、すべてのアリは、構築したパスの長さに応じて、このラウンドで通過するエッジ上にフェロモンを放出します。式は次のとおりです。

フェロモン更新の役割：

1. フェロモン蒸発：フェロモン痕跡の蒸発プロセスは、各接続上のフェロモン痕跡の濃度が自動的に徐々に減少するプロセスです。この蒸発プロセスは主に、アルゴリズムがローカル最適領域に急速に集中するのを防ぐために使用され、検索領域を拡大するのに役立ちます。

2. フェロモン強化 強化プロセスは、アリコロニー最適化アルゴリズムのオプション部分であり、オフライン更新方式と呼ばれます (オンライン更新方式もあります)。このアプローチにより、個々のアリでは実現できない集中的なアクションが可能になります。基本的なアリコロニーアルゴリズムのオフライン更新方法は、アリコロニー内のすべての m 個のアリが n 個の都市の訪問を完了した後に、残差情報を均一に更新することです。

3.3.3 反復と停止 反復と停止の条件は、適切な回数の反復後に停止して最適なパスを出力するか、指定された最適な条件が満たされているかどうかを確認し、満足のいく解決策が見つかった後に停止するかのいずれかです。最も重要なことは、私がこのアルゴリズムを理解し始めた当初、アリがエッジを歩くたびに反復が行われると考えていたが、これは実際には間違っていたということです。ここでのアルゴリズムの各反復の重要性は、各反復における m 個のアリが独自のパス プロセスを完了し、原点に戻ることです。

4. 蟻コロニーアルゴリズムの計算例

PPT のケースを使用すると、非常に直感的です。主に確率計算の乗算記号など、いくつかの記号エラーが修正され、結果は正しくなりました。

全体的なプロセスは比較的簡単です。数式を理解することに注意し、数式を例と組み合わせます。最も良い方法は、ペンで手で描くことです。これは理解しやすいです。次に、TSP 問題のアリコロニーアルゴリズム コードをプログラムする方法を見てみましょう。

5. TSP 問題に対する Ant Colony アルゴリズムの C# コード実装

Baidu で検索した蟻コロニーアルゴリズム関連のコードは基本的にすべて Matlab です。 CSDN に asp.net + C# バージョンの実装がありますが、それを読んで、カプセル化が完璧ではなく、アイデアが明確でなかったため、思い切って書き直すことにしました。それで、執筆の過程でより明確に理解できました。簡単な変更を加えた後、今のところは問題ありません。もちろん、今後も研究を続けるつもりなので、まずは基本的なプログラム プロセスを書き留めておきます。もちろん、C# のオブジェクト指向機能を使用します。他の人が書いた完全なプロセス指向のプログラムを理解するのは本当に困難です。実装プロセスとコードについて簡単に説明します。

5.1 蟻コロニーアルゴリズムシステム基本クラス

基本的な BaseTspAntSystem クラスをカプセル化しました。このクラスにはいくつかの基本的なプロパティと計算プロセスが含まれており、後続の改良バージョンではこれを直接継承できます。もちろん、デザインに欠陥がある可能性もありますので、まずはこのように進めて、要望があれば変更してください。 BaseTspAntSystem クラスの主なプロパティは次のとおりです。

基本クラスにはコンストラクタがあります。システムの初期化では、基本パラメータを渡し、関連するリストを初期化します。コードは次のとおりです。

核となるのは解決プロセスであり、必要な反復回数に応じて完全に反復されます。プロセスは確率的選択とフェロモン更新です。プログラムをより独立させ、理解しやすくするために、補助として Ant クラスを使用します。 Ant クラスには、Ant パス検索プロセスに関するすべての情報が含まれています。これについては次のセクションで紹介します。解決プロセスのコードは次のとおりです。コメントと比較アルゴリズムを参照してください。

5.2 Ant関数クラス

アルゴリズムの説明によると、m 匹のアリが同時に独自の作業とルートの検索を実行します。これは並列プロセスです。したがって、単一のプロセスでは、アリは独立しています。 ant の各反復のプロセスは比較的明確です。パスを見つけるプロセスでは、利用可能なノードのリストを維持し、最後のパスを処理することに注意を払います。 Ant クラスの主なプロパティとコンストラクターを見てみましょう。

Ant クラスの核となるのは、次の都市ノードを見つけて、すべてのパスが完了するまでループするプロセスです。次のコードは循環プロセスです。

GetNextCityByRandValue 関数は、選択するノードを決定するためにランダムな確率値を選択する補助関数です。

6. リソースと参考文献

[1] NP問題とは何か？ http://blog.csdn.net/yangtrees/article/details/8107563

[2] ウェン・ヨンジュン「巡回セールスマン問題に対する2つのインテリジェントアルゴリズム[M]」西安電電大学、2010年

[3] 楊瑞塵「時間枠と優先順位制約による車両経路問題の蟻コロニー最適化[M]」西安建築技術大学、2005年。

[4] 顧俊鋒「インテリジェントアルゴリズム - 第7章：アリコロニーアルゴリズム PPT」大連理工大学、ダウンロードアドレス：http://files.cnblogs.com/files/asxinyu/%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95%E5%9F%BA%E6%9C%AC%E7%9F%A5%E8%AF%86.rar