蚁群算法.python代码

# -*- coding: cp936 -*-
import random
import numpy as np
import copy
import sys

"""蚁群算法计算过程如下：

（1）初始化。

（2）为每只蚂蚁选择下一个节点。

（3）更新信息素矩阵。

（4）检查终止条件

如果达到最大代数，算法终止，转到第（5）步；否则，重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，
Allowed表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。
在Tabu中加入起始节点，Allowed中去掉该起始节点，重复执行（2），（3）,(4)步。

"""

#城市位置
coordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0],
            [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0],
            [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0, 5.0],[845.0,680.0],
            [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0],
            [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],
            [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],
            [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0],[685.0,595.0],
            [685.0,610.0],[770.0,610.0],[795.0,645.0],[720.0,635.0],[760.0,650.0],
            [475.0,960.0],[95.0,260.0],[875.0,920.0],[700.0,500.0],[555.0,815.0],
            [830.0,485.0],[1170.0, 65.0],[830.0,610.0],[605.0,625.0],[595.0,360.0]])

#参数设置
ALPHA,BETA,RHO,Q = 1.0,2.0,0.5,100.0

#城市数目和蚂蚁数
city_num,ant_num = 50,50

#城市距离
distance_grap = np.zeros((city_num,city_num))

#信息素
pheromone_grap = np.ones((city_num,city_num))

#---------------------蚂蚁----------------------
class ant(object):

    #初始化
    def __init__(self,ID):
        self.ID = ID#蚂蚁编号
        self.born()

    def born(self):
        self.path = []#存储蚂蚁走过的路径
        self.total_distance = 0.0#蚂蚁走过的路径的和
        self.current = -1#初始当前蚂蚁所在的位置
        self.city_state = np.ones(city_num,dtype=int)#是否遍历过的城市状态，1为还没遍历，0为已经遍历

        city_index = random.randint(0,city_num-1)#随机选择出生点
        self.current_city = city_index#出生点作为当前蚂蚁所在的城市
        self.path.append(city_index)
        self.city_state[city_index] = 0#把该城市改为已经遍历
        self.move_count = 1

    #选择下一个城市
    def select_city(self):
        next_city = -1#初始化下一个城市
        select_city_prob = np.zeros(city_num)#用于存储选择每个城市的概率
        total_prob = 0.0#概率概率总和

        #获取下一个城市的概率
        for i in range(city_num):
            if self.city_state[i]:
                try:
                    #计算选择每个城市的的概率
                    select_city_prob[i] = pow(pheromone_grap[self.current_city][i],ALPHA)*pow(1.0/distance_grap[self.current_city][i],BETA)
                    total_prob += select_city_prob[i]
                except ZeroDivisionError as e:
                    sys.exit(1)
        #轮盘算法
        if total_prob > 0:
            temp_prob = random.uniform(0.0, total_prob)
            for i in range(city_num):
                if self.city_state[i]:
                    # 轮次相减
                    temp_prob -= select_city_prob[i]
                    if temp_prob < 0.0:
                        next_city = i
                        break

        if (next_city == -1):
            next_city = random.randint(0, city_num - 1)
            while ((self.city_state[next_city]) == False):
                next_city = random.randint(0, city_num - 1)

        # 返回下一个城市序号
        return next_city

    #移动
    def move_city(self,next_city):
        self.path.append(next_city)
        self.city_state[next_city] = 0
        self.total_distance += distance_grap[self.current_city][next_city]
        self.current_city = next_city
        self.move_count += 1

    #计算所走过的城市的路程总和
    def cumulate_distance(self):
        temp_total_distance = 0.0
        temp_start = -1
        for i in range(1,city_num):
            start,end = self.path[i-1],self.path[i]
            temp_total_distance += distance_grap[start][end]
            temp_start = start
        #终点到最开始出生点的距离
        temp_total_distance += distance_grap[temp_start][0]
        self.total_distance = temp_total_distance

    #搜索路径
    def search_city(self):
        self.born()
        while self.move_count < city_num:
            next_city = self.select_city()
            self.move_city(next_city)
        self.cumulate_distance()

if __name__ == "__main__":

    #计算城市间距离
    temp_distance = np.zeros((city_num,city_num))
    for i in range(city_num):
        for j in range(i, city_num):
            temp_distance[i][j] = temp_distance[j][i] = np.linalg.norm(coordinates[i] - coordinates[j])
    distance_grap = temp_distance

    ants = [ant(ID) for ID in range(ant_num)]  # 初始蚁群
    best_ant = ant(-1)
    best_ant.total_distance = 1e6 # 初始最大距离

    iter = 1#迭代次数
    iter_max = 100#最大迭代数
    
    while iter < iter_max :
        for ant in ants:
            
            ant.search_city()
            
            if ant.total_distance < best_ant.total_distance:
                # 更新最优解
                best_ant = copy.deepcopy(ant)
                
            # 获取每只蚂蚁在其路径上留下的信息素
            temp_pheromone = np.zeros((city_num,city_num))

            for ant in ants:
                for i in range(1, len(ant.path)):
                    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_grap[i][j] = pheromone_grap[i][j] * RHO + temp_pheromone[i][j]
                    
        print(u"迭代次数：", iter, u"最佳路径总距离：", int(best_ant.total_distance))
        
        iter += 1
        
    print(best_ant.path)

参考：https://zhuanlan.zhihu.com/p/137408401