3

私は Java でタイム テーブル ジェネレーターを作成しています。AI アプローチを使用してハードな制約を満たし、最適なソリューションを見つけるのに役立ちます。これまでのところ、反復構築 (最も制約のある最初のヒューリスティック) とシミュレーテッド アニーリングを実装しており、遺伝的アルゴリズムを実装している最中です。

問題に関するいくつかの情報と、それをどのように表現するか: イベント、部屋、機能 (イベントが必要とし、部屋が満たす)、学生、およびスロットのセットがあります。問題は、各イベントにスロットと部屋を割り当てることです。学生が 1 つのスロットで 2 つのイベントに参加する必要がないこと、割り当てられたすべての部屋が必要な要件を満たしていること。

割り当てがソフト制約違反を評価する場合、セットごとに評価機能があるため、ポイントはこれを最小限に抑えることです。

私が GA を実装する方法は、反復構築 (イベントを未割り当てのままにすることができます) によって生成された母集団から始めて、通常の手順を実行することです。すすいで繰り返します。

私の問題は、私のソリューションがほとんど改善されないように見えることです。私が何をしても、個体群はランダムな適合度になる傾向があり、そこにとどまります。この適合度は常に異なりますが、下限が表示されることに注意してください。

問題はクロスオーバー関数にあると思われます。その背後にあるロジックは次のとおりです。

交差する 2 つの割り当てがランダムに選択されます。それらを割り当て A および B と呼びましょう。B のすべてのイベントに対して、次の手順を実行します (B のイベントが選択される順序はランダムです)。

A で対応するイベントを取得し、割り当てを比較します。3 つの異なる状況が発生する可能性があります。

  • それらの 1 つだけが未割り当てで、子で他の割り当てを複製できる場合は、この割り当てが選択されます。
  • 両方が割り当てられていて、一方だけが
    子への割り当て時に競合を作成しない場合は、その方が選択されます。
  • 両方が割り当てられていて競合が発生しない場合は、どちらかがランダムに選択されます。

それ以外の場合、イベントは割り当てられません。

これにより、親の割り当ての一部と母親の割り当ての一部を持つ子が作成されるため、有効な関数のように思えます。さらに、ハード制約を破ることはありません。

突然変異に関しては、SA の隣接関数を使用して、子に基づいて別の割り当てを与え、その子を置き換えています。

もう一度。このセットアップでは、初期集団が 100 で、GA が実行され、常にランダムな (高い) フィットネス値で安定する傾向があります。私が間違っている可能性があることについて、誰かが私にポインタを与えることができますか?

ありがとう

編集：いくつかのものをフォーマットしてクリアする

4

5 に答える 5

0

元の問題の説明を提供していただければ、より良い解決策を提供することができます。これが今の私の答えです。

遺伝的アルゴリズムは、厳しい制約を満たすための最良のツールではありません。これは、線形計画法の特殊なケースである整数計画法を使用して解決できる割り当て問題です。

線形計画法を使用すると、ユーザーは目的関数（評価関数）によってモデル化されたいくつかの目標を最小化または最大化できます。目的関数は、個々の決定（または決定変数）の合計と、目的関数への値または寄与によって定義されます。線形計画法では、決定変数を10進値にすることができますが、整数計画法では、決定変数を整数値にする必要があります。

それで、あなたの決定は何ですか？あなたの決定は、学生をスロットに割り当てることです。そして、これらのスロットには、イベントに必要な機能と部屋が満たす機能があります。

あなたの場合、スロットに割り当てられる学生の数を最大化する必要があります。

制約もあります。あなたの場合、学生はせいぜい1つのイベントにしか出席できません。

以下のWebサイトは、整数プログラムをモデル化する方法に関する優れたチュートリアルを提供します。

http://people.brunel.ac.uk/~mastjjb/jeb/or/moreip.html

Java固有の実装については、以下のリンクを使用してください。

http://javailp.sourceforge.net/

