問題タブ [ant-colony]

私は、さまざまなタイプのアルゴリズムを最適化するためのヒューリスティックなアプローチとして「アリのコロニー」モデルを使用することについて、あちこちで読んでいます。ただし、アリのコロニーの最適化について入門的な方法で、または詳細に説明している記事や本をまだ見つけていません。このアイデアについて詳しく学べるリソースを誰か教えてもらえますか?

アリ コロニーの最適化を実装する .NET クラス ライブラリまたは .NET フレームワークを探しています。このトピックに関するリンク、リソースなどを教えてください。

だから私はヒューリスティックアルゴリズムを実装しています、そして私はこの関数に出くわしました。

私は1からnの配列を持っています（Cでは0からn-1、w / e）。別の配列にコピーする要素の数を選択したいと思います。パラメータy（0 <y <= 1）が与えられた場合、平均が（y * n）である数の分布が必要です。つまり、この関数を呼び出すと、0からnまでの数値が返され、これらの数値の平均はy*nになります。

著者によると、「l」は乱数です：0<l<n。私のテストコードでは、現在生成されている0 <= l<=nです。そして、私は正しいコードを持っていました、しかし私は今何時間もこれをいじっています、そして私はそれを元に戻すのが面倒です。

そこで、関数の最初の部分をコーディングしました。y<= 0.5の場合、yを0.2に設定し、nを100に設定しました。つまり、0から99までの数値、平均20を返す必要がありました。結果はその間にありません。 0とnですが、一部は変動します。そして、nが大きいほど、このフロートは小さくなります。

これはCテストコードです。「x」は「l」パラメータです。

そして、ここにいくつかの結果があります（小数点以下5桁が切り捨てられます）：

記事は次のとおりです。

http://www.scribd.com/doc/3097936/cAS-The-Cunning-Ant-System

6ページと7ページ。

またはグーグルで「cAS：狡猾なアリシステム」を検索してください。

だから私は何が間違っているのですか？これと同じ機能を説明している論文が5つ以上あるので、著者が間違っているとは思いません。

私を助けてくれる人への私のすべてのインターネット。これは私の仕事にとって重要です。

ありがとう ：）

だから私は最近、アルゴリズム全般にとても興味を持っています。そして、私は最近、TSP を解決するためにアリのコロニー最適化アルゴリズムを実装しました (明らかにとても楽しいです)。今、私は解決すべき他の「問題」を見てきました。ここで、パーセンテージ要件を満たすことを含む問題を解決し、任意の制限を下回るアルゴリズムを実装したいと考えました。

例えば：

ユーザー入力:

1) 制限 - つまり、消費できるエネルギーの量。

2) 「染色体」タイプ - すなわち、青 (サブタイプ - インディゴなど)、赤 (サブタイプ - 栗色など)、黄色 (サブタイプ - ライトイエローなど) - 青のような各主要属性には、選択する「プール」があります。インディゴ、ライトブルー、シーブルーなど、さまざまなサブタイプで構成されています。-色の各サブタイプには、それに関連するさまざまなコストがあります。

3) 「理想的な」ソリューションに必要なタイプのパーセンテージ (より多くの多様性を可能にするために +/- % を導入できます)。- つまり、赤 10%、青 30%、黄 60% です。

出力：

1) 2 つの要件を満たし、必要なコストを下回っていますが、それに近く、スーパータイプのパーセンテージ要件を満たす可能な最終ソリューション。

たとえば。

これは非常に単純な例ですが、実際にはこれよりも複雑になることは明らかです。

ユーザーは、95 <= cost <= 105 のようにコストを指定します。

ユーザーは、青 25%、黄 25%、赤 50% を選択します。+/- 5% の偏差で

各色の利用可能なプール

青: 藍色: コスト = 25; 海の青: コスト = 30; ネイビー ブルー: コスト = 75;

黄色: 薄黄色: コスト = 20; 濃い黄色: コスト = 30; 超濃い黄色(笑): cost = 75;

赤: あずき色: コスト = 20; ブラッドレッド: コスト = 45; 明るい赤: コスト = 55;

したがって、アルゴリズムが実行され、さまざまな組み合わせが返されます。

組み合わせ 1: インディゴ、ダーク イエロー、ブラッド レッド: コスト = 100: ブルー = 25%、イエロー = 30%、レッド = 55%。

