英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

关于多目标优化的一种高效化学反应优化算法

Slim Bechikh, Abir Chaabani, and Lamjed Ben Said

摘要——最近，一种叫做化学反应优化算法的新式元启发式优化算法被提了出来。这种受由粒子碰撞产生的化学反应启发的搜索算法，继承了若干其他启发式演算法诸如模拟退火算法和粒子群算法的特点。这让化学反应优化算法成为如今解决单目标优化问题的最有力的搜索算法之一。在本文中，我们提出对于多目标优化的化学反应优化算法的一种变种，通过将化学反应优化算法与涉及多个相互矛盾标准的阻尼问题相结合，得到了非支配排序化学反应优化算法。由于我们的方法是基于非支配排序，本文的贡献之一是提出一种新的准线性的平均时间复杂度的快速非支配排序算法;也因此让我们的多目标算法从编程角度来讲变的非常有效率。同时通过基准问题的试验将该算法与其他的多目标算法进行了比较，在经历了多种困难环境的测试后，该算法在提供Pareto前沿的有效覆盖和充分多元化逼近方面展现出了很强的有效性和效率。

关键词：化学反应优化算法，进化计算，多目标优化，非支配排序

1．介绍

大多数的现实中的优化问题实际上有一个多目标性。它们通常包含几个相互矛盾的不可通约的项目，在一定的约束下进行最大或者最小化。一个多目标优化的分辨率问题（MOP）会引起一组折衷的解决方案和不同的目标之间的最佳权衡。当把它们放在目标空间，该组折衷的解决方案就是所谓的帕累托最优前沿。一些方法在专门的文献中被提出，它们近似提出对于离散情况和帕累托最优前沿持续不断的工作成果[51]。通过模仿生物的进化原则，进化算法（EAs）在这过去几十年中通过解决MOPs积累了不小的人气，而这些都得益于：1）他们能提供一套折衷解作为单一的模拟运行解决方案的输出2）是它们对目标的几何特征功能，如非凸性，不连续性，搜索空间的不均匀性等的不敏感性[51]。其结果是多目标进化算法(MOEAs)解决MOPs问题方面，在优化研究领域的一个新的分支的出现。这个分支被称为进化多目标优化算法（EMO），并且能称得上在研究领域计算机科学是最有吸引力和活跃的算法之一。一些量身定做的分配计划在EMO文献中被提出。这些方案可作如下划分为三个类。

A．Pareto基于排名的方案

这些计划在选择规则的设计方面直接使用了Pareto 支配关系[4]，这允许区分不同群落中的个体。首先使用Pareto支配关系并成功地生成一组非支配点是丰塞卡及菲林明[4]。他们的算法被称为多目标遗传算法（MOGA），该算法还曾短暂的被Pareto托遗传算法（NPGA）所改进过，该算法由Horn等提出通过。 [7]。无论是MOGA算法还是NPGA算法都已经在适应度赋值方面显示成效，并且这样的分配方案的效率被一些更先进的多目标进化算法的那在这些早期的设计中进一步改善。一些最值得注意他们都是非支配排序遗传算法（NSGA）[8]，NSGA-Ⅱ[9]这是前者的改进版本，强化版Pareto EA（SPEA）[10]，它的改进版SPEA2 [11]，和Pareto信封选择算法[12]。

B．基于指标方案

最近，在2004年，Zitzler和Kuuml;nzli[13]提出基础上，采用了基于Pareto性能指标优势关系新的适应值分配模式。最常用的指标是超体积[14]，ε指示符​​和R2 one[15]。其基本思想是在以下方面进行评估个体在质量指标方面的损失，如果个别个体从群体被删除。因此，解决方案具有最小损失并不再强调留在循环中为下一代;然而，有大面积亏损的解决方案是匹配选择和环境的重要考量之一。一些有代表性的算法属于这一类中有基于指标的EA（IBEA）[16]，S-度量选择EMO算法[20]，R2 EMO（R2EMOA）算法[21]，和逼近引导EMO（AGE）算法[43]。

C. 基于分解方案
基于分解算法将MOP分解为若干即时标量优化子问题。每个子问题仅是通过优化利用与其相邻的子问题的信息而进行更新。该被引用最多的算法属于本族内的多目标遗传局部搜索[19]，NSGA-III（一个多目标基于NSGA-II的优化方法）[5]，[6]和基于MOEA（MOEA / D）的分解[20]，[27]，[29]。事实上，分解似乎是一个有趣的方法，它能够解决许多多目标问题的，因为它不仅单一考虑到一个改进基于另一个改进的进化，而且它能够全局考虑所有的改进。