SolverFactory factory = new SolverFactoryLpSolve(); // use lp_solve
factory.setParameter(Solver.VERBOSE, 0); 
factory.setParameter(Solver.TIMEOUT, 100); // set timeout to 100 seconds

/**
* Constructing a Problem: 
* Maximize: 143x+60y 
* Subject to: 
* 120x+210y <= 15000 
* 110x+30y <= 4000 
* x+y <= 75
* 
* With x,y being integers
* 
*/
Problem problem = new Problem();

Linear linear = new Linear();
linear.add(143, "x");
linear.add(60, "y");

problem.setObjective(linear, OptType.MAX);

linear = new Linear();
linear.add(120, "x");
linear.add(210, "y");

problem.add(linear, "<=", 15000);

linear = new Linear();
linear.add(110, "x");
linear.add(30, "y");

problem.add(linear, "<=", 4000);

linear = new Linear();
linear.add(1, "x");
linear.add(1, "y");

problem.add(linear, "<=", 75);

problem.setVarType("x", Integer.class);
problem.setVarType("y", Integer.class);

Solver solver = factory.get(); // you should use this solver only once for one problem
Result result = solver.solve(problem);

System.out.println(result);

/**
* Extend the problem with x <= 16 and solve it again
*/
problem.setVarUpperBound("x", 16);

solver = factory.get();
result = solver.solve(problem);

System.out.println(result);
// Results in the following output:

// Objective: 6266.0 {y=52, x=22}
// Objective: 5828.0 {y=59, x=16}
于 2012-05-16T21:57:53.813 に答える
0

GA は、解の一部 (ベクトルの一部) が解の独立した部分として重要な意味を持ち、クロスオーバー関数が 2 つの解ベクトル間の解の有効な部分を統合する場合にのみ意味があると思います。DNA 配列の特定の部分が個人の特定の側面を制御または影響を与えるように、たとえば目の色は遺伝子の 1 つです。ただし、この問題では、解ベクトルのさまざまな部分が互いに影響し合い、クロスオーバーがほとんど無意味になります。これにより（私の推測では）、アルゴリズムは単一のソリューションにかなり迅速に収束し、さまざまなクロスオーバーと突然変異がフィットネスに悪影響を与えるだけになります。

GA がこの問題に適したツールだとは思いません。

于 2012-05-16T14:33:36.887 に答える
0

何が起こっているかを直接測定することから始めます。たとえば、割り当てのどの部分が「その他のケース」のキャッチオールに該当し、何もしないでしょうか?

また、与えられた情報からは正確に判断できませんが、あなたの手が「スワップ」できるようには見えません。これは問題になる可能性があります。スケジュールが厳密に制約されている場合、実行可能なものが見つかった場合、部屋 B が使用されているため、部屋 A から部屋 B にクラスを移動することはできない可能性があります。クラスを B から A に移動するとともに、クラスを A から B に移動する方法を検討する必要があります。

制約に違反することを許可することで、物事を改善できる場合もあります。クロスオーバーが制約に違反することを禁止する代わりに、それを許可することができますが、違反の「悪さ」に比例して適合性にペナルティを課すことができます。

最後に、他のオペレーターにも問題がある可能性があります。選択演算子と置換演算子が積極的すぎると、開始した場所よりもわずかに優れたものに非常に迅速に収束する可能性があります。いったん収束すると、突然変異だけで生産的な検索に戻ることは非常に困難です。

于 2012-05-18T13:47:43.923 に答える
0

この問題については GA に問題はないと思います。何人かの人々は遺伝的アルゴリズムを嫌うだけです。

これが私がチェックするものです：

最初に、あなたの GA はランダムな「高い」フィットネス値で安定するとおっしゃいましたが、これは良いことではないでしょうか? あなたの場合、「高い」フィットネスは良いまたは悪いに対応しますか? コードの一部で「高」適合度を優先し、別の部分で「低」適合度を優先しているため、一見ランダムな結果が生じる可能性があります。

