蚁群算法求TSP

该主题不支持Latex的cases效果。。。

公式随便看看吧。。。无语死了

路径选择概率：

$$
p_i=\frac{\tau_i^\alpha \eta_i^\beta}{\sum^m_{j=1} \tau_j^\alpha \eta_j^\beta}
$$

$$
其中\tau_i表示第i条路径的信息素浓度，\eta_i表示第i条路径的路径信息，m表示路径总数。
$$

$$
一般\eta_i=\frac{1}{d_i}，表示路径越短，选择的概率越大，\alpha 和\beta 是两者的贡献度参数。这个概率就是和所有路径的比值。
$$

$$
同时信息素浓度\tau_i=(1-\rho)\tau_i+\Delta\tau_i
$$

$$
其中\rho 代表信息素的挥发率，\Delta\tau_i 表示新增加的信息素
$$

在旅行商中

$$
第k只蚂蚁在城市i，下一个城市选为j的概率：
$$

$$
p_{ij}^k(t) =
\begin{cases}
\frac{(\tau_{ij}(t))^\alpha (\eta_{ij}(t))^\beta}{\sum_{l\in 未被访问的城市}(\tau_{il}(t))^\alpha (\eta_{il}(t))^\beta}, & j \in 未被访问的城市 \
0, & otherwise \
\end{cases}
$$

$$
注意蚂蚁不会重复访问同一城市，所以有otherwise
$$

对于信息素

$$
城市ij间的信息素从\tau_{ij}(t)->\tau_{ij}(t+n)，因为是一次旅行商后才更新信息素，一次周期为n个单位时间
$$

$$
\tau_{ij}(t+n)=(1-\rho)\tau_{ij}(t)+\Delta\tau_{ij}
$$

$$
\Delta\tau_{ij}^k=\sum_{k=1}^m\Delta\tau^k_{ij}
$$

$$
\Delta_{ij}^k=
\begin{cases}
\frac{Q}{L^k}, & if;蚂蚁有从i->j \
0, & otherwise \
\end{cases}
$$

$$
其中Q为常量，L^k为该只蚂蚁此次回路的总长，即走的回路越长，信息素越淡，越不会被其他蚂蚁选择
$$

进一步改进

扔色子，两种策略

• 利用
  重复走历史最优路径，收敛更快，但容易陷入局部最优
• 探索
  随机挑一种路径选择，即上面讲到的路径选择概率

进进一步改进

之前的更新信息素方法，是一只蚂蚁访问完一条回路才更新
现在我们提出局部更新和全局更新

• 局部更新
  我们现在在蚂蚁移动一次城市时就马上更新
  $$
  \tau_{ij}=(1-\rho)\tau_{ij}+\rho\Delta\tau_{ij}
  \Delta\tau{ij}的意思是：
  $$

$$
此时蚂蚁从i到j了，再看从j伸出的边里面的最大信息素边，再乘个系数，即下面公式
$$

$$
\Delta\tau{ij} = \gamma{max_k\tau_{jk}}
$$

$$
这考虑了i->j的当前边的信息素，也考虑了将来的信息素(强化学习常用)
$$

• 全局更新
  还是访问完一条回路才更新，但是仅仅对当前最优回路上$L^{opt}$的边添加信息素
  $$
  \tau_{ij}=(1-\alpha)\tau_{ij}+\alpha\Delta\tau{ij}
  $$
  $$
  \Delta\tau_{ij}=
  \begin{cases}
  \frac{1}{L^{opt}} ,& if; l_{ij} \in L^{opt}\
  0, & otherwise
  \end{cases}
  $$

其他

• 蚂蚁行走释放量的常见方法：
  • 蚁周算法（ant-cycle):蚂蚁走完整个路径后，蚂蚁行走释放部分用$\frac{Q}{L}$计算，Q表示蚂蚁释放信息素的量(常量)，L表示路径总长度）
  • 蚁密算法（ant-density):，蚂蚁走完一个城市后，蚂蚁行走释放用$Q$表示）、
  • 蚁量算法(ant-quantity):蚂蚁走完一个城市后，蚂蚁行走释放用$\frac{Q}{d_{ij}}$表示，$d_{ij}$表示城市i和j之间的距离)。
• $\alpha$为信息素重要程度因子, 其值越大, 蚂蚁选择之前走过的路径可能性就越大,搜索路径的随机性减弱, 其值越小,蚁群搜索范围就会减少,容易陷入局部最优。一般取值范围为[0,5]。
  $\beta$为启发函数重要程度因子, 其值越大, 表示启发函数在转移中的作用越大, 即蚂蚊会以较大的摡率转移到距离短的节点，蚁群就越容易选择局部较短路径,这时算法的收敛速度是加快了，但是随机性却不高，容易得到局部的相对最优。一般取值范围为[0,5]。
• 在蚂蚁挑选下一个点时，对于各边的概率，可以使用轮盘赌而不是直接按概率大小来，这样可以扩大搜索范围，避免陷入局部最优

# 但是好像耗时和结果还是不如其他人博客里的，后面再看看https://blog.csdn.net/weixin_42301220/article/details/125129090?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168787192116800184129751%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168787192116800184129751&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-125129090-null-null.142^v88^koosearch_v1,239^v2^insert_chatgpt&utm_term=%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95python&spm=1018.2226.3001.4187