化学反应具有几个特点，高效原料，状态，进程，并且有可以作为优化手段的项目。最近，一个新启发式算法的化学反应优化算法（CRO）由林和李[22]提出。提出了第一个版本是关于解决组合问题的。在这之后，它随后衍生出了第二个关于连续性问题的版本[23]。还有其他从化学反应工程中找到灵感的文字记录。我们提到例如启发式计算基础算法，由阿拉斯塔提出的人工化学反应的优化算法全局优化（ACRO）[44]。事实上，CRO算法已经证明其有效性和效率，在解决现实世界中的单目标基准问题时[24]，[25]。该CRO算法有几个不错的功能（见第II-B）该共通启发式演算法渲染单目标时非常出色。出于这个原因，我们推荐第一种多目标CRO算法，同时尝试利用好的CRO算法的特性去解决MOPs。该文献的主要贡献有以下几种。

(1)第一次提出一种多目标优化的CRO算法，我们也叫做非支配序列CRO算法（NCRO）,用以解决MOPs问题。

(2)提出一种新的非支配排序算法（NDSA），称为快速NDSA（Q-NDSA）具有一个准线性平均时间复杂度，使用线性数据结构，而不是非线性。
(3)试验显示，我们的NCRO算法相较其他的MOEAs算法具有较低的平局时间复杂度。
(4)证明了我们的NCRO算法能够跑赢一些最有代表性的多目标进化算法如NSGA-II，IBEA，MOEA/ D和AGE在,处理不同的的基准问题如Laumanns-Zitzler（DTLZ）系列和WALKING FISH GROUP（WFG）的时候。

2. 相关的工作

A．多目标优化

一个MOP包含的一个对象载体在一定的限制条件下最大或者最小化条件的过程，MOP的一般形式如下：

这里M是目标函数的数量，P为不等式约束数量，Q是等式约束数量，和分别对应变量的上确界和下确界。满足（P Q）的限制条件的解，除了满足限定的上下界约束（1）之外，就称之为可行的，集中的所有可行解的解空间用X表示。在这样的假设下，我们考虑一个最小化的MOP，因为最大化可轻松转化为最小化的基础上的对偶原理。MOP的进化产生一组折中的解决方案，即所谓的Pareto最优的解决方案或者非支配解，这组解中的目标空间的图像被称为帕累托最优前沿。因此，一个MOP的分辨率近似等于整个帕累托前沿。在下面，我们给多目标优化一些相关的背景定义。

定义1：（Pareto最优）如果一个最优解x *是帕累托最优化，且不存在任意xX。因此对所有的mI 都有I = {1，2，hellip;，m}。 在帕累托最优状态的定义中，是帕累托最优，如果没有可行的矢量X的存在，其中这个X矢量能改善同时避免对象载体的恶化。其他与帕累托最优相关联的定义如下。

定义2：（Pareto支配）一个解集u=（，，...，）据说是支配另一解集v =（，，...，）用f（u）小于等于F（u）表示，当且仅当f（u）的是部分比F（v）小。换句话说，misin;{1，hellip;，m}，我们有（u）le;（v）和m{1，hellip;，m}其中（u）lt;（v）中。

定义3：（Pareto最优集）对于MOP f（x）中，帕累托最优集是P * = {xXX，f（）f（x）}。在经典的多目标优化的文献中，这一套被称为有效集。

定义4（Pareto最优前端）。对于给定的MOP f(x)其帕累托最优集P *，帕累托最优前端PF* = {f（x）中，xP *}。多目标优化在运营研究方面已经得到相当的重视 [26]。传统的方法是通过MOP与SOP来解决多目标优化改造问题。一些聚焦方法已经在一些文章中被提出了。例如，加权求和法，ε-约束法，基准方向法，光束搜索法，等等（详见[3]）。这些方法的主要问题是他们需要由主观决策来调整几个参数，这不是一项容易的任务。另外，这些方法依赖的几何特征目标函数而且每次模拟运行它们只可以提供一个解。由于其人口为基础的性质，在两个过去的几十年，多目标进化算法已被证明是有效的黑箱工具来处理多目标优化（详见[28]查看最新的详细调查）。

B． CRO：基本算法和功能

