【正文】 到的概率為： (16)其中，和分別表示信息素和啟發(fā)式信息的影響性。 基本原理在本文的路徑規(guī)劃問題中，由于為路徑點和之間的有向路徑線段長度，為連接起始點和目標點的有向線段，為與之間的夾角，與夾角越小的線段就越可能是最優(yōu)路線的一部分，也就是說越小，選擇該路徑的概率就越大，所以，進行計算時，通過計算方向夾角余弦值，從起始點開始尋找與其連接的線段形成較小夾角的那條路線，依次尋找，便可求出最短路徑。然而，在電子地圖中每個圖元都有一個經緯度坐標[30]，利用經緯度坐標可以求出方向夾角的余弦值。假設城市道路網絡平面示意圖如圖8所示：圖8 方向夾角啟發(fā)信息Fig8 The angle between the direction of heuristic information不妨設所求路線是起點到終點的一條最短路，我們認為與夾角越小的路徑段越有可能是全局最優(yōu)路徑的一部分，由于和相連接的點是點和點，不難看出，有向線段和的夾角小于線段和線段之間的夾角，因此，首先選擇節(jié)點；同理，與相連的節(jié)點是和，優(yōu)先選擇節(jié)點；同理，優(yōu)先選擇。若是螞蟻走的路徑總長度越短即越小，則信息素濃度越大，被選中該路徑的概率也就越大，符合螞蟻尋路規(guī)則。那么對可行路徑的優(yōu)化模型為：，其中表示路徑點和之間的路線長度。一條可行路徑是包括起始點和目標點在內的個順序連接的路徑點所表示：。解決路徑規(guī)劃問題，起始點和目標點的位置是已知的，如路徑規(guī)劃是顯示在圖7，我們可以考慮空間幾何關系作為啟發(fā)式信息。所以，在我們改進的蟻群算法中，摒棄禁忌表的使用，同時加入一種新的啟發(fā)式信息：方向夾角。這些算法都是圍繞全局收斂和提高算法收斂速度這兩點進行的，但是這兩者是矛盾的統(tǒng)一體，不可能同時達到，因此要更好地改進蟻群算法必須充分考慮它的啟發(fā)信息。 夾角優(yōu)化的蟻群算法我們知道蟻群算法是一種典型的概率隨機搜索算法，許多研究表明[28]，蟻群算法在求解實際問題時容易出現兩個問題：一是停滯現象；二是當所求問題規(guī)模較大時，需要很長的搜索時間，即收斂到全局最優(yōu)解的搜索時間長。在如何解決路徑規(guī)劃問題這方面，近年來國內外學者已經做了大量的研究[26]，這其中包括蟻群算法、人工勢場法、啟發(fā)式搜索算法、神經網絡算法、模糊算法、遺傳算法[27]等等。我們給定一個帶權的有向圖，其中是包含個節(jié)點的節(jié)點集，是包含條邊的集合，是中從節(jié)點到的邊，是邊的非負權值。4 夾角優(yōu)化的蟻群算法及在路徑規(guī)劃中的應用4夾角優(yōu)化的蟻群算法及在路徑規(guī)劃中的應用 對路徑規(guī)劃問題的描述根據規(guī)劃的目的是不同的，路徑規(guī)劃可分為多車輛路徑規(guī)劃和單個車輛路徑規(guī)劃[2124]，前者主要用于車隊調度和交通管制，后者多用于各種導航系統(tǒng)，主要研究的問題是在給定的城市道路網中如何尋找從起始點到目標點的一段最佳行駛路線，即最短路線。圖5 改進算法的最優(yōu)路徑Fig5 the optimal path of improved algorithm圖6 改進算法的各代最短距離和平均距離Fig6 the shortest distance and the average distance each generation表1中給出了本文的改進算法與常規(guī)模擬退火蟻群算法20優(yōu)化的對比結果，當算法優(yōu)化結果與其最優(yōu)解的誤差小于15%時視為收斂。最新研究成果表明，上述TSP問題的理論最優(yōu)解為15377km，常規(guī)模擬退火蟻群混合算法的最優(yōu)解為15601。下面將本文提出的算法應用于我國31個省會、直轄市和自治區(qū)首府間的TSP，以測試算法的性能。當小于設定的閾值(通常取為)時，根據(2)式加強信息素；當大于設定的閾值(通常取為)時，采用回火策略?？紤]目標函數梯度的具體方法是：定義 (7)其中 (8) (9)表示向量的第個分量。因此，為了解決這個問題，我們在算法中引入回火機制，回火是指將溫度略微升高后再降溫的策略。并用改進的算法求解旅行商問題，結果表明，與常規(guī)的模擬退火蟻群算法相比，新算法的收斂速度和解的質量均得到很大的改善。本文提出了一種基于目標函數梯度的模擬退火蟻群混合算法，在優(yōu)化過程中，根據目標函數的梯度動態(tài)地控制信息素濃度和回火過程，并根據數值實驗結果對新算法的全局收斂性和解的質量進行了評測。劉波提出了一種基于模擬退火機制的蟻群算法，該算法在高溫階段以高概率加入更新集，在低溫階段采用回火策略[18]。 算法流程考慮到模擬退火算法和蟻群算法各自的特點，許多學者先后提出了基于模擬退火算法和蟻群算法的混合智能優(yōu)化算法[16]。因此根據各自的優(yōu)缺點可以將兩種智能優(yōu)化算法根據某種法則相融合或在某種優(yōu)化算法中引入其它優(yōu)化思想，形成混合優(yōu)化算法，可以充分發(fā)揮智能算法各自的優(yōu)點，揚長避短，以便取得時間性能和優(yōu)化性能的雙贏，提高算法各方面的性能。模擬退火算法的流程圖如下：圖3 模擬退火算法流程圖Fig3 The flowchart of simulated annealing algorithm 基于目標函數梯度的模擬退火蟻群算法 混合算法的基本原理通過以上對蟻群算法和模擬退火算法基本原理的研究可知，蟻群算法的優(yōu)點是正反饋、自組織、分布式，缺點是易限于局部最優(yōu)解，收斂速度慢。模擬退火算法的基本流程如下：(1) 參數初始化。該算法的基本思想是從一給定解開始的，從鄰域中隨機生成另一個解，接受準則允許的目標函數惡化在有效范圍內，它由一控制參數決定，算法由初始解和控制參數初值開始反復進行“生成新解—計算目標函數值的差—接受或拒絕”這一迭代過程，它對應著固體在某恒定高溫下趨于熱平衡的過程，減少了控制參數，系統(tǒng)越來越趨于平衡狀態(tài)，最終的系統(tǒng)狀態(tài)對應于優(yōu)化問題的整體最優(yōu)解，需要指出的是，由于固體退火緩慢冷卻可以使固體在所有溫度下達到熱平衡，因此，控制參數必須緩緩衰減才能保證優(yōu)化問題趨于整體最優(yōu)解。它源于物理中對固體退火過程的模擬，分為升溫、平衡、冷卻三個階段，先將固體加溫至充分高，再讓其漸漸冷卻，升溫時粒子變?yōu)闊o序狀內能增大，冷卻時粒子變得有序，內能逐漸減小。(4) 容易出現停滯，搜索到一定程度，所有個體的解決方案完全相同，沒有進一步搜索解空間，不利于找到更好的解決方案。(2) 基本蟻群算法計算量大，需要很久才能求出解。(3) 可以隨意地與多種啟發(fā)式算法自由組合，以提高解的性能。蟻群算法的優(yōu)點：(1) 與其它啟發(fā)式優(yōu)化算法相比，蟻群算法具有較強的魯棒性。目前來看，蟻群算法在許多領域都有廣泛的應用并取得了良好的成果，但是它自身也存在一些缺陷。經過以上的分析，蟻群算法的基本步驟總結如下：(1) 初始化參數，將只螞蟻放在個結點上；(2) 據式(1)計算每只螞蟻移動到下一結點的概率，并根據其概率進行選擇下一個結點；(3) 螞蟻遍歷一周后計算路徑長度，按式(3)更新信息素增量；(4) 所有路徑的信息素更新按式(2)進行；(5) 重復2至4步，直至滿足迭代終止條件輸出最好解。根據具體情況可以有不同的表達方式。每只螞蟻按照如下過程建構一條行走路線：(1) 根據某些規(guī)則，它們會依照概率選擇一個城市作為起點，我們把螞蟻放到該城市；(2) 螞蟻利用啟發(fā)式信息和信息素強度，以一定的概率選擇下一個允許訪問的城市（表示螞蟻下一個要走的城市），這里用禁忌表來控制不允許訪問的城市（設表示第只螞蟻的禁忌表，表示中第個元素）；(3) 螞蟻行走一周返回起始城市后，在每一條路徑上會留下信息素。在整個算法過程，人工模擬螞蟻不同于真實螞蟻的是：螞蟻具有記憶性，也就是說一只螞蟻選擇過的路徑在下次搜索時就不會再被選擇，為了方便計算，我們建立禁忌表來代表螞蟻訪問過的城市。 蟻群算法的算法流程蟻群算法是一種廣義型的隨機優(yōu)化方法[17]，像其他模型進化算法，是通過候選解組成的群體，以確定最優(yōu)解的進化過程，選擇一條搜索路徑最初只是隨機的概率，重復這個過程，成為一個有規(guī)律的搜索，并逐步接近“更好的”解決方案。當時，如圖1(f) 所示，前只螞蟻又回到點并再次面臨向左還是向右的選擇，此時，經過的螞蟻數量為，而經過的螞蟻數量為，明顯的信息素多于，這條路線會出現更多的螞蟻。當時，如圖1(d) 所示，兩組螞蟻在點相遇，且和的信息素數量相同，此時，第一組返回的只螞蟻到達點并以等概率分別走向、第二組螞蟻依然走向。當時，如圖1(b) 所示，只螞蟻從出發(fā)，以相同的概率選擇和，因此，各方向有只螞蟻行走。簡單來說，蟻群算法的基本原理在于以下三點：(1) 螞蟻能連續(xù)不斷地釋放信息素；(2) 螞蟻能感知小范圍區(qū)域內狀況；(3) 螞蟻釋放出的信息素隨時間逐步減少。螞蟻在尋找食物的過程中，如果從巢到食物源的距離很短，那么螞蟻從巢到食物源，然后再返回巢的時間就短，這表明，在同一時間內，較短路徑的螞蟻會分泌和積累更多的信息素。92 蟻群算法的原理及過程2 蟻群算法的原理及過程 蟻群算法的基本原理蟻群算法中的虛擬螞蟻吸收了大自然中真實螞蟻的行為特征。3. 闡述了模擬退火算法的基本原理和算法流程，然后介紹基于目標函數梯度的模擬退火蟻群混合算法的基本原理和算法流程，并給出新算法對TSP問題優(yōu)化的實驗結果。 論文的主要內容本論文主要包含以下幾方面：1. 首先簡要介紹了蟻群算法的意義產生的背景和研究的現狀的研究，總結了研究的意義和論文的主要內容。所以，進行計算時，通過計算方向夾角余弦值，從起始點開始尋找與其連接的線段形成較小夾角的那條路線，依次尋找，便可求出最短路徑。盡管蟻群算法理論的應用方法研究還處于初級階段，一些領域，一些課題還需要更深入的研究，需要人們更深入的探討，但是，從未來發(fā)展趨勢來看[12]，群智能的研究對人類社會的發(fā)展越來越重要了，是未來計算機研究和發(fā)展的一個重要方向。隨著社會的進步，特別是智能理論和應用算法研究和發(fā)展，學者們已經取得了很大進展，試圖將其應用于現實實踐中，并取得了意想不到的成果。與其他啟發(fā)式算法相比，這三種算法僅僅容易解決小規(guī)模問題。來自公開文獻的資料顯示，在國際群體智能計算領域，蟻群算法已經成為一個熱門的研究方向。如今，螞蟻的這種尋找食物的行為最為引人注目。這種情況下，研究者們對一些社會性動物[25]（螞蟻、蜜蜂、魚、鳥等）的自組織行為產生了興趣，許多學者利用數學建模和計算機仿真技術，產生了“群智能”。IX1 緒論1緒 論 蟻群算法生成背景和意義人工智能在1980年的20世紀，整整10年的繁榮經歷[1]，因為該方法并沒有脫離傳統(tǒng)的計算障礙，所以再次迎接著新的挑戰(zhàn)。在優(yōu)化過程中，根據目標函數的梯度動態(tài)地控制信息素濃度和回火過程，并以旅行商問題為例，根據數值實驗結果對新算法的全局收斂性和解的質量進行了評測。常規(guī)的蟻群算法只根據信息素的強度和道路的可見度進行信息素的更新，產生一定的概率，螞蟻再按照這個概率來選擇下一條較短路徑，因此，最初路徑的選擇顯得尤為重要，容易產生停滯現象，陷于局部最優(yōu)。蟻群算法是一種新興的群智能概率型搜索算法，在解決這類問題中起到了重要作用，本文在常規(guī)的蟻群算法基礎上對其做了兩方面的改進。4. 首先簡要介紹路徑規(guī)劃問題，然后介紹夾角優(yōu)化的蟻群算法的基本原理和算法流程，最后給出新算法對路徑規(guī)劃問題