改進(jìn)的蟻群算法求解TSP問題的研究.pdf

1、蟻群優(yōu)化算法(ant colony optimization，ACO)由意大利學(xué)者 Marco Dorigo，V Maniezzo,A. Colorni于1992年首先提出，是基于螞蟻群體覓食過程中沿著最短路徑行進(jìn)的這種生物學(xué)行為發(fā)展起來的一類群智能優(yōu)化方法。在解決傳統(tǒng)優(yōu)化方法難以奏效的具有NP-hard特性的組合優(yōu)化問題中利用該算法取得了令人鼓舞的效果，因而受到了學(xué)術(shù)界以及工業(yè)界的廣泛關(guān)注。目前，蟻群優(yōu)化算法已經(jīng)成為計(jì)算智能方法中的一

2、個(gè)重要分支，成為當(dāng)下蓬勃發(fā)展的熱點(diǎn)研究課題之一。蟻群優(yōu)化算法的理論研究相對(duì)滯后，特別是算法的參數(shù)選擇和收斂性證明方面還有待于進(jìn)一步研究。雖然，該研究方法處于研究的初級(jí)階段，但是一些研究成果已經(jīng)顯示出蟻群系統(tǒng)在求解復(fù)雜優(yōu)化問題方面的優(yōu)越性。目前，蟻群系統(tǒng)己成功應(yīng)用于求解旅行商問題(Traveling salesman problem TSP)、二次分配問題(QAP)和job-shop調(diào)度問題，取得了很好的實(shí)驗(yàn)效果。
　　TSP（Tr

3、avelling Salesman Problem）也稱作貨郎擔(dān)或巡回售貨員問題，在運(yùn)籌學(xué)、管理科學(xué)及工程實(shí)際中具有廣泛的用途。TSP問題是組合優(yōu)化中的著名難題，一直受到人們的極大關(guān)注。由于其NP難題性質(zhì)，至今尚未完全解決。
　　本文的主要工作如下：
　　1.對(duì)蟻群算法的基本理論以及在TSP問題中的應(yīng)用進(jìn)行了較為深入和系統(tǒng)的研究。介紹了蟻群算法的基本原理、特點(diǎn)、構(gòu)成和算法的實(shí)現(xiàn)方法。
　　2.基本蟻群算法由于存在搜索時(shí)

4、間長，易陷入局部最優(yōu)解等突出缺點(diǎn)，使得求解效果不是很好。針對(duì)這些缺陷，提出了利用改進(jìn)的蟻群算法求解TSP問題。改進(jìn)主要在參數(shù)的初始化、狀態(tài)轉(zhuǎn)移概率的選擇策略以及信息素更新方法的改進(jìn)三個(gè)方面。
　　①對(duì)于一個(gè)初始的TSP，首先考慮對(duì)其進(jìn)行預(yù)處理。在利用螞蟻算法求解問題之前，先用近鄰法構(gòu)造一個(gè)初始游歷，并計(jì)算信息素初值。
　?、诶肈origo M等提出的Ant-Q Systems算法，采用確定性和隨機(jī)性選擇相結(jié)合的選擇策略，并

5、在搜索過程中動(dòng)態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率。
　　③信息素更新采用在線單步更新信息素及離線全局更新信息素相結(jié)合的方法，即在螞蟻巡游過程中在線單步更新信息素以及在本次迭代結(jié)束時(shí)離線全局更新信息素。
　　將以上三步算法的改進(jìn)結(jié)合起來，用MATLAB模擬，選取了TSPLIB中的十個(gè)TSP問題進(jìn)行實(shí)驗(yàn)，并與用基本蟻群算法做的結(jié)果以及現(xiàn)在應(yīng)用比較廣泛的遺傳算法的結(jié)果做了比較。然后運(yùn)用改進(jìn)的蟻群算法對(duì)以中國100城市為代表的中國旅行商問題進(jìn)行了數(shù)