不失一般性，我们定义一个具有N个节点的有权图
G
=
(
N
,
A
)
G=(N,A)
G=(N,A)，其中N表示节点集合
N
=
1
,
2
,
.
.
.
,
n
N={1,2,...,n}
N=1,2,...,n，A表示边，
A
=
(
i
,
j
)
∣
i
,
j
∈
N
A={(i,j)|i,j\in N}
A=(i,j)∣i,j∈N。节点之间的距离（权重）设为
(
d
i
j
)
n
×
n
(d_{ij})_{n\times n}
(dij)n×n，目标函数即最小化起点到终点的距离之和。
设整个蚂蚊群体中蚂蚊的数量为
m
m
m, 路径节点的数量为
n
n
n, 节点
i
i
i 与节点
j
j
j 之间的相互距离为
d
i
j
(
i
,
j
=
1
,
2
,
…
,
n
)
,
t
d_{i j}(i, j=1,2, \ldots, n), t
dij(i,j=1,2,…,n),t时刻节点
i
i
i 与节点
j
j
j 连接路径上的信息素浓度为
τ
i
j
(
t
)
\tau_{i j}(t)
τij(t) 。初始时刻, 各个节点间连接路径上的信息素浓度相同, 不妨设为
τ
i
j
(
0
)
=
τ
0
\tau_{i j}(0)=\tau_{0}
τij(0)=τ0。
蚂蚁
k
(
k
=
1
,
2
,
…
,
m
)
k(k=1,2, \ldots, m)
k(k=1,2,…,m) 根据各个节点间连接路径上的信息素浓度决定其下一个访问节点, 设
P
i
j
k
(
t
)
P_{i j}^{k}(t)
Pijk(t) 表示
t
t
t 时刻蚂蚊
k
k
k 从节点
i
i
i 转移到节点
j
j
j 的概率, 其计算公式如下:
P
i
j
k
=
{
[
τ
i
j
(
t
)
]
α
⋅
[
η
i
j
(
t
)
]
β
∑
s
∈
allow
k
[
τ
i
s
(
t
)
]
α
⋅
[
η
i
s
(
t
)
]
β
s
∈
allow
k
0
s
∉
allow
k
(1)
\tag{1} P_{i j}^{k}= class="MathJax_Display">{[τij(t)]α⋅[ηij(t)]β∑s∈ allow k[τis(t)]α⋅[ηis(t)]βs∈ allow k0s∉ allow k" role="presentation" style="position: relative;">⎧⎩⎨[τij(t)]α⋅[ηij(t)]β∑s∈ allow k[τis(t)]α⋅[ηis(t)]β0s∈ allow ks∉ allow k
η
i
j
(
t
)
\eta_{i j}(t)
ηij(t) 为启发函数,
η
i
j
(
t
)
=
1
/
d
i
j
\eta_{i j}(t)=1 / d_{i j}
ηij(t)=1/dij, 表示蚂蚊从节点
i
i
i 转移到节点
j
j
j 的期望程度，
a
l
l
o
w
k
(
k
=
1
,
2
,
…
,
m
)
allow_{k}(k=1,2, \ldots, m)
allowk(k=1,2,…,m) 为蚂蚁
k
k
k待访问节点的集合。开始时,
a
l
l
o
w
k
allow_{k}
allowk中有(n-1)个元素,即包括除了蚂蚁
k
k
k出发节点的其它所有节点。随着时间的推进, allow
k
_{k}
k 中的元素不断减少, 直至为空, 即表示所有的节点均访问完毕。
首先计算每个个体的累积概率
q
j
q_{j}
qj ，如下式:
q
j
=
∑
j
=
1
l
P
i
j
k
(2)
\tag{2} q_{j}=\sum_{j=1}^{l} P_{i j}^{k}
qj=j=1∑lPijk(2)
q
j
q_{j}
qj 相当于转盘上的跨度，跨度越大的区域越容易选到，
l
l
l代表下一步可选路径的数量。 之后随机生成一个
(
0
，
1
)
(0 ， 1)
(0，1) 的小数
r
\mathrm{r}
r，比较所有
q
j
q_{j}
qj 与
r
\mathrm{r}
r 的大小，选出大于
r
r
r 的最小的那个
q
j
，
q_{j} ，
qj， 该
q
j
q_{j}
qj 对应的索引
j
j
j即为第
k
\mathrm{k}
k 只蚂蚁在第
i
i
i条路径时下一步要选择的目标点。
r
=
rand
(
0
,
1
)
j
=
index
{
min
[
q
j
>
r
]
}
(3)
\tag{3} class="MathJax_Display">r=rand(0,1)j=index{min[qj>r]}" role="presentation" style="position: relative;">r=rand(0,1)j=index{min[qj>r]}
r=rand(0,1)j=index{min[qj>r]}(3)
在蚂蚁释放信息素的同时，各个节点间连接路径上的信息素逐渐消失,设参数
ρ
(
0
<
ρ
<
1
，
一
般
取
值
为
0.1
\rho(0<\rho<1，一般取值为0.1
ρ(0<ρ<1，一般取值为0.1~
0.99
)
0.99)
0.99)表示 信息素的挥发程度。当所有的蚂蚁完成一次循环后，各个节点间链接路径上的信息素浓度需进行更新，计算公式为
{
τ
i
j
(
t
+
1
)
=
(
1
−
ρ
)
τ
i
j
(
t
)
+
Δ
τ
i
j
Δ
τ
i
j
=
∑
k
=
1
n
Δ
τ
i
j
k
(4)
\tag{4} \left\{ class="MathJax_Display">τij(t+1)=(1−ρ)τij(t)+ΔτijΔτij=∑k=1nΔτijk" role="presentation" style="position: relative;">τij(t+1)=(1−ρ)τij(t)+ΔτijΔτij=∑nk=1Δτkij
\right.
{τij(t+1)=(1−ρ)τij(t)+ΔτijΔτij=∑k=1nΔτijk(4) 其中，
Δ
τ
i
j
k
\Delta \tau_{i j}^{k}
Δτijk表示第
k
k
k只蚂蚁在节点
i
i
i与节点
j
j
j连接路径上释放的信息素浓度；
Δ
τ
i
j
\Delta \tau_{i j}
Δτij表示所有蚂蚁在节点
i
i
i与节点
j
j
j连接路径上释放的信息素浓度之和。
蚁周模型的
Δ
τ
i
j
k
\Delta \tau_{i j}^{k}
Δτijk计算公式如下
Δ
τ
i
j
k
=
{
Q
/
L
k
,
第
k
只蚂蚁从城市
i
访问城市
j
0
,
其他
(5)
\tag{5} \Delta \tau_{i j}^{k}= class="MathJax_Display">{Q/Lk, 第 k 只蚂蚁从城市 i 访问城市 j0, 其他 " role="presentation">{Q/Lk,0,第k只蚂蚁从城市i访问城市j其他
Δτijk={Q/Lk,0,第k只蚂蚁从城市i访问城市j其他(5) 式中
Q
Q
Q为信息素常数（一个正的常数），表示蚂蚁循环一次所释放的信息素总量。
L
k
L_{k}
Lk为第k只蚂蚁经过路径的总长度。
4. 算法步骤
对相关参数进行初始化，如蚁群规模（蚂蚁数量）
m
m
m、信息素重要程度因子
α
\alpha
α、启发函数重要程度因子
β
\beta
β、信息素挥发因子
ρ
\rho
ρ、信息素常数
Q
Q
Q、最大迭代次数
i
t
e
r
m
a
x
itermax
itermax。
构建解空间，将各个蚂蚁随机地置于不同的出发点，为每只蚂蚁确定当前候选道路集
更新信息素计算每个蚂蚁经过路径长度
L
k
(
k
=
1
,
2
,
…
，
m
)
L_k(k=1,2,…，m)
Lk(k=1,2,…，m)，记录当前迭代次数中的最优解（最短路径）。同时，对各个节点连接路径上信息素浓度进行更新。
判断是否终止若
i
t
e
r
<
i
t
e
r
m
a
x
iteriter<itermax，则令
i
t
e
r
=
i
t
e
r
+
1
iter=iter+1
iter=iter+1，清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。
评论记录：
回复评论：