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

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

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

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

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