3

アリコロニーアルゴリズムを開発しました。現時点ではかなりうまく機能しています。

いくつかの論点では、最良のパスではなく、最良のパスに近いものを示すことがあります。

たとえば、次のグラフがあります。

ここに画像の説明を入力

マトリックスは次のとおりです。

    1   2   3   4   5   6   7
1   0   6   5   0   0   2   0
2   6   0   3   2   1   5   0
3   5   3   0   2   5   0   0
4   0   2   2   0   3   0   0
5   0   1   5   3   0   6   0
6   2   5   0   0   6   0   2
7   0   0   0   0   0   2   0

最初の列と最初の行は頂点名です。

したがって、可能なパスは次のとおりです (パス - パスの長さ):

1. 1-2-5 with length 7
2. 1-6-2-5 with length 8
3. 1-6-5 with length 8

私のプログラムは、プログラムの 1/10 開始で 1 番目のパス、7/10 開始で 2 番目のパス、2/10 開始で 3 番目のパスを選択しています。

正しく動作していますか？

これについての説明は、アリには自分の目 (ビジョン、エッジの長さを見る) があり、フェロモン レベルを検出することもできます。自分の目で見ると、1-2 のエッジはかなり長く、1-6 のエッジよりも長いため、通常、1-2 を選択する代わりにエッジ 1-6 を選択します。6-5 と 6-2 も同様です。6-2 の方が短いので魅力的です。

私の仮定は正しいですか？

4

3 に答える 3

2

これによると: http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Summary、あなたのアプローチには2つの問題があります:

  1. アリは（最初は）ランダムにさまよいます。視界や隣接辺の長さとは関係ありません
  2. それらのフェロモン トレイルをまったくモデル化しますか?

質問への回答: アリのコロニー アルゴリズムは 100% の場合に最適なパスを表示する必要がありますか? いいえ、最適なパスを表示する必要はまったくありません。

于 2014-05-27T22:08:57.260 に答える
2

アリのコロニー最適化アルゴリズムでは、アリはグラフを歩いている間、考えられる各ステップの確率を持っています。通常、この確率は 2 つの要因に基づいています。ローカルおよびグローバルな品質の尺度です。

フェロモンは、アリがたどるパスで使用される各エッジに追加され、追加された量は、そのようなアリによって作成されたソリューションの品質に何らかの形で関連するため、グローバルな測定値は通常、エッジのフェロモンの蓄積に関連付けられます。

ローカル測定値は、通常、特定のステップの品質に関連しています。提供されている例では、エッジのコストです。

したがって、アリが貪欲な行動しかしていない場合は、使用している確率関数が局所的な品質を重視しすぎている可能性があります。ローカル検索とグローバル検索の間の適切な妥協点を示す確率関数を見つけることは、ACO 戦略をうまく適用するための基本的な側面です。

于 2014-05-28T14:15:19.187 に答える
0

最短経路にアリのコロニーを使用するのはなぜですか? 最適化アルゴリズムを必要としない最短経路を検索する場合は、A* アルゴリズム (最適なヒューリスティック関数を使用) を使用した多項式時間で最適解が得られます。TSP の問題に使用する場合は、アリのコロニーの方が適しています。

答えは: いいえ - アルゴリズムは確率論的であるため、最適解ではなく極小値になる可能性があることに注意してください。

于 2014-05-29T09:07:16.760 に答える