【正文】 作者簡介及讀研期間主要科研成果作者簡介及讀研期間主要科研成果1. 作者簡介弓英瑛，女，河南鄭州人，1988年3月生。在此向許老師致以崇高的敬意和衷心的感謝!感謝許老師在這幾年的學習工作中對我的辛勤培養(yǎng)、殷切教誨和無私的關心幫助。圖11 常規(guī)蟻群算法和夾角優(yōu)化蟻群算法所得最優(yōu)路徑Fig11 the optimal path algorithm conventional ant colony algorithm and the angle of algorithm 圖12和13分別給出了常規(guī)蟻群算法和夾角優(yōu)化蟻群算法路程進化圖。 80,80。 改進后的算法流程以上分別對路徑規(guī)劃問題和夾角優(yōu)化的蟻群算法進行了描述，本節(jié)將給出夾角優(yōu)化的蟻群算法求解路徑規(guī)劃問題的具體算法過程。那么所選擇的路線為，事實上，這條路線已經是最短路徑。圖7 路徑規(guī)劃模型Fig7 Path planning model如圖7所示的路徑規(guī)劃模型，起始點和目標點是已知的，圖中的邊構造出的是所有的可行路徑，這些邊的交點就是所有的可行路徑點，現需要規(guī)劃出一條路徑使得起始點和目標點之間的距離最短。這些算法都取得了一些較好的實驗結果，本章將對蟻群算法進行改進引入夾角這一因素來解決路徑規(guī)劃問題。本文算法的最優(yōu)解平均為15438，某次優(yōu)化的最優(yōu)路徑及各代平均距離、最短距離見圖5和圖6。回火的溫度范圍設為，若，將溫度升高至，重新進行算法迭代，當再次時，這一過程稱為回火過程，重復此過程，可以根據設定進行多次回火，回火次數設為，最大回火次數。許智宏提出一種模擬退火蟻群并行算法[17]。在判斷新解是否被接受，我們通常使用準則來判斷是否為新解：若目標函數值的差，則接受作為當前解；否則，若，則接受作為新解，否則舍棄。蟻群算法的缺點：(1) 如果不能恰當地設置參數，很容易導致慢收斂速度和質量較差的解。曾給出了三種不同類型，分別為、它們的區(qū)別在于不同的表達(4)，在模型中： (5)在模型[14]中： (6) 我們通常把第一種模型看作基本的模型，因為它考慮的是整體信息，解決問題的性能相對好。按照這個過程不斷循環(huán)下去，路徑越短，信息素積累就越多，久而久之，它們信息素數量的差距將越來越明顯，路徑將會有更多的螞蟻出現，如果時間足夠長，最終所有的螞蟻都會毫無偏向地選擇這條路線。愈多的螞蟻，留下的信息素（隨著時間的增長而減少）也是愈多，另外，隨后的螞蟻能夠感知前面的螞蟻信息素留下的多少來指導它的方向，所以某條路徑上的信息素多了，螞蟻選擇這條路的可能性比較大。如今，蟻群算法作為群智能算法的一種新型進化算法，已經在智能領域[13]表現出了極為強大的生命力，對于解決各種復雜優(yōu)化問題都顯示了它的卓越之處，由于它本身也存在許多缺陷[14]，因此蟻群算法改進方面的研究對解決這些實際優(yōu)化問題具有重要意義，并能更好地推動智能算法的不斷發(fā)展和完善，本文對蟻群算法的改進方面進行了嚴格的理論分析和完整的數值實驗，對整個群智能理論體系起到了巨大的推動作用，其本身也具有重要的理論研究價值和實踐意義。 蟻群算法的研究現狀遺傳算法、進化規(guī)劃、進化策略[7]等等，都是人們通過仿生學的研究得出解決復雜優(yōu)化問題的新方法，仿生學的出現使得人們在生物進化研究方面有了新的方法和研究方向，由于生物特有的獨特天性和特點，群落行為的產生具有一定的規(guī)律，這為學者們研究生物學提供了可貴的材料，因此出現了基于群智能理論的蟻群算法，它最早由意大利學者提出，蟻群算法包括三種基本算法[89]：。在路徑規(guī)劃問題中，各路徑之間存在方向夾角，因而，解決此問題時充分考慮到方向夾角的大小，夾角越小的線段就越有可能是最優(yōu)路線的一部分，在進行優(yōu)化的過程中，通過計算方向夾角的余弦值確定其大小，將其加入信息素的更新公式，以保證更好地找到最短路徑。3. 首先簡要介紹了模擬退火算法的基本原理和算法的過程，然后介紹了一種基于目標函數的梯度模擬退火蟻群算法的基本原理和算法流程，最后給出新算法對問題優(yōu)化的實驗結果。與積極的反饋、自組織、分布式、強健、易與其他算法相結合的優(yōu)勢，蟻群算法往往陷入局部最優(yōu)解，收斂速度慢，對初始解的要求比較高。中圖分類號： O224 論文編號： 學科分類號： 密　　級： 公 開 安徽理工大學碩 士 學 位 論 文蟻群算法的改進研究與應用作者姓名： 弓 英 瑛 專業(yè)名稱： 應 用 數 學 研究方向： 優(yōu)化理論與應用 導師姓名： 許 峰 教 授 導師單位：安徽理工大學理學院答辯委員會主席： 論文答辯日期： 年 月 日安徽理工大學研究生處 年 月 日A Dissertation in Applied MathematicsResearch and Application of Improved Ant Colony AlgorithmCandidate:Gong Yingying Supervisor:Xu FengSchool of ScienceAnhui University of Science and Technology, Shungeng Road, Huainan, 232001, 獨 創(chuàng) 性 聲 明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。從理論上講，適當轉換后改進的蟻群算法可以使任何組合優(yōu)化問題得到更快地解決。4. 首先簡要介紹路徑規(guī)劃問題，然后介紹夾角優(yōu)化的蟻群算法的基本原理和算法流程，最后給出新算法對路徑規(guī)劃問題優(yōu)化的結果。IX1 緒論1緒 論 蟻群算法生成背景和意義人工智能在1980年的20世紀，整整10年的繁榮經歷[1]，因為該方法并沒有脫離傳統(tǒng)的計算障礙，所以再次迎接著新的挑戰(zhàn)。與其他啟發(fā)式算法相比，這三種算法僅僅容易解決小規(guī)模問題。 論文的主要內容本論文主要包含以下幾方面：1. 首先簡要介紹了蟻群算法的意義產生的背景和研究的現狀的研究，總結了研究的意義和論文的主要內容。簡單來說，蟻群算法的基本原理在于以下三點：(1) 螞蟻能連續(xù)不斷地釋放信息素；(2) 螞蟻能感知小范圍區(qū)域內狀況；(3) 螞蟻釋放出的信息素隨時間逐步減少。 蟻群算法的算法流程蟻群算法是一種廣義型的隨機優(yōu)化方法[17]，像其他模型進化算法，是通過候選解組成的群體，以確定最優(yōu)解的進化過程，選擇一條搜索路徑最初只是隨機的概率，重復這個過程，成為一個有規(guī)律的搜索，并逐步接近“更好的”解決方案。經過以上的分析，蟻群算法的基本步驟總結如下：(1) 初始化參數，將只螞蟻放在個結點上；(2) 據式(1)計算每只螞蟻移動到下一結點的概率，并根據其概率進行選擇下一個結點；(3) 螞蟻遍歷一周后計算路徑長度，按式(3)更新信息素增量；(4) 所有路徑的信息素更新按式(2)進行；(5) 重復2至4步，直至滿足迭代終止條件輸出最好解。(2) 基本蟻群算法計算量大，需要很久才能求出解。模擬退火算法的基本流程如下：(1) 參數初始化。劉波提出了一種基于模擬退火機制的蟻群算法，該算法在高溫階段以高概率加入更新集，在低溫階段采用回火策略[18]?？紤]目標函數梯度的具體方法是：定義 (7)其中 (8) (9)表示向量的第個分量。圖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%時視為收斂。 夾角優(yōu)化的蟻群算法我們知道蟻群算法是一種典型的概率隨機搜索算法，許多研究表明[28]，蟻群算法在求解實際問題時容易出現兩個問題：一是停滯現象；二是當所求問題規(guī)模較大時，需要很長的搜索時間，即收斂到全局最優(yōu)解的搜索時間長。一條可行路徑是包括起始點和目標點在內的個順序連接的路徑點所表示：。然而，在電子地圖中每個圖元都有一個經緯度坐標[30]，利用經緯度坐標可以求出方向夾角的余弦值。螞蟻從“巢穴”出發(fā)尋找“食物”的過程就相當于路徑規(guī)劃中從起始點到達目標點的過程，檢驗下一個目標節(jié)點是否為食物，若為食物，則保存此時的記錄，如果不是的話，設置下一個目標節(jié)點為當前節(jié)點繼續(xù)尋找。 100,40)，障礙物3的4個頂點坐標分別為(120,圖12 常規(guī)蟻群算法路程進化圖Fig12 the figure of conventional ant colony algorithm圖13 夾角優(yōu)化蟻群算法路進化圖Fig13 the figure of ant colony optimization angle算法分析和仿真結果所示，夾角優(yōu)化可以改善算法的收斂性，提高解的質量。許老師在論文研究的各階段，給予了我很多的建議。2011年7月畢業(yè)于南陽師范學院數學與應用數學專業(yè)；2011年9月考入安徽理工大學理學院攻讀碩士學位。最后向參加論文審閱、答辯的專家和老師表示感謝和崇高的敬意。參考文獻參考文獻[1] Dorigo M. Optimization, learning and natural algorithms [D]. PhD thesis, Dipartimento di Elettronica, Politeico di Milano, Italy, 1992: 140.[2] Bonabeau E, Dorigo M, Theraulaz G. Inspiration for optimization from social insect behavior [J]. Nature, 2000, 406(6): 3942.[3] Michael J B K, JeanBernarrd B, Laurent K. Antlike task and recruitment in cooperation robots [J]. Nature, 2000, 406(31): 992995.[4] Jackson D E, Holbe M, Ratnieks F L W. Trail geometry gives polarity to ant foraging networks [J]. Nature, 2004, 432(7019): 907909.[5] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller. Equation of State Calculations by Fast Compu