基于聚集密度的约束多目标进化算法

张丽丽，许　峰

(安徽理工大学理学院，安徽　淮南　232001)



基于聚集密度的约束多目标进化算法

张丽丽，许峰

(安徽理工大学理学院，安徽淮南232001)

摘要：对基于群体聚类的约束多目标进化算法进行了改进，引入了聚集密度以度量群体中个体间的关系，保持种群的多样性。其基本思想为：首先将初始群体按多判据聚类方法分为适应度值不同的四类，然后计算类内群体中个体的聚集密度，根据适应度值和聚集密度定义一个偏序集，最后采用比例选择原则依次从偏序集中选择个体，更新精英集。通过数值实验用量化指标研究了改进算法的收敛性和分布性，结果表明：改进算法的收敛性与常规约束多目标进化算法相当，但分布性有了明显的提高。

关键词：约束多目标进化算法；种群聚类；聚集密度；分布性

约束多目标优化问题的关键是对约束条件的处理，目前已有一些典型的带约束多目标进化算法和约束处理机制：文献[1]提出的COMOGA算法，将向量评估遗传算法和Pareto排序分级的方法结合起来处理约束问题。文献[2]提出的约束VEGA，将群体划分成几个子群体来处理。文献[3]提出的约束MOGA，将基于Pareto优胜的选择方案用来处理遗传算法中的约束方程。文献[4]提出了一种基于群体分类的复杂约束多目标进化算法，根据聚类方法来处理复杂约束，算法的基本思想是：按照类内距离平方和最小，类间距离平方和最大等多种判据将种群聚类处理，再按类赋以适当的适应度值。这种算法对于处理Pareto边界比较光滑的三目标的优化问题效果较好，收敛速度较快，基本上二百代即已达到较好的优化效果，但在维持种群的多样性和分布性方面欠佳，现将此算法做了改进，在进化过程中引入聚集密度以调控种群，可以达到维持种群多样性的目的，并根据量化评价指标和数值实验结果对改进算法的性能特别是分布性进行了评测。

1多目标优化问题的相关概念

1.1多目标优化问题及其最优解

多目标优化问题可表述为[5]

(1)

式中：x为决策向量，f(x)为目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e(x)≤0确定决策向量的可行取值范围。

定义1[6]满足式(1)中的约束条件e(x)的决策向量x的集合，即

Xf={x∈X|e(x)≤0}

(2)

称为可行解集。

定义2[7]设xA，xB是两个可行解，若f(xA)≤f(xB)， 则称xA比xB优越； 若f(xA)

定义3若可行解x*满足：比x*更优越的可行解不存在，则称x*为弱Pareto最优解；

比x*优越的可行解不存在，则称x*为强Pareto最优解。

定义4Pareto最优解的集合称为Pareto最优解集或非支配解集，记为P*。

定义5Pareto最优解集P*中的所有Pareto最优解集对应的目标向量组成的曲面称为Pareto最优前沿或Pareto最优前端，记为

PF*{f(x*)=(f1(x*)，f2(x*)，…，

fm(x*))T|

x*∈P*}

(3)

两目标优化问题的Pareto最优前沿是一条平面曲线，三目标优化问题的Pareto最优前沿则为一张空间曲面。多目标优化问题的结果习惯上多采用Pareto最优前沿表示。

1.2最优解集的评价标准

多目标优化算法性能的评价包括算法的效率和最优解集的质量。算法的效率主要指算法的复杂性即算法占用的CPU时间，而最优解集的质量包括算法的收敛性和最优解集的分布性。

评价多目标优化算法性能主要依靠量化评价标准和有代表性的测试问题。

常用的量化评价指标有：

1) 世代距离[8](GD)

(4)

式中：n为算法所得最优前端PFknown中向量个数，di为PFknown中每一维向量到最优前端PFtrue中最近向量的距离。

GD主要反映了PFknown对PFtrue的逼近程度。

2) 错误率[9](ER)

(5)

式中：n为PFknown中的向量个数，且PFknown={X1，X2，…，Xn，ei定义如下

(6)

ER描述了PFknown对PFtrue的覆盖程度，即最优解集的分布性。

3) 分散性(SP)[10]

