旅行推銷(xiāo)員問(wèn)題（Travelling salesman problem, TSP）是這樣一個(gè)問(wèn)題：給定一系列城市和每對(duì)城市之間的距離，求解訪問(wèn)每一座城市一次并回到起始城市的最短回路。
它是組合優(yōu)化中的一個(gè)NP困難問(wèn)題，在運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)中非常重要。
蟻群算法（Ant Colony Optimization, ACO），又稱(chēng)螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法，對(duì)螞蟻行為進(jìn)行模仿抽象。在求解旅行推銷(xiāo)員問(wèn)題時(shí)，螞蟻隨機(jī)從某一城市出發(fā)，根據(jù)城市間距離與殘留信息素濃度按概率選擇下一城市，螞蟻?zhàn)咄晁械某鞘泻?，在走過(guò)的路徑上留下信息素，螞蟻?zhàn)叩目偮烦淘缴?，留下的信息素就越多。多次循環(huán)后，最好的路徑就有可能被篩選出。
- 早先接觸蟻群算法，最近重新回顧，感覺(jué)頗有意思。它對(duì)數(shù)學(xué)要求不高，沒(méi)有多少公式，容易理解。不過(guò)實(shí)力淺薄，僅分享一下個(gè)人嘗試和資料，供感興趣的人探索。
- 在代碼實(shí)現(xiàn)上，主要為蟻群和螞蟻兩個(gè)對(duì)象，簡(jiǎn)潔清晰，感覺(jué)是良好的教學(xué)材料。
-
此外，蟻群算法結(jié)合pygame做成可視化效果，對(duì)于小朋友的吸引力應(yīng)該很大，：)
文末相關(guān)視頻中的效果圖
運(yùn)行嘗試
求解效果圖
代碼1
- 老版詳細(xì)注釋?zhuān)a質(zhì)量不高，便于理解：
# -*- coding: UTF-8 -*-
'''
程序主體：
類(lèi)BACA的實(shí)例化->類(lèi)BACA的初始化->執(zhí)行BACA.ReadCityInfo()方法->執(zhí)行BACA.Search()方法->執(zhí)行BACA.PutAnts()方法
->類(lèi)ANT的初始化->類(lèi)ANT的實(shí)例化->執(zhí)行ANT.MoveToNextCity()方法->執(zhí)行ANT.SelectNextCity()方法->執(zhí)行ANT.AddCity()方法
->執(zhí)行ANT.UpdatePathLen()方法->執(zhí)行BACA.UpdatePheromoneTrail()方法
蟻群算法中關(guān)鍵兩個(gè)問(wèn)題，一個(gè)是選擇下一個(gè)城市的算法，主要在ANT.SelectNextCity(self, alpha, beta)方法中，其中alpha為表征
信息素重要程度的參數(shù)，beta為表征啟發(fā)式因子重要程度的參數(shù)；而更新信息素主要在BACA.UpdatePheromoneTrail(self)方法中。
'''
import os, sys, random#調(diào)入基本的python模塊
from math import *
import pylab as pl
BestTour = []#用于放置最佳路徑選擇城市的順序
CitySet = set()#sets數(shù)據(jù)類(lèi)型是個(gè)無(wú)序的、沒(méi)有重復(fù)元素的集合，兩個(gè)sets之間可以做差集，即在第一個(gè)集合中移出第二個(gè)集合中也存在的元素
CityList = []#城市列表即存放代表城市的序號(hào)
PheromoneTrailList = []#信息素列表（矩陣）
PheromoneDeltaTrailList = []#釋放信息素列表（矩陣）
CityDistanceList = []#兩兩城市距離列表(矩陣)
AntList = []#螞蟻列表
class BACA:#定義類(lèi)BACA，執(zhí)行蟻群基本算法
def __init__(self, cityCount=51, antCount=51, q=80, alpha=1, beta=3, rou=0.4, nMax=100):
#self, cityCount=51, antCount=50, q=80, alpha=2, beta=5, rou=0.3, nMax=40
#初始化方法，antCount為螞蟻數(shù)，nMax為迭代次數(shù)
self.CityCount = cityCount#城市數(shù)量，本例中為手工輸入，也可以根據(jù)城市數(shù)據(jù)列表編寫(xiě)程序獲得
self.AntCount = antCount#螞蟻數(shù)量
self.Q = q#信息素增加強(qiáng)度系數(shù)
self.Alpha = alpha#表征信息素重要程度的參數(shù)
self.Beta = beta#表征啟發(fā)因子重要程度的參數(shù)
self.Rou = rou#信息素蒸發(fā)系數(shù)
self.Nmax = nMax#最大迭代次數(shù)
self.Shortest = 10e6#初始最短距離應(yīng)該盡可能大，至少大于估算的最大城市旅行距離
random.seed()#設(shè)置隨機(jī)種子
#初始化全局?jǐn)?shù)據(jù)結(jié)構(gòu)及值
for nCity in range(self.CityCount):#循環(huán)城市總數(shù)的次數(shù)（即循環(huán)range(0,51),為0-50，不包括51）
BestTour.append(0)#設(shè)置最佳路徑初始值均為0
for row in range(self.CityCount):#再次循環(huán)城市總數(shù)的次數(shù)
pheromoneList = []#定義空的信息素列表
pheromoneDeltaList = []#定義空的釋放信息素列表
for col in range(self.CityCount):#循環(huán)城市總數(shù)的次數(shù)
pheromoneList.append(100)#定義一個(gè)城市到所有城市路徑信息素的初始值
pheromoneDeltaList.append(0)#定義一個(gè)城市到所有城市路徑釋放信息素的初始值
PheromoneTrailList.append(pheromoneList)#建立每個(gè)城市到所有城市路徑信息素的初始值列表矩陣
PheromoneDeltaTrailList.append(pheromoneDeltaList)#建立每個(gè)城市到所有城市路徑釋放信息素的初始值列表矩陣
def ReadCityInfo(self, fileName):#定義讀取城市文件的方法
file = open(fileName)#打開(kāi)城市文件
for line in file.readlines():#逐行讀取文件
cityN, cityX, cityY = line.split()#分別提取城市序號(hào)、X坐標(biāo)和Y坐標(biāo)，使用空格切分
CitySet.add(int(cityN))#在城市集合中逐步追加所有的城市序號(hào)
CityList.append((int(cityN), float(cityX), float(cityY)))#在城市列表中逐步追加每個(gè)城市序號(hào)、X坐標(biāo)和Y坐標(biāo)建立的元組
for row in range(self.CityCount):#循環(huán)總城市數(shù)的次數(shù)
distanceList = []#建立臨時(shí)儲(chǔ)存距離的空列表
for col in range(self.CityCount):
distance = sqrt(pow(CityList[row][1]-CityList[col][1], 2) + pow(CityList[row][2]-CityList[col][2], 2))#逐一計(jì)算每個(gè)城市到所有城市的距離值
distance = round(distance)
distanceList.append(distance)#追加一個(gè)城市到所有城市的距離值
CityDistanceList.append(distanceList)#追加么個(gè)城市到所有城市的距離值，為矩陣，即包含子列表
file.close()#關(guān)閉城市文件
def PutAnts(self):#定義螞蟻所選擇城市以及將城市作為參數(shù)定義螞蟻的方法和屬性
AntList.clear() # 先清空列表
for antNum in range(self.AntCount):#循環(huán)螞蟻總數(shù)的次數(shù)
city = random.randint(1, self.CityCount)#隨機(jī)選擇一個(gè)城市
ant = ANT(city)#螞蟻類(lèi)ANT的實(shí)例化，即將每只螞蟻隨機(jī)選擇的城市作為傳入的參數(shù)，使之具有ANT螞蟻類(lèi)的方法和屬性
AntList.append(ant)#將定義的每只螞蟻?zhàn)芳拥搅斜碇?
def Search(self):#定義搜索最佳旅行路徑方法的主程序
for iter in range(self.Nmax):#循環(huán)指定的迭代次數(shù)
self.PutAnts()#執(zhí)行self.PutAnts()方法，定義螞蟻選擇的初始城市和螞蟻具有的方法和屬性
for ant in AntList:#循環(huán)遍歷螞蟻列表，由self.PutAnts()方法定義獲取
for ttt in range(len(CityList)):#循環(huán)遍歷城市總數(shù)次數(shù)
ant.MoveToNextCity(self.Alpha, self.Beta)#執(zhí)行螞蟻的ant.MoveToNextCity()方法，獲取螞蟻每次旅行時(shí)的旅行路徑長(zhǎng)度CurrLen，禁忌城市城市列表TabuCityList等屬性值
ant.two_opt_search()#使用鄰域優(yōu)化算法 $$$
ant.UpdatePathLen()#使用ant.UpdatePathLen更新螞蟻旅行路徑長(zhǎng)度
tmpLen = AntList[0].CurrLen#將螞蟻列表中第一只螞蟻的旅行路徑長(zhǎng)度賦值給新的變量tmplen
tmpTour = AntList[0].TabuCityList#將獲取的螞蟻列表的第一只螞蟻的禁忌城市列表賦值給新的變量tmpTour
for ant in AntList[1:]:#循環(huán)遍歷螞蟻列表，從索引值1開(kāi)始，除第一只外
if ant.CurrLen < tmpLen:#如果循環(huán)到的螞蟻旅行路徑長(zhǎng)度小于tmpLen即前次循環(huán)螞蟻旅行路徑長(zhǎng)度，開(kāi)始值為螞蟻列表中第一只螞蟻的旅行路徑長(zhǎng)度
tmpLen = ant.CurrLen#更新變量tmpLen的值
tmpTour = ant.TabuCityList#更新變量tmpTour的值，即更新禁忌城市列表
if tmpLen < self.Shortest:#如果從螞蟻列表中獲取的最短路徑小于初始化時(shí)定義的長(zhǎng)度
self.Shortest = tmpLen#更新旅行路徑最短長(zhǎng)度
BestTour = tmpTour #更新初始化時(shí)定義的最佳旅行城市次序列表
print(iter,":",self.Shortest,":",BestTour)#打印當(dāng)前迭代次數(shù)、最短旅行路徑長(zhǎng)度和最佳旅行城市次序列表
self.UpdatePheromoneTrail()#完成每次迭代需要使用self，UpdatePheromoneTrail()方法更新信息素
#畫(huà)圖查看結(jié)果
x = []; y = []
for city in BestTour:
x.append(CityList[city-1][1])
y.append(CityList[city-1][2])
x.append(x[0])
y.append(y[0])
pl.plot(x, y)
#pl.figure()
pl.scatter(x, y)
pl.show()
def UpdatePheromoneTrail(self):#定義更新信息素的方法，需要參考前文對(duì)于蟻群算法的闡述
for ant in AntList:#循環(huán)遍歷螞蟻列表
for city in ant.TabuCityList[0:-1]:#循環(huán)遍歷螞蟻的禁忌城市列表
idx = ant.TabuCityList.index(city)#獲取當(dāng)前循環(huán) 禁忌城市的索引值
nextCity = ant.TabuCityList[idx+1]#獲取當(dāng)前循環(huán)禁忌城市緊鄰的下一個(gè)禁忌城市
PheromoneDeltaTrailList[city-1][nextCity-1] += self.Q / ant.CurrLen
#逐次更新釋放信息素列表，注意矩陣行列所代表的意義，[city-1]為選取的子列表即當(dāng)前城市與所有城市間路徑的
#釋放信息素值，初始值均為0，[nextCity-1]為在子列表中對(duì)應(yīng)緊鄰的下一個(gè)城市，釋放信息素為Q，信息素增加強(qiáng)度
#系數(shù)與螞蟻當(dāng)前旅行路徑長(zhǎng)度CurrLen的比值，路徑長(zhǎng)度越小釋放信息素越大，反之則越小。
PheromoneDeltaTrailList[nextCity-1][city-1] += self.Q / ant.CurrLen
#在二維矩陣中，每個(gè)城市路徑均出現(xiàn)兩次，分別為[city-1]對(duì)應(yīng)的[nextCity-1]和[nextCity-1]對(duì)應(yīng)的[city-1]，因此都需要更新，
#注意城市序列因?yàn)閺?開(kāi)始，而列表索引值均從0開(kāi)始，所以需要減1
lastCity = ant.TabuCityList[-1]#獲取禁忌城市列表的最后一個(gè)城市
firstCity = ant.TabuCityList[0]#獲取禁忌城市列表的第一個(gè)城市
PheromoneDeltaTrailList[lastCity-1][firstCity-1] += self.Q / ant.CurrLen
#因?yàn)槲浵伮眯行枰祷亻_(kāi)始的城市，因此需要更新禁忌城市列表最后一個(gè)城市到第一個(gè)城市旅行路徑的釋放信息素值，即最后一個(gè)城市對(duì)應(yīng)第一個(gè)城市的釋放信息素值
PheromoneDeltaTrailList[firstCity-1][lastCity-1] += self.Q / ant.CurrLen
#同理更新第一個(gè)城市對(duì)應(yīng)最后一個(gè)城市的釋放信息素值
for (city1, city1X, city1Y) in CityList:#循環(huán)遍歷城市列表，主要是提取city1即城市的序號(hào)
for (city2, city2X, city2Y) in CityList:#再次循環(huán)遍歷城市列表，主要是提取city2即城市序號(hào)，循環(huán)兩次的目的仍然是對(duì)應(yīng)列表矩陣的數(shù)據(jù)結(jié)構(gòu)
PheromoneTrailList[city1-1][city2-1] = ( (1-self.Rou)*PheromoneTrailList[city1-1][city2-1] + PheromoneDeltaTrailList[city1-1][city2-1] )
PheromoneDeltaTrailList[city1-1][city2-1] = 0#將釋放信息素列表值再次初始化為0，用于下次循環(huán)
#### print(PheromoneTrailList)
class ANT:#定義螞蟻類(lèi)，使得螞蟻具有相應(yīng)的方法和屬性
def __init__(self, currCity = 0):#螞蟻類(lèi)的初始化方法，默認(rèn)傳入當(dāng)前城市序號(hào)為0
self.TabuCitySet = set()
#定義禁忌城市集合，定義集合的目的是集合本身要素不重復(fù)并且之間可以做差集運(yùn)算，例如AddCity()方法中
#self.AllowedCitySet = CitySet - self.TabuCitySet，可以方便地從城市集合中去除禁忌城市列表的城市，獲取允許的城市列表
self.TabuCityList = []#定義禁忌城市空列表
self.AllowedCitySet = set()#定義允許城市集合
self.TransferProbabilityList = []#定義城市選擇可能性列表
self.CurrCity = 0 #定義當(dāng)前城市初始值為0
self.CurrLen = 0.0#定義當(dāng)前旅行路徑長(zhǎng)度
self.AddCity(currCity)#執(zhí)行AddCity()方法，獲取每次迭代的當(dāng)前城市CurrCity、禁忌城市列表TabuCityList和允許城市列表AllowedCitySet的值
pass#空語(yǔ)句，此行為空，不運(yùn)行任何操作
def SelectNextCity(self, alpha, beta):#定義螞蟻選擇下一個(gè)城市的方法，需要參考前文描述的蟻群算法
if len(self.AllowedCitySet) == 0:#如果允許城市集合為0，則返回0
return (0)
sumProbability = 0.0#定義概率，可能性初始值為0
self.TransferProbabilityList = []#建立選擇下一個(gè)城市可能性空列表
for city in self.AllowedCitySet:#循環(huán)遍歷允許城市集合
sumProbability = sumProbability + (
pow(PheromoneTrailList[self.CurrCity-1][city-1], alpha) *
pow(1.0/CityDistanceList[self.CurrCity-1][city-1], beta)
)
#螞蟻選擇下一個(gè)城市的可能性由信息素與城市間距離之間關(guān)系等綜合因素確定，其中alpha為表征信息素重要程度的參數(shù)，beta為表征啟發(fā)式因子重要程度的參數(shù)，
#該語(yǔ)句為前文蟻群算法闡述的選擇下一個(gè)轉(zhuǎn)移城市的概率公式的分母部分
transferProbability = sumProbability#根據(jù)信息素選擇公式和輪盤(pán)選擇得出概率列表，非0-1
self.TransferProbabilityList.append((city, transferProbability))#將城市序號(hào)和對(duì)應(yīng)的轉(zhuǎn)移城市概率追加到轉(zhuǎn)移概率列表中
threshold = sumProbability * random.random()#將概率值乘以一個(gè)0~1的隨機(jī)數(shù)，獲取輪盤(pán)指針值
for (cityNum, cityProb) in self.TransferProbabilityList:#再次循環(huán)遍歷概率列表
if threshold <= cityProb:#如果輪盤(pán)指針值大于概率值，則返回對(duì)應(yīng)的城市序號(hào)
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! key step!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
return (cityNum)
return (0)#否則返回0
def MoveToNextCity(self, alpha, beta):#定義轉(zhuǎn)移城市方法
nextCity = self.SelectNextCity(alpha, beta)#執(zhí)行SelectNextCity(),選擇下一個(gè)城市的方法，獲取選擇城市的序號(hào)，并賦值給新的變量nextCity
if nextCity > 0 : #如果選擇的城市序號(hào)大于0，則執(zhí)行self.AddCity()方法，獲取每次迭代的當(dāng)前城市Currcity、禁忌城市列表TabuCityList和允許城市列表AllowedCitySet的值
self.AddCity(nextCity)#執(zhí)行self.AddCity()方法
def ClearTabu(self):#定義清楚禁忌城市方法，以用于下一次循環(huán)
self.TabuCityList = []#初始化禁忌城市列表為空
self.TabuCitySet.clear()#初始化城市禁忌列表為空
self.AllowedCitySet = CitySet - self.TabuCitySet#初始化允許城市集合
def UpdatePathLen(self):#定義更新旅行路徑長(zhǎng)度方法
for city in self.TabuCityList[0:-1]:#循環(huán)遍歷禁忌城市列表
nextCity = self.TabuCityList[self.TabuCityList.index(city)+1]#獲取禁忌城市列表中的下一個(gè)城市序號(hào)
self.CurrLen = self.CurrLen + CityDistanceList[city-1][nextCity-1]#從城市間距離之中提取當(dāng)前循環(huán)城市與下一個(gè)城市之間的距離，并逐次求和
lastCity = self.TabuCityList[-1]#提取禁忌列表中的最后一個(gè)城市
firstCity = self.TabuCityList[0]#提取禁忌列表中的第一個(gè)城市
self.CurrLen = self.CurrLen + CityDistanceList[lastCity-1][firstCity-1]#將最后一個(gè)城市與第一個(gè)城市的距離值加到當(dāng)前旅行路徑長(zhǎng)度，獲取循環(huán)全部城市的路徑長(zhǎng)度
def AddCity(self, city):#定義增加城市到禁忌城市列表中的方法
if city <= 0:#如果城市序號(hào)小于等于0，則返回
return
self.CurrCity = city#更新當(dāng)前城市序號(hào)
self.TabuCityList.append(city)#將當(dāng)前城市追加到禁忌城市列表中，因?yàn)橐呀?jīng)旅行過(guò)的城市不應(yīng)該再進(jìn)入
self.TabuCitySet.add(city)#將當(dāng)前城市追加到禁忌城市集合中，用于差集運(yùn)算
self.AllowedCitySet = CitySet - self.TabuCitySet#使用集合差集的方法獲取允許的城市列表
def two_opt_search(self): # 領(lǐng)域搜索
cityNum = len(CityList)
for i in range(cityNum):
for j in range(cityNum-1, i, -1):
#for j in range(i+1, cityNum):
#for j in range((i+10) if (i+10)<cityNum else cityNum-1, i, -1):
curCity1 = self.TabuCityList[i] -1#此處風(fēng)格不統(tǒng)一!
preCity1 = self.TabuCityList[(i-1) % cityNum] -1
nextCity1 = self.TabuCityList[(i+1) % cityNum] -1
curCity2 = self.TabuCityList[j] -1#此處風(fēng)格不統(tǒng)一!
preCity2 = self.TabuCityList[(j-1) % cityNum] -1
nextCity2 = self.TabuCityList[(j+1) % cityNum] -1
CurrLen = CityDistanceList[preCity1][curCity1] + CityDistanceList[curCity2][nextCity2]
NextLen = CityDistanceList[preCity1][curCity2] + CityDistanceList[curCity1][nextCity2]
if NextLen < CurrLen:
tempList = self.TabuCityList[i:j+1]
self.TabuCityList[i:j+1] = tempList[::-1]
# for i in range(cityNum):
# curCity = self.TabuCityList[i] -1#此處風(fēng)格不統(tǒng)一!
# preCity = self.TabuCityList[(i-1) % cityNum] -1
# nextCity = self.TabuCityList[(i+1) % cityNum] -1
# forwardCity = self.TabuCityList[(i+2) % cityNum] -1
# CurrLen = CityDistanceList[preCity][curCity] + CityDistanceList[nextCity][forwardCity]
# NextLen = CityDistanceList[preCity][nextCity] + CityDistanceList[curCity][forwardCity]
# if NextLen < CurrLen :
# #print i
# self.TabuCityList[i], self.TabuCityList[(i+1) % cityNum] = self.TabuCityList[(i+1) % cityNum], self.TabuCityList[i]
if __name__ == '__main__':#該語(yǔ)句說(shuō)明之后的語(yǔ)句在該.py文件作為模塊被調(diào)用時(shí)，語(yǔ)句之后的代碼不執(zhí)行；打開(kāi).py文件直接使用時(shí)，語(yǔ)句之后的代碼則執(zhí)行。通常該語(yǔ)句在模塊測(cè)試中
theBaca = BACA()#BACA類(lèi)的實(shí)例化
theBaca.ReadCityInfo('eil51.tsp')#讀取城市數(shù)據(jù)
theBaca.Search()#執(zhí)行Search()方法
代碼2
- 去除注釋?zhuān)阑a，增加了最大最小蟻群規(guī)則（詳見(jiàn)文末資料），求解效果變好
# -*- coding: UTF-8 -*-
import random
from math import pow, sqrt
import numpy as np
import pandas as pd
import pylab as pl
class MMAS:
def __init__(self, antCount=20, q=100, alpha=1, beta=3,
rou=0.3, initialph=10, nMax=10000):
'''
https://svn-d1.mpi-inf.mpg.de/AG1/MultiCoreLab/papers/StuetzleHoos00%20-%20MMAS.pdf
'''
self.AntCount = antCount
self.Q = q
self.Alpha = alpha
self.Beta = beta
self.Rou = rou
self.initialPh = initialph
self.Nmax = nMax
self.Shortest = float('inf')
self.AntList = []
pl.show()
def ReadCityInfo(self, fileName):
'''
http://stackoverflow.com/questions/29281680/numpy-individual-element-access-slower-than-for-lists
'''
city_info = pd.read_csv(fileName,
sep=' ',
skiprows=6, skipfooter=1,
engine='python',
header=None,
names=('N', 'x', 'y'))
self.CityCount = city_info.shape[0]
self.CitySet = set()
self.CityDistance = [
[0] * self.CityCount for i in range(self.CityCount)]
self.CityDistanceBeta = np.zeros(
(self.CityCount, self.CityCount)).tolist()
self.Pheromone = [
[self.initialPh] * self.CityCount for i in range(self.CityCount)]
self.PheromoneDelta = np.zeros(
(self.CityCount, self.CityCount)).tolist()
self.BestTour = [None] * self.CityCount
for row in city_info.index:
for col in city_info.index:
if row != col:
distance = round(
sqrt(pow(city_info.x[row] - city_info.x[col], 2)
+ pow(city_info.y[row] - city_info.y[col], 2))
)
self.CityDistance[row][col] = distance
self.CityDistanceBeta[row][col] = pow(
1.0 / distance, self.Beta)
self.city_info = city_info
def PutAnts(self):
self.AntList.clear()
for antNum in range(self.AntCount):
city = random.choice(self.city_info.index)
ant = ANT(city, self.city_info.index,
self.CityDistance, self.Pheromone)
self.AntList.append(ant)
def Search(self):
import time
for iter in range(self.Nmax):
start = time.time()
self.PutAnts()
tmpLen = float('inf')
tmpTour = []
for ant in self.AntList:
for ttt in range(self.CityCount):
ant.MoveToNextCity(self.Alpha, self.Beta)
ant.two_opt_search()
ant.UpdatePathLen()
if ant.CurrLen < tmpLen:
self.bestAnt = ant
tmpLen = ant.CurrLen
tmpTour = ant.TabuCityList
if tmpLen < self.Shortest:
self.Shortest = tmpLen
self.BestTour = tmpTour
print(iter, "-->", self.Shortest, "-->", self.BestTour)
# self.bestAnt.two_opt_search()
self.UpdatePheromoneTrail()
end = time.time()
print(end - start)
pl.clf()
x = []; y = []
for city in self.BestTour:
x.append(self.city_info.x[city])
y.append(self.city_info.y[city])
x.append(x[0])
y.append(y[0])
pl.plot(x, y)
pl.scatter(x, y, s=30, c='r')
pl.pause(0.01)
def UpdatePheromoneTrail(self):
ant = self.bestAnt
pheromo_new = self.Q / ant.CurrLen
tabu = ant.TabuCityList
PD = self.PheromoneDelta
P = self.Pheromone
citys = self.city_info.index
for city, nextCity in zip(tabu[:-1], tabu[1:]):
PD[city][nextCity] = pheromo_new
PD[nextCity][city] = pheromo_new
lastCity = tabu[-1]
firstCity = tabu[0]
PD[lastCity][firstCity] = pheromo_new
PD[firstCity][lastCity] = pheromo_new
for c1 in citys:
for c2 in citys:
if c1 != c2:
P[c1][c2] = (
(1 - self.Rou) * P[c1][c2]
+ PD[c1][c2]
)
if P[c1][c2] < 0.001:
P[c1][c2] = 0.001
if P[c1][c2] > 10:
raise(Exception('too big Ph'))
P[c1][c2] = 10
PD[c1][c2] = 0
class ANT:
def __init__(self, currCity=0, citys=None, cityDis=None, pheromo=None):
self.TabuCityList = [currCity, ]
self.AllowedCitySet = set(citys)
self.AllowedCitySet.remove(currCity)
self.CityDistance = cityDis
self.Pheromone = pheromo
self.TransferProbabilityList = []
self.CurrCity = currCity
self.CurrLen = 0
def SelectNextCity(self, alpha, beta):
if self.AllowedCitySet:
sumProbability = 0
self.TransferProbabilityList = []
for city in self.AllowedCitySet:
sumProbability = sumProbability + (
pow(self.Pheromone[self.CurrCity][city], alpha) *
pow(1.0 /
self.CityDistance[self.CurrCity][city], beta)
)
transferProbability = sumProbability
self.TransferProbabilityList.append(
(city, transferProbability))
threshold = sumProbability * random.random()
#~print(self.TransferProbabilityList)
for cityNum, cityProb in self.TransferProbabilityList:
if threshold <= cityProb:
return (cityNum)
return None
def MoveToNextCity(self, alpha, beta):
'''
對(duì)于有0返回值的if語(yǔ)句不能使用if x: ... 判斷
'''
nextCity = self.SelectNextCity(alpha, beta)
if nextCity is not None:
self.CurrCity = nextCity
self.TabuCityList.append(nextCity)
self.AllowedCitySet.remove(nextCity)
def UpdatePathLen(self):
for city, nextCity in zip(self.TabuCityList[:-1],
self.TabuCityList[1:]):
self.CurrLen = self.CurrLen + self.CityDistance[city][nextCity]
#~print(self.TabuCityList)
lastCity = self.TabuCityList[-1]
firstCity = self.TabuCityList[0]
self.CurrLen = self.CurrLen + self.CityDistance[lastCity][firstCity]
def two_opt_search(self):
'''
1-2-3-4, 1-2 + 3-4 > 1-3 + 2-4 則交換
'''
cityNum = len(self.TabuCityList)
for i in range(cityNum):
for j in range(cityNum - 1, i, -1):
curCity1 = self.TabuCityList[i]
preCity1 = self.TabuCityList[(i - 1) % cityNum]
curCity2 = self.TabuCityList[j]
nextCity2 = self.TabuCityList[(j + 1) % cityNum]
CurrLen = self.CityDistance[preCity1][
curCity1] + self.CityDistance[curCity2][nextCity2]
NextLen = self.CityDistance[preCity1][
curCity2] + self.CityDistance[curCity1][nextCity2]
if NextLen < CurrLen:
tempList = self.TabuCityList[i:j + 1]
self.TabuCityList[i:j + 1] = tempList[::-1]
if __name__ == '__main__':
aco = MMAS()
aco.ReadCityInfo('eil51.tsp')
aco.Search()
代碼3
- 再略微修改，增加了鄰近城市選擇的機(jī)制，（詳見(jiàn)文末資料）
# -*- coding: UTF-8 -*-
import random
from math import pow, sqrt
import numpy as np
import pandas as pd
import pylab as pl
class MMAS:
def __init__(self, antCount=20, q=100, alpha=1, beta=3,
rou=0.3, initialph=10, nMax=10000):
'''
https://svn-d1.mpi-inf.mpg.de/AG1/MultiCoreLab/papers/StuetzleHoos00%20-%20MMAS.pdf
'''
self.AntCount = antCount
self.Q = q
self.Alpha = alpha
self.Beta = beta
self.Rou = rou
self.initialPh = initialph
self.Nmax = nMax
self.Shortest = float('inf')
self.AntList = []
pl.show()
def ReadCityInfo(self, fileName):
'''
http://stackoverflow.com/questions/29281680/numpy-individual-element-access-slower-than-for-lists
'''
city_info = pd.read_csv(fileName,
sep=' ',
skiprows=6, skipfooter=1,
engine='python',
header=None,
names=('N', 'x', 'y'))
self.CityCount = city_info.shape[0]
self.CitySet = set()
self.CityDistance = np.zeros(
(self.CityCount, self.CityCount))
self.CityDistanceBeta = [
[0] * self.CityCount for i in range(self.CityCount)]
self.Pheromone = [
[self.initialPh] * self.CityCount for i in range(self.CityCount)]
self.PheromoneDelta = np.zeros(
(self.CityCount, self.CityCount)).tolist()
self.BestTour = [None] * self.CityCount
for row in city_info.index:
for col in city_info.index:
if row != col:
distance = round(
sqrt(pow(city_info.x[row] - city_info.x[col], 2)
+ pow(city_info.y[row] - city_info.y[col], 2))
)
self.CityDistance[row][col] = distance # 可用[row, col]索引
self.CityDistanceBeta[row][col] = pow(
1.0 / distance, self.Beta)
self.CityNearest = self.CityDistance.argsort() # 每個(gè)城市de最近城市索引
# http://stackoverflow.com/questions/7851077/how-to-return-index-of-a-sorted-list
self.CityDistance = self.CityDistance.tolist()
self.city_info = city_info
def PutAnts(self):
self.AntList.clear()
for antNum in range(self.AntCount):
city = random.choice(self.city_info.index)
ant = ANT(city, self.city_info.index,
self.CityDistance, self.Pheromone,
self.CityNearest)
self.AntList.append(ant)
def Search(self):
import time
for iter in range(self.Nmax):
start = time.time()
self.PutAnts()
tmpLen = float('inf')
tmpTour = []
for ant in self.AntList:
for ttt in range(self.CityCount):
ant.MoveToNextCity(self.Alpha, self.Beta)
ant.two_opt_search()
ant.UpdatePathLen()
if ant.CurrLen < tmpLen:
self.bestAnt = ant
tmpLen = ant.CurrLen
tmpTour = ant.TabuCityList
if tmpLen < self.Shortest:
self.Shortest = tmpLen
self.BestTour = tmpTour
print(iter, "-->", self.Shortest, "-->", self.BestTour)
# self.bestAnt.two_opt_search()
self.UpdatePheromoneTrail()
end = time.time()
print(end - start)
pl.clf()
x = []
y = []
for city in self.BestTour:
x.append(self.city_info.x[city])
y.append(self.city_info.y[city])
x.append(x[0])
y.append(y[0])
pl.plot(x, y)
pl.scatter(x, y, s=30, c='r')
pl.pause(0.01)
def UpdatePheromoneTrail(self):
ant = self.bestAnt
pheromo_new = self.Q / ant.CurrLen
tabu = ant.TabuCityList
PD = self.PheromoneDelta
P = self.Pheromone
citys = self.city_info.index
for city, nextCity in zip(tabu[:-1], tabu[1:]):
PD[city][nextCity] = pheromo_new
PD[nextCity][city] = pheromo_new
lastCity = tabu[-1]
firstCity = tabu[0]
PD[lastCity][firstCity] = pheromo_new
PD[firstCity][lastCity] = pheromo_new
for c1 in citys:
for c2 in citys:
if c1 != c2:
P[c1][c2] = (
(1 - self.Rou) * P[c1][c2]
+ PD[c1][c2]
)
if P[c1][c2] < 0.001:
P[c1][c2] = 0.001
if P[c1][c2] > 10:
raise(Exception('too big Ph'))
P[c1][c2] = 10
PD[c1][c2] = 0
class ANT:
def __init__(self, currCity=0, citys=None,
cityDis=None, pheromo=None, cityNear=None):
self.TabuCityList = [currCity, ]
self.AllowedCitySet = set(citys)
self.AllowedCitySet.remove(currCity)
self.CityDistance = cityDis
self.Pheromone = pheromo
self.CityNearest = cityNear
self.TransferProbabilityList = []
self.CurrCity = currCity
self.CurrLen = 0
def SelectNextCity(self, alpha, beta):
if len(self.AllowedCitySet) == 0:
return None
near = self.CityNearest[self.CurrCity]
ANset = self.AllowedCitySet & set(near[1:16])
if ANset:
sumProbability = 0
self.TransferProbabilityList = []
for city in self.AllowedCitySet:
sumProbability = sumProbability + (
pow(self.Pheromone[self.CurrCity][city], alpha) *
pow(1.0 /
self.CityDistance[self.CurrCity][city], beta)
)
transferProbability = sumProbability
self.TransferProbabilityList.append(
(city, transferProbability))
threshold = sumProbability * random.random()
for cityNum, cityProb in self.TransferProbabilityList:
if threshold <= cityProb:
return (cityNum)
else:
for city in near[1:]:
if city in self.AllowedCitySet:
return city
def MoveToNextCity(self, alpha, beta):
'''
對(duì)于有0返回值的if語(yǔ)句不能使用if x: ... 判斷
'''
nextCity = self.SelectNextCity(alpha, beta)
if nextCity is not None:
self.CurrCity = nextCity
self.TabuCityList.append(nextCity)
self.AllowedCitySet.remove(nextCity)
def UpdatePathLen(self):
for city, nextCity in zip(self.TabuCityList[:-1],
self.TabuCityList[1:]):
self.CurrLen = self.CurrLen + self.CityDistance[city][nextCity]
#~print(self.TabuCityList)
lastCity = self.TabuCityList[-1]
firstCity = self.TabuCityList[0]
self.CurrLen = self.CurrLen + self.CityDistance[lastCity][firstCity]
def two_opt_search(self):
'''
1-2-3-4, 1-2 + 3-4 > 1-3 + 2-4 則交換
'''
cityNum = len(self.TabuCityList)
for i in range(cityNum):
for j in range(cityNum - 1, i, -1):
curCity1 = self.TabuCityList[i]
preCity1 = self.TabuCityList[(i - 1) % cityNum]
curCity2 = self.TabuCityList[j]
nextCity2 = self.TabuCityList[(j + 1) % cityNum]
CurrLen = self.CityDistance[preCity1][
curCity1] + self.CityDistance[curCity2][nextCity2]
NextLen = self.CityDistance[preCity1][
curCity2] + self.CityDistance[curCity1][nextCity2]
if NextLen < CurrLen:
tempList = self.TabuCityList[i:j + 1]
self.TabuCityList[i:j + 1] = tempList[::-1]
if __name__ == '__main__':
aco = MMAS()
aco.ReadCityInfo('eil51.tsp')
aco.Search()
資料
- 以前在論壇上搜集的資料，講得很好，現(xiàn)在暫時(shí)沒(méi)找到出處，見(jiàn)諒。
這位同學(xué)的附件不錯(cuò)，說(shuō)的很詳細(xì)，是一個(gè)很好的入門(mén)教程
不過(guò)不夠深入，而且有些地方明顯是抄的其它中文資源
比如對(duì)MMAS的論述有很多錯(cuò)誤，只是列舉一串公式?jīng)]有提到具體實(shí)現(xiàn)，凡是這樣的文章通常都是作者自己沒(méi)學(xué)會(huì)含糊其辭，要么就是直接抄的
附件應(yīng)該是抄的，因?yàn)?avg 參數(shù)的論述完全錯(cuò)誤，可見(jiàn)作者根本沒(méi)有寫(xiě)過(guò)MMAS，或者寫(xiě)過(guò)但是不會(huì)有他聲稱(chēng)的增強(qiáng)
（如果同學(xué)看中文資料看不懂，很正常，因?yàn)楹芸赡苁清e(cuò)的。。。。。。）
其實(shí)《Ant Colony Optimization》一書(shū)就有MMAS詳細(xì)的實(shí)現(xiàn)方法和參數(shù)建議。
我現(xiàn)在看到拿 eil51.tsp 作為最終考驗(yàn)，或者求解規(guī)模在100以下的，都覺(jué)得作者水平低＋多半是抄書(shū)郎了，因?yàn)橹灰约嚎催^(guò)《Ant Colony Optimization》，都絕對(duì)不止求解100規(guī)模的實(shí)力。
因?yàn)橹灰辛肃徲蛩阉鳎蠼鈹?shù)百城市都不成問(wèn)題，根據(jù)我的經(jīng)驗(yàn)，
沒(méi)有鄰域搜索的，100城市以上幾乎是絕對(duì)求不出最優(yōu)解，所以100城市是個(gè)分水嶺（我現(xiàn)在無(wú)視這個(gè)水平）
2_opt在求解300＋的城市會(huì)出現(xiàn)明顯精度下降，所以300城市規(guī)模也是一個(gè)分水嶺（我現(xiàn)在輕視這個(gè)水平）
3_opt在求解1000＋的城市會(huì)出現(xiàn)明顯精度下降，所以1000城市規(guī)模也是一個(gè)分水嶺（我現(xiàn)在站在這個(gè)水平）
LKH我沒(méi)學(xué)習(xí)，據(jù)作者說(shuō)可以直接優(yōu)化10萬(wàn)城市?。?！所以。。。10萬(wàn)城市也是一個(gè)分水嶺（我現(xiàn)在仰望這個(gè)水平）
再次推書(shū)：《Ant Colony Optimization》一書(shū)里面的內(nèi)容是很多的，至少還有：
1 各種蟻群算法的詳細(xì)實(shí)現(xiàn)，及其性能比較（我在頂樓貼了性能比較和建議參數(shù)這非常重要的兩頁(yè)資料，很多資料都直接引用這兩頁(yè)而不提出處，鄙視。）
2 對(duì)算法陷入停滯的檢測(cè)方法（絕絕大多數(shù)網(wǎng)上資源根本不提這一點(diǎn)，或者提到了也是錯(cuò)的，如樓上中原小農(nóng)的附件，里面說(shuō)到輪盤(pán)賭選擇是避免停滯，這一句就是錯(cuò)誤的，輪盤(pán)賭選擇是最基本的蟻群算法的核心實(shí)現(xiàn)，目的只是每個(gè)路徑都有機(jī)會(huì)被搜索到，跟避免算法停滯沒(méi)有半點(diǎn)關(guān)系。）
3 對(duì)算法的加速技巧（應(yīng)用加速技巧，可以把蟻群算法降低一個(gè)階，變成 O(n^2) 提速幾千倍?。?4 更高級(jí)的鄰域搜索，如 3_opt，k_opt，LKH，絕大多數(shù)網(wǎng)上資源根本不提鄰域搜索，所以性能一般都很差。
有能力的同學(xué)絕對(duì)應(yīng)該直接看《Ant Colony Optimization》，看完就知道所有中文資源都是二手貨+太監(jiān)版（包括我的，呵呵）。
前面說(shuō)到，蟻群算法 ＋ 鄰域搜索 ＝ 很好的優(yōu)化程度
但是，我們發(fā)現(xiàn)求解超過(guò)200城市規(guī)模的TSP問(wèn)題，還是顯得太慢。
在進(jìn)一步深入優(yōu)化蟻群算法之前，顯然必須先解決速度太慢的問(wèn)題。
原有的蟻群算法的性能分析如下：
算法復(fù)雜度 = O( 循環(huán)數(shù) * 螞蟻數(shù) * 城市數(shù)^2 )
在沒(méi)有鄰域搜索輔助的情況下，設(shè)城市數(shù) = N
循環(huán)數(shù)通常需要指定一個(gè)很大的數(shù)值，假設(shè)這個(gè)值為T(mén)
而螞蟻數(shù)的取值，建議＝城市數(shù)，所以每次循環(huán)計(jì)算所有螞蟻需要 O(N)
一個(gè)螞蟻的一個(gè)方案需要選擇N個(gè)城市，每次選擇需要從 最多N個(gè)候選城市中遍歷并且計(jì)算選擇概率，所以建立一個(gè)方案是 O(N^2)
所以算法的復(fù)雜度 ＝ T * N^3，即 O(T * N^3)
這樣的算法復(fù)雜度意味著，如果求解10個(gè)城市需要0.01秒，那么
求解150個(gè)城市就需要 15^3 * 0.01 = 33.75秒！
求解300個(gè)城市就需要 30^3 * 0.01 = 270秒！
求解1000個(gè)城市就需要 100^3 * 0.01 = 1萬(wàn)秒！
程序耗時(shí)隨著城市數(shù)增大，呈現(xiàn)3次方增長(zhǎng)，這顯然是無(wú)法求解更大規(guī)模的問(wèn)題的。
在使用了鄰域搜索以后，我們發(fā)現(xiàn)可以大大減少需要的循環(huán)數(shù)，即T可以降低，但即使忽略不計(jì)T這個(gè)值，程序仍然是 O(N^3)增長(zhǎng)速度，一切還是不變。
采用以下三個(gè)技巧，可以把 算法復(fù)雜度降低到 O(T * N^2)
頭兩個(gè)加速技巧都基于一個(gè)事實(shí)： TSP問(wèn)題最優(yōu)解的每個(gè)城市連接的都必定是附近的城市！
所以在螞蟻尋路的時(shí)候，也只需要嘗試附近的幾個(gè)城市即可，不需要嘗試所有的城市！
技巧1 ： candidate list，或者說(shuō) Nearest city list
即每個(gè)螞蟻在計(jì)算如何選擇下一個(gè)城市時(shí)，只計(jì)算距離當(dāng)前城市距離最近的若干個(gè)城市，如果這些距離最近的城市已經(jīng)走過(guò)，那么就放棄蟻群算法的概率選擇路徑，直接用貪婪法選擇可用的最近城市
當(dāng)然，我們需要預(yù)先建立一個(gè)“優(yōu)先城市”的矩陣，以方便查找。
技巧2 ：Fixed radius search
即在鄰域搜索的時(shí)候，也不需要嘗試一個(gè)城市跟所有其他城市的連接能否交換出更好的結(jié)果，只需要嘗試跟最靠近的若干個(gè)城市的交換
這兩個(gè)技巧可以把之前的嘗試N個(gè)城市，變?yōu)閲L試指定范圍n (n<N)，所以提速 N/n 倍，由于n取值通常是 10-30 ，所以新的算法復(fù)雜度跟N無(wú)關(guān)，而是一個(gè)常數(shù)，因此新的算法復(fù)雜度降低了一個(gè)階，變成 O(T * N^2)。
這樣的算法復(fù)雜度意味著，如果求解10個(gè)城市需要0.01秒，那么
求解150個(gè)城市就需要 15^2 * 0.01 = 2.25秒！
求解300個(gè)城市就需要 30^2 * 0.01 = 9秒！
求解1000個(gè)城市就需要 100^2 * 0.01 = 100秒！
技巧3 ： Don't look bit
原理是：如果該城市跟所有臨近城市的路徑，都無(wú)法交換出更好的結(jié)果，那么顯然在搜索它的臨近城市的時(shí)候，也不需要搜索這個(gè)城市。
做法是在鄰域搜索的時(shí)候，給每個(gè)城市設(shè)置一個(gè)標(biāo)志位，如果城市已經(jīng)檢查過(guò)無(wú)法交換出更好結(jié)果，就設(shè)置“不再檢查”標(biāo)志，后續(xù)的待查城市在嘗試交換的時(shí)候就忽略這個(gè)城市。
最基本的蟻群算法 2opt 3項(xiàng)加速技巧.rar (84.95 KB, 下載次數(shù): 529)
附件可以看出：
在應(yīng)用了這三個(gè)技巧以后，程序速度極大提高，尤其是城市數(shù)量較大的TSP問(wèn)題。
同樣用2個(gè)螞蟻，100次循環(huán)，求解 chn150.tsp，之前花了6秒多，現(xiàn)在只花了1.19秒
而求解更大規(guī)模的TSP問(wèn)題，就更明顯了。
實(shí)際上由于提高了程序速度，就可以把節(jié)約的時(shí)間花在更多螞蟻和更多循環(huán)次數(shù)上，并且多次求解以得到更高精度的結(jié)果。
我采用10個(gè)螞蟻，400次循環(huán)，求解 chn150.tsp，15秒之內(nèi)，離最優(yōu)解差異不超過(guò) 1%，多次求解發(fā)現(xiàn)最好的一次是 0.06%！
同樣地設(shè)置去求解 pr299.tsp ，是一分鐘之內(nèi)求解出距離最優(yōu)解不超過(guò)2%的解
至于 eil51.tsp 這樣的小規(guī)模問(wèn)題，幾秒內(nèi)就必定找到最優(yōu)解了！所以我在前帖才毫不客氣地說(shuō)：一切談?wù)撉蠼?eil51.tsp 的論文，都太低端了，完全不用放在眼里。
以上三個(gè)技巧全部來(lái)自《Ant Colony Optimization》（這似乎不用我再次強(qiáng)調(diào)了吧？呵呵。。。）
這一節(jié)是介紹五個(gè)版本的增強(qiáng)版蟻群算法：
精英蟻群 Elitist Ant System 縮寫(xiě)：EAS
最好最差蟻群 Best_Worst_Ant_System 縮寫(xiě)：BWAS
基于排名的蟻群Rank Based Ant System 縮寫(xiě)：RAS 或者 AS_rank
最大最小蟻群 Max_Min_Ant_System 縮寫(xiě)：MMAS
螞蟻合作群？（這個(gè)中文真不知道怎么翻譯好） Ant_Colony_System 縮寫(xiě)：ACS
我把這個(gè)內(nèi)容放在這么靠后的位置，是因?yàn)樵鰪?qiáng)版的蟻群算法，單用的性能實(shí)際上不如最基本的蟻群算法＋鄰域搜索
而且重要性也絕對(duì)比不上各種優(yōu)化技巧的總和。
當(dāng)然，增強(qiáng)版的蟻群算法＋鄰域搜索+優(yōu)化技巧，必定比上述所有附件都好的多！
先回顧一下基本蟻群算法的原理：
螞蟻每次走完所有城市，就在走過(guò)的路徑留下信息素，后續(xù)的螞蟻根據(jù)歷史信息素的多少來(lái)選擇要走的路徑
如果螞蟻的環(huán)游結(jié)果比較好，留下的信息素就比較多，從而使較好路徑的被選擇機(jī)會(huì)增加
經(jīng)過(guò)多次循環(huán)，就可以逐漸凸現(xiàn)最好的路徑。
但是，基本蟻群算法凸現(xiàn)最好路徑的速率非常慢（收斂太慢），需要數(shù)千，甚至上萬(wàn)次循環(huán)才能區(qū)分“好”路徑跟“壞”路徑
增加鄰域搜索，可以強(qiáng)迫螞蟻一定不走任何“有交叉”的路徑，從而使好的路徑更容易被找到。
增大信息素的蒸發(fā)率，也可以迅速使算法收斂，但是卻很有可能只搜索了有限的路徑，而找不到最優(yōu)解。
降低信息素的蒸發(fā)率，又必定導(dǎo)致算法變慢，而且可選路徑非常多，還是很難搜索出最優(yōu)解。
增強(qiáng)版的蟻群算法，可以幫助算法更快地收斂，還提高求解的精度。
我在頂樓貼出的《Ant Colony Optimization》一書(shū)的其中兩頁(yè)，有各種增強(qiáng)版蟻群算法的建議參數(shù)，性能比較，必讀！
從最簡(jiǎn)單的說(shuō)起吧：
1 精英蟻群 Elitist Ant System 縮寫(xiě)：EAS
精英蟻群算法，跟基本蟻群算法幾乎是完全一樣的，只不過(guò)強(qiáng)調(diào)了“精英螞蟻”的作用。
方法是：從所有已經(jīng)走完環(huán)游的螞蟻中，選擇結(jié)果最好的螞蟻，對(duì)其走過(guò)的路徑，留下特別多的信息素
最好的螞蟻可以選擇A：從求解到現(xiàn)在最佳的螞蟻，或者B：選擇本次循環(huán)的最佳螞蟻，效果其實(shí)差不多。
A方法的收斂速度快一點(diǎn)，B方法的隨機(jī)性大一點(diǎn)，對(duì)很大規(guī)模很多次循環(huán)的求解，也許是B方法好一點(diǎn)。
這個(gè)增強(qiáng)版最大優(yōu)點(diǎn)是實(shí)現(xiàn)非常簡(jiǎn)單，而且效果不錯(cuò)。
2 最好最差蟻群 Best_Worst_Ant_System 縮寫(xiě)：BWAS
這個(gè)算法幾乎跟精英蟻群一樣，也是保留一個(gè)精英螞蟻，留下特別多的信息素。
但是增加了“最壞螞蟻”的懲罰，本次循環(huán)的最差螞蟻，其路徑的信息素將多蒸發(fā)一次（如果這個(gè)路徑也被最好螞蟻?zhàn)哌^(guò)，則不懲罰）
這個(gè)算法的性能只比精英蟻群好一點(diǎn)點(diǎn)。
可以想象，由于懲罰了“壞螞蟻”，它的收斂速度也會(huì)高一點(diǎn)點(diǎn)，找到局部最優(yōu)解的所需循環(huán)數(shù)會(huì)低一些。
3 基于排名的蟻群Rank Based Ant System 縮寫(xiě)：RAS 或者 AS_rank
這個(gè)算法也跟精英螞蟻一樣原理：獎(jiǎng)勵(lì)比較好的螞蟻。
不同的是，RAS除了獎(jiǎng)勵(lì)最佳螞蟻，還獎(jiǎng)勵(lì)本次循環(huán)的多個(gè)螞蟻，而且按多個(gè)螞蟻的結(jié)果優(yōu)劣，給與不同大小的獎(jiǎng)勵(lì)。
由于多個(gè)螞蟻的隨機(jī)性比一個(gè)螞蟻強(qiáng)
所以這個(gè)算法的收斂性 低于 精英螞蟻，也就是說(shuō)，需要更多的循環(huán)數(shù)才能達(dá)到好結(jié)果。
但是求解結(jié)果比 精英螞蟻要好一些，尤其是沒(méi)有鄰域搜索的情況下。
4 最大最小蟻群 Max_Min_Ant_System 縮寫(xiě)：MMAS
這個(gè)算法是目前性能最好的蟻群算法，發(fā)明者就是《Ant Colony Optimization》一書(shū)的第二作者 Thomas Stutzle
它的做法是：
1 跟之前所有蟻群算法不同，所有螞蟻在走完環(huán)游之后，都不留信息素！
2 跟精英算法一樣，選出最佳螞蟻，最佳螞蟻可以留信息素。
3 為了防止所有信息素都被蒸發(fā)掉，最后只剩下最佳螞蟻的路徑，MMAS采用很小的蒸發(fā)率，從而保證所有路徑不會(huì)迅速變?yōu)?
4 強(qiáng)制所有路徑的信息素，有最大值和最小值限制，高于低于這個(gè)范圍都會(huì)被自動(dòng)設(shè)置為最大值或者最小值
從而保證最少信息素的路徑也有機(jī)會(huì)被選擇
這個(gè)復(fù)雜的信息素規(guī)則，得到非常好的結(jié)果，即使不用鄰域搜索，MMAS都可以直接求解出200以?xún)?nèi)規(guī)模的最優(yōu)解！
非常強(qiáng)悍！
當(dāng)然，由于蒸發(fā)率很低，所以要分出信息素的多和少（即路徑的好與壞）
MMAS需要非常多的循環(huán)數(shù)，不用鄰域搜索的話(huà)，推薦至少用3000循環(huán)。
我在頂樓的兩頁(yè)書(shū)，有各種蟻群算法不帶鄰域搜索時(shí)候的性能比較，建議細(xì)讀。
5 螞蟻合作群？ Ant_Colony_System 縮寫(xiě)：ACS
ACS算法是個(gè)絕對(duì)的異類(lèi)分子。它跟所有其他蟻群算法都大不一樣
1 它是唯一一個(gè)不帶鄰域搜索的時(shí)候，建議螞蟻數(shù)為10的算法（其余各種增強(qiáng)版算法的建議螞蟻數(shù)都是等于城市數(shù)）
所以不帶鄰域搜索的時(shí)候，它的速度是最快的，比其它算法低一個(gè)階，快N倍吖！
2 它是唯一一個(gè)邊走邊改變信息素的算法，而且所有路徑的信息素都不蒸發(fā)，如果沒(méi)有螞蟻?zhàn)哌^(guò)，就一直不變！
ACS在每個(gè)螞蟻?zhàn)哌^(guò)某個(gè)路徑時(shí)，該路徑的信息素馬上進(jìn)行蒸發(fā)，而且所有螞蟻都不留信息素！
也就是說(shuō)，螞蟻?zhàn)哌^(guò)的路徑，信息素不但不增加，而且還減少。
3 只有最佳螞蟻留下信息素，也就是說(shuō)最佳螞蟻?zhàn)哌^(guò)的路徑，信息素才增加。
4 ACS連選擇下一個(gè)城市的方法都不一樣，ACS先固定一個(gè)“直接選擇最多信息素路徑”的概率Q
在每個(gè)螞蟻選擇城市的時(shí)候，先扔一個(gè)隨機(jī)數(shù)，如果隨機(jī)數(shù)低于Q，則直接選擇“所有可選路徑里面，信息素最多的那一個(gè)路徑”（注：不一定是最接近的路徑）
如果隨機(jī)數(shù)大于Q，則采用基本蟻群算法的選擇法，計(jì)算所有可選路徑的信息素總和，計(jì)算每個(gè)路徑的選擇概率，再靠隨機(jī)數(shù)決定選哪一個(gè)。
不過(guò)可惜的是，這么復(fù)雜的規(guī)則，其性能卻并非最好，比不上MMAS。
另外，ACS的收斂速度雖然很高，但是卻不穩(wěn)定，也需要較多循環(huán)才能保證求解精度。
但非常值得一提的是，在沒(méi)有鄰域搜索的時(shí)候，ACS的速度是極快的。
現(xiàn)在，增強(qiáng)版的蟻群算法＋鄰域搜索，可以保證300以?xún)?nèi)的城市規(guī)模必定找到最優(yōu)解(MMAS，多次循環(huán)＋停滯檢測(cè)＋多次運(yùn)行)
而1000以?xún)?nèi)的城市，求解精度一般不超過(guò)最優(yōu)解的 103%。
另外，鄰域搜索的加入，似乎是“抹平”了各種增強(qiáng)版蟻群算法的性能差距，MMAS的性能還是最好的，但優(yōu)勢(shì)不是那么明顯了。
最后，附件還增加了對(duì)蟻群算法陷入停滯的檢測(cè)方法 check_stagnation
它的做法是：
經(jīng)過(guò)一定循環(huán)，如果最佳結(jié)果沒(méi)有變化，則檢查算法是否陷入停滯，如果停滯就重置所有路徑的信息素
檢查停滯是對(duì)于每個(gè)城市，計(jì)算它通往其他城市的所有路徑的信息素，求出最大值
如果路徑的信息素超過(guò) 最大值 * LAMBDA(LAMBDA通常選擇一個(gè)低數(shù)值，0.05或者0.02)，則算作一個(gè)有效路徑。
如果有效路徑低于一定數(shù)目，就判定算法陷入停滯，因?yàn)樗形浵伓荚谧咄粋€(gè)路線了，再多的循環(huán)也不會(huì)找到更好的結(jié)果。
所以需要對(duì)信息素低的路徑加強(qiáng)，讓它們也有機(jī)會(huì)被搜索到。
加入停滯檢測(cè)以后，再也不怕浪費(fèi)循環(huán)和時(shí)間了，保證指定更長(zhǎng)的循環(huán)數(shù)，將得到更好的結(jié)果。
相關(guān)演示視頻
- Ant Colony Optimization (AntSIm v1.1) Find an optimal path in labyrinth
- Ant Algorithm Simulator
- Ant Colony Optimization and Genetic Algorithms for the TSP
- Ant Colony Optimization Simulation
- Ant Colony Optimization (AntSIm v1.1)
其他資料下載
鏈接：http://pan.baidu.com/s/1o7KTaiu 密碼：sv1s
