蟻群算法組合優(yōu)化旅行商問題度限制最小生成樹

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-07 14:50:37   瀏覽：8864次  

摘要:組合優(yōu)化是優(yōu)化領(lǐng)域中的一個(gè)重要分支，具有非常強(qiáng)的實(shí)際應(yīng)用背景從螞蟻群體尋找最短路徑的行為受到啟發(fā)，意大利學(xué)者Dorigo等人1991年提出一種模擬蟻群行為的啟發(fā)式優(yōu)化算法——蟻群算法在過去十多年的時(shí)間里，它已經(jīng)成功地用于求解旅行商問題TSP等多種組合優(yōu)化問題 本文首先概述了組合優(yōu)化問題及其復(fù)雜性理論，接著圍繞蟻群算法的原理、理論及其應(yīng)用，就如何改進(jìn)基本蟻群算法，進(jìn)行了較為深入的研究本文的主要研究成果包括 1.將算法ACObs,τmin的收斂性定理進(jìn)行推廣，給出了蟻群系統(tǒng)ACS的收斂性證明對(duì)ACS進(jìn)行分析，總結(jié)出三種改進(jìn)策略候選集策略，局部搜索，信息素分布初始化策略最后分析了三種策略對(duì)ACS收斂性的影響 2.提出了三種求解TSP的改進(jìn)算法①基于受限制候選表的蟻群系統(tǒng)該算法將一種新型的候選表RCL引入ACS中，可以隨機(jī)調(diào)整RCL的大小，避免了多次實(shí)驗(yàn)設(shè)置候選表②基于TSP幾何結(jié)構(gòu)的蟻群系統(tǒng)該算法根據(jù)TSP的幾何結(jié)構(gòu)，定義了一種象限鄰居候選表，并設(shè)計(jì)出一種對(duì)偶象限鄰居的方法得到初始路徑，用來設(shè)置初始階段的信息素軌跡③基于最小1-樹動(dòng)態(tài)候選集的蟻群系統(tǒng)該算法將最小1-樹的概念引入蟻群算法中，定義了α-動(dòng)態(tài)候選集在MATLAB環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明三種算法都優(yōu)于基本ACS，在三種算法中，算法2好于其它算法 3.提出了一種求解度限制最小生成樹DCMST問題的改進(jìn)算法該算法針對(duì)DCMST的特點(diǎn)，設(shè)計(jì)了一種基于度的禁忌表，并提出了度信息的概念來改進(jìn)轉(zhuǎn)移概率，保證了所得解的可行性，然后使用變異思想局部優(yōu)化生成樹實(shí)驗(yàn)結(jié)果表明，這些改進(jìn)不僅提高解的質(zhì)量，而且避免了早熟收斂最后還將改進(jìn)的算法進(jìn)行適當(dāng)推廣，給出了求解多旅行商問題MTSP的具體步驟標(biāo)題:蟻群算法組合優(yōu)化旅行商問題度限制最小生成樹專業(yè):應(yīng)用數(shù)學(xué)學(xué)位:碩士單位:西安電子科技大學(xué)@關(guān)鍵詞:蟻群算法　組合優(yōu)化　旅行商問題　度限制最小生成樹　論文時(shí)間:2006分類:O224 TP301.6 導(dǎo)師:劉三陽 語種:中文文摘URL:

贊助本站