(7)

式中：n和di同GD。

显然，SP即为di的均方差。根据方差的含义，SP反映的是最优解集的均匀性。

2基于聚集密度的约束多目标算法

上述群体分类的复杂约束多目标进化算法具有较好的收敛性，但在分布性方面存在着的一定的缺陷，原因是算法仅考虑了群体中个体的R适应度，并没有考虑群体中个体间的距离，即群体的拥挤程度，这极有可能降低种群的多样性，影响解的分布性。

在进化算法中，保持解的分布性的常用方法有：小生境技术，信息熵，聚集密度，聚类分析等[11]。

本文将聚集密度引入选择过程，改善解的多样性和分布性。

2.1聚集密度

聚集密度的概念是Deb在[12]中提出来的。聚集密度可以从个体的相似度，影响因子或者聚集距离几个方面来度量，本文选择从聚集距离角度度量。聚集密度与聚集距离成反比关系，聚集距离大的聚集密度小。一个个体的聚集距离可以通过计算其与相邻的两个个体在每个子目标上的距离差之和来求取。

如图1所示，设有两个子目标f1(x)和f2(x)，Pm[i]为个体i在子目标m上的函数值，则个体i的聚集距离P[i]d是图中四边形的长与宽之和，即

P[i]d=P1[i+1]-P1[i-1]+P2[i+1]-P2[i-1]

(8)

图1　个体间的聚集距离

当有r个子目标时，个体i的聚集距离

(9)

计算出聚集距离后，再按照个体间的聚集距离越大，则个体的聚集密度就越小的原则，即可定义个体的聚集密度。这里，为了简单起见，定义聚集密度为聚集距离的倒数。

2.2基于聚集密度的约束多目标进化算法

基于聚集密度的约束多目标进化算法的步骤如下

1) 用多判据聚类方法将整个群体分成四类，不可行群体、可行非Pareto群体、聚类Pareto群体以及聚类Pareto最优群体。分别赋以适应度：R(不可行群体)≤R(可行非Pareto群体) ≤R(聚类Pareto群体)≤R(聚类Pareto最优群体)。

2) 当迭代次数小于最大迭代次数时，构造如下偏序集：① 计算种群中个体的目标函数值；② 计算每个个体的聚集密度；③ 根据目标函数值和聚集密度定义一个偏序集，该偏序集中的元素有两个属性：个体的目标函数值和聚集距离。

3) 根据比例选择原则，依次从偏序集中选择个体。

4) 对群体进行交叉运算。

5) 对群体进行均匀变异运算。

6) 条件终止判断。不满足终止条件，则进行新一轮运算，若满足终止条件，则输出计算结果，算法结束。

算法流程图如下

图2　改进算法流程图

3数值实验与算法性能评测

下面用基于聚集密度的约束多目标进化算法对两个标准约束多目标测试函数Binh4和Viennet 4进行了优化，并将计算结果与文献[12]中的原算法的计算结果进行了比较，从而检验改进算法的性能。

1) Binh4测试函数

(10)

约束条件为

(11)

Binh4测试函数的PFlocal如图3所示。

图3　Binh4 PFtrue 图

2) Viennet4测试函数

(12)

约束条件为

(13)

Viennet4测试函数的PFlocal如图4所示。

图4　Viennet4 PFtrue 图

图5　Binh4 PFknown 图(改进算法)

图6　Binh4 PFknown 图(原算法)

图7　Viennet4 PFknown 图(改进算法)

图8　Viennet4 PFknown 图(原算法)

图5～图8分别是用改进算法和原算法求出的Binh4和Viennet4的Pareto最优边界。可以很直观地看出，改进算法在解的分布性和均匀性方面均明显优于原算法。

为了更进一步定量地评价改进算法的性能，下面给出改进算法和原算法的世代距离、错误率和分散性指标的对比数据。

考虑到计算结果的随机性，表中给出的是20次实验结果的平均值。

表1　Binh4的原算法/改进算法优化指标结果

