突變管道網絡優化

Question

我工作的管網優化，我代表的染色體爲一串數字如下

例如

chromosome [1] = 3 4 7 2 8 9 6 5 

，其中，每個數字代表以及並定義井之間的距離。因爲一個染色體不能複製這些孔。例如

chromosome [1]' = 3 4 7 2 7 9 6 5 (not acceptable) 

什麼是可以處理這種表示的最佳突變？提前致謝。

Answer 1

不能說「最好」，但我用於類圖問題的一個模型是：對於每個節點（井號），計算整個人口中相鄰節點/井的集合。例如，

population = [[1,2,3,4], [1,2,3,5], [1,2,3,6], [1,2,6,5], [1,2,6,7]] 
adjacencies = { 
    1 : [2]   , #In the entire population, 1 is always only near 2 
    2 : [1, 3, 6] , #2 is adjacent to 1, 3, and 6 in various individuals 
    3 : [2, 4, 5, 6], #...etc... 
    4 : [3]   , 
    5 : [3, 6]  , 
    6 : [3, 2, 5, 7], 
    7 : [6]   
} 
choose_from_subset = [1,2,3,4,5,6,7] #At first, entire population 

然後創建一個新的個人/網絡：

choose_next_individual(adjacencies, choose_from_subset) : 
    Sort adjacencies by the size of their associated sets 
    From the choices in choose_from_subset, choose the well with the highest number of adjacent possibilities (e.g., either 3 or 6, both of which have 4 possibilities) 
    If there is a tie (as there is with 3 and 6), choose among them randomly (let's say "3") 
    Place the chosen well as the next element of the individual/network ([3]) 
    fewerAdjacencies = Remove the chosen well from the set of adjacencies (see below) 
    new_choose_from_subset = adjacencies to your just-chosen well (i.e., 3 : [2,4,5,6]) 
    Recurse -- choose_next_individual(fewerAdjacencies, new_choose_from_subset) 

的想法是，具有大量的鄰接節點已經成熟重組（因爲人口沒有收斂的，如，1-> 2），較低的「鄰接計數」（但非零）意味着收斂，並且零鄰接計數（基本上）是突變。

爲了表明樣品運行..

#Recurse: After removing "3" from the population 
new_graph = [3] 
new_choose_from_subset = [2,4,5,6] #from 3 : [2,4,5,6] 
adjacencies = { 
    1: [2]    
    2: [1, 6]  , 
    4: []   , 
    5: [6]   , 
    6: [2, 5, 7] , 
    7: [6]   
} 


#Recurse: "6" has most adjacencies in new_choose_from_subset, so choose and remove 
new_graph = [3, 6] 
new_choose_from_subset = [2, 5,7]  
adjacencies = { 
    1: [2]    
    2: [1]   , 
    4: []   , 
    5: []   , 
    7: []   
} 


#Recurse: Amongst [2,5,7], 2 has the most adjacencies 
new_graph = [3, 6, 2] 
new_choose_from_subset = [1] 
adjacencies = { 
    1: []    
    4: []   , 
    5: []   , 
    7: []   
] 

#new_choose_from_subset contains only 1, so that's your next... 
new_graph = [3,6,2,1] 
new_choose_from_subset = [] 
adjacencies = { 
    4: []   , 
    5: []   , 
    7: []   
] 

#From here on out, you'd be choosing randomly between the rest, so you might end up with: 
new_graph = [3, 6, 2, 1, 5, 7, 4] 

完整性檢查？ 3->6出現在原始1x中，6->2出現2x，2->1出現5x，1->5出現0，5->7出現0,7->4出現0.因此，您保留了最常見的鄰接關係（2-> 1）和另外兩個「可能有意義」的鄰接關係。否則，你在解決方案空間嘗試新的鄰接關係。

更新：最初我忘記了遞歸時的臨界點，您選擇了最連接的到剛剛選擇的節點。這對保持高適應性鏈條至關重要！我已經更新了描述。