繪製圖形的遺傳算法？位置分配問題

我手邊有一個分配問題，我想知道應用本地搜索技術以達到理想的解決方案（搜索空間相當大）是多麼合適。繪製圖形的遺傳算法？位置分配問題

我有一個有向圖（流程圖），我想以一種非常清晰，易於理解且易於通過人眼來閱讀的方式在2D平面上進行可視化。因此;我將爲每個頂點分配（x，y）位置。我想使用模擬退火，遺傳算法解決這個問題的，或者任何這樣的方法，則可以建議

輸入：圖G =（V，E）
輸出：一組分配， {(xi, yi) for each vi in V}。換句話說，每個頂點將被分配一個位置（x，y），其中座標是所有整數，並且> = 0.

這些是我將用來判斷解決方案的標準（我歡迎任何建議）：

編號相交邊緣應該是最小的，
在一個方向上所有的邊緣流動（即，從左至右），
高角分辨率（由兩個邊緣上相同的形成入射到最小角度頂點），
小a至少重要。

此外;我有一個初始配置（指定頂點的位置），由手工完成。這是非常混亂，這就是爲什麼我試圖自動化過程。

我的問題是，

將如何明智的是去當地的搜索技術？它會產生預期結果的可能性有多大？
我應該從什麼開始？模擬退火，遺傳算法還是別的？
我應該在開始時隨機播種或使用最初的配置開始？或者，如果你已經知道類似的實現/僞代碼/東西，請指向我。

任何幫助將不勝感激。謝謝。

編輯：它不需要很快 - 而不是實時。此外; | V | =〜200，每個頂點平均有大約1.5個出邊。該圖沒有斷開連接的組件。它確實涉及週期。

來源

2011-07-12 Murat Derya Özen

繪圖圖表的主要任務是什麼？在圖形繪圖上已經有很多研究，您應該閱讀首先...如果這不是你的主要任務，那麼只需使用一些現有的庫來完成繪圖部分。 – Szabolcs

有你發現了一個解決方案，如何在基因中存儲座標和邊緣以創建不那麼複雜的遺傳算法？我的意思是你決定把它作爲一個字符串存儲爲1,0值，或者你已經找到了一個解決方案如何存儲座標和邊緣？ – kuldarim

因爲graphviz是領先的開源圖形可視化工具之一，所以我建議你看看http://www.graphviz.org/Theory.php。

根據賦值是什麼，也許完全可以使用graphviz來完成可視化。

來源

2011-07-12 12:32:42

http://oreilly.com/catalog/9780596529321 - 在本書中，您可能會發現遺傳算法實現2D圖形的精細可視化。

在類似的情況下，我更喜歡使用遺傳算法。您也可以從隨機初始化人羣開始 - 根據我經歷幾次迭代後的經驗，您會發現相當好（但也不是最好的）解決方案。另外，使用java，你可能會使用這種算法（孤島戰略） - 這是相當有效的改進。

另外我想諮詢你差異演化算法。根據我的經驗 - 它比遺傳優化更快地找到解決方案。

來源

2011-07-12 12:35:14 stemm

This paper是一個很好的概述了各種方法。 Roberto Tomassia's book也是一個不錯的選擇。

來源

2011-07-12 12:38:35 MPG

謝謝MPG。這篇論文非常好，但它並沒有指向一個可靠的算法。這只是一個概述。此外;這本書的評論認爲它大部分都是理論性的而非實際的實現。 –

要回答你的第一個問題，我必須說這取決於。這取決於許多不同的因素，如：

它的速度有多快需要爲（它需要實時做？）
多少頂點有
多少邊緣有比較的頂點的數量（即它是一個密集的或稀疏的圖？）

如果它需要在實時完成，然後本地搜索技術不會是最好的，因爲他們可以採取同時在獲得好結果之前運行。如果圖的大小很小，它們只會足夠快。如果從一開始就很小，那麼你不應該首先使用本地搜索。

已經有算法用於渲染圖形。問題是，這個問題在哪個地方變得太大而不能有效地發揮作用？我不知道這個問題的答案，但我相信你可以做一些研究來找出答案。

現在開始討論關於本地搜索實施的問題。

從我個人的經驗來看，模擬退火比遺傳算法更容易實現。不過，我認爲這個問題很好地轉化爲兩個設置。但我會從SA開始。

對於模擬退火，您可以從隨機配置開始。然後，您可以通過將一個或多個頂點移動一些隨機距離來隨機擾動配置。我相信你可以完成算法的細節。對於遺傳算法方法，您也可以從隨機總體開始（每個圖具有頂點的隨機座標）。突變可以像我描述的SA算法中的擾動。重組可以簡單地從父母中取出隨機頂點並在子圖中使用它們。我相信你可以填補空白。

總結：只有當您的圖形足夠大才能保證它，並且如果您不需要快速完成（比如說少於幾秒），就可以使用本地搜索。否則使用不同的算法。

編輯：根據您的圖形參數，我認爲您可以只使用哪一種算法最容易編碼。當V = 200時，即使是O（V^3）算法也足夠了。就我個人而言，我覺得模擬退火將是最簡單和最好的路線。

來源

2011-07-12 12:46:25 tskuzzy

謝謝tskuzzy的答案。我已經通過編輯原始帖子回答了您的問題。它不需要很快 - 不是實時的。此外; | V | =〜200，每個頂點平均有大約1.5個出邊。我會進入其他現有的方法，看看他們需要多長時間... –

相應地編輯我的答案。 – tskuzzy

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;

寫一個函數雙評估（字符串遺傳），它會給你一個滿意度。（可能基於所述多少邊相交和邊緣方向

程序：

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]); 
    } 
}

功能可按操縱可翻轉的字符串或多個比特或編碼頂點的x和y的部分的一些位或者可能完全生成一個新的遺傳字符串，或嘗試解決它內部的問題（指向邊緣）

來源

2011-07-12 12:56:21

從數值向量到位向量的轉換是不必要的。但如果你想這樣做，我會建議使用格雷碼 – stemm

繪製圖形的遺傳算法？位置分配問題

回答

相關問題