算法简介
蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为”信息素”的物质，蚁群内的蚂蚁对”信息素”具有感知能力，它们会沿着”信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下”信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。
蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
蚁群觅食过程分析
举个简单的例子
蚂蚁群要从A（巢穴）到B（食物），最开始会派出一部分蚂蚁（代号1）走ACB路径，还有一部分蚂蚁（代号2）会走ADB路径，因为起初蚂蚁也不知道哪条路径短，所以每条路径都会有一部分蚂蚁去试探。在1走完路径到达B时，2还在路途中，此时ACB整条路径都已经有蚂蚁1留下的信息素了，而ADB只有一部分路径有信息素。在蚂蚁1返回到起点A的时候，蚂蚁2仍在途中（甚至可能还没有到达B点）。这样一来蚂蚁1就在路径ACB上留下了两次信息素，信息素浓度肯定比ADB路径上的高。
随后的蚂蚁就会选择信息素的浓度大的路径，由此往复加上信息素的挥发，最终所有蚂蚁都会选择最短的一条路径。其余路径的信息素都会挥发至0。
TSP求解思路
首先将m只蚂蚁随机放置在n个城市，然后对单个蚂蚁进行路径搜索。
t时刻位于城市i的第k只蚂蚁选择下一个城市j的概率为:
Allowed:蚂蚁k下一步允许选择的城市集合
参数α和β反映了信息素与启发信息的相对重要性，用来调节信息素与距离的重要程度。其中如果令α=0，β!=0该算法则成了贪婪启发式算法。单只蚂蚁仅根据距离来选择下一城市。如果令α!=0，β=0，则单只蚂蚁仅根据信息素来选择下一城市。
距离采用欧氏距离，根据题目所给坐标点，计算两点之间的欧氏距离即可。
信息素更新方法如下:
其中：Q为常数, wk表示第k只蚂蚁在本轮迭代中走过的路径，Lk为路径长度，ρ为小于1的常数，反映信息素挥发速度。ρ越大，信息素的挥发速度就会越慢。
对于任意一只蚂蚁，在按照上述方式走完一条完整的路径后，都会更新信息素，但是对于同一轮迭代中的蚂蚁，他们之间释放的信息素互不影响。在每一轮的迭代中，都应保留当前最优解，在所有迭代完成后即可得到问题最终解。
流程图
运行结果
迭代次数为20：
迭代次数为40：
迭代次数为60：
迭代次数为80：
迭代次数为100：
最终路径长度为427
整个求解过程的当前最优解情况：
改变参数时运行结果
α
β
初始蚂蚁数
最短路径长度
出现当前最优解的大致收敛次数
2
1
100
697
15
4
2
100
537
10
4
1
100
466
10
6
0
100
429
5
6
1
100
427
10
6
2
100
457
20
6
4
50
536
40
5
1
26
447
20
4
1
26
468
30
5
3
50
509
40
实现
import copy
from math import sqrt
import random
import matplotlib.pyplot as plt
#无向图
sample = [
[1,41,94],
[2,37,84],
[3,54,67],
[4,25,62],
[5,7,64],
[6,2,99],
[7,68,58],
[8,71,44],
[9,54,62],
[10,83,69],
[11,64,60],
[12,18,54],
[13,22,60],
[14,83,46],
[15,91,38],
[16,25,38],
[17,24,42],
[18,58,69],
[19,71,71],
[20,74,78],
[21,87,76],
[22,18,40],
[23,13,40],
[24,82,7],
[25,62,32],
[26,58,35],
[27,45,21],
[28,41,26],
[29,44,35],
[30,4,50],
]
vertex_count = len(sample) #顶点数
def draw1(ls1,ls2):
plt.plot(ls1,ls2,label=u'alpha=4 beta=4')
plt.show()
def draw(ls):
x = []
y = []
for i in ls:
x.append(sample[i-1][1])
y.append(sample[i-1][2])
plt.xlim(0, 100) # 限定横轴的范围
plt.ylim(0, 100) # 限定纵轴的范围
plt.plot(x, y, marker='o', mec='r', mfc='w',label=u'alpha=5 beta=1')
plt.legend() # 让图例生效
plt.margins(0)
plt.subplots_adjust(bottom=0.15)
plt.xlabel(u"X") #X轴标签
plt.ylabel("Y") #Y轴标签
plt.title("PATH") #标题
plt.show()
def city_dist(sample,city1,city2):
if city1 == city2:
return 9999
loc1 = []
loc2 = []
findtag = 0
dist = 0
for i in range(len(sample)):
if city1 == sample[i][0]:
loc1.append(sample[i][1])
loc1.append(sample[i][2])
findtag += 1
if city2 == sample[i][0]:
loc2.append(sample[i][1])
loc2.append(sample[i][2])
findtag += 1
if findtag == 2:
break
dist = sqrt(((loc1[0]-loc2[0])**2 + (loc1[1]-loc2[1])**2))
return dist
def evalute(sample,individual):
distance = 0
for i in range(len(individual)-1): # vertex_count = len(individual)-1
distance += city_dist(sample,individual[i], individual[i+1])
return distance
def find_pheromone(pheromone,city1,city2):
#信息素表示 [1,2,a] 即城市1与2之间的信息素为a
for i in range(len(pheromone)):
if city1 in pheromone[i] and city2 in pheromone[i]:
return pheromone[i][2]
print("return 0")
return 0
def update_pehromone(pheromone,city1,city2,new_pehromone): #更新信息素
for i in range(len(pheromone)):
if city1 in pheromone[i] and city2 in pheromone[i]:
pheromone[i][2] = 0.9 * pheromone[i][2] + new_pehromone
def get_sum(cur_city,pheromone,allowed_city,alpha,beta):
sum = 0
for i in range(len(allowed_city)):
sum += (find_pheromone(pheromone,cur_city,allowed_city[i])**alpha) * (city_dist(sample,cur_city,allowed_city[i])**beta)
return sum
def AntColony_Algorithm(sample):
#重要参数
ant_count = 26 #蚁群个体数
alpha = 5
beta = 1
loop_count = 100 #迭代次数
ant_colony = []
ant_individual = []
allowed_city = [] #待选城市
city = []
p = [] #记录选择某一城市概率
pheromone = []
draw_ls1 = []
draw_ls2 = []
best_dist = 9999
best_route = []
for i in range(1,vertex_count+1): #初始化信息素
for j in range(i+1,vertex_count+1):
pheromone.append([i,j,100]) #信息素初始化不能为0
for i in range(1,vertex_count+1): #初始化城市和概率
city.append(i)
#进行100次迭代
for i in range(loop_count):
if i%20 == 0 :
print(i)
draw(best_route)
draw_ls1.append(i)
#随机产生蚂蚁起始点
start_city = []
for j in range(ant_count):
start_city.append(random.randint(1,len(city)))
for j in range(len(start_city)):
ant_individual.append(start_city[j])
ant_colony.append(copy.deepcopy(ant_individual))
ant_individual.clear()
#所有蚂蚁完成遍历
for singal_ant in range(ant_count):
#单个蚂蚁完成路径
allowed_city = copy.deepcopy(city)
allowed_city.remove(ant_colony[singal_ant][0])
for m in range(vertex_count): #确定了起始城市，循环次数-1
cur_city = ant_colony[singal_ant][-1]
#单个蚂蚁遍历所有城市以确定下一城市
for j in range(len(allowed_city)):
probability = ((find_pheromone(pheromone,cur_city,allowed_city[j])**alpha) * (city_dist(sample,cur_city,allowed_city[j])**beta))/get_sum(cur_city,pheromone,allowed_city,alpha,beta)
p.append(probability)
#求累积概率
cumulative_probability = [0]
for j in range(len(p)):
cumulative_probability.append(cumulative_probability[j] + p[j])
#自然选择 轮盘赌概率选择下一城市
temp_random = random.random() #产生(0,1)随机数
for j in range(1,len(cumulative_probability)):
if temp_random > cumulative_probability[j-1] and temp_random < cumulative_probability[j]:
ant_colony[singal_ant].append(allowed_city[j-1]) #在单个蚂蚁中添加被选择的下一城市
del allowed_city[j-1]
break
p.clear()
ant_colony[singal_ant].append(ant_colony[singal_ant][0])
#计算每只蚂蚁的路径长度并更新所有蚂蚁路径上的信息素
for j in range(ant_count):
if evalute(sample,ant_colony[j]) < best_dist:
best_dist = evalute(sample,ant_colony[j])
best_route = copy.deepcopy(ant_colony[j])
for k in range(len(ant_colony[j])-1):
update_pehromone(pheromone,ant_colony[j][k],ant_colony[j][k+1],10000/city_dist(sample,ant_colony[j][k],ant_colony[j][k+1]))
draw_ls2.append(best_dist)
ant_colony.clear()
print("outcome")
print(pheromone)
print(best_route)
print(best_dist)
draw(best_route)
draw1(draw_ls1,draw_ls2)
AntColony_Algorithm(sample)
Original: https://blog.csdn.net/xiaomin_549/article/details/121887923
Author: xiaomin_549
Title: 蚁群算法求解TSP问题（Python实现）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/720302/
转载文章受原作者版权保护。转载请注明原作者出处！