同進化算法（進化算法是受生物進化機制啟發而産生的一系列算法）和人工神經網絡算法（神經網絡是從資訊處理角度對人腦的神經元網絡系統進行了模拟的相關算法）一樣，群智能優化算法也屬于一種生物啟發式方法，它們三者可以稱為是人工智能領域的三駕馬車（實際上除了上述三種算法還有一些智能算法應用也很廣泛，比如模拟金屬物質熱力學退火過程的模拟退火算法（Simulated Algorithm,簡稱SA），模拟人體免疫系統在抗原刺激下産生抗體過程的人工免疫系統算法（Artificial Immune System,簡稱AIS）等，但是相對三者而言，模拟退火算法和人工免疫系統算法已逐漸處于低潮期）。群智能優化算法主要是模拟了昆蟲，獸群、鳥群和魚群的群集行為，這些群體按照一種合作的方式尋找食物，群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷地改變搜尋的方向。群體智能優化算法的突出特點就是利用了種群的群體智慧進行協同搜尋，進而在解空間内找到最優解。

常見的群體智能優化算法主要有如下幾類：

蟻群算法（Ant Colony Optimizatio,簡稱ACO）【1992年提出】；

粒子群優化算法（Particle Swarm Optimization,簡稱PSO）【1995年提出】

菌群優化算法（Bacterial Foraging Optimization，簡稱BFO）【2002年提出】

蛙跳算法（Shuffled Frog Leading Algorithm,簡稱SFLA）【2003年提出】

人工蜂群算法（Artificial Bee Colony Algorithm,簡稱ABC）【2005年提出】

除了上述幾種常見的群體智能算法以外，還有一些并不是廣泛應用的群體智能算法，比如螢火蟲算法，布谷鳥算法，蝙蝠算法以及磷蝦群算法等等。

蟻群算法

螞蟻尋找食物的過程

單隻螞蟻的行為及其簡單，行為數量在10種以内，但成千上萬隻螞蟻組成的蟻群卻能擁有巨大的智慧，這離不開它們資訊傳遞的方式———資訊素。

螞蟻在行走過程中會釋放一種稱為"資訊素"的物質，用來辨別自己的行走路徑。在尋找食物的過程中，根據資訊素的濃度選擇行走的方向，并最終到達食物所在的地方。

資訊素會随着時間的推移而逐漸揮發。

在一開始的時候，由于地面上沒有資訊素，是以螞蟻們的行走路勁是随機的。螞蟻們在行走的過程中會不斷釋放資訊素，辨別自己的行走路徑。随着時間的推移，有若幹隻螞蟻找到了食物，此時便存在若幹條從洞穴到食物的路徑。由于螞蟻的行為軌迹是随機分布的，是以在機關時間内，短路徑上的螞蟻數量比長路徑上的螞蟻數量要多，進而螞蟻留下的資訊素濃度也就越高。這為後面的螞蟻們提供了強有力的方向指引，越來越多的螞蟻聚集到最短的路徑上去。

什麼是蟻群算法

蟻群算法就是模拟螞蟻尋找食物的過程，它能夠求出從原點出發，經過若幹個給定的需求點，最終傳回原點的最短路徑。這也就是著名的旅行商問題（Traveling Saleman Problem, TSP）。

蟻群算法規則

覓食規則

螞蟻感覺範圍是一個3*3的格子，也就是說，他這個格子有食物就直接過去

移動規則

螞蟻會朝着資訊素濃的地方移動，如果沒有感覺到資訊素，就會按着慣性一直走下去，别忘了螞蟻會創新。

避障規則

螞蟻在遇到障礙物的時候會選擇随機方向移動，同時遵循上面兩個規則。

import os,sys,random
from math import *
import pylab as pl
import pandas as pd
BestTour=[]     #用于放置最佳路徑選擇城市的順序
CitySet=set()   #sets資料類型是無序的，沒有重複元素的集合，兩個sets之間可以做差集，即第一個集合中移除第二個集合中也存在的元素
CityList=[]     #城市清單即存放代表城市的序号
PheromoneTraiList=[]  #資訊素清單（矩陣）
PheromoneDeltaTraiList=[]  #釋放資訊素清單（矩陣）
CityDistanceList=[]   #兩兩城市距離清單（矩陣）
AntList=[]      #螞蟻清單
class BACA:#定義類BACA，執行蟻群算法
    def __init__(self,citycount=51,antCount=51,q=80,alpha=1,beta=3,rou=0.4,nMax=300):
        #初始化方法，antCount為螞蟻數，nMax為疊代次數
        self.CityCount=citycount #城市數量
        self.AnCount=antCount   #螞蟻數量
        self.Q=q                #資訊素增加強度系數
        self.Alpha=alpha        #表征資訊素重要程度的參數
        self.Beta=beta          #表征啟發因子重要程度的參數
        self.Rou=rou            #資訊素蒸發系數
        self.Nmax=nMax          #最大疊代次數
        self.Shortest=10e6      #初始化最短距離應該盡可能大，至少大于估算的最大城市旅行距離
        pl.show()
        random.seed()           #設定随機種子
        #初始化全局資料結構及值
        for nCity in range(self.CityCount):#循環城市總數的次數
            BestTour.append(0)#設定最佳路徑初始值均為0
        for row in range(self.CityCount):
            pheromoneList=[]     #定義空的資訊素清單
            pheromoneDeltaList=[]   #定義空的資訊素清單
            for col in range(self.CityCount):
                pheromoneList.append(100)   #定義一個城市到所有城市資訊素的初始值
                pheromoneDeltaList.append(0) #定義一個城市到所有城市釋放資訊素的初始值
            PheromoneTraiList.append(pheromoneList)  #建立每個城市到所有城市路徑資訊素的初始值清單
            PheromoneDeltaTraiList.append(pheromoneDeltaList)  #建立每個城市到所有城市路徑釋放資訊素的初始值清單矩陣
    def ReadCityInfo(self,fileName):
        file=open(fileName)
        for line in file.readlines():
            cityN,cityX,cityY=line.split()
            CitySet.add(int(cityN))
            CityList.append((int(cityN),float(cityX),float(cityY)))
        for row in range(self.CityCount):
            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()
    def PutAnts(self):   #定義螞蟻所選擇城市以及将城市作為參數定義螞蟻的方法和屬性
        AntList.clear()
        for antNum in range(self.AnCount):
            city=random.randint(1,self.CityCount)
            ant=ANT(city)   #螞蟻類ANT的執行個體化，即将每隻螞蟻随機選擇的城市作為傳入的參數，使之具有ANT螞蟻類的方法和屬性
            AntList.append(ant)   #将定義的每隻螞蟻追加到清單中
    def Search(self):  #定義搜尋最佳旅行路徑方法的主程式
        for iter in range(self.Nmax):
            self.PutAnts()
            for ant in AntList:
                for ttt in range(len(CityList)):
                    #執行螞蟻ant.MoveToNextCity()方法，擷取螞蟻每次旅行時的旅行路徑長度Currlen,禁忌城市清單TabuCityLsit等屬性值
                    ant.MoveToNextCity(self.Alpha,self.Beta)
                ant.two_opt_search()
                ant.UpdatePathLen()
            tmpLen=AntList[0].CurrLen  #将螞蟻清單中第一隻螞蟻的旅行路徑長度指派給新的變量tmpLen
            tmpTour=AntList[0].TabuCityList  #将擷取的螞蟻清單的第一隻螞蟻的禁忌城市清單指派給新的變量tmpTour
            for ant in AntList[1:]:   #循環周遊螞蟻清單，從索引值1開始，除第一隻外
                if ant.CurrLen < tmpLen:
                    tmpLen=ant.CurrLen
                    tmpTour=ant.TabuCityList
            if tmpLen < self.Shortest:
                self.Shortest=tmpLen
                BestTour = tmpTour
            print(iter,":",self.Shortest,":",BestTour)
            pl.clf()
            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.scatter(x, y, s=30, c='r')
            pl.pause(0.01)
            self.UpdatePheromoneTrail()

    def UpdatePheromoneTrail(self): #定義更新資訊素的方法
        for ant in AntList:
            for city in ant.TabuCityList[0:-1]:
                idx=ant.TabuCityList.index(city)   #擷取目前循環，禁忌城市的索引值
                nextCity=ant.TabuCityList[idx+1]
                PheromoneDeltaTraiList[city-1][nextCity-1]+=self.Q/ant.CurrLen
                #逐次更新釋放資訊索清單，注意矩陣行列索代表的意義，[city-1]為選取的子清單即目前城市與所有城市間路勁的
                #的釋放資訊素值，初始值均為0，[nextCity-1]為在子清單中對應緊鄰的下一個城市，釋放資訊素為Q，資訊素增加強度
                #系數與螞蟻目前旅行路徑長度CurrLen的比值，路徑長度越小釋放資訊素越大，反之則越小。
                PheromoneDeltaTraiList[nextCity-1][city-1]+=self.Q/ant.CurrLen
            lastCity=ant.TabuCityList[-1]
            firstCity=ant.TabuCityList[0]
            PheromoneDeltaTraiList[lastCity-1][firstCity-1]+=self.Q/ant.CurrLen
            PheromoneDeltaTraiList[firstCity-1][lastCity-1]+=self.Q/ant.CurrLen
        for(city1,city1x,city1y) in CityList:
            for(city2,city2x,city2y) in CityList:
                PheromoneTraiList[city1-1][city2-1]=(1-self.Rou)*PheromoneTraiList[city1-1][city2-1]+PheromoneDeltaTraiList[city1-1][city2-1]
                PheromoneDeltaTraiList[city1 - 1][city2 - 1]=0



class ANT:  #定義螞蟻類
    def __init__(self,currCity=0):
        self.TabuCitySet=set()
        #定義禁忌城市集合，定義集合的目的是集合本身要素不重複并且之間可以做差集運算，例如AddCity()方法中
        #self.AllowedCitySet=CitySet-self.TabuCitySet 可以友善地從城市集合中去除禁忌城市清單的城市，擷取允許的城市清單
        self.TabuCityList=[]  #定義禁忌城市空清單
        self.AllowedCitySet=set() #定義允許城市集合
        self.TransferProbabilityList=[]  #定義城市選擇可能性清單
        self.CurrCity=0        #定義目前城市初始值為0
        self.CurrLen=0.0       #定義目前旅行路徑長度
        self.AddCity(currCity)   #執行AddCity()方法，擷取每次疊代的目前城市CurrCity,禁忌城市清單TabuCityList和允許城市清單AllowedCitySet的值
    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: #循環周遊允許城市集合
            sumProbability=sumProbability+(pow(PheromoneTraiList[self.CurrCity-1][city-1],alpha)*pow(1.0/CityDistanceList[self.CurrCity-1][city-1],beta))
            #螞蟻選擇下一個城市的可能性由資訊素與城市間距離之間關系等綜合因素确定，其中alpha為表征資訊素重要程度的參數，beta為表征啟發式因子重要程度的參數
            transferProbability=sumProbability  #根據資訊素選擇公式和輪盤選擇得出機率清單，非0-1
            self.TransferProbabilityList.append((city,transferProbability))  #将城市序号和對應的轉移城市機率追加到轉移機率清單中
        threshold=sumProbability*random.random()  #将機率乘以一個0-1的随機數，擷取輪盤制指針值
        for(cityNum,cityProb) in self.TransferProbabilityList:
            if threshold<=cityProb:
                return (cityNum)
        return (0)
    def AddCity(self,city):    #定義增加城市到禁忌城市清單中的方法
        if city<=0:
            return
        self.CurrCity=city   #更新目前城市序号
        self.TabuCityList.append(city)  #将目前城市追加到禁忌城市清單中，因為已經旅行過的城市不應該再進入
        self.TabuCitySet.add(city)      #将目前城市追加到禁忌城市集合中，用于差集運算
        self.AllowedCitySet=CitySet-self.TabuCitySet  #使用集合差集的方法擷取允許的城市清單
    def MoveToNextCity(self,alpha,beta):  #定義轉移城市方法
        nextCity=self.SelectNextCity(alpha,beta)
        if nextCity > 0:
            self.AddCity(nextCity)     #執行self.AddCity()方法
    def ClearTabu(self):
        self.TabuCityList=[]
        self.TabuCitySet.clear()
        self.AllowedCitySet=CitySet-self.TabuCitySet
    def UpdatePathLen(self):
        for city in self.TabuCityList[0:-1]:#循環周遊禁忌城市清單
            nextCity=self.TabuCityList[self.TabuCityList.index(city)+1]     #擷取禁忌城市清單中的下一個城市序号
            self.CurrLen=self.CurrLen+CityDistanceList[city-1][nextCity-1]  #從城市間距離之中提取目前循環城市與下一個城市之間的距離，并逐次求和
        lastCity=self.TabuCityList[-1]  #提取禁清單中的最後一個城市
        firstCity=self.TabuCityList[0]  #提取禁忌清單中的第一個城市
        self.CurrLen=self.CurrLen+CityDistanceList[lastCity-1][firstCity-1]
    def two_opt_search(self):  #領域搜尋
        cityNum=len(CityList)
        for i in range(cityNum):
            for j in range(cityNum-1,i,-1):
                curCity1=self.TabuCityList[i]-1
                preCity1=self.TabuCityList[(i-1)%cityNum]-1
                nextCity1=self.TabuCityList[(i+1)%cityNum]-1
                curCity2=self.TabuCityList[j]-1
                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]
if __name__=='__main__':
    theBaca=BACA()
    theBaca.ReadCityInfo('eil511.tsp')
    theBaca.Search()