该条路概率权重该点…这里使用了蚁群算法求解了旅行商问题同时结合了simpy来绘图

probability[i]

pheromone[self.now][self.not_to_foods[i]]

pheromone_w

distance[self.now][self.not_to_foods[i]])

distance_w

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

信息素更新为

new_pheromone[self.route[i]][self.route[i

1]]

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

import

在这里我们尝试用蚁群算法求解旅行商问题简而言之就是寻找一条链接所有点的最短路径最后要回到初始点

我想绘制一下每只蚂蚁的行走过程所以使用上次的simpy包来模拟一下

这个simpy包主要是为了更好的可视化模拟训练过程你也可以给每只蚂蚁单独线程代替

或者干脆不用管过程只用一轮一轮的上蚂蚁在信息素部分做点处理光看结果也可以。

总之大多要比simpy快class

Ant(object):

每次遵从信息素的指引选择下一个城市直到没有可选城市回到初始位置然后根据路径总长度在路径上散播信息素def

__init__(self):

这里我们为了以后整信息素时不用遍历顺便保存一下走过的长度self.route

到达食物路径一个例子是[2,1,3,2]self.not_to_foods

当前所在位置self.next_food

下一个所在位置self.Initial_Position(random.randint(0,foods_n-1))

设定初始位置#

走的时间画图就是找到起始食物点然后加上起始和终点的向量乘以当前时间-出发时间/路长就是蚂蚁位置def

n):

添加到路径self.not_to_foods.remove(n)

Set_Now(self,

下一个要到的食物self.route.append(next_food)

添加到路径self.sum_len

self.not_to_foods:self.not_to_foods.remove(next_food)

foods[next_food]

根据信息素和路径寻找下一个食物len_not_to_foods

选一个路径的概率是该点信息素^信息素权重*1/路径长^路径权重/总和这里后面会用random.choices就不用除了probability[i]

pheromone[self.now][self.not_to_foods[i]]

pheromone_w

distance[self.now][self.not_to_foods[i]])

distance_wnext_food

random.choices(self.not_to_foods,

probability)

更新信息素矩阵先添加到一个临时变量中信息素矩每隔一段时间后自己会挥发并将这个变量添加进去。

for

range(foods_n):new_pheromone[self.route[i]][self.route[i

1]]

self.sum_lennew_pheromone[self.route[i

1]][self.route[i]]

new_pheromone[self.route[i]][self.route[i

1]]def

self.Next_Food()[0]self.Set_Now(next_food)

env.timeout(distance[self.now][next_food])

等待到达终点self.now

self.route[0]self.Set_Now(next_food)

去初始点yield

env.timeout(distance[self.now][next_food])

等待到达终点self.now

self.routeself.Initial_Position(random.randint(0,foods_n-1))

重新初始化再来一轮def

我想要平均走完一波蚂蚁更新一波那么我大概需要等待平均总路长的时间因为假设蚂蚁1m/s这里就用(foods_n1)/2,两点间平均距离大概是0.5yield

env.timeout((foods_n

所有食物位置支持高维不过绘图只有二维python三维图太卡了只测试二维pheromone

np.zeros((foods_n,

一样的位置就是0不算了continuedistance[i][j]

foods[j])

range(i):plt.plot([foods[i][0],foods[j][0]],[foods[i][1],foods[j][1]],linewidthpheromone[i][j]/100)plt.scatter(foods[i][0],

foods[i][1],

到起始食物点然后加上起始和终点的向量乘以当前时间-出发时间/路长就是蚂蚁位置if

ants[i].now

foods[ants[i].now]else:position

foods[ants[i].now]

\distance[ants[i].now][ants[i].next_food]plt.scatter(position[0],

position[1])plt.text(position[0],

position[1],

刷新图形plt.draw()plt.pause(time_particles)yield

Firing(env):

env启动env.process(Change_Pheromone(env))

启动信息素矩阵env.process(plt_Refresh())

启动绘图for

启动所有蚂蚁env.process(ants[i].run())ants_n

蚂蚁数目一般1.5*foods_n

运行模拟print(min_route,min_distance)

plt.show()

plt.pause(10)这一行同时可以调大time_particles