【正文】 成背景和意義人工智能在1980年的20世紀，整整10年的繁榮經歷[1]，因為該方法并沒有脫離傳統(tǒng)的計算障礙，所以再次迎接著新的挑戰(zhàn)。常規(guī)的蟻群算法只根據信息素的強度和道路的可見度進行信息素的更新，產生一定的概率，螞蟻再按照這個概率來選擇下一條較短路徑，因此，最初路徑的選擇顯得尤為重要，容易產生停滯現象，陷于局部最優(yōu)。4. 首先簡要介紹路徑規(guī)劃問題，然后介紹夾角優(yōu)化的蟻群算法的基本原理和算法流程，最后給出新算法對路徑規(guī)劃問題優(yōu)化的結果。新算法應用于旅行商及路徑規(guī)劃問題，新算法的優(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) 性 聲 明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作及取得的研究成果。學位論文作者簽名：___________ 日期： 年 月 日學位論文版權使用授權書本學位論文作者完全了解 安徽理工大學 有保留、使用學位論文的規(guī)定，即：研究生在校攻讀學位期間論文工作的知識產權單位屬于 安徽理工大學 。與積極的反饋、自組織、分布式、強健、易與其他算法相結合的優(yōu)勢，蟻群算法往往陷入局部最優(yōu)解，收斂速度慢，對初始解的要求比較高。數值分析和實驗表明：改進的新算法不僅具有原算法的優(yōu)點，而且提高了算法的速度。3. 首先簡要介紹了模擬退火算法的基本原理和算法的過程，然后介紹了一種基于目標函數的梯度模擬退火蟻群算法的基本原理和算法流程，最后給出新算法對問題優(yōu)化的實驗結果。這種改進使我們更快速準確地找到最優(yōu)解，實驗證明這種改進算法具有有效性。在路徑規(guī)劃問題中，各路徑之間存在方向夾角，因而，解決此問題時充分考慮到方向夾角的大小，夾角越小的線段就越有可能是最優(yōu)路線的一部分，在進行優(yōu)化的過程中，通過計算方向夾角的余弦值確定其大小，將其加入信息素的更新公式，以保證更好地找到最短路徑。個體行為的社會性昆蟲雖然簡單、隨機，但它們完全可以互相團結一致地完成一些看似特別復雜的行為，比如筑巢、遷徙、覓食，鳥類在沒有管理和控制的情況下，可以齊心協力得飛行，并建立起溫暖的窩，螞蟻覓食的時候，無論有多少障礙，他們總可以找到從蟻巢到食物源的最短路徑。 蟻群算法的研究現狀遺傳算法、進化規(guī)劃、進化策略[7]等等，都是人們通過仿生學的研究得出解決復雜優(yōu)化問題的新方法，仿生學的出現使得人們在生物進化研究方面有了新的方法和研究方向，由于生物特有的獨特天性和特點，群落行為的產生具有一定的規(guī)律，這為學者們研究生物學提供了可貴的材料，因此出現了基于群智能理論的蟻群算法，它最早由意大利學者提出，蟻群算法包括三種基本算法[89]：。目前，蟻群算法的應用研究主要應用于網絡規(guī)劃、物流配送、生產調度[11]等。如今，蟻群算法作為群智能算法的一種新型進化算法，已經在智能領域[13]表現出了極為強大的生命力，對于解決各種復雜優(yōu)化問題都顯示了它的卓越之處，由于它本身也存在許多缺陷[14]，因此蟻群算法改進方面的研究對解決這些實際優(yōu)化問題具有重要意義，并能更好地推動智能算法的不斷發(fā)展和完善，本文對蟻群算法的改進方面進行了嚴格的理論分析和完整的數值實驗，對整個群智能理論體系起到了巨大的推動作用，其本身也具有重要的理論研究價值和實踐意義。4. 概要介紹了路徑規(guī)劃問題，然后論述夾角優(yōu)化的蟻群算法的基本原理和算法流程，最后給出改進后的算法對路徑規(guī)劃問題的優(yōu)化結果。愈多的螞蟻，留下的信息素（隨著時間的增長而減少）也是愈多，另外，隨后的螞蟻能夠感知前面的螞蟻信息素留下的多少來指導它的方向，所以某條路徑上的信息素多了，螞蟻選擇這條路的可能性比較大。當時，如圖1(c) 所示，沿著的第一組螞蟻到達并準備返回，而第二組在的中點處。按照這個過程不斷循環(huán)下去，路徑越短，信息素積累就越多，久而久之，它們信息素數量的差距將越來越明顯，路徑將會有更多的螞蟻出現，如果時間足夠長，最終所有的螞蟻都會毫無偏向地選擇這條路線。旅行商問題的解決有效使用了蟻群算法，下面介紹其基本算法：已知有只螞蟻,座城市,表示城市到之間的距離，表示到的可見度，表示時刻在路上的信息素強度，也可以把理解為訪問完城市之后立刻訪問城市的期望程度，表示啟發(fā)式信息可，也就是說，從路徑直接走到的期望程度與兩條路徑之間的距離成反比。曾給出了三種不同類型，分別為、它們的區(qū)別在于不同的表達(4)，在模型中： (5)在模型[14]中： (6) 我們通常把第一種模型看作基本的模型，因為它考慮的是整體信息，解決問題的性能相對好。下面對蟻群算法的優(yōu)缺點進行簡單地歸納總結。蟻群算法的缺點：(1) 如果不能恰當地設置參數，很容易導致慢收斂速度和質量較差的解。3 基于目標函數梯度的模擬退火蟻群算法3基于目標函數梯度的模擬退火蟻群算法 模擬退火算法的基本原理和算法流程模擬退火算法是基于迭代算法的一種啟發(fā)式隨機搜索算法[19]，最早的思想由等人于1953年提出[20]。在判斷新解是否被接受，我們通常使用準則來判斷是否為新解：若目標函數值的差，則接受作為當前解；否則，若，則接受作為新解，否則舍棄。模擬退火算法的優(yōu)點是算法簡單、魯棒性強、具有全局搜索能力，特別適用于復雜的非線性問題，缺點是對初始解有很強的依賴性，當系統(tǒng)不使用反饋信息，在一定程度上的解是大量的冗余迭代造成的，精確率低。許智宏提出一種模擬退火蟻群并行算法[17]。該混合算法充分考慮了目標函數的梯度，當目標函數的梯度較小時，加強當前最優(yōu)解對應的信息素，這相當于在“平坦”之處加快搜索速度，使算法加快收斂；當目標函數的梯度過大時，引入回火策略[19]，即在“陡峭”之處放緩搜索速度，以提高解的質量?；鼗鸬臏囟确秶O為，若，將溫度升高至，重新進行算法迭代，當再次時，這一過程稱為回火過程，重復此過程，可以根據設定進行多次回火，回火次數設為，最大回火次數。基于目標函數梯度的模擬退火蟻群混合算法的流程如下：步驟1 初始化參數：；步驟2 利用模擬退火算法計算出一個較優(yōu)解，在這個路徑上留下信息素；步驟3 按上述方式，根據目標函數梯度加強信息素，并采用回火策略；步驟4 將只螞蟻放在個結點處，并對每只螞蟻按式(1)的概率選擇下一個結點，完成一次循環(huán)；步驟5 在鄰域內找另外一個解，若，接受新解，否則舍棄；步驟6 依據模擬退火原理，采用回火策略， 直至，輸出最優(yōu)解，若，轉步驟2；下圖4是改進算法的框架示意圖：圖4 改進算法流程圖Fig4 The flowchart of improved algorithm 實例與分析模擬退火蟻群混合算法已被應用于TSP、車間調度問題和機器人路徑規(guī)劃問題等[1821]。本文算法的最優(yōu)解平均為15438，某次優(yōu)化的最優(yōu)路徑及各代平均距離、最短距離見圖5和圖6。它實現了智能車輛的導航功能，是任務規(guī)劃中最為基礎也是最為重要的部分，本章的核心任務是對單車輛路徑規(guī)劃問題進行研究（后面提到的路徑規(guī)劃問題均為單車輛路徑規(guī)劃問題）。這些算法都取得了一些較好的實驗結果，本章將對蟻群算法進行改進引入夾角這一因素來解決路徑規(guī)劃問題。問題中要求每個城市必須且只經過一次，為了避免重復我們需要建立禁忌表來記下螞蟻已經走過的道路，以加快搜索速度節(jié)約時間，但是，在解決路徑規(guī)劃問題中，需要找到從起始點到目標點的最短路徑，若是建立禁忌表，路線一旦偏離目標點，會使搜索陷入無路可走的地步，然而若是不使用禁忌表，該禁令的解除將很難制定策略，如算法復雜的問題。圖7 路徑規(guī)劃模型Fig7 Path planning model如圖7所示的路徑規(guī)劃模型，起始點和目標點是已知的，圖中的邊構造出的是所有的可行路徑，這些邊的交點就是所有的可行路徑點，現需要規(guī)劃出一條路徑使得起始點和目標點之間的距離最短。為了解決上述路徑規(guī)劃問題，我們使用蟻群算法中的基本模型蟻周系統(tǒng)（antcycle system）模型，它利用的是整體信息，解決問題的性能較好，在蟻周系統(tǒng)模型中，螞蟻在路徑到上釋放的信息素濃度為，且 (13)式中為啟發(fā)信息的相對重要性，即相對程度；為常數；為螞蟻所走的從起始點到目標點的路徑總長度。那么所選擇的路線為，事實上，這條路線已經是最短路徑。蟻群算法的原啟發(fā)式信息，表示示到的可見度，現加入夾角啟發(fā)信息后，啟發(fā)信息計算式修改為： (15)其中，為所有與當前路徑點之間有路徑線段相連接的路徑點所組成的集合，為該集合中的元素個數。 改進后的算法流程以上分別對路徑規(guī)劃問題和夾角優(yōu)化的蟻群算法進行了描述，本節(jié)將給出夾角優(yōu)化的蟻群算法求解路徑規(guī)劃問題的具體算法過程。 60, 80,80。 165,180)，障礙物4的3個頂點坐標分別為(120,40。圖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)化蟻群算法路程進化圖。針對這兩方面的改進，文章中也分別給出了實例分析模擬仿真，都取得了很好的結果。在此向許老師致以崇高的敬意和衷心的感謝!感謝許老師在這幾年的學習工作中對我的辛勤培養(yǎng)、殷切教誨和無私的關心幫助。在撰寫論文期間，還得到了許多同學無私的幫助。作者簡介及讀研期間主要科研成果作者簡介及讀研期間主要科研成果1. 作者簡介弓英瑛，女，河南鄭州人，1988年3月生。2. 讀研期間發(fā)表的論文及科研獲獎情況弓英瑛, 許峰. 基于目標函數梯度的模擬退火蟻群算法[J].軟件導刊,2013,12(12):6163.2012年12月獲第九屆“華為杯”全國研究生數學建模競賽三等獎.