Python 蟻群算法詳解
蟻群算法簡(jiǎn)介
蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無(wú)智能或有輕微智能的個(gè)體（Agent）通過(guò)相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問(wèn)題提供了一個(gè)新的可能性。蟻群算法最早是由意大利學(xué)者Colorni A., Dorigo M. 等于1991年提出。經(jīng)過(guò)20多年的發(fā)展，蟻群算法在理論以及應(yīng)用研究上已經(jīng)得到巨大的進(jìn)步。
蟻群算法是一種仿生學(xué)算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中，螞蟻覓食過(guò)程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路徑。下圖顯示了這樣一個(gè)覓食的過(guò)程。
在圖（a）中，有一群螞蟻，假如A是蟻巢，E是食物源（反之亦然）。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現(xiàn)了一個(gè)障礙物（圖（b）），那么，在B點(diǎn)（或D點(diǎn)）的螞蟻將要做出決策，到底是向左行駛還是向右行駛？由于一開(kāi)始路上沒(méi)有前面螞蟻留下的 信息素（pheromone） ，螞蟻朝著兩個(gè)方向行進(jìn)的概率是相等的。但是當(dāng)有螞蟻?zhàn)哌^(guò)時(shí)，它將會(huì)在它行進(jìn)的路上釋放出信息素，并且這種信息素會(huì)議一定的速率散發(fā)掉。信息素是螞蟻之間交流的工具之一。它后面的螞蟻通過(guò)路上信息素的濃度，做出決策，往左還是往右。很明顯，沿著短邊的的路徑上信息素將會(huì)越來(lái)越濃（圖（c）），從而吸引了越來(lái)越多的螞蟻沿著這條路徑行駛。
TSP問(wèn)題描述
蟻群算法最早用來(lái)求解TSP問(wèn)題，并且表現(xiàn)出了很大的優(yōu)越性，因?yàn)樗植际教匦裕敯粜詮?qiáng)并且容易與其它算法結(jié)合，但是同時(shí)也存在這收斂速度慢，容易陷入局部最優(yōu)（local optimal）等缺點(diǎn)。
TSP問(wèn)題（Travel Salesperson Problem，即旅行商問(wèn)題或者稱為中國(guó)郵遞員問(wèn)題），是一種NP-hard問(wèn)題，此類問(wèn)題用一般的算法是很難得到最優(yōu)解的，所以一般需要借助一些啟發(fā)式算法求解，例如遺傳算法（GA），蟻群算法（ACO），微粒群算法（PSO）等等。
TSP問(wèn)題（旅行商問(wèn)題）是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次 然后回到出發(fā)城市，并要求所走的路程最短。
一個(gè)TSP問(wèn)題可以表達(dá)為：求解遍歷圖G=(V,E,C)，所有的節(jié)點(diǎn)一次并且回到起始節(jié)點(diǎn)，使得連接這些節(jié)點(diǎn)的路徑成本最低。
蟻群算法原理
假如蟻群中所有螞蟻的數(shù)量為m，所有城市之間的信息素用矩陣pheromone表示，最短路徑為bestLength，最佳路徑為bestTour。每只螞蟻都有自己的內(nèi)存，內(nèi)存中用一個(gè)禁忌表（Tabu）來(lái)存儲(chǔ)該螞蟻已經(jīng)訪問(wèn)過(guò)的城市，表示其在以后的搜索中將不能訪問(wèn)這些城市；還有用另外一個(gè)允許訪問(wèn)的城市表（Allowed）來(lái)存儲(chǔ)它還可以訪問(wèn)的城市；另外還用一個(gè)矩陣（Delta）來(lái)存儲(chǔ)它在一個(gè)循環(huán)（或者迭代）中給所經(jīng)過(guò)的路徑釋放的信息素；還有另外一些數(shù)據(jù)，例如一些控制參數(shù)(α，β，ρ，Q)，該螞蟻行走玩全程的總成本或距離（tourLength），等等。假定算法總共運(yùn)行MAX_GEN次，運(yùn)行時(shí)間為t。
蟻群算法計(jì)算過(guò)程如下：
（1）初始化。
（2）為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)。
（3）更新信息素矩陣。
（4）檢查終止條件
如果達(dá)到最大代數(shù)MAX_GEN，算法終止，轉(zhuǎn)到第（5）步；否則，重新初始化所有的螞蟻的Delt矩陣所有元素初始化為0，Tabu表清空，Allowed表中加入所有的城市節(jié)點(diǎn)。隨機(jī)選擇它們的起始位置（也可以人工指定）。在Tabu中加入起始節(jié)點(diǎn)，Allowed中去掉該起始節(jié)點(diǎn)，重復(fù)執(zhí)行（2），（3）,(4)步。
（5）輸出最優(yōu)值
代碼實(shí)現(xiàn)
# -*- coding: utf-8 -*-
import random
import copy
import time
import sys
import math
import tkinter #//GUI模塊
import threading
from functools import reduce
# 參數(shù)
'''
ALPHA:信息啟發(fā)因子，值越大，則螞蟻選擇之前走過(guò)的路徑可能性就越大
，值越小，則蟻群搜索范圍就會(huì)減少，容易陷入局部最優(yōu)
BETA:Beta值越大，蟻群越就容易選擇局部較短路徑，這時(shí)算法收斂速度會(huì)
加快，但是隨機(jī)性不高，容易得到局部的相對(duì)最優(yōu)
'''
(ALPHA, BETA, RHO, Q) = (1.0,2.0,0.5,100.0)
# 城市數(shù)，蟻群
(city_num, ant_num) = (50,50)
distance_x = [
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]
distance_y = [
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]
#城市距離和信息素
distance_graph = [ [0.0 for col in range(city_num)] for raw in range(city_num)]
pheromone_graph = [ [1.0 for col in range(city_num)] for raw in range(city_num)]
#----------- 螞蟻 -----------
class Ant(object):
# 初始化
def __init__(self,ID):
self.ID = ID # ID
self.__clean_data() # 隨機(jī)初始化出生點(diǎn)
# 初始數(shù)據(jù)
def __clean_data(self):
self.path = []# 當(dāng)前螞蟻的路徑
self.total_distance = 0.0 # 當(dāng)前路徑的總距離
self.move_count = 0 # 移動(dòng)次數(shù)
self.current_city = -1 # 當(dāng)前停留的城市
self.open_table_city = [True for i in range(city_num)] # 探索城市的狀態(tài)
city_index = random.randint(0,city_num-1) # 隨機(jī)初始出生點(diǎn)
self.current_city = city_index
self.path.append(city_index)
self.open_table_city[city_index] = False
self.move_count = 1
# 選擇下一個(gè)城市
def __choice_next_city(self):
next_city = -1
select_citys_prob = [0.0 for i in range(city_num)] #存儲(chǔ)去下個(gè)城市的概率
total_prob = 0.0
# 獲取去下一個(gè)城市的概率
for i in range(city_num):
if self.open_table_city[i]:
try :
# 計(jì)算概率：與信息素濃度成正比，與距離成反比
select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
total_prob += select_citys_prob[i]
except ZeroDivisionError as e:
print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = self.ID, current = self.current_city, target = i))
sys.exit(1)
# 輪盤(pán)選擇城市
if total_prob > 0.0:
# 產(chǎn)生一個(gè)隨機(jī)概率,0.0-total_prob
temp_prob = random.uniform(0.0, total_prob)
for i in range(city_num):
if self.open_table_city[i]:
# 輪次相減
temp_prob -= select_citys_prob[i]
if temp_prob < 0.0:next_city = ibreak
# 未從概率產(chǎn)生，順序選擇一個(gè)未訪問(wèn)城市
# if next_city == -1:
# for i in range(city_num):
#if self.open_table_city[i]:
# next_city = i
# break
if (next_city == -1):
next_city = random.randint(0, city_num - 1)
while ((self.open_table_city[next_city]) == False): # if==False,說(shuō)明已經(jīng)遍歷過(guò)了
next_city = random.randint(0, city_num - 1)
# 返回下一個(gè)城市序號(hào)
return next_city
# 計(jì)算路徑總距離
def __cal_total_distance(self):
temp_distance = 0.0
for i in range(1, city_num):
start, end = self.path[i], self.path[i-1]
temp_distance += distance_graph[start][end]
# 回路
end = self.path[0]
temp_distance += distance_graph[start][end]
self.total_distance = temp_distance
# 移動(dòng)操作
def __move(self, next_city):
self.path.append(next_city)
self.open_table_city[next_city] = False
self.total_distance += distance_graph[self.current_city][next_city]
self.current_city = next_city
self.move_count += 1
# 搜索路徑
def search_path(self):
# 初始化數(shù)據(jù)
self.__clean_data()
# 搜素路徑，遍歷完所有城市為止
while self.move_count < city_num:
# 移動(dòng)到下一個(gè)城市
next_city = self.__choice_next_city()
self.__move(next_city)
# 計(jì)算路徑總長(zhǎng)度
self.__cal_total_distance()
#----------- TSP問(wèn)題 -----------
class TSP(object):
def __init__(self, root, width = 800, height = 600, n = city_num):
# 創(chuàng)建畫(huà)布
self.root = root
self.width = width
self.height = height
# 城市數(shù)目初始化為city_num
self.n = n
# tkinter.Canvas
self.canvas = tkinter.Canvas(
root,
width = self.width,
height = self.height,
bg = "#EBEBEB", # 背景白色
xscrollincrement = 1,
yscrollincrement = 1
)
self.canvas.pack(expand = tkinter.YES, fill = tkinter.BOTH)
self.title("TSP蟻群算法(n:初始化 e:開(kāi)始搜索 s:停止搜索 q:退出程序)")
self.__r = 5
self.__lock = threading.RLock() # 線程鎖
self.__bindEvents()
self.new()
# 計(jì)算城市之間的距離
for i in range(city_num):
for j in range(city_num):
temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
temp_distance = pow(temp_distance, 0.5)
distance_graph[i][j] =float(int(temp_distance + 0.5))
# 按鍵響應(yīng)程序
def __bindEvents(self):
self.root.bind("q", self.quite) # 退出程序
self.root.bind("n", self.new) # 初始化
self.root.bind("e", self.search_path) # 開(kāi)始搜索
self.root.bind("s", self.stop)# 停止搜索
# 更改標(biāo)題
def title(self, s):
self.root.title(s)
# 初始化
def new(self, evt = None):
# 停止線程
self.__lock.acquire()
self.__running = False
self.__lock.release()
self.clear() # 清除信息
self.nodes = [] # 節(jié)點(diǎn)坐標(biāo)
self.nodes2 = [] # 節(jié)點(diǎn)對(duì)象
# 初始化城市節(jié)點(diǎn)
for i in range(len(distance_x)):
# 在畫(huà)布上隨機(jī)初始坐標(biāo)
x = distance_x[i]
y = distance_y[i]
self.nodes.append((x, y))
# 生成節(jié)點(diǎn)橢圓，半徑為self.__r
node = self.canvas.create_oval(x - self.__r,
y - self.__r, x + self.__r, y + self.__r,
fill = "#ff0000",# 填充紅色
outline = "#000000",# 輪廓白色
tags = "node",
)
self.nodes2.append(node)
# 顯示坐標(biāo)
self.canvas.create_text(x,y-10, # 使用create_text方法在坐標(biāo)（302，77）處繪制文字
text = '('+str(x)+','+str(y)+')', # 所繪制文字的內(nèi)容
fill = 'black' # 所繪制文字的顏色為灰色
)
# 順序連接城市
#self.line(range(city_num))
# 初始城市之間的距離和信息素
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = 1.0
self.ants = [Ant(ID) for ID in range(ant_num)] # 初始蟻群
self.best_ant = Ant(-1) # 初始最優(yōu)解
self.best_ant.total_distance = 1 << 31 # 初始最大距離
self.iter = 1 # 初始化迭代次數(shù)
# 將節(jié)點(diǎn)按order順序連線
def line(self, order):
# 刪除原線
self.canvas.delete("line")
def line2(i1, i2):
p1, p2 = self.nodes[i1], self.nodes[i2]
self.canvas.create_line(p1, p2, fill = "#000000", tags = "line")
return i2
# order[-1]為初始值
reduce(line2, order, order[-1])
# 清除畫(huà)布
def clear(self):
for item in self.canvas.find_all():
self.canvas.delete(item)
# 退出程序
def quite(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
self.root.destroy()
print (u"\n程序已退出...")
sys.exit()
# 停止搜索
def stop(self, evt):
self.__lock.acquire()
self.__running = False
self.__lock.release()
# 開(kāi)始搜索
def search_path(self, evt = None):
# 開(kāi)啟線程
self.__lock.acquire()
self.__running = True
self.__lock.release()
while self.__running:
# 遍歷每一只螞蟻
for ant in self.ants:
# 搜索一條路徑
ant.search_path()
# 與當(dāng)前最優(yōu)螞蟻比較
if ant.total_distance < self.best_ant.total_distance:
# 更新最優(yōu)解
self.best_ant = copy.deepcopy(ant)
# 更新信息素
self.__update_pheromone_gragh()
print (u"迭代次數(shù)：",self.iter,u"最佳路徑總距離：",int(self.best_ant.total_distance))
# 連線
self.line(self.best_ant.path)
# 設(shè)置標(biāo)題
self.title("TSP蟻群算法(n:隨機(jī)初始 e:開(kāi)始搜索 s:停止搜索 q:退出程序) 迭代次數(shù): %d" % self.iter)
# 更新畫(huà)布
self.canvas.update()
self.iter += 1
# 更新信息素
def __update_pheromone_gragh(self):
# 獲取每只螞蟻在其路徑上留下的信息素
temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
for ant in self.ants:
for i in range(1,city_num):
start, end = ant.path[i-1], ant.path[i]
# 在路徑上的每?jī)蓚€(gè)相鄰城市間留下信息素，與路徑總距離反比
temp_pheromone[start][end] += Q / ant.total_distance
temp_pheromone[end][start] = temp_pheromone[start][end]
# 更新所有城市之間的信息素，舊信息素衰減加上新迭代信息素
for i in range(city_num):
for j in range(city_num):
pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
# 主循環(huán)
def mainloop(self):
self.root.mainloop()
#----------- 程序的入口處 -----------
if __name__ == '__main__':
TSP(tkinter.Tk()).mainloop()
總結(jié)
本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注本站的更多內(nèi)容！
版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信