パーセントコロナの最適化または遺伝的アルゴリズムのパーセントベースの問題

Question

私は最近、一般的にアルゴリズムに最近魅了されました。そして、私は最近、TSPを解決するためのアリのコロニー最適化アルゴリズムを実装しました（明らかに非常に楽しい）。今私は解決するために他の "問題"を見てきました。今度は、パーセンテージ要件を満たすことを含む問題を解決し、任意の制限を下回るアルゴリズムを実装したかったのです。

ユーザ入力：

1）制限 -i.e.例えば

費やすことができるエネルギーの量。

2）「染色体」型 -i.e. - 青のような主要な属性には、インディゴ、藍、藍などの異なるサブタイプからなる「プール」があります。ライトブルー、シーブルー。 - それぞれのサブタイプの色には、さまざまなコストが関連付けられています。

3）「理想的な」ソリューションに必要なタイプの割合（より多くの品種を可能にするために+/-％を導入することができます）。 -i.e.赤10％、青30％、黄色60％。

出力：

1）以下のものは、次の2つの要件を満たすことができ、最終的な解決策 - しかし、近くに - 必要なコストやスーパータイプの割合の要件を満たします。

などです。

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

ユーザー= を次のようにコストがなければならない指定ユーザーブルー25％、25％、黄色、赤の50％を選択< = 105

費用。 インディゴ：各色のための利用可能なプール

ブルー+/- 5％の偏差

とコスト= 25。 シーブルー：費用= 30; ネイビーブルー：費用= 75;

イエロー： ライトイエロー：コスト= 20; ダークイエロー：費用= 30; スーパーダークイエロー（笑）：費用= 75;

赤： マルーン：コスト= 20; ブラッドレッド：費用= 45; 明るい赤色：費用= 55;

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

組み合わせ1：インジゴ、ダークイエロー、血液レッド：コスト= 100：ブルー= 25％、イエロー= 30％、レッド= 55％。

組合せ2：海の青、淡黄色、血液赤：コスト= 105：青=〜30％、黄色=〜20％、赤=〜50％

組合せ3：ように等。

EDIT：セカンド編集

出力が異なる組み合わせのセットで構成されます。例えば

一の溶液のような組み合わせで構成されることがあります

コンビネーション1：

一つの解決策は、この表されるであろうコスト= 20。 50％青、25％黄、25％赤;

組み合わせ2：コスト= 30;青10％、黄50％、赤40％;

組み合わせ3：コスト= 50;青色25％、黄色25％、赤色50％;合計コスト= 100、それはx％青、y％黄、z％赤で構成されています。

要件を解決するには、要件を満たしていればそれを捨てないでください。

のEND EDIT

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

もっと効率的な解決策か、まったく別のアルゴリズムであるかもしれないことだけを考えてください。私はこのようなことにはかなり慣れていて、ちょうど1週間以上前にそれについて読むことを始めました。

EDIT：まず編集

私は5つの良いユニークなソリューションがしたいことを指定します（任意の数である5を20可能性があり、3することができます）。

Answer 1

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

Answer 2

私はあなたの表現と見るだけの問題ACOは+/- X％です。各色の一定の割合で

あなたが言ったように、あなただけ進めることができます：

黄色、青と赤は、異なるサブタイプが道路を表し、その重量はコストとに依存した場所 です必要な収入。

次に、あなただけのTSP用としてお使いAOC法を適用されますが、アリがどのように動くかを少し変える：

1. は、それが制約
コストの選択をfullfills場合にのみ、1つのパスにフェロモンを追加します の「最適な長さ」= Nの％に最も近い経路長最適コスト（イエローパスの上記の例では、* 95 25％に最も近いもの ）

あなたはフローティング割合制約を追加する場合：

は、あなたが最良のコストだとしましょうです：

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

このコストは、あなたがX1 X2にいくつかの小さなvarationsを扱うことができます最適でない場合そして、あなたのコスト最適化するために、X3、：たとえば、X1-EおよびX2 + Eの

を各ペアXiのために、一つの小さなイプシロン与えられ、例えばe*(costseablue-costLightYellow)

によってあなたのコストを変更するだろう、Xjのようにもの（iとjにリンクされた色のコスト）XiにXを追加し、Xi、Xjのすべてのカップルのコストを改善できなくなるまでXjから削除することができます。

Answer 3

グラフが三角不等式を満たしている場合は、最小限のスパニングツリーと完全体重非二部マッチングアルゴリズムを試してみることをお勧めします。 Christofides et al。最適の3/2以内のソリューションを保証します。 AOCは良い結果をもたらすことができますが、多くの問題に対して最適化する必要があります。私はphp（phpclasses.org）でChristofidesアルゴリズムを書いています。あなたはそれを試してみることを歓迎します。私はそれが動作しているかわからない。それはときどき奇妙な結果をもたらします。おそらく私のFleuryアルゴリズムの実装ですか？