問題タブ [ant-colony]

私はアリのコロニー最適化アルゴリズムをやっています。いくつか質問があります。throw ant-colonyを検索しようとしましたが、何も見つかりませんでした。

1 — アルゴリズムの結果は?

いくつかのグラフがあり、開始点から目標点までの最適なパスを見つける必要がありますよね? このアルゴリズムは、ダイクストラ アルゴリズム (1 つの最短パスを見つける) のようには機能しません。そこには確率要素があります。10 サイクル後、5000 匹のアリが最悪の経路を選択できますが、それにもかかわらず、より良い経路のフェロモンは 1000 倍になります。つまり、4999 匹のアリが選択した(99% の確率)1 -> 3 -> 5という事実にもかかわらず、 5000 番目のアリがパスを選択できることを意味します(平均確率は 1%)。1 -> 2 -> 5あくまでも一例です。したがって、問題は、最も最適化された (最適な、いくつかのパラメーターで最適な) パスを検出する方法です。それを検出する必要がありますか、または1 -> 2 -> 5私の例では正しい結果 (起こります...) であり、最後に選択したパスを出力する必要がありますか?

2 — 結果の出力方法

この答えはおそらく最初の答えに依存します。どうやって？各サイクルの動作アルゴリズムとプロトコルの総まとめを出力する必要があると思います。

要約データは次のようになります。

プロトコルは次のとおりです。

助言がありますか？各反復の出力データを手伝ってください。

3 — フェロモン レベルは、特定の値に達すると成長を停止します

なぜそうなのですか？例えば（500匹のアリ）、ベストパス上のフェロモンレベルは検索（サイクル）の最大10ステップまで成長し、その後安定します。それは良い動作ですか、それとも私のアルゴリズムにエラーがあることを意味しますか? エラーがない場合、なぜこの動作が表示されるのですか?

4 — 私のプログラムのアーキテクチャ

onclickアルゴリズムの NEXT STEP (次のサイクル) を呼び出すハンドラを作成するのが良い方法だと思います。しばらくループしていた例を見ました（リンクを覚えていない、お見せできません:'(今）。私の方法は受け入れられますか、それともまったく間違っていますか？

アリのコロニー最適化問題のパフォーマンスを向上させようとしています。そのために、openCL を使用してフェロモンの更新部分を並行して実行しています。私はopenCLの学習を始めたばかりで、これが私が開発したカーネルコードです。シーケンシャル バージョンよりも高速に実行されますが、それでもパフォーマンスを向上できると思いますが、他にできることは見つかりません。このコードをさらに改善する方法はありますか?

PS: 私が作業しているコンピューターには GPU がないため、このコードは CPU でのみテストしました。

私はこの論文を理解しようとしており、ロボット ナビゲーション論文の改善されたアリのコロニー最適化のライブ実装を行っています。実装しようとしているときに、頭に浮かぶいくつかの質問がありました。

1. 著者は、負のフェロモンの蓄積について紹介しました（上記論文の 2 ページ 2 列目に記載）。しかし、それが何であるか、どこで使用されているかわかりませんでした! 紙の中では、それについてグーグルで検索しただけでなく、それについても話していません。それは何ですか、どこで使用しますか? フェロモンの付着と蒸発はすでに行っています。

2. ゴール シーク アルゴリズム (ページ 2) では、すべてのアリが次の位置に移動した後、および蒸発が実行された後に、フェロモンの堆積が行われます。ですから、その際、フェロモンの蓄積は、すべてのアリを繰り返し、現在の位置のフェロモン濃度を更新することによって行われますね。

3. その目標探索アルゴリズム (2 ページ目) で、著者は について語っていCheck if termination criteria metます。ということは、アリが目的地（目的地）に到達したかどうかを確認するということですか？その場合、実行を終了する必要があります。ではない？

4. それとは別に、私は彼が 2 ページの目標探索アルゴリズムの次の 3 行で何を意味しているのか理解できませんでした。

   • 壁からのアリの距離を制御する

   • バックトラッキングを防ぐ

   • 四角ループ防止

上記の論文の関連部分のスクリーンショットを含めました。

上記の質問をクリアしていただければ幸いです。

編集

これに対する応答がなかったので、ここで別の質問をしました: https://softwareengineering.stackexchange.com/questions/238639/ant-colony-optimization-movement-of-ants

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

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

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

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

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

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

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

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

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

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

巡回セールスマン問題 (TSP) と迷路解決問題を含むアルゴリズムを作成しています。基本的に、迷路内にはポイントがあり、それらすべてのポイントへの最適なパスを見つけて、最終的に迷路を出る必要があります。

ACO アルゴリズムを使用して、正常に機能する迷路の出口を見つけ始めました。しかし、TSP をそれに統合するにはどうすればよいでしょうか。

私たちの最初の推測は強化学習でしょう。何か案は？