旅行推銷員問題（Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路划址。
它是組合優(yōu)化中的一個NP困難問題音同，在運(yùn)籌學(xué)和理論計算機(jī)科學(xué)中非常重要欠动。
蟻群算法（Ant Colony Optimization, ACO）贸营，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法橙弱，對螞蟻行為進(jìn)行模仿抽象歧寺。在求解旅行推銷員問題時，螞蟻隨機(jī)從某一城市出發(fā)棘脐，根據(jù)城市間距離與殘留信息素濃度按概率選擇下一城市斜筐，螞蟻?zhàn)咄晁械某鞘泻螅谧哌^的路徑上留下信息素蛀缝，螞蟻?zhàn)叩目偮烦淘缴僮傺耄粝碌男畔⑺鼐驮蕉嗲⒔骸６啻窝h(huán)后濒蒋，最好的路徑就有可能被篩選出扇调。
- 早先接觸蟻群算法，最近重新回顧在讶，感覺頗有意思煞抬。它對數(shù)學(xué)要求不高，沒有多少公式构哺，容易理解革答。不過實(shí)力淺薄，僅分享一下個人嘗試和資料曙强，供感興趣的人探索蝗碎。
- 在代碼實(shí)現(xiàn)上，主要為蟻群和螞蟻兩個對象旗扑，簡潔清晰，感覺是良好的教學(xué)材料袱衷。
-
此外笑窜，蟻群算法結(jié)合pygame做成可視化效果，對于小朋友的吸引力應(yīng)該很大，：)
文末相關(guān)視頻中的效果圖
運(yùn)行嘗試
求解效果圖
代碼1
- 老版詳細(xì)注釋蜡塌，代碼質(zhì)量不高，便于理解：
# -*- coding: UTF-8 -*-
'''
程序主體：
類BACA的實(shí)例化->類BACA的初始化->執(zhí)行BACA.ReadCityInfo()方法->執(zhí)行BACA.Search()方法->執(zhí)行BACA.PutAnts()方法
->類ANT的初始化->類ANT的實(shí)例化->執(zhí)行ANT.MoveToNextCity()方法->執(zhí)行ANT.SelectNextCity()方法->執(zhí)行ANT.AddCity()方法
->執(zhí)行ANT.UpdatePathLen()方法->執(zhí)行BACA.UpdatePheromoneTrail()方法
蟻群算法中關(guān)鍵兩個問題，一個是選擇下一個城市的算法，主要在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ù)類型是個無序的帮非、沒有重復(fù)元素的集合陨舱，兩個sets之間可以做差集蝉揍，即在第一個集合中移出第二個集合中也存在的元素
CityList = []#城市列表即存放代表城市的序號
PheromoneTrailList = []#信息素列表（矩陣）
PheromoneDeltaTrailList = []#釋放信息素列表（矩陣）
CityDistanceList = []#兩兩城市距離列表(矩陣)
AntList = []#螞蟻列表
class BACA:#定義類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ù)列表編寫程序獲得
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)#定義一個城市到所有城市路徑信息素的初始值
pheromoneDeltaList.append(0)#定義一個城市到所有城市路徑釋放信息素的初始值
PheromoneTrailList.append(pheromoneList)#建立每個城市到所有城市路徑信息素的初始值列表矩陣
PheromoneDeltaTrailList.append(pheromoneDeltaList)#建立每個城市到所有城市路徑釋放信息素的初始值列表矩陣
def ReadCityInfo(self, fileName):#定義讀取城市文件的方法
file = open(fileName)#打開城市文件
for line in file.readlines():#逐行讀取文件
cityN, cityX, cityY = line.split()#分別提取城市序號宇色、X坐標(biāo)和Y坐標(biāo)由蘑，使用空格切分
CitySet.add(int(cityN))#在城市集合中逐步追加所有的城市序號
CityList.append((int(cityN), float(cityX), float(cityY)))#在城市列表中逐步追加每個城市序號闽寡、X坐標(biāo)和Y坐標(biāo)建立的元組
for row in range(self.CityCount):#循環(huán)總城市數(shù)的次數(shù)
distanceList = []#建立臨時儲存距離的空列表
for col in range(self.CityCount):
distance = sqrt(pow(CityList[row][1]-CityList[col][1], 2) + pow(CityList[row][2]-CityList[col][2], 2))#逐一計算每個城市到所有城市的距離值
distance = round(distance)
distanceList.append(distance)#追加一個城市到所有城市的距離值
CityDistanceList.append(distanceList)#追加么個城市到所有城市的距離值，為矩陣尼酿，即包含子列表
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ī)選擇一個城市
ant = ANT(city)#螞蟻類ANT的實(shí)例化，即將每只螞蟻隨機(jī)選擇的城市作為傳入的參數(shù)植影，使之具有ANT螞蟻類的方法和屬性
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()方法思币，獲取螞蟻每次旅行時的旅行路徑長度CurrLen鹿响，禁忌城市城市列表TabuCityList等屬性值
ant.two_opt_search()#使用鄰域優(yōu)化算法 $$$
ant.UpdatePathLen()#使用ant.UpdatePathLen更新螞蟻旅行路徑長度
tmpLen = AntList[0].CurrLen#將螞蟻列表中第一只螞蟻的旅行路徑長度賦值給新的變量tmplen
tmpTour = AntList[0].TabuCityList#將獲取的螞蟻列表的第一只螞蟻的禁忌城市列表賦值給新的變量tmpTour
for ant in AntList[1:]:#循環(huán)遍歷螞蟻列表，從索引值1開始谷饿，除第一只外
if ant.CurrLen < tmpLen:#如果循環(huán)到的螞蟻旅行路徑長度小于tmpLen即前次循環(huán)螞蟻旅行路徑長度惶我，開始值為螞蟻列表中第一只螞蟻的旅行路徑長度
tmpLen = ant.CurrLen#更新變量tmpLen的值
tmpTour = ant.TabuCityList#更新變量tmpTour的值，即更新禁忌城市列表
if tmpLen < self.Shortest:#如果從螞蟻列表中獲取的最短路徑小于初始化時定義的長度
self.Shortest = tmpLen#更新旅行路徑最短長度
BestTour = tmpTour #更新初始化時定義的最佳旅行城市次序列表
print(iter,":",self.Shortest,":",BestTour)#打印當(dāng)前迭代次數(shù)博投、最短旅行路徑長度和最佳旅行城市次序列表
self.UpdatePheromoneTrail()#完成每次迭代需要使用self绸贡，UpdatePheromoneTrail()方法更新信息素
#畫圖查看結(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):#定義更新信息素的方法，需要參考前文對于蟻群算法的闡述
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)禁忌城市緊鄰的下一個禁忌城市
PheromoneDeltaTrailList[city-1][nextCity-1] += self.Q / ant.CurrLen
#逐次更新釋放信息素列表毅哗，注意矩陣行列所代表的意義听怕，[city-1]為選取的子列表即當(dāng)前城市與所有城市間路徑的
#釋放信息素值，初始值均為0虑绵，[nextCity-1]為在子列表中對應(yīng)緊鄰的下一個城市尿瞭，釋放信息素為Q，信息素增加強(qiáng)度
#系數(shù)與螞蟻當(dāng)前旅行路徑長度CurrLen的比值翅睛，路徑長度越小釋放信息素越大声搁，反之則越小。
PheromoneDeltaTrailList[nextCity-1][city-1] += self.Q / ant.CurrLen
#在二維矩陣中捕发，每個城市路徑均出現(xiàn)兩次疏旨，分別為[city-1]對應(yīng)的[nextCity-1]和[nextCity-1]對應(yīng)的[city-1]，因此都需要更新爬骤，
#注意城市序列因?yàn)閺?開始充石，而列表索引值均從0開始，所以需要減1
lastCity = ant.TabuCityList[-1]#獲取禁忌城市列表的最后一個城市
firstCity = ant.TabuCityList[0]#獲取禁忌城市列表的第一個城市
PheromoneDeltaTrailList[lastCity-1][firstCity-1] += self.Q / ant.CurrLen
#因?yàn)槲浵伮眯行枰祷亻_始的城市霞玄，因此需要更新禁忌城市列表最后一個城市到第一個城市旅行路徑的釋放信息素值骤铃，即最后一個城市對應(yīng)第一個城市的釋放信息素值
PheromoneDeltaTrailList[firstCity-1][lastCity-1] += self.Q / ant.CurrLen
#同理更新第一個城市對應(yīng)最后一個城市的釋放信息素值
for (city1, city1X, city1Y) in CityList:#循環(huán)遍歷城市列表，主要是提取city1即城市的序號
for (city2, city2X, city2Y) in CityList:#再次循環(huán)遍歷城市列表坷剧，主要是提取city2即城市序號惰爬，循環(huán)兩次的目的仍然是對應(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:#定義螞蟻類惫企，使得螞蟻具有相應(yīng)的方法和屬性
def __init__(self, currCity = 0):#螞蟻類的初始化方法撕瞧，默認(rèn)傳入當(dāng)前城市序號為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)前旅行路徑長度
self.AddCity(currCity)#執(zhí)行AddCity()方法，獲取每次迭代的當(dāng)前城市CurrCity页畦、禁忌城市列表TabuCityList和允許城市列表AllowedCitySet的值
pass#空語句胖替，此行為空，不運(yùn)行任何操作
def SelectNextCity(self, alpha, beta):#定義螞蟻選擇下一個城市的方法豫缨，需要參考前文描述的蟻群算法
if len(self.AllowedCitySet) == 0:#如果允許城市集合為0独令，則返回0
return (0)
sumProbability = 0.0#定義概率，可能性初始值為0
self.TransferProbabilityList = []#建立選擇下一個城市可能性空列表
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)
)
#螞蟻選擇下一個城市的可能性由信息素與城市間距離之間關(guān)系等綜合因素確定好芭，其中alpha為表征信息素重要程度的參數(shù)燃箭，beta為表征啟發(fā)式因子重要程度的參數(shù)，
#該語句為前文蟻群算法闡述的選擇下一個轉(zhuǎn)移城市的概率公式的分母部分
transferProbability = sumProbability#根據(jù)信息素選擇公式和輪盤選擇得出概率列表舍败，非0-1
self.TransferProbabilityList.append((city, transferProbability))#將城市序號和對應(yīng)的轉(zhuǎn)移城市概率追加到轉(zhuǎn)移概率列表中
threshold = sumProbability * random.random()#將概率值乘以一個0~1的隨機(jī)數(shù)招狸，獲取輪盤指針值
for (cityNum, cityProb) in self.TransferProbabilityList:#再次循環(huán)遍歷概率列表
if threshold <= cityProb:#如果輪盤指針值大于概率值，則返回對應(yīng)的城市序號
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! key step!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
return (cityNum)
return (0)#否則返回0
def MoveToNextCity(self, alpha, beta):#定義轉(zhuǎn)移城市方法
nextCity = self.SelectNextCity(alpha, beta)#執(zhí)行SelectNextCity(),選擇下一個城市的方法瓤湘，獲取選擇城市的序號瓢颅，并賦值給新的變量nextCity
if nextCity > 0 : #如果選擇的城市序號大于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):#定義更新旅行路徑長度方法
for city in self.TabuCityList[0:-1]:#循環(huán)遍歷禁忌城市列表
nextCity = self.TabuCityList[self.TabuCityList.index(city)+1]#獲取禁忌城市列表中的下一個城市序號
self.CurrLen = self.CurrLen + CityDistanceList[city-1][nextCity-1]#從城市間距離之中提取當(dāng)前循環(huán)城市與下一個城市之間的距離木人，并逐次求和
lastCity = self.TabuCityList[-1]#提取禁忌列表中的最后一個城市
firstCity = self.TabuCityList[0]#提取禁忌列表中的第一個城市
self.CurrLen = self.CurrLen + CityDistanceList[lastCity-1][firstCity-1]#將最后一個城市與第一個城市的距離值加到當(dāng)前旅行路徑長度信柿，獲取循環(huán)全部城市的路徑長度
def AddCity(self, city):#定義增加城市到禁忌城市列表中的方法
if city <= 0:#如果城市序號小于等于0，則返回
return
self.CurrCity = city#更新當(dāng)前城市序號
self.TabuCityList.append(city)#將當(dāng)前城市追加到禁忌城市列表中醒第，因?yàn)橐呀?jīng)旅行過的城市不應(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__':#該語句說明之后的語句在該.py文件作為模塊被調(diào)用時，語句之后的代碼不執(zhí)行稠曼；打開.py文件直接使用時形病，語句之后的代碼則執(zhí)行。通常該語句在模塊測試中
theBaca = BACA()#BACA類的實(shí)例化
theBaca.ReadCityInfo('eil51.tsp')#讀取城市數(shù)據(jù)
theBaca.Search()#執(zhí)行Search()方法
代碼2
- 去除注釋霞幅，美化代碼漠吻，增加了最大最小蟻群規(guī)則（詳見文末資料），求解效果變好
# -*- 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):
'''
對于有0返回值的if語句不能使用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ī)制途乃，（詳見文末資料）
# -*- 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() # 每個城市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):
'''
對于有0返回值的if語句不能使用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)在暫時沒找到出處耍共，見諒烫饼。
這位同學(xué)的附件不錯，說的很詳細(xì)试读，是一個很好的入門教程
不過不夠深入杠纵，而且有些地方明顯是抄的其它中文資源
比如對MMAS的論述有很多錯誤，只是列舉一串公式?jīng)]有提到具體實(shí)現(xiàn)钩骇，凡是這樣的文章通常都是作者自己沒學(xué)會含糊其辭淡诗，要么就是直接抄的
附件應(yīng)該是抄的，因?yàn)?avg 參數(shù)的論述完全錯誤伊履，可見作者根本沒有寫過MMAS，或者寫過但是不會有他聲稱的增強(qiáng)
（如果同學(xué)看中文資料看不懂款违，很正常唐瀑，因?yàn)楹芸赡苁清e的。插爹。哄辣。。赠尾。力穗。）
其實(shí)《Ant Colony Optimization》一書就有MMAS詳細(xì)的實(shí)現(xiàn)方法和參數(shù)建議。
我現(xiàn)在看到拿 eil51.tsp 作為最終考驗(yàn)气嫁，或者求解規(guī)模在100以下的当窗，都覺得作者水平低＋多半是抄書郎了，因?yàn)橹灰约嚎催^《Ant Colony Optimization》寸宵，都絕對不止求解100規(guī)模的實(shí)力崖面。
因?yàn)橹灰辛肃徲蛩阉鳎蠼鈹?shù)百城市都不成問題梯影，根據(jù)我的經(jīng)驗(yàn)巫员，
沒有鄰域搜索的，100城市以上幾乎是絕對求不出最優(yōu)解甲棍，所以100城市是個分水嶺（我現(xiàn)在無視這個水平）
2_opt在求解300＋的城市會出現(xiàn)明顯精度下降简识，所以300城市規(guī)模也是一個分水嶺（我現(xiàn)在輕視這個水平）
3_opt在求解1000＋的城市會出現(xiàn)明顯精度下降，所以1000城市規(guī)模也是一個分水嶺（我現(xiàn)在站在這個水平）
LKH我沒學(xué)習(xí)感猛，據(jù)作者說可以直接優(yōu)化10萬城市Ｆ呷拧！唱遭！所以戳寸。。拷泽。10萬城市也是一個分水嶺（我現(xiàn)在仰望這個水平）
再次推書：《Ant Colony Optimization》一書里面的內(nèi)容是很多的疫鹊，至少還有：
1 各種蟻群算法的詳細(xì)實(shí)現(xiàn)袖瞻，及其性能比較（我在頂樓貼了性能比較和建議參數(shù)這非常重要的兩頁資料，很多資料都直接引用這兩頁而不提出處拆吆，鄙視聋迎。）
2 對算法陷入停滯的檢測方法（絕絕大多數(shù)網(wǎng)上資源根本不提這一點(diǎn)，或者提到了也是錯的枣耀，如樓上中原小農(nóng)的附件霉晕，里面說到輪盤賭選擇是避免停滯，這一句就是錯誤的捞奕，輪盤賭選擇是最基本的蟻群算法的核心實(shí)現(xiàn)牺堰，目的只是每個路徑都有機(jī)會被搜索到，跟避免算法停滯沒有半點(diǎn)關(guān)系颅围。）
3 對算法的加速技巧（應(yīng)用加速技巧伟葫，可以把蟻群算法降低一個階，變成 O(n^2) 提速幾千倍Ｔ捍佟）
4 更高級的鄰域搜索筏养，如 3_opt，k_opt常拓，LKH渐溶，絕大多數(shù)網(wǎng)上資源根本不提鄰域搜索，所以性能一般都很差弄抬。
有能力的同學(xué)絕對應(yīng)該直接看《Ant Colony Optimization》茎辐，看完就知道所有中文資源都是二手貨+太監(jiān)版（包括我的，呵呵）眉睹。
前面說到荔茬，蟻群算法 ＋ 鄰域搜索 ＝ 很好的優(yōu)化程度
但是，我們發(fā)現(xiàn)求解超過200城市規(guī)模的TSP問題竹海，還是顯得太慢慕蔚。
在進(jìn)一步深入優(yōu)化蟻群算法之前，顯然必須先解決速度太慢的問題斋配。
原有的蟻群算法的性能分析如下：
算法復(fù)雜度 = O( 循環(huán)數(shù) * 螞蟻數(shù) * 城市數(shù)^2 )
在沒有鄰域搜索輔助的情況下孔飒，設(shè)城市數(shù) = N
循環(huán)數(shù)通常需要指定一個很大的數(shù)值，假設(shè)這個值為T
而螞蟻數(shù)的取值艰争，建議＝城市數(shù)坏瞄，所以每次循環(huán)計算所有螞蟻需要 O(N)
一個螞蟻的一個方案需要選擇N個城市，每次選擇需要從 最多N個候選城市中遍歷并且計算選擇概率甩卓，所以建立一個方案是 O(N^2)
所以算法的復(fù)雜度 ＝ T * N^3鸠匀，即 O(T * N^3)
這樣的算法復(fù)雜度意味著，如果求解10個城市需要0.01秒逾柿，那么
求解150個城市就需要 15^3 * 0.01 = 33.75秒缀棍！
求解300個城市就需要 30^3 * 0.01 = 270秒宅此！
求解1000個城市就需要 100^3 * 0.01 = 1萬秒！
程序耗時隨著城市數(shù)增大爬范，呈現(xiàn)3次方增長父腕，這顯然是無法求解更大規(guī)模的問題的。
在使用了鄰域搜索以后青瀑，我們發(fā)現(xiàn)可以大大減少需要的循環(huán)數(shù)璧亮，即T可以降低，但即使忽略不計T這個值斥难，程序仍然是 O(N^3)增長速度枝嘶，一切還是不變。
采用以下三個技巧哑诊，可以把 算法復(fù)雜度降低到 O(T * N^2)
頭兩個加速技巧都基于一個事實(shí)： TSP問題最優(yōu)解的每個城市連接的都必定是附近的城市躬络！
所以在螞蟻尋路的時候，也只需要嘗試附近的幾個城市即可搭儒，不需要嘗試所有的城市！
技巧1 ： candidate list提茁，或者說 Nearest city list
即每個螞蟻在計算如何選擇下一個城市時淹禾，只計算距離當(dāng)前城市距離最近的若干個城市，如果這些距離最近的城市已經(jīng)走過茴扁，那么就放棄蟻群算法的概率選擇路徑铃岔，直接用貪婪法選擇可用的最近城市
當(dāng)然，我們需要預(yù)先建立一個“優(yōu)先城市”的矩陣峭火，以方便查找毁习。
技巧2 ：Fixed radius search
即在鄰域搜索的時候，也不需要嘗試一個城市跟所有其他城市的連接能否交換出更好的結(jié)果卖丸，只需要嘗試跟最靠近的若干個城市的交換
這兩個技巧可以把之前的嘗試N個城市纺且，變?yōu)閲L試指定范圍n (n<N)，所以提速 N/n 倍稍浆，由于n取值通常是 10-30 载碌，所以新的算法復(fù)雜度跟N無關(guān)，而是一個常數(shù)衅枫，因此新的算法復(fù)雜度降低了一個階嫁艇，變成 O(T * N^2)。
這樣的算法復(fù)雜度意味著弦撩，如果求解10個城市需要0.01秒步咪，那么
求解150個城市就需要 15^2 * 0.01 = 2.25秒！
求解300個城市就需要 30^2 * 0.01 = 9秒益楼！
求解1000個城市就需要 100^2 * 0.01 = 100秒猾漫！
技巧3 ： Don't look bit
原理是：如果該城市跟所有臨近城市的路徑点晴，都無法交換出更好的結(jié)果，那么顯然在搜索它的臨近城市的時候静袖，也不需要搜索這個城市觉鼻。
做法是在鄰域搜索的時候，給每個城市設(shè)置一個標(biāo)志位队橙，如果城市已經(jīng)檢查過無法交換出更好結(jié)果坠陈，就設(shè)置“不再檢查”標(biāo)志，后續(xù)的待查城市在嘗試交換的時候就忽略這個城市捐康。
最基本的蟻群算法 2opt 3項(xiàng)加速技巧.rar (84.95 KB, 下載次數(shù): 529)
附件可以看出：
在應(yīng)用了這三個技巧以后仇矾，程序速度極大提高，尤其是城市數(shù)量較大的TSP問題解总。
同樣用2個螞蟻贮匕，100次循環(huán)，求解 chn150.tsp花枫，之前花了6秒多刻盐，現(xiàn)在只花了1.19秒
而求解更大規(guī)模的TSP問題，就更明顯了劳翰。
實(shí)際上由于提高了程序速度敦锌，就可以把節(jié)約的時間花在更多螞蟻和更多循環(huán)次數(shù)上，并且多次求解以得到更高精度的結(jié)果佳簸。
我采用10個螞蟻乙墙，400次循環(huán)，求解 chn150.tsp生均，15秒之內(nèi)听想，離最優(yōu)解差異不超過 1%，多次求解發(fā)現(xiàn)最好的一次是 0.06%马胧！
同樣地設(shè)置去求解 pr299.tsp 汉买，是一分鐘之內(nèi)求解出距離最優(yōu)解不超過2%的解
至于 eil51.tsp 這樣的小規(guī)模問題，幾秒內(nèi)就必定找到最優(yōu)解了佩脊！所以我在前帖才毫不客氣地說：一切談?wù)撉蠼?eil51.tsp 的論文录别，都太低端了，完全不用放在眼里邻吞。
以上三個技巧全部來自《Ant Colony Optimization》（這似乎不用我再次強(qiáng)調(diào)了吧组题？呵呵。抱冷。崔列。）
這一節(jié)是介紹五個版本的增強(qiáng)版蟻群算法：
精英蟻群 Elitist Ant System 縮寫：EAS
最好最差蟻群 Best_Worst_Ant_System 縮寫：BWAS
基于排名的蟻群Rank Based Ant System 縮寫：RAS 或者 AS_rank
最大最小蟻群 Max_Min_Ant_System 縮寫：MMAS
螞蟻合作群？（這個中文真不知道怎么翻譯好） Ant_Colony_System 縮寫：ACS
我把這個內(nèi)容放在這么靠后的位置，是因?yàn)樵鰪?qiáng)版的蟻群算法赵讯，單用的性能實(shí)際上不如最基本的蟻群算法＋鄰域搜索
而且重要性也絕對比不上各種優(yōu)化技巧的總和盈咳。
當(dāng)然，增強(qiáng)版的蟻群算法＋鄰域搜索+優(yōu)化技巧边翼，必定比上述所有附件都好的多鱼响！
先回顧一下基本蟻群算法的原理：
螞蟻每次走完所有城市，就在走過的路徑留下信息素组底，后續(xù)的螞蟻根據(jù)歷史信息素的多少來選擇要走的路徑
如果螞蟻的環(huán)游結(jié)果比較好丈积，留下的信息素就比較多，從而使較好路徑的被選擇機(jī)會增加
經(jīng)過多次循環(huán)债鸡，就可以逐漸凸現(xiàn)最好的路徑江滨。
但是，基本蟻群算法凸現(xiàn)最好路徑的速率非常慢（收斂太慢）厌均，需要數(shù)千唬滑，甚至上萬次循環(huán)才能區(qū)分“好”路徑跟“壞”路徑
增加鄰域搜索，可以強(qiáng)迫螞蟻一定不走任何“有交叉”的路徑棺弊，從而使好的路徑更容易被找到晶密。
增大信息素的蒸發(fā)率，也可以迅速使算法收斂模她，但是卻很有可能只搜索了有限的路徑惹挟，而找不到最優(yōu)解。
降低信息素的蒸發(fā)率缝驳，又必定導(dǎo)致算法變慢，而且可選路徑非常多归苍，還是很難搜索出最優(yōu)解用狱。
增強(qiáng)版的蟻群算法，可以幫助算法更快地收斂拼弃，還提高求解的精度夏伊。
我在頂樓貼出的《Ant Colony Optimization》一書的其中兩頁，有各種增強(qiáng)版蟻群算法的建議參數(shù)吻氧，性能比較溺忧，必讀！
從最簡單的說起吧：
1 精英蟻群 Elitist Ant System 縮寫：EAS
精英蟻群算法盯孙，跟基本蟻群算法幾乎是完全一樣的鲁森，只不過強(qiáng)調(diào)了“精英螞蟻”的作用。
方法是：從所有已經(jīng)走完環(huán)游的螞蟻中振惰，選擇結(jié)果最好的螞蟻歌溉，對其走過的路徑，留下特別多的信息素
最好的螞蟻可以選擇A：從求解到現(xiàn)在最佳的螞蟻，或者B：選擇本次循環(huán)的最佳螞蟻痛垛，效果其實(shí)差不多草慧。
A方法的收斂速度快一點(diǎn)，B方法的隨機(jī)性大一點(diǎn)匙头，對很大規(guī)模很多次循環(huán)的求解漫谷，也許是B方法好一點(diǎn)。
這個增強(qiáng)版最大優(yōu)點(diǎn)是實(shí)現(xiàn)非常簡單蹂析，而且效果不錯舔示。
2 最好最差蟻群 Best_Worst_Ant_System 縮寫：BWAS
這個算法幾乎跟精英蟻群一樣，也是保留一個精英螞蟻识窿，留下特別多的信息素斩郎。
但是增加了“最壞螞蟻”的懲罰，本次循環(huán)的最差螞蟻喻频，其路徑的信息素將多蒸發(fā)一次（如果這個路徑也被最好螞蟻?zhàn)哌^缩宜，則不懲罰）
這個算法的性能只比精英蟻群好一點(diǎn)點(diǎn)。
可以想象甥温，由于懲罰了“壞螞蟻”锻煌，它的收斂速度也會高一點(diǎn)點(diǎn)，找到局部最優(yōu)解的所需循環(huán)數(shù)會低一些姻蚓。
3 基于排名的蟻群Rank Based Ant System 縮寫：RAS 或者 AS_rank
這個算法也跟精英螞蟻一樣原理：獎勵比較好的螞蟻宋梧。
不同的是，RAS除了獎勵最佳螞蟻狰挡，還獎勵本次循環(huán)的多個螞蟻捂龄，而且按多個螞蟻的結(jié)果優(yōu)劣，給與不同大小的獎勵加叁。
由于多個螞蟻的隨機(jī)性比一個螞蟻強(qiáng)
所以這個算法的收斂性 低于 精英螞蟻倦沧，也就是說，需要更多的循環(huán)數(shù)才能達(dá)到好結(jié)果它匕。
但是求解結(jié)果比 精英螞蟻要好一些展融，尤其是沒有鄰域搜索的情況下。
4 最大最小蟻群 Max_Min_Ant_System 縮寫：MMAS
這個算法是目前性能最好的蟻群算法豫柬，發(fā)明者就是《Ant Colony Optimization》一書的第二作者 Thomas Stutzle
它的做法是：
1 跟之前所有蟻群算法不同告希，所有螞蟻在走完環(huán)游之后，都不留信息素烧给！
2 跟精英算法一樣燕偶，選出最佳螞蟻，最佳螞蟻可以留信息素础嫡。
3 為了防止所有信息素都被蒸發(fā)掉杭跪，最后只剩下最佳螞蟻的路徑，MMAS采用很小的蒸發(fā)率，從而保證所有路徑不會迅速變?yōu)?
4 強(qiáng)制所有路徑的信息素涧尿，有最大值和最小值限制系奉，高于低于這個范圍都會被自動設(shè)置為最大值或者最小值
從而保證最少信息素的路徑也有機(jī)會被選擇
這個復(fù)雜的信息素規(guī)則，得到非常好的結(jié)果姑廉，即使不用鄰域搜索缺亮，MMAS都可以直接求解出200以內(nèi)規(guī)模的最優(yōu)解！
非常強(qiáng)悍桥言！
當(dāng)然萌踱，由于蒸發(fā)率很低，所以要分出信息素的多和少（即路徑的好與壞）
MMAS需要非常多的循環(huán)數(shù)号阿，不用鄰域搜索的話并鸵，推薦至少用3000循環(huán)。
我在頂樓的兩頁書扔涧，有各種蟻群算法不帶鄰域搜索時候的性能比較园担，建議細(xì)讀。
5 螞蟻合作群枯夜？ Ant_Colony_System 縮寫：ACS
ACS算法是個絕對的異類分子弯汰。它跟所有其他蟻群算法都大不一樣
1 它是唯一一個不帶鄰域搜索的時候，建議螞蟻數(shù)為10的算法（其余各種增強(qiáng)版算法的建議螞蟻數(shù)都是等于城市數(shù)）
所以不帶鄰域搜索的時候湖雹，它的速度是最快的咏闪，比其它算法低一個階，快N倍吖摔吏！
2 它是唯一一個邊走邊改變信息素的算法鸽嫂，而且所有路徑的信息素都不蒸發(fā)，如果沒有螞蟻?zhàn)哌^征讲，就一直不變据某！
ACS在每個螞蟻?zhàn)哌^某個路徑時，該路徑的信息素馬上進(jìn)行蒸發(fā)稳诚，而且所有螞蟻都不留信息素！
也就是說瀑踢，螞蟻?zhàn)哌^的路徑扳还，信息素不但不增加，而且還減少橱夭。
3 只有最佳螞蟻留下信息素氨距，也就是說最佳螞蟻?zhàn)哌^的路徑，信息素才增加棘劣。
4 ACS連選擇下一個城市的方法都不一樣俏让，ACS先固定一個“直接選擇最多信息素路徑”的概率Q
在每個螞蟻選擇城市的時候，先扔一個隨機(jī)數(shù)，如果隨機(jī)數(shù)低于Q首昔，則直接選擇“所有可選路徑里面寡喝，信息素最多的那一個路徑”（注：不一定是最接近的路徑）
如果隨機(jī)數(shù)大于Q，則采用基本蟻群算法的選擇法勒奇，計算所有可選路徑的信息素總和预鬓，計算每個路徑的選擇概率，再靠隨機(jī)數(shù)決定選哪一個赊颠。
不過可惜的是格二，這么復(fù)雜的規(guī)則，其性能卻并非最好竣蹦，比不上MMAS顶猜。
另外，ACS的收斂速度雖然很高痘括，但是卻不穩(wěn)定长窄，也需要較多循環(huán)才能保證求解精度。
但非常值得一提的是远寸，在沒有鄰域搜索的時候抄淑，ACS的速度是極快的。
現(xiàn)在驰后，增強(qiáng)版的蟻群算法＋鄰域搜索肆资，可以保證300以內(nèi)的城市規(guī)模必定找到最優(yōu)解(MMAS，多次循環(huán)＋停滯檢測＋多次運(yùn)行)
而1000以內(nèi)的城市灶芝，求解精度一般不超過最優(yōu)解的 103%郑原。
另外，鄰域搜索的加入夜涕，似乎是“抹平”了各種增強(qiáng)版蟻群算法的性能差距犯犁，MMAS的性能還是最好的，但優(yōu)勢不是那么明顯了女器。
最后酸役，附件還增加了對蟻群算法陷入停滯的檢測方法 check_stagnation
它的做法是：
經(jīng)過一定循環(huán)，如果最佳結(jié)果沒有變化驾胆，則檢查算法是否陷入停滯涣澡，如果停滯就重置所有路徑的信息素
檢查停滯是對于每個城市，計算它通往其他城市的所有路徑的信息素丧诺，求出最大值
如果路徑的信息素超過 最大值 * LAMBDA(LAMBDA通常選擇一個低數(shù)值入桂，0.05或者0.02)，則算作一個有效路徑驳阎。
如果有效路徑低于一定數(shù)目牲证，就判定算法陷入停滯，因?yàn)樗形浵伓荚谧咄粋€路線了甲抖，再多的循環(huán)也不會找到更好的結(jié)果愚屁。
所以需要對信息素低的路徑加強(qiáng)，讓它們也有機(jī)會被搜索到。
加入停滯檢測以后，再也不怕浪費(fèi)循環(huán)和時間了，保證指定更長的循環(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