import matplotlib.pyplot as plt
import numpy as np

class Graph:
    class Edge:
        # 两点的坐标
        def __get_distance(self,coor_a,coor_b):
            dis = 0
            for i in range(len(coor_a)):
                dis += (coor_a[i]-coor_b[i])**2
            return np.sqrt(dis)

        # 边的起点和终点的编号，所有点的坐标，信息素
        def __init__(self,begin,end,coordinates,pheromone=1):
            self.begin = begin
            self.end = end
            self.pheromone = pheromone
            self.distance = self.__get_distance(coordinates[begin],coordinates[end])

    # data是图的二维的所有边
    def __init__(self,coordinates):
        node_num = len(coordinates)
        self.data = [[Graph.Edge(i,j,coordinates) for j in range(node_num)] for i in range(node_num)]


class Ant:
    # 图，起点，计算概率的两个超参数
    def __init__(self,graph,begin,alpha,beta):
        self.graph = graph
        self.begin = begin
        self.__visited = [False for _ in range(len(graph.data))]
        self.__visited[begin] = True
        self.__tour_len = 0
        self.__cur_node = begin
        self.alpha = alpha
        self.beta = beta
        self.__tour = [begin]


    # 计算获得下一步去哪个城市(选哪个边)
    def __next_node(self)->int:
        # 与当前所在结点相邻的各边的概率
        probs = []
        # 与当前所在结点相邻的各边的概率总和
        total_prob = 0.0
        for next_edge in self.graph.data[self.__cur_node]:
            p = 0
            if not self.__visited[next_edge.end]:
                p = (next_edge.pheromone ** self.alpha) * ((1.0 / next_edge.distance) ** self.beta)
                total_prob += p
            probs.append(p)
        probs = list(map(lambda p:p/total_prob,probs))
        # 轮盘赌
        next_node_idx = np.random.choice([i for i in range(len(probs))], size=1, p=probs, replace=False)
        return next_node_idx[0]
    # 正式前往下一个
    def to_next(self):
        next_node =self.__next_node()
        self.__visited[next_node] = True
        self.__tour_len += self.graph.data[self.__cur_node][next_node].distance
        self.__cur_node = next_node
        self.__tour.append(self.__cur_node)

    def get_tour_len(self):
        last_node = self.__tour[-1]
        last_edge_len = self.graph.data[last_node][self.begin].distance
        return self.__tour_len + last_edge_len

    def get_tour(self)->list:
        return self.__tour + [self.begin]


class ACO:
    # 蚂蚁数量，图，蚂蚁数，迭代数，挥发率，两个超参数，新增信息素计算公式里的Q
    def __init__(self,num_ant=500,num_iter=100,evaporation_rate=0.1,alpha=1.0,beta=5.0,Q=1):
        self.num_ant = num_ant
        self.num_iter = num_iter
        self.alpha = alpha
        self.beta = beta
        self.Q = Q
        self.evaporation_rate = evaporation_rate
        self.shortest_tour_len = float('inf')
        self.shortest_tour = None

    def run(self,graph:Graph,begin):
        shortest_tour_len_records = []
        node_num = len(graph.data)
        for iter in range(self.num_iter):
            # 每一次迭代换一批蚂蚁
            ants = [Ant(graph,begin,self.alpha,self.beta) for _ in range(self.num_ant)]
            for ant in ants:
                # 蚂蚁走完一圈
                for _ in range(node_num-1):
                    ant.to_next()
                # 比较，取最小值
                tour_len = ant.get_tour_len()
                if tour_len < self.shortest_tour_len:
                    self.shortest_tour_len = tour_len
                    self.shortest_tour = ant.get_tour()
            # 更新走过的边

            for i in range(node_num):
                for j in range(node_num):
                    # 挥发一部分信息素
                    graph.data[i][j].pheromone *= (1 - self.evaporation_rate)
                    # 每只蚂蚁都留下信息素
                    for ant in ants:
                        tour_len = ant.get_tour_len()
                        pre_node = ant.begin
                        for cur_node in ant.get_tour()[1:]:
                            graph.data[pre_node][cur_node].pheromone += self.Q / tour_len
                            pre_node = cur_node
            # 记录方便画图
            shortest_tour_len_records.append(self.shortest_tour_len)
        return self.shortest_tour,self.shortest_tour_len,shortest_tour_len_records


# 坐标数据
coordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0],
            [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0],
            [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0,  5.0],[845.0,680.0],
            [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0],
            [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],
            [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],
            [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0],[685.0,595.0],
            [685.0,610.0],[770.0,610.0],[795.0,645.0],[720.0,635.0],[760.0,650.0],
            [475.0,960.0],[95.0,260.0],[875.0,920.0],[700.0,500.0],[555.0,815.0],
            [830.0,485.0],[1170.0, 65.0],[830.0,610.0],[605.0,625.0],[595.0,360.0],
            [1340.0,725.0],[1740.0,245.0]])

aco = ACO(num_ant=45,num_iter=100)
g = Graph(coordinates)
begin = 0
tour,length,records = aco.run(g,begin)
print(tour,length)
plt.plot(range(100),records)
plt.show()