Python實現(xiàn)蟻群優(yōu)化算法的示例代碼

更新時間：2023年08月04日 08:37:51 作者：微小冷

蟻群算法是一種源于大自然生物世界的新的仿生進(jìn)化算法，本文主要介紹了Python如何實現(xiàn)蟻群算法，文中通過示例代碼具有一定的參考價值，感興趣的小伙伴們可以了解一下

蟻群算法

蟻群算法是Colori A等人在1991年提出的，通過模仿螞蟻覓食行為，抽象出信息素這一獎懲機(jī)制，從而賦予螞蟻智能Agent的身份，使之得以在最佳路線問題中大展身手。

現(xiàn)有一群螞蟻想從A0?點走到An?點，假設(shè)兩點中間有多條路徑可以選擇，螞蟻不知道哪條路更近，所以最開始無論選擇哪條路，機(jī)會都是相等的。但是，當(dāng)某一條路有螞蟻走過之后，就會留下信息素，如果每一只螞蟻的速度是恒定的，那么路程越短，螞蟻在這條路上往返也就越快，反過來說，單位時間內(nèi)，越短的路會有更多的螞蟻走過，從而留下的信息素就會越多，這就是蟻群算法的基本原理了。

當(dāng)不同路徑均留下信息素后，螞蟻們再行選擇路線就不是等概率的了，他們會有更大的概率選擇信息素更濃的路線。隨著時間的推演，信息素也會揮發(fā)，從而螞蟻們不斷更新他們的路線，這個過程就是蟻群優(yōu)化(Ant Clony Optimization, ACO)。

螞蟻的基本變量

很顯然，蟻群算法的前提是來一群螞蟻對象，而螞蟻作為一個智能體，至少要有一些記憶，需要記住以下內(nèi)容

城市個數(shù)
城市地圖
每個城市留下的信息素
已經(jīng)走過和尚未到達(dá)的城市
移動的步數(shù)
已經(jīng)走過的距離

而經(jīng)過初始化之后，這個螞蟻必須得來到某個城市，所以需要一個隨機(jī)選擇城市的函數(shù)，下面就是一個螞蟻所必備的初始化流程

import numpy as np
from functools import reduce
class Ant(object):
    def __init__(self, nCity, graph, pheromone):
        self.nCity = nCity          # 城市數(shù)
        self.graph = graph          # 城市地圖
        self.pheromone = pheromone  # 信息素地圖
        self.cityEnabled = [True] * nCity  # 尚未到達(dá)的城市標(biāo)記
        self.nMove = 0              # 移動步數(shù)
        self.dTotal = 0.0           # 已經(jīng)走過的距離
        self.initData()             # 初始化出生點
    # 隨機(jī)選擇城市
    def randCity(self):
        return np.random.randint(0,self.nCity-1) 
    # 初始化
    def initData(self):
        self.nowCity = self.randCity()          # 隨機(jī)選擇一個城市
        self.path = [self.nowCity]              # 保存當(dāng)前走過的城市
        self.cityEnabled[self.nowCity] = False  # 當(dāng)前城市不再探索
        self.nMove = 1                          # 初始時的移動計數(shù)

螞蟻的優(yōu)化流程

某只螞蟻在初始化之后，就要通過它敏銳的“嗅覺”選擇下一個城市，直到走完所有城市為止。而選擇城市時，需要用到信息素地圖作為判斷依據(jù)。信息素濃度為p，兩點距離為d，則螞蟻前往該城市的概率為

其中，α和β分別叫做信息素啟發(fā)因子和期望啟發(fā)因子，故而在Ant類中新建方法：

# 計算到達(dá)第i個城市的概率
def getOneProb(self, i):
    ALPHA = 1.0
    BETA = 2.0
    dis = self.graph[self.nowCity][i]
    phe = self.pheromone[self.nowCity][i]
    # 計算移動到該城市的概率
    if not self.cityEnabled[i]: return 0  
    else: return pow(phe, ALPHA) * pow(1/dis, BETA)

有了這個，就可以得到去所有城市的概率，然后隨機(jī)則取

def choiceNext(self):
    # 前往所有城市的概率
    pSlct = [self.getOneProb(i) for i in range(self.nCity)]
    pSum = np.cumsum(pSlct)
    # 生成一個隨機(jī)數(shù)，這個隨機(jī)數(shù)在pSum中落入的區(qū)間就是選擇的城市
    pTemp = np.random.uniform(0.0, pSum[-1])
    return  np.searchsorted(pSum, pTemp)

在選中接下來前往的城市之后，就要動身前往