クロスオーバー操作の背後にあるロジックについて、もう少し注意したいと思います。基本的に、これらの選択のいずれかを行ってもクロスオーバーした個人のフィットネスがまったく向上しないという 3 つのケースすべてに多くの状況がありますが、それでも「リソース」(別のリソースに使用される可能性のある割り当て) を使用しています。 class/student/etc.) GA は伝統的にクロスオーバーを介してより悪い動作を引き起こす割り当てを行うことを理解していますが、とにかくクロスオーバーフェーズですでに少し計算を実行しています.実際にフィットネスを改善するものを選択しないでください.全然交差しない？

考慮すべきオプションのコメント : 反復的な構築アプローチは非常に興味深いものですが、これにより、クロスオーバーで問題を引き起こす可能性がある過度に複雑な遺伝子表現が生じる可能性があります。ビットまたは整数の配列 (または 2D 配列) として単一の個別のソリューションをモデル化することは可能ですか? 配列が非常に長い場合でも、より単純なクロスオーバー手順を使用する価値がある場合があります。グーグルの「ga遺伝子表現タイムテーブル」をお勧めします。より好きで、より簡単に多くの個人にスケーリングできるアプローチを見つけることができます（GAの場合、100はかなり小さい人口サイズですが、まだテストしていることを理解しています。世代？）

最後に、どの言語で作業しているかわかりませんが、それが Java であり、手動で GA をコーディングする必要がない場合は、ECJを参照することをお勧めします。手作業でコーディングする必要がある場合でも、表現や繁殖パイプラインの開発に役立つ可能性があります。

于 2012-05-18T17:54:39.613 に答える
0

GA の初心者は、多くの標準的な間違いを犯す可能性があります。

  • 一般に、クロスオーバーを行うときは、最初に親または親を勝者にしたものを子供が継承する可能性があることを確認してください。言い換えれば、ゲノムの「遺伝子」フラグメントが問題ステートメントに意味のあるマッピングを持っているゲノム表現を選択します。よくある間違いは、すべてをビットベクトルとしてエンコードしてから、クロスオーバーでビットベクトルをランダムな場所で分割し、ビットベクトルが表す良いものを分割し、それによって個々を良い候補としてトップに浮かび上がらせたものを破壊することです。(制限された) 整数のベクトルは、より良い選択である可能性が高く、整数は突然変異によって置き換えることができますが、交差によって置き換えることはできません。何かを保存しない (100% である必要はありません。

  • 一般に、思っているよりもはるかに少ないミューテーションを使用してください。突然変異は、主に人口の多様性を維持するために存在します。初期集団にわずかな優位性を持つものが何も含まれていない場合、その集団は当面の問題に対して小さすぎ、高い突然変異率は一般に役に立ちません。

  • この特定のケースでは、クロスオーバー関数が複雑すぎます。すべてのソリューションをクロスオーバーに有効に保つことを目的とした制約を決して入れないでください。代わりに、クロスオーバー関数は無効なソリューションを自由に生成できるようにする必要があり、無効なソリューションに多少の(完全ではない) ペナルティを課すのはゴール関数の仕事です。GA が機能する場合、100% 有効な割り当てが可能であれば、最終的な回答に無効な割り当ては含まれません。クロスオーバーで有効性を主張することは、有効なソリューションが無効なソリューションを介して他のより有効なソリューションへのショートカットを取ることを防ぎます。

パフォーマンスの低い GA を作成したと考えている人には、次のテストを実施することをお勧めします。次に、勝者選択ステップと目標関数 (使用するものは何でも - トーナメント、ランキングなど) をランダムな選択に置き換えて、もう一度実行します。実際のエバリュエーター/ゴール関数とほぼ同じ速度でまだ収束する場合は、実際には機能する GA がありません。GA が機能しないと言う多くの人々は、コードに何らかの間違いを犯しています。つまり、GA はランダム検索と同じくらいゆっくりと収束するため、この手法から誰かを遠ざけるのに十分です。

于 2015-03-25T17:46:39.957 に答える