面向路徑規(guī)劃的多策略和變異算子蟻群算法研究.pdf

1、分類(lèi)號(hào)：密級(jí)：UDC：學(xué)號(hào)：406112212076南昌大學(xué)碩士研究生學(xué)位論文面向路徑規(guī)劃的多策略和變異算子蟻群算法研究面向路徑規(guī)劃的多策略和變異算子蟻群算法研究ResearchonCombinedMultistrategyMutationOperatbasedAntColonyAlgithmfPathPlanning霍艷麗培養(yǎng)單位（院、系）：信息工程學(xué)院計(jì)算機(jī)系指導(dǎo)教師姓名、職稱(chēng)：曾勍煒研究員指導(dǎo)教師姓名、職稱(chēng)：李向軍教授申請(qǐng)學(xué)位的學(xué)

2、科門(mén)類(lèi)：工學(xué)學(xué)科專(zhuān)業(yè)名稱(chēng)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)論文答辯日期：2015年5月26日答辯委員會(huì)主席：評(píng)閱人：2015年月日摘要I摘要摘要路徑規(guī)劃優(yōu)化方法及其應(yīng)用是人工智能領(lǐng)域備受關(guān)注的一個(gè)研究方向，基于蟻群算法研究路徑規(guī)劃是其中具有代表意義的方法之一。從不同的應(yīng)用問(wèn)題背景來(lái)看，目前已提出的基于蟻群算法的路經(jīng)規(guī)劃方法，在收斂時(shí)長(zhǎng)、個(gè)體適應(yīng)度、易陷入局部最優(yōu)解等方面還存在值得進(jìn)一步改善之處。鑒于此，本文從二維、三維路徑規(guī)劃兩個(gè)應(yīng)用角度出發(fā)，引入多策略

3、組合優(yōu)化思想和變異算子，重點(diǎn)研究了面向路徑規(guī)劃的改進(jìn)型蟻群算法。主要開(kāi)展了以下研究工作：1研究提出了面向二維路徑規(guī)劃的一種多策略組合優(yōu)化蟻群算法ACACMs(AntColonyAlgithmbasedonCombinedMultistrategy)。該算法通過(guò)信息素更新、2opt局部?jī)?yōu)化、限定信息素濃度范圍等多策略組合優(yōu)化的方法來(lái)改進(jìn)傳統(tǒng)蟻群算法，以改善傳統(tǒng)蟻群算法收斂時(shí)間慢、易陷入局部最優(yōu)解等缺陷。二維TSP（TravelingSal

4、esmanProblems）求解實(shí)例及與基本蟻群算法、基于遺傳機(jī)制蟻群算法的比對(duì)實(shí)驗(yàn)表明，ACACMs算法是有效可行的，且在收斂時(shí)間降低、搜索路徑縮短、提高最優(yōu)解質(zhì)量等方面效果良好。2研究提出了面向三維路徑規(guī)劃的一種變異算子蟻群算法ACAMO(AntColonyAlgithmbasedonMutationOperat)。該算法在改進(jìn)啟發(fā)式函數(shù)設(shè)計(jì)、選擇概率確定、信息素更新策略等基礎(chǔ)上，引入逆轉(zhuǎn)變異和插入變異算子，通過(guò)選擇逆轉(zhuǎn)點(diǎn)反序排列部

5、分路徑節(jié)點(diǎn)和隨機(jī)插入路徑節(jié)點(diǎn)的方法搜索無(wú)碰路徑，對(duì)蟻群算法進(jìn)行了局部?jī)?yōu)化改良。TSPLIB模擬數(shù)據(jù)集上的三維路徑規(guī)劃仿真實(shí)驗(yàn)表明，相比基本蟻群算法和基于遺傳機(jī)制改進(jìn)的蟻群算法，ACAMO算法在搜索路徑、收斂時(shí)間、個(gè)體適應(yīng)度等方面有明顯改善，算法是有效可行的。本文研究貢獻(xiàn)主要在于從信息素更新策略、2opt局部?jī)?yōu)化策略、限定信息素濃度范圍策略、啟發(fā)式函數(shù)設(shè)計(jì)、選擇概率確定及變異算子引入等多方面對(duì)基本蟻群算法進(jìn)行改進(jìn)，并應(yīng)用于二維和三維路徑規(guī)