# 移動到新的城市
def moveTo(self, city):
    self.path.append(city)          # 添加目標(biāo)城市
    self.cityEnabled[city] = False  # 目標(biāo)城市不可再探索
    # 總路程增加當(dāng)前城市到目標(biāo)城市的距離
    self.dTotal += self.graph[self.nowCity][city]  
    self.nowCity = city             # 更新當(dāng)前城市
    self.nMove += 1                 # 移動次數(shù)

唯一需要注意的是，旅行商問題要求走一圈，也就是說，當(dāng)走遍所有城市之后，要記得把第一個城市和最后一個城市的距離添加到全部路程當(dāng)中，故其總的搜索流程如下

def run(self):
    self.initData()
    while self.nMove < self.nCity:
        next_city = self.choiceNext()
        self.moveTo(next_city)
    self.dTotal += self.graph[self.path[0]][self.path[-1]]
    return self.dTotal

至此，就實現(xiàn)了一個螞蟻類。

蟻群優(yōu)化

有了螞蟻，那么接下來就要有蟻群，以及適用于蟻群算法的城市網(wǎng)點。設(shè)城市坐標(biāo)序列為xi?和yi?，則根據(jù)這組坐標(biāo)點的個數(shù)就是城市數(shù)nCity，而城市距離矩陣可表示為

另一方面，蟻群優(yōu)化過程中，信息素更新至關(guān)重要，其值受到兩個因素影響，一是螞蟻走過會使之增加，二則是時間流逝會使之揮發(fā)，故而需要有一個揮發(fā)系數(shù)RHO。信息素更新函數(shù)如下

# 更新信息素
RHO = 0.5       # 信息素?fù)]發(fā)系數(shù)
def updatePheromone(nCity, pheromone, ants):
    # 初始化螞蟻在兩兩城市間的信息素, 50行50列
    temp = np.zeros([nCity, nCity])
    # 遍歷每只螞蟻對象
    for ant in ants:
        for i in range(1, nCity):  # 遍歷該螞蟻經(jīng)過的每個城市
            st, ed = ant.path[i-1], ant.path[i]
            # 在兩個城市間留下信息素，濃度與總距離成反比
            temp[st, ed] += Q / ant.dTotal
            temp[ed, st] = temp[st, ed]  # 信息素矩陣軸對稱
    return pheromone * RHO + temp

至此，萬事俱備，只欠東風(fēng)，蟻群優(yōu)化算法的主體程序如下

import copy
# xs, ys為城市的x和y坐標(biāo)
# nAnts為螞蟻個數(shù), nIter為迭代次數(shù)
def aco(xs, ys, nAnts, nIter):
    nCity = len(xs)
    xMat, yMat = xs-xs.reshape(-1,1), ys-ys.reshape(-1,1)
    graph = np.sqrt(xMat**2 + yMat**2)
    pheromone = np.ones([nCity, nCity]) # 信息素矩陣
    ants = [Ant(nCity, graph, pheromone) for _ in range(nAnts)]
    best = Ant(nCity, graph, pheromone)  # 初始化最優(yōu)解
    best.dTotal = np.inf
    bestAnts = []           # 輸出并保存
    for i in range(nIter):
        for ant in ants:
            ant.pheromone = pheromone
            ant.run()
            # 與當(dāng)前最優(yōu)螞蟻比較步行的總距離
            if ant.dTotal < best.dTotal:
                # 更新最優(yōu)解
                best = copy.deepcopy(ant)
        print(f"{i},{best.dTotal}")
        # 更新信息素
        pheromone = updatePheromone(nCity, pheromone, ants)
        bestAnts.append(best)
    return bestAnts

驗證與可視化

又到了激動人心的驗證時刻。根據(jù)aco函數(shù)的輸入?yún)?shù)來看，主要需要一組空間坐標(biāo)，設(shè)置如下

# 每個城市的x和y坐標(biāo)
xs = np.array([
    178,272,176,171,650,499,267,703,408,437,491,74,532,
    416,626,42,271,359,163,508,229,576,147,560,35,714,
    757,517,64,314,675,690,391,628,87,240,705,699,258,
    428,614,36,360,482,666,597,209,201,492,294])
ys = np.array([
    170,395,198,151,242,556,57,401,305,421,267,105,525,
    381,244,330,395,169,141,380,153,442,528,329,232,48,
    498,265,343,120,165,50,433,63,491,275,348,222,288,
    490,213,524,244,114,104,552,70,425,227,331])
xMat, yMat = xs-xs.reshape(-1,1), ys-ys.reshape(-1,1)
distance_graph = np.sqrt(xMat**2 + yMat**2)

最后main函數(shù)為

if __name__ == '__main__':
    bAnts = aco(xs, ys, 50, 300)
    index = bAnts[-1].path
    index = index + [index[0]]
    plt.plot(xs[index], ys[index], marker='*')
    plt.tight_layout()
    plt.show()

最終優(yōu)化后的螞蟻路線如下