python 实现蚁群算法（simpy带绘图）_python蚁群算法收敛的图

这里使用了蚁群算法求解了旅行商问题，同时结合了simpy来绘图

选择下一个食物的函数为：

probability[i] = pheromone[self.now][self.not_to_foods[i]] ** pheromone_w + (
        1 / distance[self.now][self.not_to_foods[i]]) ** distance_w

该条路概率权重=该点信息素^信息素权重*（1/路径长）^路径权重/总和，这里后面会用random.choices就不用除了

信息素更新为：

new_pheromone[self.route[i]][self.route[i + 1]] += pheromone_Q / self.sum_len

pheromone = np.add((1 - volatilize) * pheromone, new_pheromone)

总信息素会挥发volatilize比例，然后所有蚂蚁路径每一段加上固定释放的信息量/路径总长度

话不多说，都在代码注释里了

import random
import simpy
import matplotlib.pyplot as plt
import numpy as np
 
 
# 在这里我们尝试用蚁群算法求解旅行商问题，简而言之，就是寻找一条链接所有点的最短路径最后要回到初始点
# 我想绘制一下每只蚂蚁的行走过程，所以使用上次的simpy包来模拟一下，
# 这个simpy包主要是为了更好的可视化模拟训练过程，你也可以给每只蚂蚁单独线程代替，
# 或者干脆不用管过程，只用一轮一轮的上蚂蚁，在信息素部分做点处理，光看结果也可以。总之大多要比simpy快
 
class Ant(object):  # 蚂蚁类
    # 说一下训练过程，有很多只蚂蚁，从随机位置出发，
    # 每次遵从信息素的指引，选择下一个城市，直到没有可选城市，回到初始位置然后根据路径总长度在路径上散播信息素
    def __init__(self):  # 蚂蚁构造函数
        # 一只蚂蚁，只需要保存走过的食物就可以，
        # 这里我们为了以后整信息素时不用遍历，顺便保存一下走过的长度
        self.route = []  # 到达食物路径，一个例子是：[2,1,3,2]
        self.not_to_foods = []  # 未到达的食物点
        self.sum_len = 0  # 走过路径总长度
        self.now = 0  # 当前所在位置
        self.next_food = 0  # 下一个所在位置
        self.Initial_Position(random.randint(0,foods_n-1))  # 设定初始位置
        # 绘图参数
        self.now_position = [0, 0]  # 起始到终点的向量
        self.proportion = env.now  # 走的时间，画图就是找到起始食物点，然后加上（起始和终点的向量乘以（当前时间-出发时间）/路长）就是蚂蚁位置，
 
    def Initial_Position(self, n):  # 选择初始位置'
        self.now = n  # 当前所在的食物
        self.next_food = n  # 下一个要到的食物
        self.route = []
        self.not_to_foods = [i for i in range(foods_n)]  # 未到达的食物点
        self.sum_len = 0
        self.route.append(n)  # 添加到路径
        self.not_to_foods.remove(n)  # 初始点不会在未到的食物点
 
    def Set_Now(self, next_food):  # 到下一个点
        self.next_food = next_food  # 下一个要到的食物
        self.route.append(next_food)  # 添加到路径
        self.sum_len += distance[self.now][next_food]  # 总路径增加
        if next_food in self.not_to_foods:
            self.not_to_foods.remove(next_food)  # 移出未到的食物点
        self.now_position = foods[next_food] - foods[self.now]  # 走的方向
        self.proportion = env.now  # 出发时间
 
    def Next_Food(self):  # 根据信息素和路径寻找下一个食物
        len_not_to_foods = len(self.not_to_foods)  # 没选择的食物个数
        probability = np.zeros(len_not_to_foods)  # 选择食物的概率
        for i in range(len_not_to_foods):
            # 选一个路径的概率是该点信息素^信息素权重*（1/路径长）^路径权重/总和，这里后面会用random.choices就不用除了
            probability[i] = pheromone[self.now][self.not_to_foods[i]] ** pheromone_w + (
                    1 / distance[self.now][self.not_to_foods[i]]) ** distance_w
        next_food = random.choices(self.not_to_foods, probability)  # 根据权重选择下一个点
        return next_food
 
    def Change_Pheromone(self):  # 更新信息素矩阵，先添加到一个临时变量中，信息素矩每隔一段时间后自己会挥发并将这个变量添加进去。
        for i in range(foods_n):
            new_pheromone[self.route[i]][self.route[i + 1]] += pheromone_Q / self.sum_len
            new_pheromone[self.route[i + 1]][self.route[i]] = new_pheromone[self.route[i]][self.route[i + 1]]
 
    def run(self):  # 蚂蚁出动
        global min_distance, min_route
        while True:
            while self.not_to_foods:  # 未空还能找食物
                next_food = self.Next_Food()[0]
                self.Set_Now(next_food)  # 根据信息素和路径去下一个食物位置
                yield env.timeout(distance[self.now][next_food])  # 等待到达终点
                self.now = next_food  # 到达位置
            # 没有食物可以去了
            next_food = self.route[0]
            self.Set_Now(next_food)  # 去初始点
            yield env.timeout(distance[self.now][next_food])  # 等待到达终点
            self.now = next_food  # 到达位置
            self.Change_Pheromone()  # 到了初始点之后，更新信息素
            if min_distance > self.sum_len:
                min_distance = self.sum_len
                min_route = self.route
            self.Initial_Position(random.randint(0,foods_n-1))  # 重新初始化，再来一轮
 
 
