4

質問
以下の問題に対して遺伝的アルゴリズムを試す価値はあると思いますか?

問題の側面は、ジェネレーター/フィットネス関数スタイルのセットアップに最適だと思います。(似たようなプロジェクトを失敗した場合は、ぜひご連絡ください。似たようなことはしないでください)

物事を構造化し、これを正しく釘付けにする方法についてのヒントをありがとう。

問題
次の実世界の問題に使用する適切なスケジューリング アルゴリズムを探しています。

このような 15 スロットのシーケンスがあります (数字は 0 から 20 まで変化する場合があります)。

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

(そして、このタイプの合計 10 の異なるシーケンスがあります)

各シーケンスは配列に拡張する必要があり、各スロットは 1 つの位置を取ることができます。

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1

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

  • [行単位、つまり水平方向] 配置される 1 の数は、11 または 111 のいずれかでなければなりません
  • [行単位] 1 の 2 つのシーケンス間の距離は 00 以上である必要があります
  • 各列の合計は、元の配列と一致する必要があります。
  • マトリックスの行数を最適化する必要があります。

次に、配列は 4 つの異なる行列の 1 つを割り当てる必要があり、行数が異なる場合があります。

A, B, C, D

A、B、C、D は実際の部門です。負荷は、他の部門の目標を妨げないように、10 日間にわたって合理的に公平に配置する必要があります。

各行列は、10 個の異なる元のシーケンスの拡張と比較されるため、次のようになります。

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

これらの特定のスポットは予約されている場合があります（予約するだけにするか、予約しないか、機能ベースにするかはわかりません）。 予約されたスポットは、会議やその他のイベントである可能性があります

各行 (たとえば、すべての A) の合計は、2% 以内でほぼ同じになるはずです。つまり、sum(A1 から A10) は (B1 から B10) とほぼ同じである必要があります。

行数は異なる場合があるため、たとえば次のようになります。

A1: 5 行 A2: 5 行 A3: 1 行、その 1 行はたとえば次のようになります。

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

等..

サブ問題*

問題の一部だけを解決できてとてもうれしいです。たとえば、次のように入力できます。

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

上記の制約に従って、行数が最小化された 1 と 0 を持つシーケンスの適切な配列を取得します。

4

2 に答える 2

2

サブ問題解決の試み

さて、ここにアイデアがあります。このソリューションは遺伝的アルゴリズムの使用に基づいていませんが、その方向に進むためにいくつかのアイデアを使用できます。

基底ベクトル

まず、私が考える基底ベクトルを生成する必要があります。たとえば、シーケンスが 15 ではなく 3 つの数値である場合、基底ベクトルは次のようになります。

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

シーケンス長 3 の解は、正の整数のみを使用したこれら 3 つのベクトルの線形結合になります。言い換えれば、一般的な解決策は

a*v1 + b*v2 + c*v3

ここで、a、b、c は正の整数です。数列 [1 2 1] の場合、解は v1 = 1、v2 = 1、v3 = 0 です。最初にやりたいことは、長さ 15 の可能な基底ベクトルをすべて見つけることです。私の大まかな計算から、長さ 15 の基底ベクトルが 300 ～ 400 個あります。必要に応じて、それらを生成するためのヒントをいくつか提供できます。

解決策を見つける

ここで、これらの基底ベクトルを合計/大きさで並べ替えます。次に、解を探す際に、合計が最大の基底ベクトルから始めます。総行数が少なくなるため、合計が最大のベクトルから始めます。また、各基底ベクトルの線形係数のエントリを含む配列 veccoefs もあります。解を探し始めた時点では、veccoef はすべて 0 です。

したがって、最初の基底ベクトル (最大の合計/大きさを持つベクトル) を取得し、解決できない結果 (たとえば、0 1 0 を含む) または結果の数値のいずれかが作成されるまで、シーケンスからこのベクトルを減算します。負です。ベクトルを減算した回数を veccoefs に保存します。シーケンスから基底ベクトルを減算した結果を、次の基底ベクトルのシーケンスとして使用します。結果にゼロしか残っていない場合は、ループを停止します。

この方法の効率/精度についてはわかりませんが、少なくともいくつかのアイデアが得られるかもしれません.

その他の可能な解決策

これを解決するための別のアイデアは、基底ベクトルを使用して問題を最適化/最小二乗問題として形成することです。基本的な問題が Sum[(Ax - b)^2] を最小化するように、基底ベクトルの行列を作成します。ここで、A は基底ベクトルの行列、b は入力シーケンス、x は基底ベクトルの係数です。ただし、行数も最小化する必要があるため、x^T*x のような項を最小化関数に追加できます。x^T は x の転置です。私の意見では難しいのは、整数ベクトル係数を促進する微分項を追加することです。それを行う方法を考えることができれば、最適化はこれを行うための非常に良い方法になる可能性があります.

また、メトロポリス型のモンテカルロ ソリューションを検討することもできます。各ステップで、ベクトルを追加するか、ベクトルを削除するか、ベクトルを置き換えるかをランダムに選択します。追加/削除/置換されるベクトルはランダムに選択されます。この変更が受け入れられる確率は、変更前と変更後のソリューションの適合性の比率になります。適合性は、現在の解とシーケンスの差を 2 乗して合計し、解に含まれる行/基底ベクトルの数を引いたものに等しくなる可能性があります。約 50% の承認率を得るには、さまざまな用語に対して適切な定数を入力する必要があります。これがうまく機能するかどうかはちょっと疑問ですが、可能な解決策を探すときはまだ検討する必要があると思いました.

于 2010-02-15T08:12:13.010 に答える
1

GA はこの問題に適用できますが、5 分のタスクにはなりません。それぞれのどの実装が最適かを知らなくても、いくつかのものを組み合わせる必要があります。
そう：

  1. 解決策の表現 - 可能な解決策をどのように表現しますか? マトリックスを使用するのが最も簡単なようです。1 次元配列のコレクションを使用することも可能です。しかし、いくつかの制約があるので、SuperGene のコンセプトは検討する価値があるのではないでしょうか?
  2. 特定の遺伝子表現に対して適切な突然変異/交差演算子を使用する必要があります。
  3. ソリューションにどのように制約を適用しますか? 適切ではないものを破壊しますか？貴重な情報が含まれている場合はどうなりますか? 個体群にとどまらせて、フィットネスにいくらかのペナルティを追加して、子孫に貢献するが、次の世代には渡らないようにすることもできますか?

とにかく、GAはこの問題に適用できると思います。それは価値がありますか？通常、GA は最適なアルゴリズムではありませんが、他のアルゴリズムが失敗した場合でも適切なアルゴリズムです。最も楽しいという理由だけでGAを使用しますが、代替ソリューションを探します（念のため）。

PS個人的な洞察：70 < N < 100（ボードNxN、Nクイーン）のNクイーン問題を解決していました。アルゴリズムは N が低い場合は正常に機能していましたが (すべての組み合わせを試していたのでしょうか?)、N がこの範囲にあるため、適切な解決策を見つけることができませんでした。フィットネスはすぐに最大値の約 90% まで跳ね上がりましたが、最終的には常に 2 つのクイーンが競合していました。しかし、それは非常に単純な実装でした。

于 2010-02-09T10:38:30.860 に答える