Python 蟻群算法詳解

在這裡插入圖片描述

蟻群算法簡介

蟻群算法(Ant Clony Optimization, ACO)是一種群智能算法,它是由一群無智能或有輕微智能的個體(Agent)通過相互協作而表現出智能行為,從而為求解復雜問題提供瞭一個新的可能性。蟻群算法最早是由意大利學者Colorni A., Dorigo M. 等於1991年提出。經過20多年的發展,蟻群算法在理論以及應用研究上已經得到巨大的進步。

蟻群算法是一種仿生學算法,是由自然界中螞蟻覓食的行為而啟發的。在自然界中,螞蟻覓食過程中,蟻群總能夠按照尋找到一條從蟻巢和食物源的最優路徑。下圖顯示瞭這樣一個覓食的過程。

在這裡插入圖片描述

在圖(a)中,有一群螞蟻,假如A是蟻巢,E是食物源(反之亦然)。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現瞭一個障礙物(圖(b)),那麼,在B點(或D點)的螞蟻將要做出決策,到底是向左行駛還是向右行駛?由於一開始路上沒有前面螞蟻留下的 信息素(pheromone) ,螞蟻朝著兩個方向行進的概率是相等的。但是當有螞蟻走過時,它將會在它行進的路上釋放出信息素,並且這種信息素會議一定的速率散發掉。信息素是螞蟻之間交流的工具之一。它後面的螞蟻通過路上信息素的濃度,做出決策,往左還是往右。很明顯,沿著短邊的的路徑上信息素將會越來越濃(圖(c)),從而吸引瞭越來越多的螞蟻沿著這條路徑行駛。

TSP問題描述

蟻群算法最早用來求解TSP問題,並且表現出瞭很大的優越性,因為它分佈式特性,魯棒性強並且容易與其它算法結合,但是同時也存在這收斂速度慢,容易陷入局部最優(local optimal)等缺點。

TSP問題(Travel Salesperson Problem,即旅行商問題或者稱為中國郵遞員問題),是一種NP-hard問題,此類問題用一般的算法是很難得到最優解的,所以一般需要借助一些啟發式算法求解,例如遺傳算法(GA),蟻群算法(ACO),微粒群算法(PSO)等等。

TSP問題(旅行商問題)是指旅行傢要旅行n個城市,要求各個城市經歷且僅經歷一次 然後回到出發城市,並要求所走的路程最短。

一個TSP問題可以表達為:求解遍歷圖G=(V,E,C),所有的節點一次並且回到起始節點,使得連接這些節點的路徑成本最低。

蟻群算法原理

假如蟻群中所有螞蟻的數量為m,所有城市之間的信息素用矩陣pheromone表示,最短路徑為bestLength,最佳路徑為bestTour。每隻螞蟻都有自己的內存,內存中用一個禁忌表(Tabu)來存儲該螞蟻已經訪問過的城市,表示其在以後的搜索中將不能訪問這些城市;還有用另外一個允許訪問的城市表(Allowed)來存儲它還可以訪問的城市;另外還用一個矩陣(Delta)來存儲它在一個循環(或者迭代)中給所經過的路徑釋放的信息素;還有另外一些數據,例如一些控制參數(α,β,ρ,Q),該螞蟻行走玩全程的總成本或距離(tourLength),等等。假定算法總共運行MAX_GEN次,運行時間為t。

蟻群算法計算過程如下:

(1)初始化。

(2)為每隻螞蟻選擇下一個節點。

(3)更新信息素矩陣。

(4)檢查終止條件

如果達到最大代數MAX_GEN,算法終止,轉到第(5)步;否則,重新初始化所有的螞蟻的Delt矩陣所有元素初始化為0,Tabu表清空,Allowed表中加入所有的城市節點。隨機選擇它們的起始位置(也可以人工指定)。在Tabu中加入起始節點,Allowed中去掉該起始節點,重復執行(2),(3),(4)步。

(5)輸出最優值

代碼實現

# -*- coding: utf-8 -*-
import random
import copy
import time
import sys
import math
import tkinter #//GUI模塊
import threading
from functools import reduce

