?? 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 + -