关于算法:蚁群算法

3次阅读

共计 4723 个字符，预计需要花费 12 分钟才能阅读完成。

蚁群算法（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 random
import numpy as np
import 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内容示意城市的横纵坐标，如下所示：

正文完