目錄
- 任務要求
- 實踐
- 代碼
- 思路
- 參考
任務要求
寫論文和報告（論文流程：問題——算法——評估——結論)
實踐
擷取連結
代碼
solutionbase.py
#此為蟻群算法基線模型
import numpy as np
import random as ra
def TSP(net):
\'\'\'初始化\'\'\'
n = net.shape[0]
h = 0.1 #揮發率
m = 3 #螞蟻數量
t0 = m / TanXin(n, net) #初始資訊素濃度
a = 1
b = 2
#存儲結構
R = np.ones([m, n+1], dtype=int) #螞蟻路徑矩陣
T= np.ones([n, n]) * t0 #資訊濃度矩陣
C = np.ones(m) #路徑長度序列
global_best = float(\'inf\') #全局最優值
global_bestR = None #全局最優路徑
\'\'\'循環\'\'\'
for turn in range(50):
for k in range(m): # 螞蟻k
for p in range(n + 1):
if p == 0:
R[k][0] = ra.randint(0, n-1)
elif p == n:
R[k][n] = R[k][0]
else:
i = R[k][p - 1] # 前一個結點
js = neighbor(n, net, i)
js = list(set(js) - set(R[k][:p])) # 下一個可能節點
tjs = [T[i, j]**a * (1 / net[i, j])**b for j in js]
sum_tjs = sum(tjs)
pjs = [tj / sum_tjs for tj in tjs] # 下一個可能節點的機率
# 輪盤算法求下一個節點j
r = ra.random()
for z in range(len(pjs)):
if r <= pjs[z]:
j = js[z]
else:
r -= pjs[z]
R[k][p] = j # 把j加入k螞蟻的路徑
C[k] = sum([net[R[k][i], R[k][i+1]] for i in range(n)])
# 更新t
for i in range(n):
for j in range(n):
T[i, j] = (1-h)* T[i, j]
for k in range(m):
if j == R[k][list(R[k]).index(i)+1]:
T[i, j] += 1 / C[k]
#更新全局最優值
local_best = min(C) #局部最優值
bestk = list(C).index(local_best) #局部最優值對應的螞蟻編号
if local_best < global_best:
global_best = local_best
global_bestR = R[bestk].copy()
# \'\'\'輸出\'\'\'
# print(\'最短路徑為：\', global_best)
# print(\'最短路徑長度：\', global_bestR)
return global_best
def TanXin(n, net):
R = np.ones(n+1, dtype=int)
while True:
for p in range(n+1):
if p == 0:
R[0] = ra.randint(0, n-1)
elif p == n:
R[n] = R[0]
else:
i = R[p-1]
js = neighbor(n, net, i)
js = list(set(js)-set(R[:p]))
ljs = [net[i, j] for j in js]
j = js[ljs.index(min(ljs))]
R[p] = j
C = sum([net[R[i], R[i+1]] for i in range(n)])
if C != float(\'inf\'):
break
return C
def neighbor(n, net, i):
return [j for j in range(n) if j != i if net[i][j] != float(\'inf\')]
if __name__ == \'__main__\':
net = np.array([[float(\'inf\'), 3, 1, 2],
[3, float(\'inf\'), 5, 4],
[1, 5, float(\'inf\'), 2],
[2, 4, 2, float(\'inf\')]])
TSP(net)
solution.py
#此為蟻群算法的改進模型
\'\'\'
改進:
(1) 資訊素初始化按根據距離配置設定，加快收斂(具體使得平均值為t0,但是具體每一個值按路徑長度配置設定)
(2) 設定穩定時刻點turn0，如果在超過規定時間(y)全局最優值沒有發生變化，那麼此時為turn0時刻
turn0時刻後的資訊素揮發速率變快，蟻群産生資訊素減少，以此增加路徑選擇的發散性
具體為：資訊素保留率：(1-h) * 1 / (turn-turn0)
一隻螞蟻在(i, j)上生産的資訊素： 1 / C[k] * 1 / (turn-turn0)
(3) 設定重來時刻點turn1,如果在turn0後的一段時間(x)後全局最優值沒有發生變化，那麼此時為turn1時刻
此時重新初始化，融斷最多發生u次
\'\'\'
import numpy as np
import random as ra
def TSP(net):
\'\'\'初始化\'\'\'
n = net.shape[0]
h = 0.1 #揮發率
m = 3 #螞蟻數量
t0 = m / TanXin(n, net) #初始資訊素濃度
a = 1
b = 2
#存儲結構
R = np.ones([m, n+1], dtype=int) #螞蟻路徑矩陣
T = np.ones([n, n]) #資訊濃度矩陣
#初始化資訊濃度矩陣
sum_edge = 0
num_edge = 0
for i in range(n):
for j in range(n):
if i == j or net[i, j] == float(\'inf\'):
continue
sum_edge += 1.0 / net[i, j]
num_edge += 1;
for i in range(n):
for j in range(n):
if i == j or net[i, j] == float(\'inf\'):
continue
T[i, j] = T[i, j] * num_edge * t0 * 1 / net[i, j] / sum_edge
C = np.ones(m) #路徑長度序列
global_best = float(\'inf\') #全局最優值
global_bestR = None #全局最優路徑
#改進部分
y = 5
x = 5
u = 5
turn0times = 0 #計時器1（記錄到turn0前未變化的次數）
turn1times = 0 #計時器2 (記錄到turn0後為變化的次數)
turn1num = 0 #計數器2 (記錄重來的次數)
turn0 = None #穩定時刻點
isturn0 = False #是否到達穩定時刻點
isturn1 = True #是否到達重來時刻點
\'\'\'循環\'\'\'
turn = 0
while turn <= 50:
if isturn0:
turn1times += 1
for k in range(m): # 螞蟻k
for p in range(n + 1):
if p == 0:
R[k][0] = ra.randint(0, n-1)
elif p == n:
R[k][n] = R[k][0]
else:
i = R[k][p - 1] # 前一個結點
js = neighbor(n, net, i)
js = list(set(js) - set(R[k][:p])) # 下一個可能節點
tjs = [T[i, j]**a * (1 / net[i, j])**b for j in js]
sum_tjs = sum(tjs)
pjs = [tj / sum_tjs for tj in tjs] # 下一個可能節點的機率
# 輪盤算法求下一個節點j
r = ra.random()
for z in range(len(pjs)):
if r <= pjs[z]:
j = js[z]
else:
r -= pjs[z]
R[k][p] = j # 把j加入k螞蟻的路徑
C[k] = sum([net[R[k][i], R[k][i+1]] for i in range(n)])
#更新T
for i in range(n):
for j in range(n):
T[i, j] = (1-h)* T[i, j]
if isturn0:
T[i, j] *= 1.0 / (turn-turn0)
for k in range(m):
if j == R[k][list(R[k]).index(i)+1]:
deltaT = 1 / C[k]
if isturn0:
deltaT *= 1.0 / (turn-turn0)
T[i, j] += deltaT
#更新全局最優值
local_best = min(C) #局部最優值
bestk = list(C).index(local_best) #局部最優值對應的螞蟻編号
if local_best < global_best:
global_best = local_best
global_bestR = R[bestk].copy()
turn0times = 0
if isturn0:
isturn1 = False
else:
turn0times += 1
if turn0times == 5:
turn0 = turn
isturn0 = True
turn += 1
if turn1times == x and isturn1 and turn1num <= u:
turn1num += 1
sum_edge = 0
num_edge = 0
for i in range(n):
for j in range(n):
if i == j or net[i, j] == float(\'inf\'):
continue
sum_edge += 1.0 / net[i, j]
num_edge += 1;
for i in range(n):
for j in range(n):
if i == j or net[i, j] == float(\'inf\'):
continue
T[i, j] = T[i, j] * num_edge * t0 * 1 / net[i, j] / sum_edge
C = np.ones(m)
global_best = float(\'inf\')
global_bestR = None
turn0times = 0
turn1times = 0
turn0 = None
isturn0 = False
isturn1 = True
turn = 0
# \'\'\'輸出\'\'\'
# print(\'最短路徑為：\', global_best)
# print(\'最短路徑長度：\', global_bestR)
return global_best
def TanXin(n, net):
R = np.ones(n+1, dtype=int)
while True:
for p in range(n+1):
if p == 0:
R[0] = ra.randint(0, n-1)
elif p == n:
R[n] = R[0]
else:
i = R[p-1]
js = neighbor(n, net, i)
js = list(set(js)-set(R[:p]))
ljs = [net[i, j] for j in js]
j = js[ljs.index(min(ljs))]
R[p] = j
C = sum([net[R[i], R[i+1]] for i in range(n)])
if C != float(\'inf\'):
break
return C
def neighbor(n, net, i):
return [j for j in range(n) if j != i if net[i][j] != float(\'inf\')]
if __name__ == \'__main__\':
net = np.array([[float(\'inf\'), 3, 1, 2],
[3, float(\'inf\'), 5, 4],
[1, 5, float(\'inf\'), 2],
[2, 4, 2, float(\'inf\')]])
TSP(net)
思路
TSP問題描述
TSP問題又稱旅行商問題、貨郎擔問題，是數學領域的著名問題，也是計算機中的NP難問題。TSP問題的具體描述為：給定一系列城市和每對城市之間的距離，求解通路每一座城市一次并回到起始城市的最短回路。
蟻群算法的描述
蟻群算法的思想來自于自然界螞蟻覓食，螞蟻在尋找食物源時，會在路徑上留下螞蟻獨有的路徑辨別——資訊素，一條路徑越短，該路徑的資訊素濃度就越高。螞蟻會感覺其他螞蟻在各條路徑上留下的資訊素，更傾向于選擇資訊素濃度高的路徑。随着時間的推移，越來越多的螞蟻選擇某一條路徑，該路徑的資訊素濃度就越高，越能吸引螞蟻，形成正回報機制。最終大部分螞蟻集中于最短的路徑上。
基線模型
對于TSP問題，設蟻群中螞蟻數量為\(m\)，結點數為\(n\)，結點i和結點j的距離為\(net_{ij}\), t時刻結點i和j之間連接配接的路徑的資訊素濃度為\(T_{ij}(t)\)。初始時刻，所有邊的資訊素濃度設定為一個固定值，螞蟻随機從不同的結點出發，按照一定機率選擇路徑。不妨設\(P_{ij}^k(t)\)為在t時刻處于結點i的螞蟻k選擇結點j作為下一個結點的機率。螞蟻選擇下一個結點的機率收到兩方面的影響，一是目前資訊素濃度，二是通路下一個結點的長度，是以定義：
\[P_{ij}^k(t)=\frac{{[T_{ij}(t)]^a}\cdot{[\frac{1}{net_{ij}}]^b}}{\sum_{j\in allow_k}({[T_{ij}(t)]^a}\cdot{[\frac{1}{net_{ij}}]^b})}
\]
其中\(allow_k\)為螞蟻k下一步可以到達的結點集合，随着時間的推移，\(allow_k\)中的元素會越來越少，最終變為空集;\(a\)和\(b\)為重要程度因子
随着時間的推移，路徑上資訊素濃度會不斷揮發，而螞蟻行走也會增加路徑上的資訊素濃度，是以定義資訊素的狀态轉移方程為：
\[\left\{
\begin{aligned}
& T_{ij}(t+1) = (1-h) * T_{ij}(t) + \sum_{k=1}^m(\bigtriangleup T_{ij}^k(t)) \\
& \bigtriangleup T_{ij}^k(t) = 1 / C^k(t)
\end{aligned}
\right.
\]
其中\(h\)為資訊素揮發率;\(\bigtriangleup T_{ij}^k(t)\)為t時刻第k隻螞蟻在邊(i, j)上增加的資訊素濃度;\(C^k(t)\)為在t時刻第k隻螞蟻經過路徑的總長度。
改進模型
初始資訊素濃度的改進：
在基線模型中，初始資訊素濃度賦予相同的指，我認為這并不是一個好的方式，原因如下：
(1)一開始的資訊素濃度不具有指導性，使得收斂速度下降
(2)可能使得螞蟻一開始向着錯誤的路徑前進，資訊素在錯誤的路徑上轉移，容易陷入局部最優
是以我們根據路徑大小給資訊素濃度賦予不同的初值：
\[T_{ij}(0) = Q \cdot numEdge \cdot \frac{1/net_{ij}}{\sum_{i,j}(1/net_{ij})}
\]
其中，Q為初始濃度值，根據螞蟻數量m除以貪心選擇的路徑長度得到;numEdge為網絡的邊數。該資訊素初始化方法使得初始資訊素濃度的平均值為Q,但是邊的長度會影響具體的取值——邊越短，初始資訊素濃度越大。
資訊素更新政策的改進：
在基線模型中，資訊素濃度的更新政策是不變的。我們知道，運作一段時間後，蟻群會集中于某條路徑，目前最優解往往就固定不變了，容易陷入局部最優。為了增加算法的全局搜尋能力，減小局部最優發生的機率，需要一種更合理的資訊更新政策。當疊代次數較小時，需要保證螞蟻在路徑上留下的資訊素濃度足夠高，以確定算法可以更快的收斂，而當算法收斂到一定程度時，如果多次疊代中算法所求得最有路徑長度一直未發生變化，那麼算法既有可能得到正确的結果，也有可能陷入局部最優，為了避免算法陷入局部最優的機率，需要适當增加資訊素揮發速率和減少螞蟻走過路徑留下的資訊素，避免資訊素過于集中，使得螞蟻能有更大機率去探索潛在的最優路徑，提高算法的全局搜尋能力。為了友善算法的描述，給出如下定義：
定義：如果存在某個時間節點t0,在一定固定的時長内，目前最優路徑未發生變化，則稱時間節點t0為穩定時刻點。
\[\left\{
\begin{aligned}
&T_{ij}(t+1) = (1-h) * T_{ij}(t) + \sum_{k=1}^m(\bigtriangleup T_{ij}^k(t)) & t < t0\\
&T_{ij}(t+1) = \frac{(1-h) * T_{ij}(t)}{t-t0} + \frac{\sum_{k=1}^m(\bigtriangleup T_{ij}^k(t))}{t-t0} & t >= t0
\end{aligned}
\right.
\]
資訊素矩陣的重置
為了進一步增加全家搜尋的能力，在這裡我們引入融斷機制。當進入穩定時刻點t0後的一段時間内，全局最優解仍然沒有發生變化，那麼我們會将資訊素矩陣重新初始化.
算法的流程圖
算法評估
下面通過TSPLIB提供的三個資料集，來對比基線算法和改進算法的優劣。
資料集為：rand75.tsp eil76.tsp rat99.tsp
初始參數為: a=1, b=2, h=0.1 m=3
重複次數為：10
基線模型和改進模型的平均相對誤差
| 資料集 | 基線模型 | 改進模型 |
|---|---|---|
| 資料集rand75.tsp | 129% | 57% |
| 資料集eil76.tsp | 180% | 79% |
| 資料集rat99.tsp | 165% | 73% |
平均誤差計算公式：\(error = \frac{predicted_value - measured_value}{measured_value}\)
改進模型較基線模型相對誤差減少量
| 資料集 | 平均相對誤差減少量 |
|---|---|
| 資料集rand75.tsp | 72% |
| 資料集eil76.tsp | 101% |
| 資料集rat99.tsp | 92% |
注意：資料的準确性不行，因為資料集大小不夠，重複次數也不夠，但是電腦不給力，時間不等人，隻能這樣了。
結論
可以看出，改進的模型相較與基線模型有一定的提升，但是依然存在一些問題：
(1)算法的時間消耗較大
(2)算法的結果相較于真實值還存在較大的相對誤差。
(3)算法的參數沒有缺少更多的實驗
(4)具體的改進函數缺少更多的實驗
參考
改進蟻群算法在TSP問題中的應用