3

BIG版後の質問：

遺伝的アルゴリズムを使用してランキングを作成する必要があります。次のようなデータがあります。

P(a>b)=0.9
P(b>c)=0.7
P(c>d)=0.8
P(b>d)=0.3

a,b,c,dここで、をサッカー チームの名前と解釈して、 で勝つP(x>y)確率をとします。チームのランキングを作成したいのですが、いくつかの観察が不足しており、a vs d と a vs c の一致がないために欠落しています。目標は、その 4 チーム リーグの現在の状況を最もよく表すチーム名の順序を見つけることです。xyP(a>d)P(a>c)

チームが 4 つしかない場合、解決策は簡単です。まず、4!=24欠損値を無視しながら、4 つのチームのすべての順序について確率を計算します。

P(abcd)=P(a>b)P(b>c)P(c>d)P(b>d)

P(abdc)=P(a>b)P(b>c)(1-P(c>d))P(b>d)

...

P(dcba)=(1-P(a>b))(1-P(b>c))(1-P(c>d))(1-P(b>d))

そして、確率が最も高いランキングを選択します。他のフィットネス機能を使用したくありません。

私の質問 ：

n 要素の順列の数はn!、すべての順序付けの確率の計算であるため、大きな n (私の n は約 40) では不可能です。その問題に遺伝的アルゴリズムを使用したいと考えています。

突然変異演算子は、ランキングの 2 つ (またはそれ以上) の要素の場所を単純に切り替えることです。

しかし、2 つの順序付けのクロスオーバーを作成するにはどうすればよいでしょうか。

非対称 TSP 問題のパス「abcd」のコスト関数として解釈できP(abcd)ますが、x から y への移動のコストは y から x への移動のコストとは異なりP(x>y)=1-P(y<x)ます。TSP の問題には非常に多くの交叉演算子がありますが、私の問題は TSP とは少し異なるため、独自の交叉演算子を設計する必要があると思います。概念分析のためのソリューションまたはフレームのアイデアはありますか?

概念レベルおよび実装レベルでの最も簡単な方法は、2 つのソリューション間でサブオーダーを交換するクロスオーバー オペレーターを使用することです。

CrossOver(ABcD,AcDB) = AcBD

要素のランダムなサブセット (この場合は大文字の 'a,b,d') の場合、最初のサブオーダー - 要素 'a,b,d' のシーケンスを 2 番目のオーダーにコピー アンド ペーストします。

Edition : 非対称 TSP は対称 TSP に変換できますが、下位順序付けが禁止されているため、GA アプローチは不適切です。

4

3 に答える 3

3

これは間違いなく興味深い問題であり、ほとんどの回答とコメントは問題のセマンティックな側面 (つまり、フィットネス関数の意味など) に焦点を当てているようです。

構文要素に関するいくつかの情報を追加します-意味のある方法でクロスオーバーや突然変異をどのように行いますか. 明らかに、TSP と並行して指摘したように、順列の問題があります。したがって、GA を使用する場合、候補解の自然な表現は、ポイントの順序付けられたリストに過ぎず、反復、つまり順列を避けるように注意してください。

TSP はそのような順列問題の 1 つであり、TSP アルゴリズムから取得して直接使用できるクロスオーバー オペレーター ( Edge Assembly Crossoverなど) が多数あります。ただし、そのアプローチには問題があると思います。基本的に、問題は次のとおりです。TSP では、ソリューションの重要な品質は隣接性です。つまり、abcdはcdabと同じ適応度を持ちます。これは、異なる都市で開始および終了する同じツアーであるためです。あなたの例では、この相対位置の概念よりも絶対位置がはるかに重要です。abcdは、ある意味でaが最良の点であることを意味します。リストの最初にあることが重要です。

効果的なクロスオーバー演算子を取得するために必要な重要なことは、親に含まれるプロパティが何であるかを説明し、それらのプロパティを正確に抽出して結合することです。Nick Radcliffe はこれを「敬意を持った組み換え」と呼びました(論文はかなり古いため、理論は現在では少し異なって理解されていますが、原理は正しいことに注意してください)。TSP で設計された演算子を問題に適用すると、親からの無関係な情報を保存しようとする子孫が生まれます。

理想的には、文字列内の絶対位置を保持しようとする演算子が必要です。私が知っている最高のものは、Cycle Crossover (CX) として知られています。頭のてっぺんから適切な参照がありませんが、卒業制作の一部として実装したコードをいくつか紹介できます。CX の基本的な考え方は、説明がかなり複雑ですが、実際に見てみるとはるかに簡単です。次の 2 点を取り上げます。

