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

1、組合優(yōu)化是優(yōu)化領(lǐng)域中的一個重要分支，具有非常強的實際應用背景。從螞蟻群體尋找最短路徑的行為受到啟發(fā)，意大利學者Dorigo等人1991年提出一種模擬蟻群行為的啟發(fā)式優(yōu)化算法——蟻群算法。在過去十多年的時間里，它已經(jīng)成功地用于求解旅行商問題(TSP)等多種組合優(yōu)化問題。 本文首先概述了組合優(yōu)化問題及其復雜性理論，接著圍繞蟻群算法的原理、理論及其應用，就如何改進基本蟻群算法，進行了較為深入的研究。本文的主要研究成果包括： 1

2、.將算法ACObs,τmin的收斂性定理進行推廣，給出了蟻群系統(tǒng)(ACS)的收斂性證明。對ACS進行分析，總結(jié)出三種改進策略：候選集策略，局部搜索，信息素分布初始化策略。最后分析了三種策略對ACS收斂性的影響。 2.提出了三種求解TSP的改進算法：①基于受限制候選表的蟻群系統(tǒng)。該算法將一種新型的候選表RCL引入ACS中，可以隨機調(diào)整RCL的大小，避免了多次實驗設(shè)置候選表；②基于TSP幾何結(jié)構(gòu)的蟻群系統(tǒng)。該算法根據(jù)TSP的幾何結(jié)構(gòu)

3、，定義了一種象限鄰居候選表，并設(shè)計出一種對偶象限鄰居的方法得到初始路徑，用來設(shè)置初始階段的信息素軌跡；③基于最小1-樹動態(tài)候選集的蟻群系統(tǒng)。該算法將最小1-樹的概念引入蟻群算法中，定義了α-動態(tài)候選集。在MATLAB環(huán)境下進行仿真實驗，結(jié)果表明三種算法都優(yōu)于基本ACS，在三種算法中，算法2好于其它算法。 3.提出了一種求解度限制最小生成樹(DCMST)問題的改進算法。該算法針對DCMST的特點，設(shè)計了一種基于度的禁忌表，并提出了