表2　Viennet 4的原算法/改进算法优化指标结果

从表1和表2中可以很清楚地看出，原算法和改进算法的GD指标相差不大，但改进算法的ER和SP指标与原算法相比明显占优。

综合图5～图8和表1～表2，可以得出明确的结论：基于聚集密度的改进约束多目标进化算法的收敛性与原算法相当，但分布性和均匀性有了明显的提高。

4结束语

本文根据聚集密度的特点，将聚集密度引入群体聚类约束多目标进化算法，数值实验结果和量化指标表明：与原算法相比，改进算法解的分布性有了明显的提高。

由于多目标进化算法的理论基础目前还很薄弱，收敛性和分布性等关键理论问题无法从理论层次进行证明，所以算法的改进验证只能基于对比实验。

提高多目标优化算法解的分布性和均匀性的方法有多种，如小生境技术，信息熵，聚集密度，聚类分析等。本文采用的聚集密度方法与其它方法相比，优点是既能从宏观上刻画群体的多样性与分布性，也能从微观上描述个体间的内在关系，缺点是计算复杂度偏高。这完全符合优化中的“没有免费的午餐定理(No Free Lunch， NFL)”。

参考文献：

[1]SURRY P D， RADCLIFFE N J. The COMOGA Method： Constrained Optimisation by Multi-objective Genetic Algorithms[J].Control and Cybernetics，1997，26：391-412.

[2]COELLO CAC. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization[J].Engineering Optimization，2000，32：275-308.

[3]COELLO C A C.Constraint-handling using an evolutionary multi-objective optimization technique[J].Civil Engineering and Environmental System，2000，17：319-346.

[4]张丽丽， 许峰. 基于群体分类的复杂约束多目标优化遗传算法[J]. 教育技术导刊， 2009(12)：38-41.

[5]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：6.

[6]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：7.

[7]郑金华. 多目标进化算法及其应用[M].北京：科学出版社，2010：3-4.

[8]VELDHUIZEN D A， LAMONT G B. Evolutionary computation and convergence to a Pareto front[C]// In John R Koza. Late breaking papers at the genetic programming 1998 conference， Stanford University， California. Stanford Bookstore：221-228.

[9]COELLO COELLO C A. Evolutionary algorithms for solving muli-objective problems [M]. Kluwer Acedemic， 2002：14-18.

[10]E ZITZLER，K DEB，L THIELE.Comparison of multiobective eveolutionary algorithms：Empirical results[J]. Evolutionary Computation，2002，8(2)：173-195.

[11]郑金华. 多目标进化算法及其应用[M]. 北京： 科学出版社， 2007：118-124.

[12]DEB KALYANMOY， SAMIR AGRAWAL， AMRIT PRATAB, et al. Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimiztion：NSGA-II[C]//Kan GAL Report 200001.Indian Institute of Technooogy， Kanpur，India，2000.

(责任编辑：李丽)

Constrained Multi-objective Evolutionary Algorithm Based on Crowding Density

ZHANG Li-li, XU Feng

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

Abstract:The constrained multi-objective evolutionary algorithm based on group clustering was improved, and crowding-density was introduced to measure the relationship among individuals and maintain the diversity of population. The basic idea is that the initial population is divided into four groups with different fitness by multi-criterion clustering method, and the crowding-density of each group is calculated. A poset is defined according to the objective function value and crowding-density, and the individuals are selected from poset by the principle of proportion selection, then the elite set is updated. The convergence and distribution of improved algorithm were studied by means of numerical experiments, and the results showed that the convergence of improved algorithm is roughly equal to the conventional multi-objective evolutionary algorithm, but the distribution of improved algorithm is significantly improved.

Key words:constrained multi-objective evolutionary algorithm; group clustering; crowding density; distribution

收稿日期：2015-05-28

基金项目：安徽省教育厅自然科学基金资助项目(2012kb236)

作者简介：张丽丽(1979-)， 女， 安徽凤台人，讲师，硕士，研究方向：进化计算、群智能计算。

中图分类号：TP301.6

文献标志码：A

文章编号：1672-1098(2016)01-0050-06