# 參數
'''
ALPHA:信息啟發因子,值越大,則螞蟻選擇之前走過的路徑可能性就越大
      ,值越小,則蟻群搜索范圍就會減少,容易陷入局部最優
BETA:Beta值越大,蟻群越就容易選擇局部較短路徑,這時算法收斂速度會
     加快,但是隨機性不高,容易得到局部的相對最優
'''
(ALPHA, BETA, RHO, Q) = (1.0,2.0,0.5,100.0)
# 城市數,蟻群
(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()          # 隨機初始化出生點
    # 初始數據
    def __clean_data(self):
        self.path = []               # 當前螞蟻的路徑           
        self.total_distance = 0.0    # 當前路徑的總距離
        self.move_count = 0          # 移動次數
        self.current_city = -1       # 當前停留的城市
        self.open_table_city = [True for i in range(city_num)] # 探索城市的狀態
        city_index = random.randint(0,city_num-1) # 隨機初始出生點
        self.current_city = city_index
        self.path.append(city_index)
        self.open_table_city[city_index] = False
        self.move_count = 1
    # 選擇下一個城市
    def __choice_next_city(self):
        next_city = -1
        select_citys_prob = [0.0 for i in range(city_num)]  #存儲去下個城市的概率
        total_prob = 0.0
        # 獲取去下一個城市的概率
        for i in range(city_num):
            if self.open_table_city[i]:
                try :
                    # 計算概率:與信息素濃度成正比,與距離成反比
                    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)
        # 輪盤選擇城市
        if total_prob > 0.0:
            # 產生一個隨機概率,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 = i
                        break
        # 未從概率產生,順序選擇一個未訪問城市
        # 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,說明已經遍歷過瞭
                next_city = random.randint(0, city_num - 1)
        # 返回下一個城市序號
        return next_city
    # 計算路徑總距離
    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

    # 移動操作
    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):
        # 初始化數據
        self.__clean_data()
        # 搜素路徑,遍歷完所有城市為止
        while self.move_count < city_num:
            # 移動到下一個城市
            next_city =  self.__choice_next_city()
            self.__move(next_city)
        # 計算路徑總長度
        self.__cal_total_distance()
#----------- TSP問題 -----------
class TSP(object):
    def __init__(self, root, width = 800, height = 600, n = city_num):
        # 創建畫佈
        self.root = root                               
        self.width = width      
        self.height = height
        # 城市數目初始化為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:開始搜索 s:停止搜索 q:退出程序)")
        self.__r = 5
        self.__lock = threading.RLock()     # 線程鎖
        self.__bindEvents()
        self.new()
        # 計算城市之間的距離
        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))
    # 按鍵響應程序
    def __bindEvents(self):
        self.root.bind("q", self.quite)        # 退出程序
        self.root.bind("n", self.new)          # 初始化
        self.root.bind("e", self.search_path)  # 開始搜索
        self.root.bind("s", self.stop)         # 停止搜索
    # 更改標題
    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 = []  # 節點坐標
        self.nodes2 = [] # 節點對象
        # 初始化城市節點
        for i in range(len(distance_x)):
            # 在畫佈上隨機初始坐標
            x = distance_x[i]
            y = distance_y[i]
            self.nodes.append((x, y))
            # 生成節點橢圓,半徑為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)
            # 顯示坐標
            self.canvas.create_text(x,y-10,              # 使用create_text方法在坐標(302,77)處繪制文字
                    text = '('+str(x)+','+str(y)+')',    # 所繪制文字的內容
                    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)                          # 初始最優解
        self.best_ant.total_distance = 1 << 31           # 初始最大距離
        self.iter = 1                                    # 初始化迭代次數 
    # 將節點按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])
    # 清除畫佈
    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()
    # 開始搜索
    def search_path(self, evt = None):
        # 開啟線程
        self.__lock.acquire()
        self.__running = True
        self.__lock.release()
        while self.__running:
            # 遍歷每一隻螞蟻
            for ant in self.ants:
                # 搜索一條路徑
                ant.search_path()
                # 與當前最優螞蟻比較
                if ant.total_distance < self.best_ant.total_distance:
                    # 更新最優解
                    self.best_ant = copy.deepcopy(ant)
            # 更新信息素
            self.__update_pheromone_gragh()
            print (u"迭代次數:",self.iter,u"最佳路徑總距離:",int(self.best_ant.total_distance))
            # 連線
            self.line(self.best_ant.path)
            # 設置標題
            self.title("TSP蟻群算法(n:隨機初始 e:開始搜索 s:停止搜索 q:退出程序) 迭代次數: %d" % self.iter)
            # 更新畫佈
            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]
                # 在路徑上的每兩個相鄰城市間留下信息素,與路徑總距離反比
                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]
    # 主循環
    def mainloop(self):
        self.root.mainloop()
#----------- 程序的入口處 -----------
if __name__ == '__main__':

    TSP(tkinter.Tk()).mainloop()

總結

本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀: