蚁群算法（Ant Colony Algorithm）最后于1992年由意大利学者M.Dorigo等人提出，它是一种模仿自然界中实在蚁群觅食行为的仿生优化算法。钻研发现：每只蚂蚁觅食时在走过的路线上会留下一种称为信息素的物质，蚂蚁之间靠感知这种物质的浓度进行信息传递。蚂蚁在抉择门路时总是偏向于朝信息索浓度高的方向挪动，而间隔短的门路上走过的蚂蚁多，留下的信息素也多，后续蚂蚁抉择它的概率也会越大；其余门路上的信息素会随着工夫的推移一直挥发，这样就造成了一种正反馈机制，最初整个蚁群汇集到最短门路上。
人工蚁群算法模仿了这一过程。每只蚂蚁在解空间独立地搜寻可行解，解越好留下的信息素越多，随着算法推动，较优解门路上的信息素增多，抉择它的蚂蚁也随之增多，最终收敛到最优或近似最优的解上。
一、算法原理
蚂蚁零碎是最早的蚁群零碎，它采纳 \(\tau_{ij}(t)\) 来模拟t时刻门路 \(i\) 到 \(j\) 下面的信息残留量，即信息素浓度。相似于蚂蚁觅食过程，每条门路下面的信息素会挥发，如果有蚂蚁通过的时候，信息素的浓度会相应减少。因而，蚂蚁零碎中的信息素浓度的更新公式为：
$$\tau_{ij}(t+n)=\rho·\tau_{ij}(t)+\Delta\tau_{ij}$$
式中，\(\rho\) 是一个 \(0\) 到 \(1\) 的数字，\((1-\rho)\) 为挥发因子。另外，\(\Delta\tau_{ij}\) 示意一次旅行（遍历完所有城市）后，所有门路\(i\) 到 \(j\)的蚂蚁留下的信息素总量，即：
$$\Delta\tau_{ij}=\sum_{k=1}^m\Delta\tau_{ij}^kr$$
式中，\(\Delta\tau_{ij}^k\) 示意第k只蚂蚁在门路 \(i\) 到 \(j\) 下面留下的信息素量。如果第 \(k\) 只蚂蚁通过门路 \(i\) 到 \(j\) ，则：
$$\Delta\tau_{ij}^k=\frac{Q}{L_kr}$$
式中，\(Q\) 为一个常数，\(L_k\) 为蚂蚁曾经走过门路的总长度。否则，第 \(k\) 只蚂蚁在 \(i\) 到 \(j\) 下面留下的信息素量为 \(0\)。
一般来说有了信息素浓度的更新公式，就能够间接给出蚂蚁对每条门路的抉择概率了。然而，为了更好的利用TSP问题本身的性质，M.Dorigo等引入了一个启发项：\(\eta=\frac{1}{d_{ij}}\) 。通过联合信息素浓度和启发因子，能够失去蚂蚁抉择门路 \(i\) 到 \(j\) 的概率为：
$$p_{ij}^{k}(t)=\left\{\begin{array}{rcl}\frac{[\tau_{ij}(t)]^\alpha·[\eta_{ij}]^{\beta}}{\sum_{k= \in allowed \: [\tau_{ik}(t)]^\alpha·[\eta_{ik}]^{\beta} } }, && {j \in allowed_k}\\ 0, & & {else}\end{array} \right.$$
式中，\(\alpha\) 和 \(\beta\) 是调节因子，用于调节 \(\tau_{ij}(t)\) 和 \(\eta_{ij}\) 之间的作用。此外 \(allowed_k\) 示意蚂蚁\(k\) 还没有走过的门路（用禁忌表存储曾经走过的门路），通过这种存储能够保障所有解的逻辑可行。如果门路 \(i\) 到 \(j\) 上的信息浓度越大 \(\tau_{ij}(t)\) 的值就越大，该门路被抉择的概率就越大；同样，如果该门路长度越短，则 \(\eta=\frac{1}{d_{ij}}\) 越大，该门路被抉择的概率也越大。
求解TSP问题的蚁群算法中的人工蚂蚁具备以下特点：
1）他们概率性地抉择下一条门路，该概率与门路长度和门路上的信息素浓度无关；
2）为了保障解的逻辑可行，蚂蚁不容许抉择曾经走过的门路（通过禁忌表实现）；
3）蚂蚁走过一条门路时会在该门路下面分泌一种叫做信息素的物质。
二、代码实现
import randomimport numpy as npimport math#==========================================#对称矩阵，计算任意两个城市之间的间隔def distance_p2p_mat(): dis_mat=[] for i in range(num_city): dis_mat_each=[] for j in range(num_city): dis=math.sqrt(pow(location[i][0]-location[j][0],2)+pow(location[i][1]-location[j][1],2)) dis_mat_each.append(dis) dis_mat.append(dis_mat_each) # print(dis_mat) return dis_mat#计算所有寻找到的门路对应的间隔def cal_newpath(dis_mat,path_new): dis_list=[] for each in path_new: dis=0 for j in range(num_city-1): dis=dis_mat[each[j]][each[j+1]]+dis dis=dis_mat[each[num_city-1]][each[0]]+dis#回家 dis_list.append(dis) return dis_list#==========================================location=np.loadtxt('./city_location.txt')num_ant=200 #蚂蚁个数num_city=30 #城市个数alpha=1 #信息素影响因子beta=5 #冀望影响因子info=0.1 #信息素的挥发率Q=1 #常数count_iter = 0 #迭代计数器iter_max = 30 #迭代次数dis_list=distance_p2p_mat() #计算任意两个城市间的间隔dis_mat=np.array(dis_list) #将list转化为矩阵e_mat_init=1.0/(dis_mat+np.diag([10000]*num_city)) #冀望矩阵。加对角阵是原矩阵对角线为0，而除数不能是0，所以先用一个比拟大的数垫一下diag=np.diag([1.0/10000]*num_city) #上一步生成的num_city*num_city维的对角线为1000的对角矩阵e_mat=e_mat_init-diag #曾经做过除法了，所以让对角线元素还原，再减去那个对角矩阵pheromone_mat=np.ones((num_city,num_city)) #信息浓度矩阵。初始化每条边的信息素浓度，全1矩阵path_mat=np.zeros((num_ant,num_city)).astype(int) #蚂蚁的门路矩阵。初始化每只蚂蚁门路，都从0城市登程.(如果不加数据转化，则默认生成的是float类型的0，即0.0)while count_iter < iter_max: #最外层迭代 for ant in range(num_ant): #对每一只蚂蚁进行剖析 visit=0 #都从0城市登程 unvisit_list=list(range(1,30)) #未拜访的城市。这个语句生成一个[1..29]的数组。再加上对立的出发点0，共30个城市 for j in range(1,num_city): #j代表第ant个蚂蚁的第j步 trans_list=[] trans=0 for k in range(len(unvisit_list)): #第ant个蚂蚁的第j步取哪个城市 trans +=np.power(pheromone_mat[visit][unvisit_list[k]],alpha)*np.power(e_mat[visit][unvisit_list[k]],beta) #计算第ant个蚂蚁由visit地位向k地位走的概率。这里要留神：间接累加 trans_list.append(trans) #将 每一步 累加的后果保留到一个数组中 #轮盘法抉择下一个城市 rand=random.uniform(0,trans)#产生随机数 for t in range(len(trans_list)): if(rand <= trans_list[t]): #因为之前就曾经累加了，trans_list[t]肯定是一个递增数组，所以能够间接与trans_list[t]相比拟 visit_next=unvisit_list[t] #抉择下标为t的城市作为这个蚂蚁下一步的方向 break path_mat[ant,j]=visit_next #装填这只蚂蚁的门路矩阵 unvisit_list.remove(visit_next) #在未走的城市列表中删去这个结点。这个操作，就会使unvisit_list这个数组变成断断续续的 visit=visit_next #更新这只蚂蚁的以后地位 #所有蚂蚁的门路表填满之后，算每只蚂蚁的总间隔 dis_allant_list=cal_newpath(dis_mat,path_mat) #选取领有最短门路的蚂蚁的门路 # 留神：这里其实能够不必写成if-else构造，但那样对于每一次迭代都须要一次min和max计算，而有时候后一次迭代后果并不一定比前一次迭代后果更优，就会造成冗余计算。 # 应用if-else构造后，每一次迭代只是一个判断，并不需要每次都进行min和max计算 if count_iter == 0: dis_new=min(dis_allant_list) path_new=path_mat[dis_allant_list.index(dis_new)].copy() else: if min(dis_allant_list) < dis_new: dis_new=min(dis_allant_list) path_new=path_mat[dis_allant_list.index(dis_new)].copy() # 为了防止残留信息素过多而吞没启发式信息，所以要及时的更新信息素矩阵 pheromone_change=np.zeros((num_city,num_city)) for i in range(num_ant): for j in range(num_city-1): pheromone_change[path_mat[i,j]][path_mat[i,j+1]] += Q/dis_mat[path_mat[i,j]][path_mat[i,j+1]] pheromone_change[path_mat[i,num_city-1]][path_mat[i,0]] += Q/dis_mat[path_mat[i,num_city-1]][path_mat[i,0]] #最初一个结点到终点 pheromone_mat=(1-info)*pheromone_mat + pheromone_change count_iter += 1 #迭代计数+1，进入下一次迭代 print('最短距离：',dis_new)print('最短门路：',path_new)city_location.txt内容示意城市的横纵坐标，如下所示：
41 9437 8454 6725 627 642 9968 5871 4454 6283 6964 6018 5422 6083 4691 3825 3824 4258 6971 7174 7887 7618 4013 4082 762 3258 3545 2141 2644 354 50