我正在嘗試開發一種遺傳算法，它將找到最有效的方式來連接指定位置處的給定數量的節點。爲遺傳算法創建「交叉」函數以改善網絡路徑
所有網絡上的節點必須能夠連接到服務器節點，必須有在網絡中沒有循環。它基本上是一棵樹。
我有一個功能，可以衡量任何給定的網絡佈局的「健身」。 阻礙我的是我無法想到一個交叉功能，它需要2個網絡結構（父母），並以某種方式混合它們來創建滿足上述條件的後代。
任何想法？
說明：每個節點都有固定的x，y座標位置。只有它們之間的路線可以改變。
首先，讓我有一個問題回答你的問題：
如果創建違反「無週期」規則和「連接到服務器」規則的網絡佈局如何適應度函數的行爲？
如果簡單地通過一個可憐的健康分數懲罰給定的網絡佈局，你不需要做任何特殊，除了採取兩種網絡佈局和跨越他們過來，有1/2的佈局A，有1/2佈局B這是一個非常基本的交叉功能，它應該可以工作。
但是，如果你是負責構建一個有效的佈局，不能依靠無效的佈局簡單地被淘汰，你需要做更多的工作。
聽起來像你需要創建一個Minimum Spanning Tree網絡。我知道這並不能真正回答你的遺傳算法問題，但這是一個很好理解的問題。兩種經典方法是Prim和Krustal。也許這些算法和它們用來選擇邊緣連接的方法可能會給你一些線索。也許基因不描述網絡，而是通過特定的邊緣連接節點的可能性？或者選擇一個節點連接下一個方法？
或者只是看看別人誰是done this before，或this。
埃米爾 - 我認爲這個想法是，每個生成的樹將包含相同的一組節點，按不同的順序排列。
也許，而不是使用基於交叉遺傳算法，你會更好用更少的仿生hill-climbing算法？定義一組交換（例如在節點之間交易孩子）以充當可能的突變，然後迭代變異並檢查您的適應度函數。與所有這類搜索的情況一樣，你很容易陷入局部最大值，所以從不同的起始位置運行很多是個好主意。
我認爲節點總是相同的，它們的連接方式各不相同。我現在可以看到，這可能是考慮它的錯誤方法。 – 2009-12-30 20:46:26
此外，你應該使用評論的第一部分的答案:) – 2009-12-30 20:46:56
哈哈，我會，但我仍然需要更多的「聲譽點」來評論其他人的解決方案。我將在未來。 :) – JohnE 2009-12-30 20:52:28
想法嘗試：在度量空間（例如3維歐幾里得空間）中編碼節點的位置。沒有「不正確的」任務，所以跨界絕不是破壞性的。從這樣的任務中，您始終可以構建最近鄰居樹，最小生成樹或類似樹。
這是一個比較普遍的想法只是例子：不樹直接編碼，編碼來自這總可以構造一棵樹的一些信息。棘手的部分是這樣做，讓孩子的樹木保持父母的重要屬性。
遺傳算法中交叉的目的是爲了潛在從一個父母與另一個父母的好的部分解決方案。在這種情況下考慮部分解決方案的一種方法可能是緊密連接節點的子樹。如果你的健身功能相對於整個樹的局部部分的小改動相當平滑，這可能是考慮交叉的有用方法。
鑑於此，交叉的一種可能的形式是以下幾點：
開始有兩個母樹，P1和P2。隨機選擇兩個節點（可能在節點之間的最小距離上進行某種強制實施），N1和N2。
上的節點到節點的基礎上，從N1根據P1的聯繫「生長」樹C1向外，同時從N2向外生長另一個樹開始P2 。不要將相同的節點添加到兩個樹 - 保持節點集完全不相交。繼續，直到所有節點被添加到C1或C2。這給了我們來自每個親本的「特徵」重組，保證爲無環的形式。
重組是通過添加附加鏈路來完成，從C1到C2，以創建新的子Ç。至於要選擇哪個鏈接，可以隨機選擇（統一或根據某種分佈），或者可以通過貪婪算法（基於某種啓發式或基於新樹的總體適應度）來選擇。
在這裏有很多很好的可能的解決方案，我希望我們從OP得到更多的反饋。 – 2010-01-06 21:41:55
您可以檢查交叉運算符，它確保您在子染色體中沒有重複節點。這些交叉運算符中的幾個是Order Crossover（OX）和Edge Crossover運算符。這種交叉運算符也有助於使用GA解決TSP問題。
之後，你將不得不檢查你是否得到任何週期或不。如果是，則生成一對新的染色體。當然這是蠻力。
那家提出了以下算法旅行商，我已經適應了成功的幾個圖形問題，早期的會議之一紙：
整個人口，計算和下降的節點進行排序連接數（換句話說，如果N0連接到N1，N2，N3，那麼它有3個連接，如果N1總是連接到N4，它只有1）。
最初，採取計數最高的節點。將此稱爲current_gene_node。 （說，N0）
LOOP： 將current_gene_node添加到您的後代。
從連接列表中刪除該節點。 （沒有周期，所以從進一步的考慮中刪除N0。）
如果current_gene_node在人口沒有任何連接，選擇人口（突變的隨機未選中節點）
否則，從該節點連接列表，以此爲基礎進行連接的流行彩票的選擇（如果current_gene_node = N0，並且連接N0是例如N1 = 50％，N2 = 30％，N3 = 20％-N1具有50％的機會成爲下一個current_gene_node）。
進入循環，直到所有的節點連接
這不是真的在直接從2位家長選擇的感基因，但它遵循選擇基於人口患病率的相同的數學壓力。所以它對我和我來說都是「足夠的遺傳」，對我來說它工作得很好:-)
你的主要任務是：編碼GA還是使用GA解決問題？如果您的任務是後者，您希望使用哪種語言進行編碼？ – 2009-12-31 11:52:35
使用GA解決問題。我正在使用Java。我已經構建了很多程序和功能。 – Meir 2009-12-31 16:04:50