多目标进化算法在通信网络中的应用研究

湖北工业大学 黄伟

多目标进化算法在通信网络中的应用研究

湖北工业大学 黄伟

进化算法的出现提供了新的复杂问题求解的新思路，正是因为进化算法的智能型、通用性和稳健性、本质并行性，最重要的是进化算法的全局搜索能力，进化算法已经在很多领域上得到了广泛的应用。本文从生物个体与环境、个体与个体之间的竞争与协作关系出发，首先针对无约束多目标优化问题提出了相应的进化模型与算法，然后分析了已有多目标进化算法的收敛性。给出了衡量不同算法性能的定量性能指标。

进化算法；通信网络

多目标进化算法[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）