最優(yōu)化方法與設計報告

1、基于ACO的旅行商問題研究110《最優(yōu)化方法與設計》實驗報告基于基于ACO的旅行商問題研究的旅行商問題研究陳航航(09212688)計算機技術Email:chhangh@TelNo.:13660371747摘要摘要本實驗參考前人的經(jīng)驗把已有的改進模型整合在一起在基本的AS算法上作了以下幾方面的改進:添加了每次迭代最優(yōu)解的全局更新(即ACS)強化了正反饋的過程使用了蟻恒模型計算信息素增量對信息素進行上下界限制以避免算法過早收斂于局部最優(yōu)解

2、.最后還添加了基于路徑信源的信息素擴散模型.本文對基于路徑信源的信息素擴散模型是否有效抱有懷疑態(tài)度于是本實驗重點比較添加與沒添加基于路徑信源的信息素擴散模型對實驗結果的影響.結果表明沒添加該模型的算法結果比添加了的要好這個模型并不適用于本算法其效果還有待證明.關鍵字關鍵字蟻群算法蟻恒模型上下界限制信息素擴散模型1意義和目標意義和目標對于蟻群算法的研究主要集中在兩個方面問題的求解：靜態(tài)組合優(yōu)化問題和動態(tài)組合優(yōu)化問題.靜態(tài)組合優(yōu)化問題包括旅

3、行商問題(TSP)、二次分配問題(QAP)、車間調(diào)度問題、車輛路徑問題、車輛路由問題等它指的是在解決問題的時候該問題的拓撲分布和轉換開銷不會發(fā)生變化.例如：經(jīng)典的TSP問題其城市的位置和城市間的距離在算法運行的時候是不會發(fā)生變化的.與此不同在動態(tài)組合優(yōu)化問題的求解過程中該問題的拓撲分布或轉換開銷可能會發(fā)生改變.ACO最初的應用就是用于TSP而近年ACO在組合優(yōu)化問題方面的研究及應用都有了非常大的進步但仍處在高速發(fā)展階段.本文選擇TSP這

4、一典型問題有一定的研究意義.本文將介紹蟻群算法現(xiàn)今的發(fā)展動態(tài)研究現(xiàn)有算法的優(yōu)缺點爭取在前人的基礎上做出算法改進以得到較好的結果.基于ACO的旅行商問題研究310而也能改善整個群體的性能減少計算時間.2001年韓國學者LeeSG等人提出了一種新的改進的信息素更新策略[4]:其一局部信息素修改時揮發(fā)系數(shù)動態(tài)改變其二全局信息素更新時則將螞蟻所走路的較短的那些路徑上的信息加強而較差的那些路徑上的信息減弱.與此同時國內(nèi)學者吳斌、史忠植首先在蟻群算

5、法的基礎上提出了基于MMAS的相遇算法MMMAS(MeetingMaxMinAntSystem)[6]提高了蟻群算法螞蟻一次周游的質量然后將相遇算法與采用并行策略的分段算法相結合提出一種基于蟻群算法的TSP問題分段求解算法實驗結果表明該算法有較好的有效性.后來魏平等人通過對目標函數(shù)的自動適應來調(diào)整螞蟻的路徑搜索行為同時通過路徑選擇過程中的多樣性來保證得到更多的搜索空間以快速找到函數(shù)的全局最優(yōu)解從而提出了一種求解函數(shù)優(yōu)化的蟻群算法[7].

6、朱慶保、楊志軍等人基于最近鄰居選擇、動態(tài)信息素更新和變異策略的高速收斂算法簡稱NDMACO算法[8].該算法以最近的鄰居節(jié)點選擇和動態(tài)信息更新策略來加速全局收斂以一種獨特的變異策略來加快局部尋優(yōu)使收斂速度大幅度地提高.2009年冀俊忠等基于事例的類似思想提出一種快速求解TSP的蟻群算法PIPDMACO[9]使收斂速度有顯著的提高.此算法提出一種新的信息素增量模型以體現(xiàn)螞蟻在不同路徑上行走時所產(chǎn)生的信息量差異同時以經(jīng)過的路徑作為信息素擴散

7、濃度場的信源改善了信息素擴散模型最后采用較低復雜度的變異策略對迭代的結果進行優(yōu)化以加快可行解的搜索.3算法理論分析算法理論分析本實驗采用基本的蟻群系統(tǒng)[10]模型借鑒前人的經(jīng)驗在基本模型上做出幾方面的修改.3.1蟻群算法求解蟻群算法求解TSP問題的基本模型問題的基本模型TSP問題的目標是極小化城市間的距離.設n是TSP規(guī)模也就是城市數(shù)目m是蟻群中螞蟻的總數(shù)目aij是城市i和城市j之間的路徑dij表示相應的歐氏距離而是路徑aij的啟發(fā)信息