蚁群算法解决TSP问题

TSP问题

旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

设计思路

1、随机生成n个位置(坐标),把坐标点绘制到页面上。

2、设置蚂蚁数量为m,把m只蚂蚁随机放在n个位置上。

3、设置每条路径的初始信息素为 $info_{ij}(0) = C$。

4、计算t时刻蚂蚁k(1到m)由位置i移动到位置j的概率 $probability_{ij}^k$。
$$
probability_{ij}^k =
\begin{cases}
\frac{info_{ij}^α(t) reciprocal_{ij}^β}{\sum info_{is}^α(t) reciprocal_{is}^β}, & j \in allowed_k,s \in allowed_k \
0, & \text{other} \
\end{cases}
$$

(1)$info_{ij}(t)$ 表示t时刻ij上的信息素。
$$
info_{ij}(t+1) = ρ \cdot info_{ij}(t) + Δinfo_{ij}
$$

ρ表示信息素挥发因子,控制信息素保留多少。
$Δinfo_{ij}$表示(本次移动)ij路径遗留的信息素。

$$Δinfo_{ij} = \sum_{k=1}^m Δinfo_{ij}^k$$

$$
Δinfo_{ij}^k =
\begin{cases}
\frac{Q}{L_k}, & \text{当第k只蚂蚁经过ij时} \
0, & \text{当不经过时} \
\end{cases}
$$

$L_k$表示(本次移动)蚂蚁k经过的路径和。

(2)$reciprocal_{ij}$ 表示ij之间距离的倒数,较近的坐标有较大的可能被选中。
$$distance_{ij} = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$
$$reciprocal_{ij} = \frac{1}{distance_{ij}}$$

(3)α表示信息启发式因子,控制信息素对概率的影响力大小,进而控制蚂蚁选择坐标。

(4)β表示期望值启发式因子,控制距离对概率的影响力的大小,进而控制蚂蚁选择坐标。
(5)$allowed_k$表示蚂蚁k下一步允许选择的坐标集合,$travelled_k$表示蚂蚁k已经走过的坐标集合。

5、比较选择每个坐标的概率,依次为每只蚂蚁选择下一个坐标。

6、重复4-5,直到蚂蚁走完所有坐标。

7、使用 $travelled_k$集合,分别计算m只蚂蚁走过的路径和,选择出最小的路径和,作为本次迭代的最优解。

8、把m只蚂蚁随机放在n个位置上。

9、重复4-8,直到达到指定的迭代次数,最后一次迭代的最优解,就是我们找到的最优解。

源码分享

https://github.com/voidking/TSP_MATLAB.git

书签

Mathjax与LaTex公式简介
http://mlworks.cn/posts/introduction-to-mathjax-and-latex-expression/

0%