前言
在用基于DEAP設(shè)計的遺傳算法求解函數(shù)極值后，我們想要進(jìn)一步解決一些更加困難點(diǎn)的問題。TSP問題就是很好的實驗算法的舞臺。本文將會介紹以下內(nèi)容：
- TSP問題的定義與運(yùn)用遺傳算法求解
- 對比遺傳算法與貪心算法及其改進(jìn)型在用時和精確度兩方面的表現(xiàn)
- 探討可能的改進(jìn)方向
TSP問題的定義與GA求解
TSP問題簡介
旅行商問題（Traveling Salesman Problem(TSP)）描述：
給出
個不同的城市
以及城市兩兩之間的距離
，求一個商人從某個城市出發(fā)，走遍所有城市并回到起點(diǎn)所需要經(jīng)過的路徑總距離為多少？
即求解一個路徑（也即城市的排列）
，使得
取最小值
如果對兩個城市有
，那該問題被稱為對稱旅行商問題(Symmetric Traveling Salesman Problem(STSP))。否則就是非對稱旅行商問題(ATSP)。
盡管描述很簡單，TSP問題是一個非常經(jīng)典而重要的問題：
- 自從1930年代 Merrill M.Flood在學(xué)界引起了對該問題的重視以來，學(xué)者們已經(jīng)從圖論、組合優(yōu)化、線性規(guī)劃等不同角度對該問題進(jìn)行了深入廣泛的研究。
- TSP問題的一個特殊性在于它必然存在可以找到的最優(yōu)解（通過窮舉法一定能在
時間內(nèi)找到該最優(yōu)解），但是在計算復(fù)雜度方面它是一個經(jīng)典的NP-hard問題。因而快速有效尋找TSP的最優(yōu)解仍然是個有吸引力的問題。
- 在實際應(yīng)用方面，它可以被視為物流調(diào)度，交通規(guī)劃，芯片布線優(yōu)化等等問題的抽象簡化。
TSP問題的遺傳算法求解
通過之前對DEAP的解讀，我們很容易就能基于該框架，寫出一個求解TSP問題的GA算法。在TSPLib上測試該算法之前，我們先在隨機(jī)生成的數(shù)據(jù)集上進(jìn)行測試與改進(jìn)：
## 環(huán)境設(shè)置
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
from scipy.spatial import distance
from deap import creator, base, tools, algorithms
import random
params = {
'font.family': 'serif',
'figure.figsize': [4.0, 3.0],
'figure.dpi': 300,
'savefig.dpi': 300,
'font.size': 12,
'legend.fontsize': 'small'
}
plt.rcParams.update(params)
#--------------------------------
## 定義TSP中的基本元素
# 用[n,2]的np.array存儲城市坐標(biāo)；每行存儲一個城市
def genCity(n, Lb = 100 ,Ub = 999):
# 生成城市坐標(biāo)
# 輸入：n -- 需要生成的城市數(shù)量
# 輸出: nx2 np array 每行是一個城市的[X,Y]坐標(biāo)
np.random.seed(42) # 保證結(jié)果的可復(fù)現(xiàn)性
return np.random.randint(low = Lb, high = Ub, size=(n,2))
# 計算并存儲城市距離矩陣
def cityDistance(cities):
# 生成城市距離矩陣 distMat[A,B] = distMat[B,A]表示城市A，B之間距離
# 輸入：cities -- [n,2] np array， 表示城市坐標(biāo)
# 輸出：nxn np array， 存儲城市兩兩之間的距離
return distance.cdist(cities, cities, 'euclidean')
def completeRoute(individual):
# 序列編碼時，缺少最后一段回到原點(diǎn)的線段
return individual + [individual[0]] # 不要用append
# 計算給定路線的長度
def routeDistance(route):
# 輸入：
# route -- 一條路線，一個sequence
# 輸出：routeDist -- scalar，路線的長度
if route[0] != route[-1]:
route = completeRoute(route)
routeDist = 0
for i,j in zip(route[0::],route[1::]):
routeDist += cityDist[i,j] # 這里直接從cityDist變量中取值了，其實并不是很安全的寫法，單純偷懶了
return (routeDist), # 注意DEAP要求評價函數(shù)返回一個元組
# 路徑可視化
def plotTour(tour, cities, style = 'bo-'):
if len(tour)>1000: plt.figure(figsize = (15,10))
start = tour[0:1]
for i,j in zip(tour[0::], tour[1::]):
plt.plot([cities[i,0],cities[j,0]], [cities[i,1],cities[j,1]], style)
plt.plot(cities[start,0],cities[start,1],'rD')
plt.axis('scaled')
plt.axis('off')
#--------------------------------
## 設(shè)計GA算法
nCities = 30
cities = genCity(nCities) # 隨機(jī)生成nCities個城市坐標(biāo)
# 問題定義
creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 最小化問題
creator.create('Individual', list, fitness=creator.FitnessMin)
# 定義個體編碼
toolbox = base.Toolbox()
toolbox.register('indices', random.sample, range(nCities), nCities) # 創(chuàng)建序列
toolbox.register('individual', tools.initIterate, creator.Individual, toolbox.indices)
# 生成族群
N_POP = 100
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(N_POP)
# 注冊所需工具
cityDist = cityDistance(cities)
toolbox.register('evaluate', routeDistance)
toolbox.register('select', tools.selTournament, tournsize = 2)
toolbox.register('mate', tools.cxOrdered)
toolbox.register('mutate', tools.mutShuffleIndexes, indpb = 0.2)
# 數(shù)據(jù)記錄
stats = tools.Statistics(key=lambda ind: ind.fitness.values)
stats.register('avg', np.mean)
stats.register('min', np.min)
# 調(diào)用內(nèi)置的進(jìn)化算法
resultPop, logbook = algorithms.eaSimple(pop, toolbox, cxpb = 0.5, mutpb = 0.2, ngen = 200, stats = stats, verbose = True)
本次運(yùn)行的結(jié)果為：
gen nevals avg min
0 100 14201 11314.5
1 58 13675.4 11505.4
2 58 13410.6 11300.1
3 60 13174.9 11064.3
4 57 12962.4 10907.4
5 63 12796.9 10470.6
6 66 12585.8 10644.2
7 64 12245.2 10232
8 68 12067 9592.99
9 62 12059.6 9592.99
10 70 12206.6 9592.99
11 57 11908.6 9496.14
12 42 11468.3 9496.14
13 60 11393.1 9062.07
14 47 11109.7 9062.07
15 63 11123.8 9062.07
16 58 10923.4 8926.45
17 61 10995.1 8545.11
18 58 11174.7 9062.07
19 76 11091.9 9062.07
20 53 10993.1 8888.39
21 58 11016.3 8842.55
22 52 10914.2 8842.55
23 47 10745.8 8659.72
24 54 10526 8659.72
25 60 10870.4 8717.75
26 56 11078.5 8717.75
27 66 10904.5 8717.75
28 55 10796.9 8717.75
29 58 10840.5 8568.54
30 70 10783.7 8714.81
31 75 10945.5 8714.81
32 62 10906.3 8714.81
33 55 10883.5 8714.81
34 61 10768.4 8717.75
35 64 10861.7 9045.8
36 72 10839 9097.6
37 73 10819.7 8860.66
38 70 10528.5 8736.59
39 55 10250.1 8736.59
40 67 10563.3 8513.88
41 50 10602.1 8513.88
42 59 10518 8513.88
43 61 10596.9 8931.09
44 57 10780 9109.96
45 67 10757.6 8771.09
46 60 10504.8 8771.09
47 63 10421.2 8771.09
48 69 10526.5 8771.09
49 58 10442.3 8691.01
50 65 10535.4 8771.09
51 62 10683 8771.09
52 68 10532.6 8804.67
53 54 10488.4 8804.67
54 62 10583.1 8408.69
55 53 10514.8 8833.92
56 57 10524.8 9052.01
57 65 10599.3 8732.31
58 58 10227.1 8732.31
59 62 10358.2 8732.31
60 66 10532 8730.2
61 51 10348.5 8671.23
62 67 10542 8671.23
63 60 10584.6 8663.02
64 57 10417.8 8522.64
65 58 10552.6 8522.64
66 61 10413.8 8367.42
67 66 10422.5 8671.23
68 57 10559.6 8671.23
69 58 10263.6 8285.6
70 60 10463.1 8285.6
71 65 10499 8285.6
72 55 10330.4 8529.22
73 67 10350.1 8576.73
74 73 10271 7570.84
75 51 10252.9 8289.29
76 60 10343.2 8112.17
77 61 9767.09 7565.35
78 57 9751.91 7565.35
79 50 9684.03 7565.35
80 53 9808.93 7565.35
81 59 9509.4 7565.35
82 58 9758.84 7565.35
83 65 9852.58 6437.84
84 56 9866.73 6437.84
85 55 9572.01 6298.22
86 61 9217.73 6298.22
87 63 9311.42 6298.22
88 61 9057.95 6298.22
89 63 9103.11 6298.22
90 66 9116.68 6298.22
91 51 9024.19 6454.46
92 45 8683.05 6454.46
93 64 8584.42 6709.33
94 59 8942 6709.33
95 64 9082.05 6709.33
96 71 9037.46 6709.33
97 60 9154.49 6933.71
98 67 9384.12 6933.71
99 75 9682.95 7115.49
100 61 9300.16 7266.03
101 50 9035.16 7266.03
102 52 8740.91 6960.39
103 62 9063.54 7145.63
104 62 9220.89 7252.07
105 57 9210.75 6956.42
106 52 9228 6956.42
107 62 9095.18 6956.42
108 55 8764.35 6956.42
109 65 8961.6 6956.42
110 62 9029.89 6911.78
111 56 8757.81 6558.41
112 75 8436.12 6261.76
113 48 8489.56 6261.76
114 56 8379.92 6261.76
115 50 8567.57 6348.63
116 58 8505.19 6405.25
117 56 8485.4 5930.98
118 58 8689.05 5930.98
119 68 8504.73 6167.82
120 70 8123.5 6167.82
121 58 7992.72 6128.46
122 60 8441.54 6128.46
123 59 8270.66 6128.46
124 58 7944.21 5924.28
125 61 8259.92 5924.28
126 68 7954.45 5924.28
127 63 7913.86 6063.51
128 62 8507.67 6063.51
129 52 8079.8 6063.51
130 62 8180.93 5693.15
131 79 8299 6063.51
132 60 8070.93 6255.88
133 70 8149.17 6048.78
134 54 8125.64 6268.16
135 65 8161.05 6080.82
136 62 8093.43 6221.13
137 54 8046.15 6221.13
138 67 8064.43 5715.42
139 57 8108.32 5447.17
140 63 7910.74 5362.81
141 56 8040.57 5362.81
142 61 7936.12 5362.81
143 59 7951.14 5362.81
144 60 8222.17 5362.81
145 70 7815.39 5362.81
146 57 7660.78 5362.81
147 61 7545.06 5362.81
148 62 7619.84 5362.81
149 51 7387.11 5362.81
150 66 7396.11 5362.81
151 57 7224.2 5362.81
152 62 7062.38 5280.67
153 60 7450.55 5280.67
154 57 7058.69 5280.67
155 51 7452.15 5218.92
156 64 7332.41 5280.67
157 55 7261.36 5280.67
158 53 6949.59 5280.67
159 51 7034.86 5280.67
160 57 6985.01 5280.67
161 67 6554.21 5280.67
162 62 6671.5 5280.67
163 61 6938.98 5121.92
164 57 7247.23 5121.92
165 69 7018.4 5039.78
166 67 6764.25 5039.78
167 61 7172.14 5039.78
168 58 7172.76 5039.78
169 48 6760.36 5039.78
170 66 6591.99 5039.78
171 59 7039.59 5039.78
172 51 6917.34 5039.78
173 60 6631.73 5039.78
174 58 6683.84 4997.91
175 65 6559.69 4997.91
176 69 6908.49 4910.62
177 61 7016.93 4910.62
178 60 6772.34 4910.62
179 58 6492.51 4757.57
180 67 6389.65 4757.57
181 49 6018.27 4757.57
182 55 6364.89 4757.57
183 68 6781.2 4757.57
184 63 6500.91 4757.57
185 60 6451.73 4757.57
186 73 7277.07 4757.57
187 57 6232.07 4757.57
188 74 6360.29 4757.57
189 60 6608.44 4757.57
190 52 6222.14 4757.57
191 51 6482.11 4757.57
192 52 6118.93 4732.05
193 57 6170.32 4732.05
194 65 6303.12 4732.05
195 52 6060.32 4732.05
196 57 6133.72 4757.57
197 60 6120.28 4757.57
198 66 5602.95 4757.57
199 68 6006.72 4757.57
200 60 6057.53 4757.57
對結(jié)果進(jìn)行可視化：
tour = tools.selBest(resultPop, k=1)[0]
tourDist = tour.fitness
tour = completeRoute(tour)
print('最優(yōu)路徑為:'+str(tour))
print('最優(yōu)路徑距離為：'+str(tourDist))
plotTour(tour, cities)
可視化結(jié)果：
最優(yōu)路徑為:[7, 15, 0, 14, 12, 6, 17, 25, 8, 27, 21, 20, 23, 24, 18, 13, 11, 1, 10, 29, 22, 9, 3, 28, 4, 5, 19, 26, 16, 2, 7]
最優(yōu)路徑距離為：(4757.574098243668,)
從肉眼可見的角度上，這個解距離最優(yōu)解還是有差距的。
30cities_SGA
對訓(xùn)練過程可視化如下：
fitnessVSiterations_SGA
算法對比與分析
nnTSP + 2OPT
最近鄰算法：nn TSP
窮舉法能夠保證求出TSP問題的最優(yōu)解，但是其耗時會隨著問題規(guī)模的擴(kuò)大而劇增。假設(shè)求解一個規(guī)模為10的TSP問題需要1秒，那么可以估計對于更大規(guī)模問題，窮舉法所需要的時間：
| 問題規(guī)模（城市數(shù)量） | 求解時間 |
|---|---|
| 10 | 1 秒 |
| 11 | 11 秒 |
| 12 | 2.2 分 |
| 13 | 28.6 分 |
| 14 | 6.7 小時 |
| 15 | 100 小時 |
| 16 | 1601 小時 |
而在應(yīng)用于實際時，TSP問題的規(guī)模往往成千上萬，用窮舉法求解顯然不現(xiàn)實，因此我們需要更加有效的求解方法。
在考慮問題時，一般算法設(shè)計的策略有以下幾種:
- 暴力破解：列出所有可能性，一一嘗試并最終給出答案；
- 近似算法：如果問題的最優(yōu)解或準(zhǔn)確解很難給出，那么可以嘗試找出問題的次優(yōu)解或近似解；
- 貪心算法：對于多步驟算法，可以在每一步都取局部最優(yōu)，并重復(fù)直到問題解決；
- 迭代算法：用一個算法求解，另一個算法來提升解的有效性；
- 集合算法：在算法集中準(zhǔn)備一系列算法，依次嘗試并取最好結(jié)果；
- 分而治之：講一個問題劃分為一系列子問題，依次求解后組合成最后結(jié)果；
- 站在巨人肩膀上：參考已有算法（just google it!）。
強(qiáng)烈推薦Peter Norvig的[這篇文章](https://nbviewer.jupyter.org/url/norvig.com/ipython/TSP.ipynb)，其中詳細(xì)分析了TSP問題的各種求解思路和python代碼實現(xiàn)。
最近鄰算法就是同時包含了近似算法和貪心算法思想的一種算法。用于求解TSP問題時，nnTSP可以描述為：
- 從某個城市出發(fā)；
- 移動到離現(xiàn)在所處城市最近的且沒有訪問過的鄰居去；
其實現(xiàn)還是非常簡單的：
# 在未訪問列表中尋找當(dāng)前位置的最近鄰
def nearestNeighbor(cityDist, currentPos, unvisited):
# 輸入：cityDist -- [n,n] np array,記錄城市間距離
# currentPos -- 一個數(shù)字，指示當(dāng)前位于的城市
# unvisited -- 一個列表，指示可選鄰居列表
# 輸出：
# nextToVisit -- 一個數(shù)字，給出最近鄰的index
# dist -- 一個數(shù)字，給出到最近鄰的距離
neighborDist = cityDist[currentPos,unvisited]
neighborIdx = np.argmin(neighborDist)
nextToVisit = unvisited[neighborIdx]
dist = neighborDist[neighborIdx]
return nextToVisit, dist
# 用貪婪算法求解TSP
def nnTSP(cities, start = 0):
cityList = list(range(cities.shape[0]))
tour = [start]
unvisited = cityList.copy()
unvisited.remove(start)
currentPos = start
tourDist = 0
cityDist = cityDistance(cities)
while unvisited:
# 當(dāng)unvisited集合不為空時，重復(fù)循環(huán)
# 找到當(dāng)前位置在unvisited中的最近鄰
nextToVisit, dist = nearestNeighbor(cityDist, currentPos, unvisited)
tourDist += dist
currentPos = nextToVisit
tour.append(nextToVisit)
unvisited.remove(nextToVisit)
# 重新回到起點(diǎn)
tour.append(start)
tourDist += cityDist[currentPos, start]
return tour,tourDist
在上面相同的問題上應(yīng)用nnTSP求解：
tour,tourDist = nnTSP(cities)
print('nnTSP尋找到的最優(yōu)路徑為：' + str(tour))
print('nnTSP尋找到最優(yōu)路徑長度為：' + str(tourDist))
plotTour(tour, cities)
結(jié)果為：
nnTSP尋找到的最優(yōu)路徑為：[0, 15, 7, 14, 2, 16, 19, 26, 5, 4, 9, 28, 3, 22, 29, 1, 11, 13, 10, 12, 6, 21, 20, 27, 25, 17, 8, 23, 18, 24, 0]
nnTSP尋找到最優(yōu)路徑長度為：5156.612343174932
30cities_nnTSP
repNNTSP
從nnTSP的算法設(shè)計上可以看到，該算法求出的最優(yōu)路徑是和起點(diǎn)相關(guān)的，對于不同的起點(diǎn)，會產(chǎn)生不同的最優(yōu)路徑。因而一個簡單的改進(jìn)思路是我們以每個城市為起點(diǎn)進(jìn)行一次nnTSP搜索，然后在所有得到的路線中選取最優(yōu)的。
代碼實現(xiàn)如下：
# 重復(fù)nnTSP但是每次用不同的起點(diǎn)，挑選最佳的結(jié)果
def repNNTSP(cities):
optimizedRoute = [] # 最優(yōu)路徑
minDistance = np.Inf # 最優(yōu)路徑長度
for i in range(len(cities)):
tour,tourDist = nnTSP(cities, start = i)
if tourDist < minDistance:
optimizedRoute = tour
minDistance = tourDist
return optimizedRoute, minDistance
結(jié)果為：
repNNTSP尋找到的最優(yōu)路徑為：[20, 21, 27, 25, 17, 8, 15, 0, 7, 14, 2, 16, 19, 26, 5, 4, 9, 28, 3, 22, 29, 1, 11, 13, 10, 12, 6, 23, 18, 24, 20]
repNNTSP尋找到的最優(yōu)路徑長度為：4529.115576833992
30cities_repnnTSPtour
如預(yù)期一般，這個結(jié)果比nnTSP更優(yōu)秀，而且感覺上距離最優(yōu)解已經(jīng)很接近了。
2-OPT
在nnTSP給出的結(jié)果中，包含了一些交叉。這些交叉會導(dǎo)致路徑長度的增加：
cross
可以看到當(dāng)出現(xiàn)X交叉時，從三角不等式可知，兩根紅線表示的長度一定小于兩根藍(lán)線，故而解開這樣的交叉一定能減少路徑長度。
我們可以考慮運(yùn)用迭代思想，在使用nnTSP得到一條可行的路徑之后，對路徑進(jìn)行優(yōu)化，從而得到比nnTSP更優(yōu)，同時比窮舉法更快的解法。
這里我們可以在nnTSP建立了可行路徑之后，選用2-Opt作為優(yōu)化算法，其步驟為：
- 設(shè)路徑
長度為
和終點(diǎn)
；
- 對位于
之間的子路徑
進(jìn)行反轉(zhuǎn)；
- 如果翻轉(zhuǎn)后的路徑較優(yōu)，將其設(shè)置為最優(yōu)路徑
# 2OPT
def opt(cityDist, route, k=2):
# 用2-opt算法優(yōu)化路徑
# 輸入：cityDist -- [n,n]矩陣，記錄了城市間的距離
# route -- sequence，記錄路徑
# 輸出： 優(yōu)化后的路徑optimizedRoute及其路徑長度
nCities = len(route) # 城市數(shù)
optimizedRoute = route # 最優(yōu)路徑
minDistance = routeDistance(route) # 最優(yōu)路徑長度
for i in range(1,nCities-2):
for j in range(i+k, nCities):
if j-i == 1:
continue
reversedRoute = route[:i]+route[i:j][::-1]+route[j:]# 翻轉(zhuǎn)后的路徑
reversedRouteDist = routeDistance(reversedRoute)
# 如果翻轉(zhuǎn)后路徑更優(yōu)，則更新最優(yōu)解
if reversedRouteDist < minDistance:
minDistance = reversedRouteDist
optimizedRoute = reversedRoute
return optimizedRoute, minDistance
用2-OPT迭代優(yōu)化nnTSP:
optimizedRoute, minDistance = opt(cityDist, tour)
print('nnTSP + 2OPT優(yōu)化后的最優(yōu)路徑為：' + str(optimizedRoute))
print('nnTSP + 2OPT優(yōu)化后的最優(yōu)路徑長度為：' + str(minDistance))
plotTour(optimizedRoute, cities)
結(jié)果：
nnTSP + 2OPT優(yōu)化后的最優(yōu)路徑為：[0, 15, 7, 14, 2, 16, 19, 26, 5, 4, 9, 28, 3, 22, 29, 1, 11, 13, 10, 12, 24, 18, 23, 8, 17, 25, 27, 20, 21, 6, 0]
nnTSP + 2OPT優(yōu)化后的最優(yōu)路徑長度為：(4847.935437722887,)
30cities_nnTSP_2OPT
可以看到在應(yīng)用2-OPT之后，相比優(yōu)化之前，路徑長度減少了308.677；但是另一方面，通過簡單的對sub-tour進(jìn)行翻轉(zhuǎn)并沒有能完全uncross所有的交叉。
這個優(yōu)化方法同樣可以用于repNNTSP，來檢查是否能找到更優(yōu)解。用2-OPT迭代優(yōu)化repNNTSP的代碼:
repnnTSPtourOptimized, repnnTSPtourDistOptimized = opt(cityDist, repnnTSPtour, 2)
print('repnnTSPtour + 2OPT優(yōu)化后的最優(yōu)路徑為：' + str(repnnTSPtourOptimized))
print('repnnTSPtour + 2OPT優(yōu)化后的最優(yōu)路徑長度為：' + str(repnnTSPtourDistOptimized))
plotTour(repnnTSPtourOptimized, cities)
結(jié)果：
repnnTSPtour + 2OPT優(yōu)化后的最優(yōu)路徑為：[20, 21, 27, 25, 8, 17, 15, 0, 7, 14, 2, 16, 19, 26, 5, 4, 9, 28, 3, 22, 29, 1, 11, 13, 10, 12, 6, 23, 18, 24, 20]
repnnTSPtour + 2OPT優(yōu)化后的最優(yōu)路徑長度為：(4479.933406593657,)
30cities_repnnTSPtour_2OPT
這個結(jié)果看起來已經(jīng)非常像最優(yōu)解了：路徑之間沒有交叉，干凈利落的沿著各點(diǎn)形成的convex hull游走。
算法對比
用時
在筆者的工作站上不那么精確地分別測試幾種算法在求解規(guī)模為30的TSP時的耗時：
在SGA種群規(guī)模為100，進(jìn)化200代時，通常的用時在700ms左右：
707 ms ± 6.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
而nnTSP的用時為：
142 μs ± 5.05 μs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
repNNTSP則不出所料是nnTSP的大約30倍：
4.21 ms ± 61.8 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
而作為迭代改進(jìn)算法的2-Opt在一條路線上的用時為：
2.64 ms ± 18.8 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
總結(jié)算法的耗時：
| 問題規(guī)模 | SGA | nnTSP | repNNTSP | 2-OPT |
|---|---|---|---|---|
| 30 | 707 ms | 0.142 ms | 4.21 ms | 2.64 ms |
| 100 | 1.76 s | 0.727 ms | 68.3 ms | 2.85 ms |
| 300 | 4.71 s | 3.95 ms | 1.19 s | 2.87 ms |
| 500 | 7.63 s | 9.6 ms | 4.86 s | 2.71 ms |
| 1000 | 35.9 s | 34.7 ms | 15.2 s | 2.64 ms |
time_consumption
精度
由于遺傳算法并非每次都能穩(wěn)定收斂于一個值，此處列出的解是5次計算所得的均值
| 問題規(guī)模 | SGA | nnTSP | repNNTSP | nnTSP+2-OPT | repNNTSP+2-OPT |
|---|---|---|---|---|---|
| 30 | 5156.61234 | 4529.11558 | 4847.93543 | 4479.93341 | |
| 100 | 9597.18163 | 8664.28408 | 9388.79648 | 8532.54589 | |
| 300 | 14958.54994 | 14753.59721 | 14033.02485 | 13914.14821 |
為了在速度上稍有競爭力，只有200代迭代的情況下，SGA往往還沒有收斂到最佳，波動還是相對較大的。但是規(guī)模問題越大，SGA收斂需要的迭代步數(shù)越多，強(qiáng)行在200步結(jié)束迭代的結(jié)果就是獲取的解毫無競爭力。
小結(jié)
在隨機(jī)生成的TSP問題中，我們的SGA基本上被其他算法吊打：
- SGA需要的時間遠(yuǎn)大于nnTSP和repNNTSP；而且它對問題的規(guī)模更加敏感，在大規(guī)模問題上想要收斂到滿意的解需要更多迭代步與更大的種群，這又會造成計算時間進(jìn)一步增加；
- 可能的改進(jìn)方向之一是加入環(huán)境選擇而不是用生成的子代完整替代父代，保證留下精英族群，來加速收斂；
- 可能的改進(jìn)方向之二是對種群規(guī)模、迭代步數(shù)、交叉和突變概率等超參數(shù)進(jìn)行調(diào)參，以使算法在TSP問題上更快收斂，并且獲得更好的結(jié)果；
- 可能的改進(jìn)方向之三在于利用問題特性，在SGA的基礎(chǔ)上加入局部搜索算法，例如用2-OPT改善精英解；
- 下一期將會試著按照這三個方向進(jìn)行SGA的改進(jìn)。
