グラフを描く遺伝的アルゴリズム？位置割り当ての問題

Question

私は割り当ての問題を手にしており、望ましい解決策（検索スペースがかなり大きい）に達するためにローカル検索技術を適用するのがどれほど適しているのだろうと思っています。

私は人間の目で非常にはっきりと理解でき、読みやすい方法で2次元平面上で視覚化したい有向グラフ（フローチャート）を持っています。したがって、私は（x、y）の位置を各頂点に割り当てます。私はシミュレーテッドアニーリング、遺伝的アルゴリズムを使用してこの問題を解決すると思って、または任意のそのような方法は、あなたがお勧めすることができ

入力：グラフG =（V、E）
出力：割り当てのセット、 {(xi, yi) for each vi in V}。言い換えれば、各頂点には、座標がすべて整数で、> = 0の位置（x、y）が割り当てられます。

これは私が解決策を判断するために使用する基準です（私は何か提案を歓迎します）。エッジは最小限であるべきである交差の

• 番号、
• 一方向のすべてのエッジの流れ（すなわち、左から右へ）、
• 高い角度分解能（同じ上の2つの縁 入射することにより形成最小角度頂点）、
• 小少なくとも重要です。

さらに、私は手作業で作った初期の構成（頂点への位置の割り当て）を持っています。それは非常に面倒です、そして、それが私がプロセスを自動化しようとしている理由です。

私の質問は、どのように賢明なことは、ローカル検索技術で行くことになり

• ですか？どのようにして が望ましい結果を生み出すでしょうか？

• まずはどうすればよいですか？模擬アニーリング、遺伝的アルゴリズム または何か他のもの？

• 最初に無作為にシードするか、最初に コンフィグレーションを使用する必要がありますか？

• また、同様の実装/擬似コード/事柄について既に知っている場合は、教えてください。

ご協力いただきますようお願い申し上げます。ありがとう。

編集：リアルタイムではなく、高速である必要はありません。さらに、 | V | =〜200であり、各頂点は平均で約1.5の出力エッジを有する。グラフには切断されたコンポーネントはありません。それはサイクルを伴う。

Answer 1

graphvizはオープンソースのグラフ・ビジュアライザーの1つで、http://www.graphviz.org/Theory.phpをお勧めします。

割り当てに応じて、おそらくグラフビズを使用してビジュアライゼーションを行うのが理にかなっています。

Answer 2

http://oreilly.com/catalog/9780596529321 - このドキュメントでは、2Dグラフの詳細な視覚化のための遺伝的アルゴリズムの実装を見つけることができます。

同様の状況で私は遺伝的アルゴリズムを使うのが好きです。また、初期化された人口をランダムに設定することもできます。経験を重ねるうちに、か​​なり良い（ただし最高ではない）解決策が見つかるでしょう。

また、Javaを使用すると、このアルゴリズムを独立させることができます（アイランドアイランド戦略） - これは効率的な改善です。

また、私はあなたに助言したいと思います差分進化アルゴリズム。私の経験から、遺伝的最適化よりもはるかに迅速に解決策を見つけることができます。

Answer 3

This paperは、さまざまなアプローチの概観です。 Roberto Tomassia's bookも良い賭けです。

Answer 4

あなたの最初の質問に答えるために、私はそれが依存していると言わなければなりません。それは、次のようなさまざまな要因の数に依存：

それは（それがリアルタイムで行われる必要があるのでしょうか？）
• を
• どのように多くのエッジがありますどのように多くの頂点である必要がありますどのくらいの速

リアルタイムで実行する必要がある場合は、ローカル検索の手法が最適ではないでしょう。なぜなら、これらの頂点の数は、頂点の数と比較されるからです。良い結果を得る前に実行することができます。グラフのサイズが小さければ、それらは十分に速いだけです。そしてそれが小さい場合は、まずローカル検索を使用する必要はありません。

説明したようにグラフをレンダリングするためのアルゴリズムは既にあります。問題は、問題が大きくなりすぎて効果的にならない点です。私はその質問に対する答えはわかりませんが、あなたが調べるために何らかの調査をすることができると確信しています。

ここでローカル検索の実装について質問します。

私の個人的な経験から、シミュレートされたアニーリングは、遺伝的アルゴリズムより簡単に実装できます。しかし、私はこの問題が両方の設定にうまく変換されると思います。私はSAで始めるだろう。

シミュレーテッドアニーリングの場合、ランダムな構成から始めます。次に、1つまたは複数の頂点をランダムな距離だけ移動させて、ランダムに構成を摂動させることができます。私はあなたがアルゴリズムの詳細を完了できると確信しています。

遺伝的アルゴリズムのアプローチでは、ランダムな母集団から開始することもできます（各グラフには頂点のランダム座標があります）。突然変異は、私が記述したSAアルゴリズムの摂動のようにすることができる。再組み立ては、親からのランダムな頂点を子グラフで使用するだけです。再び、私は空白を埋めることができると確信しています。

合計：ローカル検索は、グラフのサイズが十分である場合や、すばやくすばやく実行する必要がない場合（たとえば、数秒未満など）にのみ使用します。それ以外の場合は別のアルゴリズムを使用します。

編集：グラフのパラメータに照らして、私はあなたがコードするのが最も簡単なアルゴリズムを使用するだけでよいと思います。 V = 200では、O（V^3）アルゴリズムでさえ十分である。個人的には、シミュレーテッドアニーリングが最も簡単で最善のルートになるように感じます。

Answer 5

function String generateGenetic() 
String genetic = ""; 
for each vertex in your graph 
    Generate random x and y; 
    String xy = Transform x and y to a fixed-length bit string; 
    genetic + = xy; 
endfor 
return genetic; 

あなたはレベルのレベルを与える関数double evaluate（String genetic）を書いてください。 （おそらく、どのように多くのエッジ交差したエッジ方向に基づいて

プログラム：

int population = 1000; 
int max_iterations = 1000; 
double satisfaction = 0; 
String[] genetics = new String[population]; //this is ur population; 
while((satisfaction<0.8)&&(count<max_iterations)){ 
    for (int i=0;i<population;i++){ 
     if(evaluate(genetics[i])>satisfaction) 
      satisfaction = evaluate(genetics[i]); 
     else 
      manipulate(genetics[i]); 
    } 
} 

funcitonは、文字列または複数のビットまたは頂点のxおよびyをコードする部分のいくつかのビットを反転することができる操作または新しい遺伝子列を完全に生成するか、内部の問題を解決しようとするかもしれません（エッジを指示する）