📄 algorithm.htm
字号:
<html>
<head>
<title>Untitled Document</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>
<body bgcolor="#FFFFFF">
<table width="750" border="0">
<tr align="center">
<td><font size="5"><b>软件中涉及到的算法及参数说明</b></font></td>
</tr>
</table>
<table width="750" border="0">
<tr>
<td>
<p>本软件目前包含标准蚁群算法、MMAS中的对信息量进行限制的算子、我对蚁群算法的一种改进算法。 蚁群算法针对不同的问题有稍微不同的结构，由于蚁群算最初是以解决TSP问题的形式提出的，而且学习蚁群算法通常以TSP问题为例，因此本软件中的蚁群算法采用求解TSP问题的算法。有关蚁群算法的详细资料可参考我的论文《带杂交算子的蚁群算法》（发表在《计算机工程》2001年第12期），这里介绍仅简略介绍蚁群算法，目的是说明本软件中采用的参数名称（因为不同文献中，参数的字母代号可能不同）。
</p>
<p>本软件中的标准蚁群算法的模型如下： 在求解TSP时，首先建立一个蚁群，其中的每一只蚂蚁都执行这样的操作：</p>
<p> （1） 按下式计算每只蚂蚁一次周游的路径 </p>
<p><img src="images/Eq1.gif" width="397" height="86"> (公式1）</p>
<p>其中，q为区间[0,1]上的随机数，q0是ACS中引进的一个参数（本软件中取其为0），S根据下式确定：</p>
<p><img src="images/Eq2.gif" width="567" height="192">（公式2）</p>
<p>其中，<img src="images/prsk.gif" width="40" height="34">表示蚂蚁k由当前城市r转移到城市s的概率，η(r，s)=1/d（r，s）（d（r，s）表示城市r与城市s之间的距离），τ（r，s）表示城市r与城市s之间的残留信息量（对应于真实蚁群系统中各点的外激素强度），Jk表示第k只蚂蚁还未访问过的城市，α，β是用于调节τ(r,s)与η(r,s)之间的关系的参数。</p>
<p> （2） 每生成一只蚂蚁的一次周游路径，对它经过的路径上的各条弧按下式调整信息量强度 </p>
<p>τ(r,s)= （1-ρ）·τ(r,s)+ ρτ0 （公式3）</p>
<p>其中，τ0为信息量的初始值，r，s分别为蚂蚁经过的一条弧的起点和终点 （3） 所有蚂蚁都完成一次周游后，按下式对最优的蚂蚁经过的路径上的信息量进行全局更新</p>
<p> τ(r,s)←(1-ρ)×τ(r,s)+Δτ(r,s) （公式4）</p>
<p>其中，Δτ(r,s)= 1/ L ，（如果路径(r,s)是算法当前已求出的最优路径的一部分）或Δτ(r,s)= 0（其他情况时）。ρ为区间（0，1）上的参数（通常这里的ρ与公式3中的ρ取相等的值，因此这里用同一个字母表示），L为算法已求出的最优路径长度。（这里的最优路径可以是全局最优路径，也可以是这一次循环中的最优路径，在本文的实验中将采用本次循环中的最优路径）</p>
<p> 当每只蚂蚁都完成一次上述操作时，就称该算法进行了一次周游（Iteration）。 循环以上步骤，直到周游次数达到指定次数或在一定时间内没有新的更优解出现。（注：考虑到实验中的需要，本软件中采用前者作为停止计算的标志之一，另一个标志是用户单击"停止计算"键）</p>
<p><b>本软件中采用的限制信息量的算子如下：</b> 当计算过程中信息量大于你设定的最大值时，信息量将设置为等于最大值。当计算过程中信息量小于你设定的最小值时，信息量将设置为等于最小值。</p>
<p> <b>本软件中采用的一种改进算法如下：</b> 该改进算法主要修改了全局更新公式（即公式4）。 当所有蚂蚁完成一次周游后，增加对最差蚂蚁经过的路径的更新。若（r,s）为最差蚂蚁路径中的一段弧，且不是最优蚂蚁周游路径中的弧，则该弧上的信息量按下式调整
</p>
<p>τ(r,s)= （1-ρ）·τ(r,s)-εLworst/Lbest （公式5）</p>
<p> 其中，ε为新方法中引入的参数，Lworst表示当前周游中最差蚂蚁的路径长度，Lbest表示当前周游中最优蚂蚁的路径长度。</p>
<p> 算法的具体描述如下： </p>
<p>（1） 初始化； </p>
<p>（2） 根据公式1、公式2为每只蚂蚁选择路径； </p>
<p>（3） 每生成一只蚂蚁的路径就按公式3进行一次局部更新规则； </p>
<p>（4） 循环执行步骤(2)、(3)直到每只蚂蚁都生成一条路径； </p>
<p>（5） 评选出最优和最差蚂蚁； </p>
<p>（6） 对最优蚂蚁按公式4执行全局更新规则； </p>
<p>（7） 对最差蚂蚁按公式5执行全局更新规则；</p>
<p> 循环执行步骤（2）-（7）直到执行次数达到指定数目或连续若干代内没有更好的解出现。 </p>
<p><a href="Help.htm">[返回首页]</a></p>
</td>
</tr>
</table>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -