解决多目标优化问题的几种进化算法的比较研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇解决多目标优化问题的几种进化算法的比较研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：进化算法具有适于解决多目标优化问题的特性，近来一直用于求解此类问题。群体智能优化算法是一种基于群体智能的进化算法，通过简单个体的交互表现出高度智能，大大增强了解决和处理优化问题的能力。分析了遗传算法、粒子群算法和混洗蛙跳算法的具体流程，比较了这三种进化算法的优劣。

关键词：进化算法；群体智能；遗传算法；粒子群算法；混洗蛙跳算法

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)07-1614-03

Solve the Multi-objective Optimization Problem of Comparative Study of Several Evolutionary Algorithm

WANG Xiao-di, XIAO Wei

(Hunan Normal University, Changsha 410081, China)

Abstract: Evolution algorithms, which preperty is resolving Mop, recently is used for solving/settling these problems. Swarm intelligence optimization algorithm is advanced algorithm based on swarm intelligence, highly enhanced the ability of resolving and handling optimization problem by showing high intelligence internal mutual reciprocity among simple individuals. We compared the advantagement and disadvantagement by analyzing detail process of GA,PSO and SFLA.

Key words: evolution algorithms; swarm intelligence; GA; PSO; SFLA

从古老的时代开始，人们就力求在解决一个问题的众多方案中寻求一种最优方案，并且一直对这一课题进行研究和探讨，这就是所谓的优化问题。研究优化问题有着很重要的意义，因为人类所有活动都是围绕“认识世界、建设世界”来进行的，认识世界需要建立模型即建模，而建设世界需要的是优化决策，所以建模与优化无处不在，始终贯穿在一切人类活动的过程之中。

但是在现实过程中，对问题的优化往往伴随着目标的约束，要求在符合一定的条件下，达到最优化的目的，并且这些优化问题通常还是多目标的，需要对多个目标同时进行优化，即通常所讲的多目标优化问题。以n个自变量和k个目标函数的多目标最大化问题为例来描述多目标约束化问题为[1]：

max f(x)={f1(x),f2(x),…,fk(x)}

S.T. e(x)={e1(x),e2(x),…,em(x)}≤0

其中，x=(x1,x2,…,xn) ∈X?奂Rn,y=(y1,y2,…,yk)∈Y?奂Rk,x表示决策向量，y表示目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e(x)≤0确定决策变量x的可行取值范围。这里假设所有的目标函数都要求最大化，如果其中某一个目标函数fi需要最小化，只要最大化（-fi）,所有的公式仍然成立。

进化算法有一些适于求解MOP的特点，包括能同时处理一组解个体，每运行一次即能获得多个有效的解个体，以及对问题均衡面的形状和连续性不敏感，即能很好地逼近非凸性或不连续的均衡面或曲线。因此，多目标的进化算法在近年来就一直用于求解MOP问题。

群体智能优化算法是一种基于群体智能的进化算法，通过模拟实际生物群体生活中个体与个体之间的相互交流与合作，用简单、有限的个体行为与智能，通过相互作用形成整个群体的整体能力。这种算法本质上是一种概率搜索，它不需要问题的梯度信息，具有较强的鲁棒性，并且，每个个体的能力或遵循的规则非常简单，群体智能的实现简单、方便，加上系统用于通信的开销少，易于扩充，能通过简单个体的交互表现出高度的智能，使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决，大大增强了人们解决和处理优化问题的能力。

1 遗传算法

遗传算法将生物遗传过程中随机配对交叉极致和进化过程中的适者生存法则相结合，通过模拟生物进化的机制和过程来搜索最优解。

遗传算法首先对解空间进行编码，每个编码对应要求解问题的一个解，然后随机选择一组解作为初始的解集，并根据指定的适应值函数计算出每个解的适应值，再按照适者生存的 原则从初始解中选出一组解按照事先设定好的交叉率和变异率进行交叉和变异操作，生成一组新解，随后再次用适应值函数计算每个解的适应值，再以此过程反复迭代，直到满足迭代停止条件。此时得到的编码经过解码就可以堪称额所求解问题的近似最优解。

由遗传算法的基本原理，可得出遗传算法具有以下几个特点：

1）以决策变量的编码为运算对象，可以直接操作结构对象；

2）不受函数约束条件的制约，由目标函数变换来的适应值函数进行搜索；

3）采取群体搜索，具有并行性，从一组解迭代到另一组解；

4）具有自组织、自适应性；

5）不依赖于问题的具体领域和类型，有很好的通用性。

这些特点使遗传算法不仅具有良好的全局搜索和优化能力，而且与其他优化算法之间有良好的兼容性。

