求解兩類組合優(yōu)化問題的改進(jìn)蟻群算法.pdf

1、組合優(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

2、.將算法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)

3、，定義了一種象限鄰居候選表，并設(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ì)了一種基于度的禁忌表，并提出了