最優(yōu)化方法與設(shè)計(jì)報(bào)告

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

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

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

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

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

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

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