虽然遗传算法具有很多优点，但也存在很多不足，主要缺点表现为以下几个方面[2]：

1）虽然二进制编码符合最小字符集编码规则，也便于用模式定力对算法进行分析，但对连续函数的优化问题存在映射误差，不便反应所要求问题的特定知识；

2）随机产生的初始种群无法保证种群的多样性，在求解高要求精度的问题时容易陷入局部最优；

3）由于不限制适值函数的取值范围，不能保证算法一定收敛；

4）静态设置控制参数，且参数的选取主要靠经验，不能适应环境的变化；

5）在需要优化的参数较多时，明显表现不足等。

2 粒子群算法

粒子群优化算法的提出是基于对简化的社会模型的模拟。由Eberhart和Kennedy于1995年根据鸟群捕食的行为研究所得。算法的基本原理可描述为：一个由若干粒子（Particle）组成的群体（Swarm）在D维搜索空间中以一定的速度飞行，每个粒子在搜索过程中，考虑自己搜索到的历史最好点以及群体内（或者是邻域内）其他粒子的历史最好点，并在这个基础上执行位置上（或者是粒子的状态上，也就是问题的解）的变化。设第i个粒子的位置表示为xi=(xi1,xi2,…,xid)，此粒子的速度表示为vi=(vi1,vi2,…,viD)，1≤i≤m，1≤d≤D，并且此粒子经历过的历史最好点表示为pi=(pi1,pi2,…,piD)，群体内（或邻域内）所有粒子经过的最好点为pg=(pg1,pg2,…,pgD)。一般地，粒子的位置和速度是在连续的实数空间内取值。每个粒子的速度和位置按照如下方程变化[3]：

其中，c1，c2为学习因子或者称为加速系数，一般取正常数。学习因子使粒子有自我总结和向群体中的优秀个体学习的能力，从而向自己的历史最优点以及群体或邻域内的历史最优点逼近。ξ,η∈U[0,1]，是在[0,1]区间中均匀分布的伪随机数，每个粒子的速度上限为Vmax。

为改善算法的收敛性能，Shi和Eberhart在1998年的论文中引入惯性权重这一概念，并且将速度的更新方程改为：

其中，ω为惯性权重，其大小决定了对粒子当前速度继承的多少，惯性权重选择得适当，就能使粒子具有均衡的开发能力（即局部搜索能力）和探索能力（即广域搜索能力）。特别的，当ω=1时，就是基本粒子群优化算法。

粒子群算法的优点在于收敛速度快并且容易实现，加之其需要调整的参数比较少，就可以直接采用实数编码，算法的结构也就相对简单。但是，粒子群算法的缺点也比较明显，例如其实施过程与参数的取值有较大的关系，而参数的取值仍然是一个亟待解决的问题；在解决高维复杂问题优化时，经常会陷入局部最优；或者在接近或进入全局最优点区域时的收敛速度也会比较缓慢。

3 蛙跳算法

混洗蛙跳算法是一种受自然生物模仿启示而产生的基于群体的协同搜索方法，此算法模拟青蛙群体在寻觅食物时，分成不同的族群进行思想传递的过程，将全局信息交换与局部搜索结合，局部搜索使局部的个体间信息传递，混合策略使局部见的思想得到交换[4]。

在混洗蛙跳算法中，种群由许多只结构相同的青蛙组成，每只青蛙代表一个解。整个种群分成多个子群，每一个子群包含一定数量的青蛙，称为一个memeplex，不同的memeplex使具有不同思想的青蛙的集合，分别按照一定策略在解空间中执行局部深度搜索。每一个memeplex中，每只青蛙都有自己的思想，并且受其他青蛙思想的影响，通过memetic进化来发展，在经过定义的局部搜索迭代次数结束后，思想在混合过程中进行交换。这样，经过一定的memetic进化以及跳跃混合过程，这些想法就在各个memeplex中传播开来，然后，局部搜索和混合跳跃过程一直持续到满足了定义的收敛条件为止。局部深度搜索和全局跳跃交换的平衡策略使算法能跳出局部极值点，向全局最优的方向进化，这也是混洗蛙跳算法的主要特点[5]。

蛙跳算法的流程具体为：

① 始化种群。在可行解空间Ω?奂Rd中，随机生成初始种群F包含k=m*n只青蛙，其中，m表示memeplex的数量即子种群的数量，n为每个memeplex中青蛙的只数，d是维变量。每一只青蛙代表青蛙的当前位置，在应用于解决优化问题时表示解空间中的一个候选解，则第i只青蛙表示为F(i)=(F1i,F2i,…,Fdi)，设F(i)的适应值用fi表示。

