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