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

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

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

3、SP問題與遺傳算法做了比較,充分體現(xiàn)了蟻群算法在此類問題上的優(yōu)勢(shì)。(2)應(yīng)用蟻群算法求解一類有約束整數(shù)規(guī)劃問題算例,并且就該非線性整數(shù)規(guī)劃算例中參數(shù)的選擇進(jìn)行了詳盡的比較,得到了解決該算例的最優(yōu)參數(shù)選擇。在此過程中,既考慮了算法的全局性,又考慮到了算法的收斂速度,并且針對(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ù)模擬問題應(yīng)用蟻群算法進(jìn)行建模以及算法流程設(shè)計(jì),給出了蟻群算法在這個(gè)問題上

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