自適應(yīng)的并行蟻群算法及其應(yīng)用.pdf

1、蟻群算法是一種新型的求解復(fù)雜優(yōu)化問(wèn)題的模擬進(jìn)化算法，它是由意大利學(xué)者M(jìn).Dorigo等人受到自然界中真實(shí)蟻群集體行為的啟發(fā)而首先提出來(lái)的。大量實(shí)驗(yàn)結(jié)果表明，它在解決許多組合優(yōu)化問(wèn)題時(shí)都能表現(xiàn)出較好的求解能力，經(jīng)過(guò)了許多國(guó)內(nèi)外學(xué)者不斷地對(duì)其進(jìn)行擴(kuò)展和改進(jìn)，蟻群算法正經(jīng)歷著一個(gè)不斷發(fā)展和完善的過(guò)程。 大量模擬實(shí)驗(yàn)表明，對(duì)于中小規(guī)模的應(yīng)用問(wèn)題，蟻群算法一般能夠在許可的時(shí)間范圍內(nèi)獲得滿意解，而對(duì)于大規(guī)?；虺笠?guī)模的求解任務(wù)，簡(jiǎn)單的串行蟻

2、群算法則力不從心。另外，簡(jiǎn)單串行蟻群算法在應(yīng)用過(guò)程中一個(gè)比較突出的問(wèn)題是它容易產(chǎn)生早熟現(xiàn)象，這主要是因?yàn)樵谒阉鞒跗冢姸辔浵亗€(gè)體的運(yùn)動(dòng)較為隨機(jī)，所以螞蟻很難在較短時(shí)間內(nèi)從復(fù)雜無(wú)章的路徑中找出一條較好的路徑。但是如果一味加快收斂速度容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度后，所有個(gè)體所發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步地搜索。這些缺點(diǎn)將嚴(yán)重地影響蟻群算法的應(yīng)用。因此，人們利用蟻群算法固有的并行特性，將并行技術(shù)與傳統(tǒng)的蟻群算法相結(jié)合，從而來(lái)

3、提高蟻群算法的效率和減少蟻群算法早熟現(xiàn)象的發(fā)生。 本文在分析蟻群算法的原理及性能的基礎(chǔ)上，指出了影響并行蟻群算法性能的關(guān)鍵因素為：確定信息交流的對(duì)象、交流的內(nèi)容和交流周期，給出了優(yōu)化這三個(gè)因素的具體策略，在此基礎(chǔ)上提出了自適應(yīng)的并行蟻群算法。在確定信息交流對(duì)象方面，為了克服傳統(tǒng)并行蟻群算法中處理機(jī)無(wú)規(guī)律地選擇信息交流對(duì)象的缺點(diǎn)，提出了基于適應(yīng)度排序、基于子種群的收斂系數(shù)等策略。在信息交流內(nèi)容方面，提出了新的交流策略，使得處理機(jī)之

4、間除了交流局部最優(yōu)解之外，可以交流具有較高信息素的超頂點(diǎn)，還可以交流信息素矩陣，以利用子群體上信息素的正負(fù)反饋?zhàn)饔脕?lái)改變子群體的進(jìn)化環(huán)境。在確定信息交流周期方面，提出了根據(jù)解的多樣性和收斂系數(shù)來(lái)自適應(yīng)地調(diào)節(jié)信息交流周期的策略，以增強(qiáng)算法的搜索能力。這些不同的信息交流策略將形成不同的并行策略，從而得到不同的并行蟻群算法。本文將這些自適應(yīng)的并行蟻群算法應(yīng)用于頻率分配問(wèn)題、二次分配問(wèn)題、旅行商問(wèn)題；并采用MPI綁定C語(yǔ)言進(jìn)行編程，對(duì)實(shí)驗(yàn)得到的