②将所有青蛙排序。将整个种群中的k只青蛙按照指定的适应值的降序排序，生成组数X={F(i),fi;i=1,2,…,k}，其中，F(i)表示排在第i位的那只青蛙，因此，当i=1时，表示这只青蛙的位置最好。

③将青蛙分组。将整个种群分成m个memeplex：Y1，Y2，…，Ym，每一个memeplex包含有n只青蛙，可将其表示为：其总，k=1,2,…,m，也就是第1只青蛙进入memeplex1，第2只青蛙进入memeplex2，直到第m只青蛙进入memeplex m，然后第m+1只青蛙又进入memeplex1，第m+2只青蛙进入memeplex2，直到第2m只青蛙进入memeplex m，并且依此类推，直到所有青蛙分配完毕。

④在每一个memeplex中做memetic进化。在每个memeplex中，每只青蛙都受到其他青蛙思想的影响，通过memetic进化，每只青蛙都向目标位置靠近，具体memetic进化步骤如下：

a) 设im=0，0≤im≤m，表示memeplex的计数

iN=0，0≤iN≤N，表示进化的迭代次数，N为设定的最大迭代次数

用Pg表示整个种群中位置最好的青蛙，显然，Pg就是F(1)，并且，在每组memeplex中，用Pb表示本组中位置最好的青蛙，用Pw表示本组中位置最坏的青蛙，在每一次进化中，改善最坏位置青蛙Pw的位置

b) im=im+1

c) iN=iN+1

d) 设青蛙移动的距离为diN+1=rand()*(pb-pw)，则青蛙的新位置为：

其中，rand()是介于0与1之间的一个随机数。Dmax是允许青蛙移动的最大距离，当diN+1>Dmax时取Dmax，当diN+1

e) 若上述过程能使原位置最坏的青蛙达到一个好的位置，即能产生一个更好的解，就用新位置上的青蛙取代原来的青蛙，否则，用Pg代替Pb重复上述过程。

f) 若用Pg代替Pb重复上述过程仍不能生成更好的青蛙，就随机生成一个新位置的青蛙取代原最坏位置的青蛙Pw。

g) 若iN

h) 若im

⑤将青蛙混合，也就是使青蛙在各memeplex间跳跃。在每个memeplex都执行了一定的memetic进化后，将各子群Y1，Y2，…，Ym重新合并为X，即X={Yk,k=1,2,…,m}，然后将X更新按适应值的降序排序，并且及时更新整个种群中最好的青蛙Pg。

⑥若达到迭代的终止条件，则停止迭代，否则跳转至步骤③。一般来说，当循环进化到一定次数后，代表最好解的青蛙就不再改变了，这个时候，算法停止，有时，也可以通过设定最大迭代进化次数来作为终止条件。

与其他的进化算法相近，混洗蛙跳算法是一种基于群体智能的后启发式计算技术，结合了模因演化算法和粒子群算法这二者的长处[6]，并且概念简单容易理解，参数少，全局搜索能力比较强，在最初应用于水资源网络的分配问题时，产生了较好的效果。但是，对于一些复杂的问题这个算法依然存在着收敛速度不是很快、易于陷入局部极值的缺点,并且传统的蛙跳算法模型适合于解决连续优化问题,不适合解决离散的组合优化问题。

4 总结与展望

以上就是对遗传算法、粒子群算法这两种典型群体智能优化方法以及蛙跳算法这种新兴的群体智能优化方法简单的研究，通过对比可以看出，每种算法都有自己独特的优点和缺点，但是面对高维的复杂问题的时候都表现出容易陷入局优、不能保证很好的收敛。

其实，除了上述几种优化方法，还有很多的群体智能优化方法如蚁群算法、鱼群算法等等，我们可以对这些算法进行更加深入的研究，利用各算法的优点，将其结合起来，对某种算法进行改进，取长补短，就可以更好地解决多目标优化问题。

参考文献：

[1] 谢承旺,丁立新.多目标进化算法中选择策略的研究[J].计算机科学,2009,36(9):167-170.

[2] 徐波.遗传算法及其在数据挖掘中的应用[J].电脑编程技巧与维护,2010,(4):9-11.

[3] 汪定伟,王俊伟.智能优化方法[M].北京:高等教育出版社,2007.

[4] EUSUFF M M,LANSEY K E.Water distribution network design using the shuffled frog leaping algorithm[A].World Water Congress[C].2001.

[5] 栾琛.混洗蛙跳算法研究及其发展现状[J].大众科技,2009(1):25-26.

[6] 栾琛,盛建伦.基于粒子群算法的混洗蛙跳算法[J].计算机与现代化,2009(11):39-41.