蟻群算法與其他算法的混合.pdf

1、自從上世紀(jì)50年代中期創(chuàng)立仿生學(xué)以來，人們不斷地從生物進(jìn)化的機(jī)理中得到啟發(fā)，提出了許多用于解決復(fù)雜優(yōu)化問題的新方法，比如神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火算法、進(jìn)化規(guī)劃等，并成功應(yīng)用于解決實(shí)際問題。由意大利學(xué)者M(jìn).Dorigo，Vmaniezzo，A.Colorni于1992年首先提出的蟻群系統(tǒng)(Ant ColonySystem，ACS)，是一種新穎的仿生進(jìn)化算法，適用于求解復(fù)雜組合優(yōu)化問題。目前，蟻群系統(tǒng)己成功應(yīng)用于求解旅行商問題(TSP)

2、、二次分配問題和job-shop調(diào)度問題等，取得了很好的實(shí)驗(yàn)效果。受其影響，蟻群系統(tǒng)的研究已經(jīng)逐漸引起了更多學(xué)者和專家的關(guān)注。雖然，該研究方法處于研究的初級(jí)階段，但是一些研究成果已經(jīng)顯示出蟻群系統(tǒng)在求解復(fù)雜優(yōu)化問題方面的優(yōu)越性。作為一種全局搜索的方法，蟻群算法具有正反饋性、并行性、分布性、自組織性等特點(diǎn)。但是，蟻群算法也存在一些不足之處:例如，算法需要較長(zhǎng)的搜索時(shí)間、容易出現(xiàn)早熟停滯現(xiàn)象等。 針對(duì)上述不足，我們?cè)谏钊胙芯肯伻核惴?/p>

3、的同時(shí)，又對(duì)免疫算法和禁忌搜索等算法進(jìn)行了一定的分析和研究，提出了幾種新的用于求解旅行商問題(TSP)的蟻群改進(jìn)算法。旨在借鑒其他仿生算法的長(zhǎng)處，利用其優(yōu)點(diǎn)彌補(bǔ)蟻群算法的不足，從而提高蟻群算法的求解性能。 本文的主要內(nèi)容包括：首先，針對(duì)蟻群算法中的個(gè)體螞蟻缺乏識(shí)別問題特征信息的能力，將免疫算法中疫苗的思想引入到蟻群算法中，新算法從TSP問題本身出發(fā)，提取出該 問題的一種本質(zhì)特征，將此特征信息作為疫苗注射給精英螞蟻，使其具有“免疫

4、”的能力，能識(shí)別該固有特征，以提高精英螞蟻的搜索質(zhì)量，從而使得整體的求解能力得以提高。其次，因?yàn)橄伻核惴ㄈ菀壮霈F(xiàn)早熟停滯，而禁忌搜索算法可以接受劣解，搜索時(shí)能跳出局部最優(yōu)解，轉(zhuǎn)向解空間的其他解，從而獲得更好的全局最優(yōu)解。故將兩種算法混合，用蟻群算法作全局搜索，禁忌搜索算法作局部搜索。從而加速收斂速度，使算法的搜索性能得以提高。最后，根據(jù)蟻群算法與遺傳算法、模擬退火算法的特性，提出了采用遺傳算法生成信息素分布，利用蟻群算法求精確解的遺傳蟻