多目標(biāo)進化算法在通信網(wǎng)絡(luò)中的應(yīng)用研究

湖北工業(yè)大學(xué) 黃偉

多目標(biāo)進化算法在通信網(wǎng)絡(luò)中的應(yīng)用研究

湖北工業(yè)大學(xué) 黃偉

進化算法的出現(xiàn)提供了新的復(fù)雜問題求解的新思路，正是因為進化算法的智能型、通用性和穩(wěn)健性、本質(zhì)并行性，最重要的是進化算法的全局搜索能力，進化算法已經(jīng)在很多領(lǐng)域上得到了廣泛的應(yīng)用。本文從生物個體與環(huán)境、個體與個體之間的競爭與協(xié)作關(guān)系出發(fā)，首先針對無約束多目標(biāo)優(yōu)化問題提出了相應(yīng)的進化模型與算法，然后分析了已有多目標(biāo)進化算法的收斂性。給出了衡量不同算法性能的定量性能指標(biāo)。

進化算法；通信網(wǎng)絡(luò)

多目標(biāo)進化算法[1][2][3]對于科學(xué)家和工程師來說是一個非常重要的研究課題，因為在現(xiàn)實問題中大多都具備多目標(biāo)的特征，通常來說是很難處理的，過去在運籌學(xué)、決策學(xué)和計算機科學(xué)等學(xué)科中涌現(xiàn)出很多確定型或者隨機化的方法，專門用于求解多個目標(biāo)的優(yōu)化問題，現(xiàn)代計算機設(shè)備的能力急劇提高。需要高計算速度和大內(nèi)存的隨機化搜索算法越來越受到青睞，模擬進化算法就是其中一種重要的隨機化算法，這種算法被證明為不僅可以很好地處理復(fù)雜的單目標(biāo)問題，而且也非常適合于解決多目標(biāo)問題。

所謂的目標(biāo)優(yōu)化問題一般地就是指通過一定的優(yōu)化算法獲得目標(biāo)函數(shù)的最優(yōu)化解。當(dāng)優(yōu)化的目標(biāo)函數(shù)為一個時稱之為單目標(biāo)優(yōu)化 (Single-objective Optimization Problem,SOP)。當(dāng)優(yōu)化的目標(biāo)函數(shù)有2個或2個以上時稱為多目標(biāo)優(yōu)化 (Multi-objective Optimization Problem,MOP)。不同于單目標(biāo)優(yōu)化的解為有限解，多目標(biāo)優(yōu)化的解通常是一組均衡解。顯而易見，多目標(biāo)優(yōu)化問題比單目標(biāo)優(yōu)化問題更接近工程實踐，同時更加復(fù)雜。很多工程實踐中的優(yōu)化問題最后都可以轉(zhuǎn)化為多目標(biāo)優(yōu)化問題。因此，對多目標(biāo)優(yōu)化問題的深入研究對于實踐應(yīng)用更具價值。

生物界中的螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物（pheromone）—信息素，使得一定范圍內(nèi)的其他螞蟻能夠覺察并影響其行為。當(dāng)某些路徑上走過的螞蟻越來越多時，留下的這種信息素也越多，以致后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的吸引強度，蟻群就是靠著這種內(nèi)部的生物協(xié)同機制逐漸形成一條它們自己事先并未意識到的最短路線。蟻群算法從這種模型中得到啟示并用于解決優(yōu)化問題。蟻群算法每個優(yōu)化問題的解都是搜索空間中的一只螞蟻，螞蟻都有一個由被優(yōu)化函數(shù)決定的適應(yīng)度值（與要釋放的信息素成正比），螞蟻就是根據(jù)它周圍的信息素的多少決定它們移動的方向，同時螞蟻也在走過的路上釋放信息素，以便影響別的螞蟻。

在該算法中，可行解經(jīng)過多次迭代后，最終將以最大的概率逼近問題的最優(yōu)解。它不僅利用了正反饋原理、在一定程度上可以加快進化過程，而且是一種本質(zhì)并行的算法，不同個體之間不斷進行信息的交流和傳遞，從而能夠相互協(xié)作，有利于發(fā)現(xiàn)較好解。

但是蟻群算法作為一種新興的算法，還存在一定的缺陷，如：該算法需要較長的搜索時間，由于蟻群中各個個體的運動是隨機的，雖然通過信息交換能夠向著最優(yōu)解優(yōu)化，但是當(dāng)群體規(guī)模較大時，很難在較短的時間內(nèi)從大量雜亂無章的路徑中找出一條較好的路徑。而且在搜索到一定程度后，該算法容易出現(xiàn)停滯現(xiàn)象。

[1]戴汝為.從基于邏輯的人工智能到社會智能的發(fā)展[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2006，3(2):24—25.

[2]Hackwood S，Beni G．Self-organization of Sensors for Swam Intelligence[A]．Robotics And Automation，1992 Proceedings，1992 IEEE Intemationalconferenceon[C].Piseataway，NJ:IEEEPress.1992，(1):819-829．

[3]Bonabeau E，DorigoM，Theraulaz G．Swarm Intelligence:From Natural to ArtifieialSystems[M]．NewYork:Oxford University Press.1999:10-27．

2017-10-10）