6

だから私は最近、アルゴリズム全般にとても興味を持っています。そして、私は最近、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 の場合もあります)。

4

3 に答える 3

1

ACOの表現で私が目にする唯一の問題は、 +/- X% です。

各色の固定パーセンテージを使用すると、次のように進めることができます。

青、黄、赤は場所です。さまざまなサブタイプが道路を表し、その重みはコストと必要な流量によって異なります。

次に、TSP と同様に AOC メソッドを適用するだけですが、アリの動き方を少し変更します。

  1. コストの制約を満たす場合にのみ、1 つのパスにフェロモンを追加する
  2. 「最適な長さ」に最も近いパスの長さの選択 = 最適コストの N% (上の例では、黄色のパスの場合、25%*95 に最も近いパス)

浮動パーセンテージ制約を追加する場合は、次のようにします。

あなたが最高のコストだとしましょう：

Cost = X1*light yellow +X2*sea blue+X3*blood red for example.

このコストが最適でない場合は、コストを最適化するために、X1 X2 および X3 でいくつかの小さなバリエーションを使用できます。

たとえば、X1-e と X2+e はコストを次のように変更します。e*(costseablue-costLightYellow)

たとえば、1 つの小さなイプシロンが与えられた場合、costi<costj(i と j にリンクされた色のコスト) Xi,Xj の各ペアに対して、Xi のすべてのカップルのコストを改善できなくなるまで、イプシロンを Xi に追加し、Xj から削除することができます。 、Xj。

于 2011-08-09T15:17:18.937 に答える
1

グラフが三角形の不等式を満たす場合は、最小スパニング ツリーと完全重み非二部マッチング アルゴリズムを試すことをお勧めします。クリストフィデス等。最適の 3/2 以内のソリューションを保証します。AOC は良好で迅速な結果をもたらしますが、多くの問題に対して最適化する必要があります。クリストフィデス アルゴリズムを php (phpclasses.org) で作成しました。ぜひお試しください。それが機能しているかどうかはわかりません。時々奇妙な結果をもたらします。それはおそらく、Fleury アルゴリズムの私の実装ですか?

于 2011-08-09T15:36:45.793 に答える
1

あなたの色の問題は私にはかなり些細なことのように思えます.ブルートフォースでさえ速いと思います..だからあなたのアリのコロニーもおそらくそれを解決することができます:)

于 2011-08-09T15:11:49.087 に答える