多目標進化算法在通信網絡中的應用研究

湖北工業大學 黃偉

多目標進化算法在通信網絡中的應用研究

湖北工業大學 黃偉

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

進化算法；通信網絡

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

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

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

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

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

[1]戴汝為.從基于邏輯的人工智能到社會智能的發展[J].復雜系統與復雜性科學，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）