CRO是一个新的最近提出启发式算法[22]。它是受到化学反应的热力学第一定律启发。 CRO包含一群粒子群通过四个化学反应装置：1）贴壁无效碰撞; 2）分解; 3）分子无效碰撞;和4）合成。因此，同样地遗传算法（GA），分子相对应的个体和化学反应对应于不断变化的母体。然而，CRO由操作者区分变化的事实和环境。不同的是，GA产生后代人口然后使后者与母体之间的竞争人群中，CRO一旦产生后代，它的竞争对手为实现在与其父（S）生存相应的化学反应。类似于其他进化算法或共通启发式演算法，CRO包括三个阶段：1）初始化; 2）迭代;和3）最后阶段。第一个首先初始化的不同参数
这是如下。
(1)PopSize：分子的人口规模。
(2)KELossRate：动能（KE）的损失率
(3)MoleColl：一个决定化学反应是单分子的或者是多分子反应，为0或1。
(4)缓冲液：缓冲区的初始能量。
(5)InitialKE：初始KE能量。
(6)alpha;和beta;：两个参数控制激化和多样化。
有关这些参数的作用的更多详细信息，有兴趣的读者可以去阅读[23]和[30]。一旦初始化集被执行时，分子集合的创建和演化过程就开始了。后者是根据以下四个变化运算符（基本化学反应）。
(1)贴壁无效碰撞：这种反应会对分子与墙壁进行碰撞，然后反弹离开剩余在一个单个单元。在这种碰撞中，我们只扰乱现有的分子结构omega;到。这可以通过任何做邻里运营商N（bull;）。
(2)分解：它对应于一种情况，此时分子撞墙，然后分解成若干部分（为简单起见，我们考虑两个部分在本文中）。任何可以从W产生与的机制都是被允许的，分解反应的目的是允许算法在足够多次无效碰撞的本地搜索之后去探索解空间的源头。
(3)分子间无效碰撞：这种反应发生的条件是当多个分子相互碰撞其他的粒子然后反弹了。分子（假设二）碰撞前后保持不变。这个初级反应与单分子无效反应是非常相似的，因为我们从和产生了和，使得和= N（）和= N（）。该反应的目的是同时探索每个分子之间的反应。
(4)合成：该反应是分解的相反情况。当综合情况发生时，多个（假设二个）分子相互碰撞并彼此融合在一起。 我们获得从和的融合产生的。任何容许分子合成的解决方案都是被允许的，其中所得分子是在远离现有解空间的源头中的。

该CRO机制是基于能量分布的原则的，因此，分子会产生能量的改变或者是分子之间的碰撞。一个分子可以集中在容器的壁或者是​碰撞彼此。这是通过随机数t决定的，t 的范围是[0，1]。若tgt; MoleColl或者是系统只有一个分子，我们就有单向分子碰撞。否则，就是分子之间的碰撞了。这两个无效碰撞实施的是地方搜索（强化），在分解与合成的过程中产生多样化的效果。两个碰撞前的分子在潜在能量层上产生新的分子结构（PES）（即他们选择接近原始方案的新的解）。因此，所得到的分子的能量往往接近那些原有的能量阶段。相反，分解和合成倾向​​于获得新的分子结构，可能的原因的反应的能量层级已经脱离了原来的。这样使得开发的过程获得了良好的平衡和探索。之后，它输出的总体化学过程中发现的最佳解决方案的处理方案。值得注意的是，合成操作是降低人口规模很重要的操作之一。反之，分解反应则会增加人口。在CRO中分子有几个属性，这些对于反应都是至关重要，那就是：1）的分子结构omega;表达手头问题编码解决的解决方案; 2）势能（PE）对应于所考虑的分子的目标函数值。3）对应于该量化非负数的KE系数，该系统的接受现有方案的恶化方案的接受程度[类似于模拟退火（SA）]。该可选属性如下。

(1)点击数（NumHit）:分子之间的碰撞次数。

(2)最小结构（MinStruct）：这是具有最小结构的omega;对应的PE势能，分子已经达到最稳定的状态。后一个分子经历若干碰撞，它经历了许多结构的变革，具有不同的相应的最小势能PE。 MinStruct是在最低势能PE参与其他反应的结构。该属性在粒子群优化方面是一个非常好的概念（PSO）。

(3)最小的PE（MinPE）：当分子达到其MinStruct，MinPE是其对应的PE。

(4)最低命中数（MinHit）：它是命中数当一个分子实现MinStruct。它是一个抽象的当到达MinStruct时的时间符号。欲了解更多有关每个属性和作用的详细信息，该请读者参考[22]。

该CRO最近已成功地应用于不同的组合和持续优化问题[31] - [33]。对于CRO几个不错的性能是一个很好的检测。这些属性如下。

(1)CRO框架允许不同的部署操作，以适应不同的问题。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[145949]，资料为PDF文档或Word文档，PDF文档可免费转换为Word