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

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

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

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

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

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