蟻群算法理論、應(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)化、網(wǎng)絡(luò)路由、函數(shù)優(yōu)化、數(shù)據(jù)挖掘、機(jī)器人路徑規(guī)劃等領(lǐng)域獲得了廣泛的應(yīng)用，并取得了較好的效果。 本論文圍繞蟻群算法的理論及其應(yīng)用，就如何解決非線性整數(shù)規(guī)劃問題、連續(xù)性優(yōu)化問題、聚類問題、與其它算法混合以及

2、收斂性進(jìn)行了較為深入、系統(tǒng)的研究。本文的主要研究成果包括： （1）提出了一種新的蟻群算法來求解無約束的整數(shù)規(guī)劃問題。螞蟻在整數(shù)空間內(nèi)運(yùn)動，同時(shí)在路徑上留下激素，以此引導(dǎo)搜索方向。對蟻群算法參數(shù)的合理選取進(jìn)行了實(shí)驗(yàn)分析，給出了算法參數(shù)選取的基本原則。數(shù)值試驗(yàn)計(jì)算結(jié)果表明該方法比較有效，并具有通用性。對幾個(gè)典型的整數(shù)規(guī)劃問題，如武器-目標(biāo)分配、多處理機(jī)調(diào)度、可靠性優(yōu)化等問題，根據(jù)各問題的特點(diǎn)，采用了不完全相同方法，并與其他方法作了比

3、較，效果比較有效。提出了一種求解旅行商問題的多樣信息素的蟻群算法。根據(jù)蟻群算法信息素更新的特性，把蟻群的三種不同的信息素更新方式混合在一起，既利用了局部信息，又考慮了整體信息，將局部搜索和全局搜索相結(jié)合，使收斂性得到提高。旅行商問題的仿真實(shí)驗(yàn)結(jié)果表明了該混合算法的有效性。提出一種解決連續(xù)優(yōu)化問題的蟻群算法。把連續(xù)解空間分成若干空間網(wǎng)格點(diǎn)，采用蟻群算法找出信息量大的空間網(wǎng)格點(diǎn)，縮小變量范圍，繼續(xù)找出信息量大的空間網(wǎng)格點(diǎn)，直到網(wǎng)格的間距小于

4、預(yù)先給定的精度。 （2）對模式識別中典型問題-聚類問題進(jìn)行了研究，提出了兩種求解聚類問題的蟻群算法。一種方法是模擬螞蟻尋食過程，螞蟻在模式樣本到聚類中心的路徑上留下外激素，外激素引導(dǎo)聚類過程；另一種是與K-均值算法混合，利用K-均值方法的結(jié)果作為初值，根據(jù)分類結(jié)果更新信息素。測試數(shù)據(jù)顯示與K-均值算法混合的算法效果相當(dāng)好。 （3）提出了與模擬退火算法混合的兩種算法。一種是在模擬退火算法中運(yùn)用蟻群算法思想找鄰域的解，稱為蟻

5、群模擬退火算法，并用該算法解決圓排列問題；另一種是由模擬退火算法生成初始信息素分布，然后由蟻群算法根據(jù)累計(jì)更新的信息素找出若干組解后，再經(jīng)過模擬退火算法在鄰域內(nèi)找另外一個(gè)解的操作，得到更有效的解，稱為模擬退火蟻群算法，并用該算法解決旅行商問題。 （4）根據(jù)蟻群算法與遺傳算法的特性，提出了與遺傳算法混合的蟻群算法。由遺傳算法生成初始信息素分布，在螞蟻算法尋優(yōu)中，采用遺傳算法的交叉和變異的策略，得到更有效的解。 （5）利用混

6、沌運(yùn)動的遍歷性、隨機(jī)性和規(guī)律性等特點(diǎn)，提出了一種求解旅行商問題的混沌蟻群（CACO）算法。該算法的思想是采用混沌初始化進(jìn)行改善個(gè)體質(zhì)量和利用混沌擾動避免搜索過程陷入局部極值。與模擬退火算法、標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，仿真結(jié)果表明該方法是一種簡單有效的算法。 （6）對群智能算法中另一種算法－粒子群算法進(jìn)行了研究，提出了模擬退火思想的粒子群算法來解連續(xù)性優(yōu)化問題，經(jīng)過與基本粒子群算法比較測試，證實(shí)它是一種簡單有效的算法。提出了混沌粒子群

7、優(yōu)化算法連續(xù)性優(yōu)化問題，典型復(fù)雜函數(shù)優(yōu)化仿真結(jié)果表明該方法是一種有效的算法。提出了一種結(jié)合遺傳算法的思想的混合粒子群算法來解決背包問題，對于目前還沒有好的解法的組合優(yōu)化問題，很容易地修改此算法就可解決。根據(jù)蟻群算法與粒子群優(yōu)化（PSO）算法的特性，提出了兩種混合算法。一種是結(jié)合遺傳算法、蟻群算法和模擬退火算法的思想提出混合粒子群算法。用該算法求解著名的旅行商問題，被證實(shí)是一種比較有效的方法。另一種是粒子群－蟻群算法，首先隨機(jī)產(chǎn)生若干組比