蚁群算法求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]。 - 在蚂蚁挑选下一个点时,对于各边的概率,可以使用轮盘赌而不是直接按概率大小来,这样可以扩大搜索范围,避免陷入局部最优
1 | # 但是好像耗时和结果还是不如其他人博客里的,后面再看看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 |
- 标题: 蚁群算法求TSP
- 作者: urlyy
- 创建于 : 2023-06-27 22:37:07
- 更新于 : 2025-03-16 01:04:15
- 链接: https://urlyy.github.io/2023/06/27/蚁群算法学习/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。