組み合わせ 2: 海の青、薄黄色、血の赤: コスト = 105: 青 = ~30%、黄 = ~20%、赤 = ~50%

組み合わせ 3: などなど。

編集: 2 番目の編集

出力は、さまざまな組み合わせのセットで構成されます。

たとえば、1 つのソリューションは次のような組み合わせで構成される場合があります。

1 つの解決策は次のように表されます。

組み合わせ 1: コスト = 20; 青 50%、黄 25%、赤 25%。

組み合わせ 2: コスト = 30; 青 10%、黄 50%、赤 40%。

組み合わせ 3: コスト = 50; 青 25%、黄 25%、赤 50%。

解決策: = (組み合わせ 1、組み合わせ 2、組み合わせ 3) 総コスト = 100 で、x% 青、y% 黄色、z% 赤で構成されます。

ソリューションを要件と比較し、近い場合は保持し、そうでない場合は破棄します。

編集終了

だから私の質問はです。遺伝的アルゴリズムが機能することはわかっています。しかし、ACO の実装も同様に機能するでしょうか? たとえば、青、黄、赤は「場所」に相当し、それらのサブタイプは異なる「道路」を表します。

より効率的なソリューション、またはまったく異なるアルゴリズムが何であるかを考えてみてください。私はこのことにかなり慣れていないので、1 週間ほど前に読み始めました。

編集：最初の編集

5 つの適切な一意のソリューションが必要であることを指定したいと思います (5 は任意の数で、3 の場合も 20 の場合もあります)。

コザがここで説明しているように、遺伝的プログラミングを使用して食物採餌行動が可能な進化中のアリを見ています。時間ステップごとに、各アリをループして、そのコンピューター プログラムを実行します (コロニー内のすべてのアリで同じプログラムが使用されます)。MOVE-ONE-STEP現在、TURN-LEFT、 、 などの単純な命令を定義していますが、引数を順番に実行するTURN-RIGHT関数もあります。PROGN私が抱えている問題は、PROGN命令を順番に実行できるため、アリは単一の時間ステップで複数のアクションを実行できることです。自然とは異なり、アリを並行して走らせることはできません。つまり、他のすべてのアリが自分の順番を待っている間に、1 つのアリがいくつかのアクションを実行して環境を操作する可能性があります。

これが通常の方法なのか、それとももっと良い方法があるのか​​ 疑問に思っています。コザはそれについて何も言及していないようです。つまり、シナリオを拡張して、単一の時間ステップで一度だけ発生するものに依存する可能性のある他のエージェント (敵など) を使用したいと考えています。

無向グラフですべての k-clique を見つけたい。したがって、グラフ内のすべての k クリークを見つけるために、アリのコロニーに基づいた正確なアルゴリズムが必要です。たとえば、次の隣接行列を考えてみましょう。

この隣接行列には、(1,2,3)、(2,3,4)、(3,4,5) の 3 つの 3 クリークがあります。

すべてのグラフでこのkクリークを見つけたいです。note=K は K-clique アルゴリズムの入力です。

01MKP の ACO を実装しようとしています。私の入力値は OR-Library mknap1.txt からのものです。私のアルゴリズムによると、最初にアイテムをランダムに選択します。次に、構築グラフの他のすべての項目の確率を計算します。確率方程式は、フェレモン レベルとヒューリスティック情報に依存します。

私の pheremon マトリックスのセルは、初期値 (0.2) で定数値を持っています。このため、次のアイテムを見つけようとすると、フェレモン マトリックスが 0.2 のために無効になります。したがって、私の確率関数は、ヒューリスティック情報をチェックして、次に進むアイテムを決定します。ご存知のように、発見的情報方程式は

