4 Computer Engineering and Applications
的信息素 将依照公式(4)进行改变.
(4)
式中,∂表示局部信息素挥发率,τ0 代表初始信
息素量,值为 1/ ( n*Lnn ),Lnn 是根据贪婪法则(每次
进行下一城市选择时,选择最近的城市点)得到的路径
长度,而 n 则是当前测试集的城市数.由此可知,在初
始阶段τ0 是个远小于Δτij 的值,它们之间至少 有
n 倍的差距.
1.1.4 全局信息素更新
在 ACS 模型中只更新属于最好路径的各条边的
信息素浓度.
除了局部信息素更新外,ACS 还通过全局信息素
的更新方式增加最优解被选择 的概率,如公式(5)和
公式(6)所示.
(5)
(6)
式中, 为全局信息素挥发率,ij 为每次迭代
信息素增量,Lgb 为当前最优路 径长度. ACS 的全局
信息素更新策略,即在最优路径释放信息素,使全局
最优解对以后迭代蚂蚁的路径构建成正反馈作用,增
加整个算法的收敛速度.
1.2 信息熵
1948 年,香农(Shannon)在他著名的《通信的数学
原理》论文中指出:“信息是用来消除随机不确定性
的东西”,并提出了“信息熵”的概念,来解决信息
的度量问题.
对于任意一个随机变量 X,它的信息熵 H(X)定义
如下:p(x)代表随机事件 x 的概率.如公式(7),公式(8)所
示.
ε
(7)
(8)
1.3 K-opt
k-opt 局部搜索算法也称 k 交换算法. k-opt 的基
本原理是应用局部搜索的概念,通过对 k 条边(弧)
进行交换,在初始解的邻域中对初始解进行调整,接
受得到改进的可行解.一次最多可以找到的新可行解
的个数为 2^k.设 T 是一条初始路径, 该算法总是试
图找到 2 个有序集合: X , X ∈ T 和 Y , Y ∈ T,如果
在一定要求下用 Y 集合代替 X 集合,使得新的费用代
价变小,则这 k 条边的交换就被称为 k-opt 交换.优化解
X 就叫做 T 的 k-opt 优化解.
举例当 k=3 时,可能得到如下的 8 条 k-opt 的新路
径.如图 1(a)-(h)所示.
(a)3-opt 的第 1 种情况 (b)3-opt 的第 2 种情况 (c)3-opt 的第 3 种情况 (d)3-opt 的第 4 种情况
(e)3-opt 的第 5 种情况 (f)3-opt 的第 6 种情况 (g)3-opt 的第 7 种情况 (h)3-opt 的第 8 种情况
图 1 3-opt 优化
Fig.1 3-opt optimization