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

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

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

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

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

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

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

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

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

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

[1]戴汝為.從基于邏輯的人工智能到社會(huì)智能的發(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）