蟻群算法在組合優(yōu)化問(wèn)題中的若干應(yīng)用及其收斂性研究.pdf

1、意大利學(xué)者Dorigo M.,Maniezzo V.和Colorni A.于1992年通過(guò)模擬蟻群覓食行為提出了一種基于種群的模擬進(jìn)化算法—蟻群優(yōu)化(ACO)。該算法的出現(xiàn)引起了學(xué)者們的極大關(guān)注,在過(guò)去短短十多年的時(shí)間里,已在組合優(yōu)化、函數(shù)優(yōu)化等領(lǐng)域以及網(wǎng)絡(luò)路由、數(shù)據(jù)挖掘、機(jī)器人路徑規(guī)劃等工程問(wèn)題上獲得了廣泛的應(yīng)用,并取得了良好的效果。
　　本論文圍繞蟻群算法的理論及其應(yīng)用,就如何解決旅行商TSP問(wèn)題、一類組合優(yōu)化問(wèn)題、股票指數(shù)模

2、擬問(wèn)題、電網(wǎng)規(guī)劃問(wèn)題以及用有限馬爾可夫吸收鏈理論在蟻群算法的收斂性問(wèn)題上進(jìn)行了較為深入、系統(tǒng)的研究。
　　本文的主要研究成果包括:(1)應(yīng)用蟻群算法求解旅行商問(wèn)題(TSP)算例。蟻群算法提出的初衷就是解決旅行商問(wèn)題。螞蟻在進(jìn)行最優(yōu)化求解時(shí)在經(jīng)過(guò)的路徑上留下了信息素,以此引導(dǎo)搜索方向。本文對(duì)該算例中蟻群算法的參數(shù)的合理選取進(jìn)行了實(shí)驗(yàn)分析,并且給出了解決該TSP算例最優(yōu)的參數(shù)選擇以及不同參數(shù)下解用MFC語(yǔ)言變成的圖示。并且選取了一例T

3、SP問(wèn)題與遺傳算法做了比較,充分體現(xiàn)了蟻群算法在此類問(wèn)題上的優(yōu)勢(shì)。(2)應(yīng)用蟻群算法求解一類有約束整數(shù)規(guī)劃問(wèn)題算例,并且就該非線性整數(shù)規(guī)劃算例中參數(shù)的選擇進(jìn)行了詳盡的比較,得到了解決該算例的最優(yōu)參數(shù)選擇。在此過(guò)程中,既考慮了算法的全局性,又考慮到了算法的收斂速度,并且針對(duì)以上兩個(gè)標(biāo)準(zhǔn)制定了相應(yīng)的參數(shù)進(jìn)行了對(duì)比。由此可以建立對(duì)該算法優(yōu)劣的一個(gè)評(píng)判標(biāo)準(zhǔn)。(3)對(duì)股票指數(shù)模擬問(wèn)題應(yīng)用蟻群算法進(jìn)行建模以及算法流程設(shè)計(jì),給出了蟻群算法在這個(gè)問(wèn)題上

4、應(yīng)用的基本思路,通過(guò)對(duì)這個(gè)典型應(yīng)用問(wèn)題的建模,可以把蟻群算法推廣到其他類似的問(wèn)題當(dāng)中。(4)對(duì)電網(wǎng)規(guī)劃問(wèn)題應(yīng)用蟻群算法進(jìn)行建模,建立基本的程序流程,并且對(duì)一實(shí)際算例用C++實(shí)現(xiàn)軟件上求解,得到通過(guò)蟻群算法求解該類問(wèn)題的方法,并且通過(guò)實(shí)際算例證實(shí)算法的有效性,通過(guò)對(duì)這個(gè)典型應(yīng)用問(wèn)題的建模和求解,可以把蟻群算法推廣到其他類似的問(wèn)題當(dāng)中。(5)應(yīng)用有限馬爾可夫吸收鏈理論對(duì)蟻群算法在解決組合優(yōu)化問(wèn)題時(shí)的收斂性進(jìn)行證明。首先證明此時(shí)蟻群算法的模型