1.定義
蟻群算法(Ant Colony Optimization, ACO)是由Marco Dorigo于1992年在他的博士論文“Ant system: optimization by a colony of cooperating agents”中提出积蜻，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為芦岂。
2.原理簡述
??螞蟻在尋找食物或者運(yùn)動(dòng)過程中，會在移動(dòng)的行進(jìn)的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)橙凳。該物質(zhì)有兩種比較重要的特性：
- 會隨著時(shí)間逐漸揮發(fā)茧吊；
- 信息素對螞蟻有吸引力豆村。
而螞蟻在選擇路徑的時(shí)候也會有一定的特性:
- 螞蟻往往傾向于選擇信息素濃度更高的方向行進(jìn)，但也會有螞蟻特立獨(dú)行缨历；
- 在沒有信息素作為參考的地方猩谊，螞蟻一般隨機(jī)選擇行進(jìn)方向千劈，并帶有一定慣性。
因此受信息素機(jī)制的影響牌捷，并在正反饋的作用下墙牌，蟻群覓食往往會形成一條長長的隊(duì)伍。
??如圖1所示暗甥，在兩點(diǎn)AB之間有兩條路徑喜滨。蟻群準(zhǔn)備在AB之間來回搬運(yùn)食物，由于剛開始路徑1和路徑2上都沒有信息素撤防，因此蟻群隨機(jī)選擇路徑虽风，兩條路徑各占50%。然后由于路徑1比路徑2短寄月，因此單位時(shí)間內(nèi)辜膝，經(jīng)過路徑1的螞蟻更多(假如，那么路徑1上的螞蟻一個(gè)來回后漾肮，路徑2上的螞蟻才剛到B)厂抖，因此路徑1上的信息素也相對更濃。在這種正反饋機(jī)制的作用下克懊，最終大部分螞蟻都會選擇走更短的路徑1忱辅。
3.蟻群算法簡析
原理
受蟻群覓食等行為的啟發(fā)，有學(xué)者將其引入到算法中用于解決類似問題谭溉，并提出了蟻群算法墙懂。下面，我們針對一個(gè)具體的有個(gè)城市的TSP問題夜只，構(gòu)建一個(gè)基礎(chǔ)的ACS蟻群算法來求解垒在。
首先設(shè)定一個(gè)啟發(fā)值
并給他初始化一個(gè)常數(shù)，這里我們另
扔亥，其中
為城市i與j之間的距離。然后再設(shè)置一個(gè)參數(shù)
谈为，該參數(shù)表示城市i和j之間的路徑信息素濃度旅挤，算法一開始將其初始化為一個(gè)較小常數(shù)。
對于
個(gè)城市的TSP問題伞鲫，蟻群算法的基本框架就是將
(
粘茄，一般可設(shè)為
)只螞蟻隨機(jī)分配到
次，求得最終所需的最優(yōu)路徑柒瓣。對于第k只螞蟻儒搭，它下一個(gè)選擇去往哪個(gè)城市由如下公式?jīng)Q定：
這里，表示第
只螞蟻
從城市
運(yùn)動(dòng)到到城市
的概率芙贫，
表示第
分別代表信息濃度
與啟發(fā)因子
磺平。
信息素的更新魂仍。蟻群算法的核心之一在于信息素的更新策略，有部分改進(jìn)的蟻群算法就是針對其信息素更新策略做了優(yōu)化拣挪。這里擦酌，當(dāng)
該公式表示信息素的揮發(fā)機(jī)制菠劝，其中
為N個(gè)城市的鏈接集合赊舶，
表示信息素的揮發(fā)率。其中
的定義為：
即每只螞蟻在城市i和j之間殘留的信息素之和赶诊。
ACS - Python實(shí)現(xiàn)
- 首先實(shí)現(xiàn)一個(gè)函數(shù)用于生成TSP問題所需的城市集合笼平。
import numpy as np
import matplotlib.pyplot as plt
def creat_city(num, scale):
"""
input:
num: 城市數(shù)量
scale: 城市坐標(biāo)范圍x,y in (0, scale)
return:
V：城市的坐標(biāo)集合
E：城市的鄰接矩陣
"""
x = np.random.choice(scale, num)
y = np.random.choice(scale, num)
V = np.stack((x,y), axis=1)
inner = -2 * V.dot(V.T)
xx = np.sum(V**2, axis=1, keepdims=True)
E = xx + inner + xx.T
E = E**0.5
index = [i for i in range(num)]
#為了防止螞蟻出現(xiàn)自旋，鄰接矩陣上的對角線取值盡量大一點(diǎn)甫何。
E[index,index] = 9999999
return V,E
我們使用下面的代碼在400*400的范圍內(nèi)生成20個(gè)城市出吹，其生成的的效果如圖2所示：
V, E = creat_city(20, 400)
plt.scatter(V[:,0], V[:,1], alpha=0.6, c = "r") # 繪制散點(diǎn)圖，透明度為0.6（這樣顏色淺一點(diǎn)辙喂，比較好看）
plt.show()
- 算法所需的其他必備函數(shù)
- 依概率采樣函數(shù)
import heapq
import random
def a_res(samples, m):
"""
:samples: [(item, weight), ...]
:k: number of selected items
:returns: [(item, weight), ...]
"""
heap = [] # [(new_weight, item), ...]
for sample in samples:
wi = sample[1]
if wi==0:
continue
ui = random.uniform(0, 1)
ki = ui ** (1/wi)
if len(heap) < m:
heapq.heappush(heap, (ki, sample))
elif ki > heap[0][0]:
heapq.heappush(heap, (ki, sample))
if len(heap) > m:
heapq.heappop(heap)
return [item[1] for item in heap]
- 由信息素濃度獲得螞蟻去往下一個(gè)城市的概率捶牢。
def possibility(eta, gamma, other_city, cur_city):
"""
返回候選城市集合中，從start到各候選城市的概率巍耗，只返回有路徑的
"""
alpha = 1
beta = 5
start_city = cur_city[-1]
t_i = gamma[start_city]
n_i = eta[start_city]
temp = (t_i**alpha * n_i**beta)
temp[cur_city] = 0
add = temp.sum()
p_ij = temp/add
return p_ij
- 其他函數(shù)
def rotate(l, n):
'''
旋轉(zhuǎn)列表秋麸。
'''
return l[n:] + l[:n]
def get_path_dis(root, E):
"""
獲取該路徑距離。
"""
dis = E[root[:-1], root[1:]].sum()
return dis + E[root[0],root[-1]]
- 蟻群算法實(shí)現(xiàn)
def ACS(V, E, M, num):
"""
Ant system
V : 點(diǎn)集
E: 鄰接矩陣炬太，點(diǎn)之間的連接性灸蟆，
M: 螞蟻數(shù)量
num：迭代次數(shù)
"""
#相關(guān)參數(shù)
global_best_path=None #當(dāng)前最優(yōu)路徑
global_best_dis = 99999999
cur_city = None
other_city = [i for i in range(len(V))]
lo = 0.5 #信息素?fù)]發(fā)率
#信息素啟發(fā)值
eta = 1/E
eta[np.isinf(eta)] = 0
#信息素濃度
E_mean = E[E>0].mean()
gamma = np.full(E.shape, 1/len(V))
V_index = [i for i in range(len(V))]
for i in range(num):
epoch_gamma = np.zeros_like(gamma) #保存每一輪的各路徑信息素累積量
local_best_path=None #每一次迭代當(dāng)前最優(yōu)路徑
local_best_dis = 99999999
for j in range(M):
cur_city = [j%len(V)]
other_city = [i for i in range(len(V))]
other_city.remove(cur_city[-1])
while(other_city):
p_ij = possibility(eta, gamma, other_city, cur_city)
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
epoch_gamma[cur_city[-1],next_city] += gamma[cur_city[-1],next_city]
cur_city.append(next_city)
other_city.remove(next_city)
epoch_dis = get_path_dis(cur_city, E)
if epoch_dis < local_best_dis:
local_best_dis = epoch_dis
local_best_path = cur_city
if local_best_dis < global_best_dis:
global_best_dis = local_best_dis
global_best_path = local_best_path
gamma = (1 - lo) * gamma + epoch_gamma
print("The shortest distance is {}m and the best path is: ".format(global_best_dis), end="")
best_path = rotate(global_best_path, global_best_path.index(0))
for index in best_path:
print(" city_" + str(index) + " ->", end="")
print("city_0\n")
return best_path
- 算法計(jì)算結(jié)果
root = ACS(V, E, 20, 50)
path = V[root]
path = np.append(path, [path[0]], axis=0)
plt.plot(path[:,0], path[:,1], marker="o", mfc="r")
plt.show()
MMAS(最大-最小蟻群系統(tǒng))
- MMAS算法簡介
我們從圖3中可以看到，ACS算法對于20個(gè)城市的TSP問題已經(jīng)能夠得到相對較優(yōu)的結(jié)果了亲族。但是ACS仍然有一些缺點(diǎn)炒考，比如收斂速度比較慢，獲取容易陷入局部最小值等等霎迫。針對這些缺陷有學(xué)者又提出了最大-最小蟻群系統(tǒng)斋枢。該改進(jìn)算法與基本的蟻群算法有以下幾點(diǎn)不同
-
，這也正是該算法名字的由來知给。通常該最大 最小值有我們自己設(shè)定瓤帚。
- 算法開始將城市之間的信息素濃度都初始化為
描姚。
- 每次迭代信息素更新時(shí)只針對最優(yōu)路徑進(jìn)行更新，而不考慮其他路徑戈次。其中最優(yōu)路徑可為局部最優(yōu)路徑(本次迭代最優(yōu))或全局最優(yōu)路徑(所有迭代最優(yōu))轩勘。具體更新公式如下：
其中怯邪，
指本次迭代最優(yōu)路徑绊寻，
為本次迭代最優(yōu)路徑中從城市
,其中
為一個(gè)自己設(shè)置的常數(shù)擎颖，
是本次迭代最優(yōu)路徑的長度榛斯。
- MMAS算法python實(shí)現(xiàn)
def MMAS(V, E, M, num, islocal=True):
"""
最大最小蟻群算法
V : 點(diǎn)集
E: 鄰接矩陣，點(diǎn)之間的連接性搂捧，
M: 螞蟻數(shù)量
num：迭代次數(shù)
"""
#相關(guān)參數(shù)
global_best_path=None #當(dāng)前最優(yōu)路徑
global_best_dis = 99999999
cur_city = None
other_city = [i for i in range(len(V))]
lo = 0.8 #信息素?fù)]發(fā)率
e = num #精英路徑權(quán)重
tao_min = 0.1 / num
tao_max = 1
#信息素啟發(fā)值
eta = 1/E
eta[np.isinf(eta)] = 0
#信息素濃度
E_mean = E[E>0].mean()
gamma = np.full(E.shape,tao_max)
V_index = [i for i in range(len(V))]
for i in range(num):
epoch_gamma = np.zeros_like(gamma) #保存每一輪的各路徑信息素累積量
local_best_path=None #每一次迭代當(dāng)前最優(yōu)路徑
local_best_dis = 99999999
for j in range(M):
cur_city = [j%len(V)]
other_city = [i for i in range(len(V))]
other_city.remove(cur_city[-1])
while(other_city):
p_ij = possibility(eta, gamma, other_city, cur_city)
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
if next_city not in other_city:
next_city = int(a_res(np.stack((V_index,p_ij),axis=1), 1)[0][0])
epoch_gamma[cur_city[-1],next_city] += gamma[cur_city[-1],next_city]
cur_city.append(next_city)
other_city.remove(next_city)
epoch_dis = get_path_dis(cur_city, E)
if epoch_dis < local_best_dis:
local_best_dis = epoch_dis
local_best_path = cur_city
if local_best_dis < global_best_dis:
global_best_dis = local_best_dis
global_best_path = local_best_path
#信息素更新
gamma = (1 - lo) * gamma
if islocal:
for i,j in np.stack((local_best_path[1:] + local_best_path[:1], local_best_path), axis=1):
gamma[i,j] += e / local_best_dis
else:
for i,j in np.stack((global_best_path[1:] + global_best_path[:1], global_best_path), axis=1):
gamma[i,j] += e / global_best_dis
gamma[gamma>tao_max] = tao_max
gamma[gamma<tao_min] = tao_min
print("The shortest distance is {}m and the best path is: ".format(global_best_dis), end="")
best_path = rotate(global_best_path, global_best_path.index(0))
for index in best_path:
print(" city_" + str(index) + " ->", end="")
print("city_0.\n")
return best_path
-
MMAS算法運(yùn)行結(jié)果
從圖4可以看到驮俗，MMAS對于TSP問題能得到很好的解，并且收斂速度也比較快允跑。因此一般對于TSP類問題使用MMAS來求解是比較合適的王凑。
圖4. MMAS結(jié)果
蟻群算法的其他優(yōu)化版本
這里我們限于篇幅僅僅簡單介紹了ACS和MMAS，其實(shí)對于蟻群算法還有精英系統(tǒng)(EAS)聋丝、排序蟻群(ASrank)索烹、連續(xù)正交蟻群(COAC)等等。此外弱睦，我們這里僅僅是用TSP算法來舉例百姓，實(shí)際上，蟻群算法可以被應(yīng)用到許多問題上况木，比如調(diào)度問題垒拢、設(shè)置問題、分配問題火惊、車輛路徑問題等等求类。讀者朋友如果有興趣可以去擴(kuò)展這些知識，相信會很有收獲的屹耐！
4.參考資料
https://zh.wikipedia.org/wiki/%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95
https://www.voidking.com/dev-aco/
https://zhuanlan.zhihu.com/p/45985636
https://blog.csdn.net/zuochao_2013/article/details/71872950
https://blog.csdn.net/acsunqi/article/details/76060669
https://cloud.tencent.com/developer/article/1369213