abcdefgh
cfhgedba

  1. 親 1 の開始点をランダムに選択します。簡単にするために、位置 0 から "a" を付けて開始します。

  2. 次に、親 2 に直接ドロップし、そこで値を観察します (この場合は "c")。

  3. 次に、親 1 で「c」を検索します。2 番目の位置にあります。

  4. ここで再びまっすぐ下にドロップし、親 2、位置 2 の「h」を観察します。

  5. 再び、7 番目の親 1 でこの「h」を検索します。

  6. まっすぐ下にドロップして、親 2 の「a」を観察します。

  7. この時点で、親 1 で「a」を検索すると、既に行った位置に到達することに注意してください。過去を続けて、ただ循環します。実際、訪問した一連の位置 (0、2、7) を「サイクル」と呼びます。グループとして親の間でこれらの位置の値を交換するだけで、両方の親のサイクルの各位置に同じ 3 つの値が異なる順序であるために、両方の親が順列プロパティを保持することに注意してください。

  8. サイクルに含まれるポジションのスワップを行います。

これは 1 サイクルのみであることに注意してください。次に、すべての位置がサイクルに含まれるまで、毎回新しい (未訪問の) 位置からこのプロセスを繰り返します。上記の手順で説明した 1 回の反復の後、次の文字列が得られます (「X」は、親の間で値が交換されたサイクル内の位置を示します。

cbhdefga
afcgedbh
X X    X

完了するまで、サイクルを見つけて交換し続けます。

私が github アカウントからリンクしたコードは、私自身のメタヒューリスティック フレームワークにしっかりとバインドされますが、コードから基本的なアルゴリズムを引き出して、独自のシステムに適応させるのはかなり簡単な作業だと思います。

特定のドメインに合わせてよりカスタマイズされた何かを行うことで、かなりの利益が得られる可能性があることに注意してください。CX のようなものは、TSP 演算子に基づくものよりも優れたブラック ボックス アルゴリズムになると思いますが、ブラック ボックスは通常、最後の手段です。他の人の提案は、より良い全体的なアルゴリズムにつながる可能性があります。

于 2012-04-16T12:19:06.627 に答える
2

なんと興味深い問題でしょう！私がそれを理解していれば、あなたが本当に求めているのは次のとおりです。

「グラフ内の各辺の重みが円弧が正しい方向に描かれる確率を表す、重み付けされた有向グラフが与えられた場合、グラフのトポロジカル ソートである確率が最大のノードの完全なシーケンスを返します。」

したがって、グラフに N 個のエッジがある場合、さまざまな可能性の 2^N 個のグラフがあり、いくつかの順序付けが複数のグラフに表示されます。

これが役立つかどうかはわかりません（非常に簡単なGoogle検索ではわかりませんでしたが、忍耐力があればより多くの成功を収めることができるかもしれません）が、「確率論的」のいずれかと組み合わせて「トポロジカルソート」を探していると思います、「ランダム」、「ノイズ」、または「エラー」(エッジの重みは信頼性の要因と見なすことができるため) が役立つ場合があります。

ただし、あなたの例では、 P(a>c) は必要ないというあなたの主張に強く疑問を呈します。アプリケーション空間を最もよく知っているのはあなたですが、P(a>c) = 0.99 を指定すると、P(a>c) = 0.01 を指定する場合とは異なる f(abc) の適応度が得られるように私には思えます。

条件と仮想解が与えられた場合、(あなたの例では) P(a>c) の値を推測し始めることができるかもしれないので、「ベイジアン」も入れたいと思うかもしれません。問題は、「トポロジカルソート」と「ベイジアン」が、マルコフ連鎖とマルコフ決定問題に関連する大量のヒットを提供することです。これは役立つ場合とそうでない場合があります。

于 2012-04-14T22:02:23.427 に答える
2

私は幾分類似したランキングの問題に取り組み、以下で説明するのと同様の手法に従いました。これはあなたのために働きますか：

オブジェクトの未知数valueが、正規分布などの何らかの分布によって推定値から逸脱すると仮定します。a > b, 0.9「値aは、を中心とした分布の 90% パーセンタイルにあります。」などのランキング ステートメントを解釈しますb。

すべてのステートメントについて:

def realArrival = calculate a's location on a distribution centered on b
def arrivalGap = | realArrival - expectedArrival | 
def fitness = Σ arrivalGap

フィットネス機能はMIN(fitness)

FWIW、私の問題は実際にはビンパッキングの問題であり、「ランク」ステートメントに相当するのはユーザー提供のランキング（1、2、3など）でした。つまり、完全に TSP ではなく、NP-Hard です。OTOH、ビンパッキングには、受け入れられたエラーに比例する疑似多項式ソリューションがあり、これは私が最終的に使用したものです。それがあなたの確率的ランキングステートメントでうまくいくかどうかはよくわかりません。

于 2012-04-14T18:50:48.247 に答える