def Change_Pheromone(env):
    global pheromone, new_pheromone
    while True:
        # 每隔一段时间，挥发，更新信息素，
        # 我想要平均走完一波蚂蚁更新一波，那么，我大概需要等待平均总路长的时间（因为假设蚂蚁1m/s）这里就用(foods_n+1)/2,两点间平均距离大概是0.5
        yield env.timeout((foods_n + 1) / 2)
        pheromone = np.add((1 - volatilize) * pheromone, new_pheromone)
        new_pheromone = np.zeros((foods_n, foods_n))
 
 
# 初始化函数，初始化蚁群，食物，信息素矩阵，
def Initialization(ants_n, foods_n, dimension):
    '''
    :param ants_n:  蚁群大小
    :param foods_n: 食物数目
    :param dimension: 维度
    :return: 初始化蚁群，食物，信息素矩阵，距离矩阵
    '''
    ants = [Ant() for _ in range(ants_n)]  # 蚁群
    np.random.seed(0)  # 随机数种子，让生成的位置一致,你可以删去
    foods = np.random.rand(foods_n, dimension)  # 所有食物位置，支持高维，不过绘图只有二维（python三维图太卡了），只测试二维
    pheromone = np.zeros((foods_n, foods_n))+2  # 信息素矩阵初始为路径长度平均数的倒数之类的
    distance = np.zeros((foods_n, foods_n))  # 距离矩阵
    for i in range(foods_n):  # 计算欧氏距离
        for j in range(foods_n):
            if i > j:  # 以前算过了，抄过来
                distance[i][j] = distance[j][i]
                continue
            if i == j:  # 一样的位置就是0，不算了
                continue
            distance[i][j] = np.sqrt(np.sum((foods[i] - foods[j]) ** 2))
    return ants, foods, pheromone, distance
 
 
def plt_Refresh():  # 绘图
    while True:
        plt.clf()  # 清屏
        plt.xlim(0, 1)
        plt.ylim(-0.1, 1)
        # 绘图
        plt.text(0.05, -0.05, "now_time = " + str(env.now))
        for i in range(foods_n):  # 所有的食物点
            for j in range(i):
                plt.plot([foods[i][0],foods[j][0]],[foods[i][1],foods[j][1]],linewidth=pheromone[i][j]/100)
            plt.scatter(foods[i][0], foods[i][1], 100)
            plt.text(foods[i][0], foods[i][1], i)
        for i in range(ants_n):  # 所有的蚂蚁点
            # 到起始食物点，然后加上（起始和终点的向量乘以（当前时间-出发时间）/路长）就是蚂蚁位置，
            if ants[i].now == ants[i].next_food:
                position = foods[ants[i].now]
            else:
                position = foods[ants[i].now] + ants[i].now_position * (env.now - ants[i].proportion) / \
                           distance[ants[i].now][ants[i].next_food]
            plt.scatter(position[0], position[1])
            plt.text(position[0], position[1], i)
 
        # 刷新图形
        plt.draw()
        plt.pause(time_particles)
        yield env.timeout(time_particles)
 
 
def Firing(env):  # env启动
    env.process(Change_Pheromone(env))  # 启动信息素矩阵
    env.process(plt_Refresh())  # 启动绘图
    for i in range(ants_n):  # 启动所有蚂蚁
        env.process(ants[i].run())
 
 
ants_n = 15  # 蚂蚁数目，一般1.5*foods_n
foods_n = 10  # 食物数目
dimension = 2  # 维度，建议2，因为绘图只搞了2
min_distance = float("inf")  # 最小距离
min_route = []  # 最小路径
# 一些超参数
pheromone_w = 1  # 信息素权重
distance_w = 6  # 距离权重
volatilize = 0.5  # 信息素挥发比例
pheromone_Q = 10  # 总信息素
run_time = 100  # 模拟时间
time_particles = 0.05  # 绘图间隔
new_pheromone = np.zeros((foods_n, foods_n))
# 绘图
plt.figure()
plt.pause(10)    # 方便我录屏，等10s再出画面你们要删去
env = simpy.Environment()  # 设置环境并启动模拟
ants, foods, pheromone, distance = Initialization(ants_n, foods_n, dimension)  # 初始化,通常，蚁群数目是食物数目1.5倍
print(foods)
Firing(env)  # 开火，启动（添加要模拟的函数）
env.run(until=run_time)  # 运行模拟
 
print(min_route,min_distance)
plt.show()  # 遍历完成后不消失

自己用建议删去 plt.pause(10)这一行，同时，可以调大time_particles，

这是结果：

视频审核还没通过，通过了就放出来