遺傳算法 - 路徑的交叉和變異運算符

Question

我想知道是否有人知道任何直觀的交叉和變異操作符在圖中的路徑？謝謝！

Answer 1

嗯..這是一個非常困難的問題，人們爲此寫論文，但仍然沒有正確的答案。

一般規則是「這一切都取決於你的域名」。

有一些通用GA庫會爲您做一些工作，但爲了獲得最佳效果，建議您自己實施GA操作，特別是針對您的域。

您可能在Theoretical CS上有更多回答，但您需要更多地擴展您的問題並添加有關您的任務和域的更多詳細信息。

更新： 所以你有一個圖。在GA術語中，通過圖的路徑表示個體，路徑中的節點將是染色體。 在這種情況下，我會說突變可以表示爲與原始位置之間的路徑偏差 - 其中一個節點將移動到某處，並調整路徑以使路徑中的開始值和結束值保持不變。

突變可能會導致無效的個人。在這種情況下，您需要做出決定：允許無效的決策，並希望它們能夠融合到一些尚未解決的解決方案中。或者當場殺死他們。當我和GA一起工作時，我確實允許使用無效解決方案，並在健身方面增加「不適合」值。一些研究人員認爲這可以幫助廣泛探索解決方案空間。

交叉只能發生在彼此交叉的路徑上：在交叉點上，將路徑的剩餘部分與父母交換。

請記住，交叉有多種方式：個人可以交叉在多個點或只在一個。在圖形的情況下，您可以有多個交叉點，並且這自然會導致多個子圖。

正如我之前所說，這樣做沒有對錯的方法，但只有通過試驗才能找到最好的方法。

Answer 2

問題有點老，但問題似乎並沒有過時或解決，所以我認爲我的研究仍然可能對某人有所幫助。在TSP問題中，每個突變都是有效的（這是因爲染色體代表訪問固定節點的順序 - 交換順序，然後始終可以創建有效結果），但在TSP問題中相當微不足道最短路徑或最佳路徑，其中染色體是精確的路徑表示，這不適用，並不明顯。所以這裏是我如何處理使用遺傳算法求解最優路徑的問題。

對於交叉，有幾個選項：

1. 對於有至少一個公共點路線（除了開始和結束點） - 發現在這個地方所有共同點和交換子路徑交叉

   的

   父1：51 33 41 7 12 91 60

   父2：51 9 33 25 12 43 15 60

   潛在過境點爲和。我們可以得到以下兒童：51 9 33 41 7 12 43 15 60和51 33 25 12 91 60，這是使用這兩個交叉點的交叉結果。

2. 當沒有共同點，請從每個父母任意兩點並連接兩條路線（你可以使用，要麼隨意穿越，回溯或像A *或定向搜索啓發式搜索）。現在這條路可能被視爲交叉路徑。爲了更好地理解，見下面兩種交叉方法圖片：

   看到http://i.imgur.com/0gDTNAq.png

   黑色和灰色的路徑父母，粉紅色和橙色的路徑是 孩子，綠點是一個交叉的地方，紅色分是開始 和結束節點。第一個圖顯示第一種交叉點，第二個圖顯示另一個交叉點的實例。

對於突變，也有幾個選項。一般來說，對於具有平均密度的圖而言，像交換節點順序或添加隨機節點這樣的虛擬變異實際上是無效的。因此，下面是保證有效突變的方法：

1. 從路徑中隨機取兩個點，並用這兩個節點之間的隨機路徑替換它們。

   染色體：51 33 41 7 12 91 60，隨機點：和，無規/最短然後之間的路徑：33 29 71 12，突變的染色體：51 33 29 71 12 91 60

2. 查找路徑隨機點，清除，並連接其鄰居（真的非常相似，第一個）

3. 從路徑查找隨機點，並找到隨機路徑到它的鄰居

4. 嘗試從一些隨機選擇的點減去路徑，直到到達初始路由上的任何點（第一種方法的輕微修改）。

   看到http://i.imgur.com/19mWPes.png

   每個圖表對應於適當的順序每個突變方法。在上一個例子中，橙色路徑是替換突變點（綠色節點）之間的原始路徑的路徑。

注：這個方法顯然可以有性能缺陷的情況下，尋找替代subroute時（使用隨機或啓發式方法）將停留在一些地方或找到很長的和無用的子路徑，所以考慮限制突變執行時間或試驗次數。

對於我而言，這是發現在同時保持節點重量小於給定的約束和最大化頂點的權重之和方面的最優路徑，這些方法是非常有效的，並給予了良好的效果。如果您有任何問題，請隨時提問。此外，對不起我的MS油漆技能;）

更新

一個很大的提示：我基本上是用我在執行這種方法，但沒有使用隨機路徑生成的一個大缺點。我決定用最短路徑遍歷隨機挑選點（一個或多個）切換到半隨機路徑產生 - 這是很多比較有效（但顯然未必適用於所有的問題）。