(Ravg はリソース制約の平均です)。このため、私の問題です。関数は、最大の利益値を持つアイテムを選択します。(最初の繰り返しで、私のアルゴリズムが 600 の利益を持つアイテムをランダムに選択したとしましょう。次に、2 回目の繰り返しで、2400 の利益値を選択します。しかし、OR-Library では、2400 の利益値を持つアイテムがリソース違反を引き起こします。 2番目に選ばれたのは、利益が2400のアイテムです。

私のアルゴリズムに何か問題がありますか？ACOについて何か知っている人が私を助けてくれることを願っています. 前もって感謝します。

入力値:

私のアルゴリズム:

問題の背景

私は現在、AntColonySystemアルゴリズムのフレームワークを開発しています。私は、彼らが適用された最初の問題である巡回セールスマン問題（TSP）でそれらを試すことから始めようと思いました。タスクにはC＃を使用します。

すべてのTSPインスタンスは、各エッジに関連付けられた2つの異なる重みを持つ完全な無向グラフで構成されます。

質問

これまで、隣接リスト表現のみを使用してきましたが、それらはまばらなグラフにのみ推奨されることを読みました。私はデータ構造に関して最も知識のある人ではないので、無向の完全グラフを実装するための最も効率的な方法は何でしょうか？

必要に応じて、追加の詳細を提供できます。

お時間をいただきありがとうございます。

アップデート

重量の明確化。各エッジには、次の2つの値が関連付けられます。

1. 2つの都市間の距離（d（i、j）= d（j、i）両方向に同じ距離）
2. その特定の端にアリによって沈着したフェロモンの量

オペレーション。グラフで実行する操作の簡単な要約：

• 各ノードについて、その特定のノードのアリは、すべての入射エッジに関連付けられた値を反復処理する必要があります

問題の明確化

アリコロニー最適化アルゴリズムは、TSPが最初に適用された場所であるため、TSPを「解決」できます。「解決」とは、メタヒューリスティック最適化と呼ばれるアルゴリズムファミリーの一部であり、最適な解決策を返すことを保証するものではないためです。

当面の問題について：

• 各アリは記憶を持っているので、アリはツアーを完了する方法を知っています。
• アリが都市を訪れるたびに、その都市を記憶に保存します。
• アリが新しい都市への訪問を検討するたびに、アリはその記憶を検索し、そのエッジがすでに訪問した都市に到達しない場合にのみ、発信エッジを選択します。
• アリが選択できるエッジがなくなると、ツアーが完了します。この時点で、アリが作成したツアーを、その記憶をさかのぼって遡ることができます。

研究記事の詳細：アリの巣システムの記事

効率に関する考慮事項

メモリよりも実行時間（速度）の方が気になります。

簡単なアリのコロニー シミュレーションを構築しようとしています。世界は正方形のグリッドです。それらのそれぞれは、あるレベルのフェロモンと任意の数のアリで構成できます。フェロモンには、食物フェロモンと巣フェロモンの2種類があります。アリは環境について何も知りませんが、巣に戻ったアリは巣のフェロモンに従い (ほとんどの場合、近くのすべてのセルの中でフェロモン レベルが最大のセルに移動することを選択するという意味で)、食物フェロモンを残します。

時折、アリは最大のフェロモンの方向ではなくランダムな動きをします。シミュレーションの各ティックで、アリは 8 つの近くのセルのフェロモンのレベルをチェックし、現在のセルのフェロモン レベルがすべての近くのセルのフェロモン レベルの最大値よりも低い場合、いくつかのフェロモンを追加します。

現在のシミュレーションはうまく機能していますが、見つかったパスは最適なものではありません。解決方法がわからない2つの問題があります。

1. 対角線の移動が非対角線の移動よりも長いという事実をシミュレートするにはどうすればよいですか (上、下、左、または右)?

1. フェロモンの拡散をどのようにシミュレートすればよいですか? 現在、フェロモンは時間の経過とともに蒸発しますが、拡散はありません。シミュレーションの各ティックごとに、各セルから一定量のフェロモンを近くの 8 つのセルに転送しようとしましたが、結果は完全に混乱しました。環境全体がフェロモンでいっぱいでした。メカニズムが原因だったと思います。アリはフェロモンレベルを調整するために使用します。

巡回セールスマン問題を解決するために Ant Colony Optimization のソフトウェア実装を開発しましたが、ACO の確率的性質により、ACO アルゴリズムを実行するたびに、毎回異なる最適に近い解が生成されます。ACO をより決定論的にする方法はありますか? 100% 決定論的ではないことは理解していますが、同じ問題空間で複数回実行できる必要があり、少なくともほとんどの場合、同様の解決策を考え出す必要があります。α、β、ρ、および反復回数を微調整してみましたが、この時点では暗所で撮影しているだけです。