化学反应优化CRO算法综述.doc

化学反应优化算法综述杨振，周辉（南通大学 电子信息学院，江苏 南通226019）摘要：讨论化学反应优化算法的开发与应用。首先阐述2010年以来的化学反应优化算法的开发过程；其次根据已有的研究结果对其参数设置进行系统分析，并讨论算法中的能量守恒定律和四个初等反应常用的操作算子，针对不同问题提出了各种改进方法，此外介绍了一些常用的测试函数并与其他现有算法进行比较；最后介绍了CRO算法的应用领域，并给出进一步可能的研究方向。关键词：进化算法；化学反应优化；初等反应；中央能量缓冲器；能量守恒定律中图分类号： TP301.6 文献标识号： AA review of chemical reaction optimization algorithmYANG Zhen, ZHOU Hui(School of Electronics and Information, Nantong University, Nantong 226019, China)Abstract: The developments and applications of chemical reaction optimization (CRO) algorithm are discussed. Firstly, developments in the chemical reaction optimization algorithm since 2010 are reviewed; Then the parameter Settings are analyzed systematically according to the existing research results, the energy conservation principle and the operators of four elementary reactions which the algorithm used commonly are discussed , and some improvement methods of different problems are proposed, In addition, some common test functions and the comparisons between CRO and others existing evolutionary algorithms are introduced; Finally, the applications of CRO are introduced and the further possible research directions are reviewed.Key words: avolutionary algorithm; chemical reaction optimization(CRO);elementary reactions ；the central energy buffer；energy conservation principle0 引言化学反应优化算法(Chemical Reaction Optimization,简称CRO)是由Albert Y.S. Lam和Victor O.K. Li于2010年开发的一种新型演化计算技术，灵感来源于大自然中的化学反应。它模拟化学反应中分子间的相互作用以寻求最小系统势能的过程。在短短几年里，CRO已经成功地解决许多复杂问题，并且在许多测试函数中性能优于已知的其他优化算法。目前人们对CRO的研究已由单一的二次分配领域渗透到多个应用领域；由解决低维单目标问题发展到解决高维动态组合问题；由刚开始的离散域范围拓展到连续域范围，使得这种新兴的启发式优化算法展现出优异的发展，并已成为可与遗传算法、蚁群算法相媲美的智能优化算法。本文首先介绍了CRO算法的基本原理和标准版本，然后讨论化学反应优化算法的发展以及应用状况，并与其它进化算法进行比较，最后对该算法存在的不足及未来可能的研究方向进行展望。1 算法原理CRO算法与其他进化算法相似，也是基于群体的。一般来说，化学反应只需遵循两个热力学定律以及四种初等反应。在化学反应的持续过程中，反应物经过过渡状态总是会转变成系统势能最小的更稳定的生成物。 由此可见，化学反应优化就是使系统势能达到最小的优化过程。CRO是一个多代理算法，操作代理是分子。每个分子都有CRO必需的几个属性，包括（a）分子结构（），（b）势能（PE），以及（c）动能（KE）。其中PE=f（w）。其余属性取决于使用者和利用算法构建的变异CRO。在已发表的大多数CRO变异体中，有些可选属性也是适用的，比如，（d）碰撞次数（NumHit），（e）最小结构（MinStruct），（f）最小势能（MinPE），（g）最小碰撞次数（MinHit）。1.1 能量守恒定律CRO的基本原理是能量守恒定律，把所有涉及的分子和连着buffer的一个有限空间称作完备系统。系统的总能量由初始种群大小PopSize，初始动能值InitialKE及初始中央能量缓冲器buffer决定，即 （1）其中， 分别表示在时间t时，分子i的势能，动能，种群大小，中央缓冲能量。C是常量。k，l分别表示反应前后的种群大小，分别表示反应前的分子和反应后生成的分子，则必须满足下列能量守恒条件，初等反应才能发生。即 （2）从理论上讲，能量达到负值的任何操作都是不可行的。若一些实际问题的函数值可能涉及到负值（负PE），就要把此类问题等价转换成函数值为正的问题。1.2 四个初等反应化学变化是由碰撞引发的，存在两种碰撞类型：分子内部碰撞和分子间碰撞，因此存在四种初等反应：单分子无效碰撞，分解，分子间无效碰撞和合成。单分子无效碰撞指单个分子在独立空间内进行碰撞，在这个碰撞中，只有分子结构发生微小变化为，即 。N(.)是任意邻域搜索算子，就有=N()和=f（）。能量守恒条件为 （3）分解指单个分子在独立空间内进行碰撞，在这个碰撞中，分子分解成多个部分（考虑分解成两个部分），即。当时，分解才是有效反应。另外，由于分解的复杂性，使用buffer 获取，设 ，相互独立且， 。此时 （4）分子间无效碰撞指多个分子相互碰撞后相互作用，反应分子数不改变（假设两个分子）。即 。，。能量守恒条件为 （5）合成是与分解对应的，指多个分子（这里假设两个）相互碰撞，最后融合在一起的过程，即。能量守恒条件为 （6）CRO是一种松散耦合的化学反应的优化技术，它并不试图捕捉每一个化学反应的细节。根据分子结构，分子动能、势能、以及对中心能量缓冲器的设置，Lam和Li对CRO的结构进行了系统的开发和探索，形成CRO的标准版本1。CRO的流程图如图1所示。图1 CRO的流程图2 CRO算法的参数分析2.1 算法参数CRO参数包括种群规模PopSize，分子数目设置常数MoleColl，动能损失率常数KELossRate，初始动能值InitialKE，初始中央缓冲能量器buffer，分解与合成常数和。（1）种群规模PopSizeCRO是一个种群可变的优化技术。种群规模PopSize在不同迭代中可能是不同的。当单分子或分子间无效碰撞发生时，分子数目前后不变；而当发生分解和合成反应时，分子数量分别增加和减小，使用分解与合成常数和控制频率。（2）权重因子在CRO中有四个权重因子：分子数目设置常数MoleColl，动能损失率常数KELossRate，分解与合成常数和。MoleColl决定参与初等反应的分子数量，用于选择初等反应类型。KELossRate表示单分子碰撞时动能损失下限，0KELossRate1，且aKELossRate,1。常数和决定其分解与合成准则，分解准则为：NumHit MinHit (7)当满足（7）式，发生分解反应，否则，发生单分子无效碰撞。合成准则为： （8）当满足（8）式，发生合成反应，否则，发生分子间无效碰撞。2.2 参数设置根据推导6,7，一般设置参数PopSize = 10，KELossRate = 0.2，MoleColl = 0.2， InitialKE =1000 =500， = 10 和buffer = 0。初等反应中产生的新分子需要判断是否为可行解，为此，我们提供三种方法来处理约束条件：1. 设计一个总是映射到可行解区域的操作算子。2. 允许操作算子产生不可行解，但在每次迭代的最后，我们要设置一种修正机制来将任意不可行解转变成可行解。3. 允许没有任何修正机制的不可行解，但在目标函数上对不可行解实施一种惩罚机制。更多处理约束条件的技术参考4 。 3 CRO算法的操作算子3.1 两两交换两两交换也称为双交换或段位移3，是组合问题中的邻域搜索算子，应用在单分子无效碰撞和分子间无效碰撞中。考虑解形式是n维向量的问题，即。从中随机抽取两个不同元素，交换位置即得到 。3.2 高斯突变 高斯突变是连续问题的邻域搜索算子，也应用在单分子无效碰撞和分子间无效碰撞中。考虑连续解空间的问题，即，；。首先设是均值为0，方差为的高斯概率密度函数是一个随机变量。取其值为，则有。这时，新解的值为： (9)3.3 1/2变化1/2变化是分解的一种操作算子，具体操作方式如下：假设分解的两个新解为和。对于，首先复制中元素到中，然后从中随机选择n/2个元素，对选择的每一个元素都根据问题约束条件来重新配置一个新值。例如，假设问题规定只能够从集合中取值，则就只能从中随机选择一个元素。假设是连续集合，可以对增加一个随机摄动，就如上一部分讲到的高斯突变中给赋值一样。的操作方式同上。由于和中元素都是随机选取且随机赋值，每次分解反应的和都是不同的。3.4 概率选择概率选择是合成的一种操作算子，具体操作方式如下：由和合成所得，中每一个元素都是等概率的从中随机选取。表1 CRO算法与其他三种算法结果比较实 问题 最优 迭代例 尺寸 解 次数FANTISAMin. Max. Mean StdDev Min. Max. Mean StdDevnug21 21 2438 150 000 (2438) 2464 2444.44 8.03 (2438) 2462 2445.72 9.42nug24 24 3488 150 000 (3488) 3546 3500.40 13.69 (3488) (3526) 3498.40 13.07nug25 25 3744 150 000 (3744) 3772 3750.36 7.50 3744) 3768 (3746.96) 5.36nug27 27 5234 150 000 (5234) 5324 (5249.52) 24.87 (5234) 5314 5259.04 31.47nug28 28 5166 150 000 (5166) 5266 5203.24 24.99 (5166) 5278 (5201.28) 30.17nug30 30 6124 150 000 6128 6210 6158.56 23.00 (6124) 6214 (6146.96) 22.08kra32 32 88 700 150 000 (88 700) 91 490 90 373.80 746.27 (88 700) 93 060 90 664.6 1085.55wil50 50 48 816 150 000 48 964 49 254 49 098.72 71.41 (48 844) 49 296 (48 937.12) (96.30)wil100 100 273 038 150 000 274 800 (275 980) 275 436.48 (279.92) (273 816) 276 034 (274 683.32) 525.24实 问题 最优 迭代例 尺寸 解 次数TABUCROMin. Max. Mean StdDevMin. Max. Mean StdDevnug21 21 2438 150 000 (2438) 2484 2452.28 10.63 (2438) (2456) (2443.64) (5.39)nug24 24 3488 150 000 (3488) 3554 3503.20 15.74 (3488) (3526) (3494.88) (10.21)nug25 25 3744 150 000 (3744) 3788 3751.76 10.84 (3744) (3760) 3749.68 (4.19)nug27 27 5234 150 000 (5234) 5382 5285.56 40.33 (5234) (5298) 5259.36 (18.92)nug28 28 5166 150 000 (5166) 5282 5219.76 35.68 (5166) (5238) 5202.52 (18.24)nug30 30 6124 150 000 (6124) 6234 6175.28 25.93 6128 (6206) 6170.12 (19.48)kra32 32 88 700 150 000 (88 700) 94 430 91 714.60 1344.64 (88 700) (91 260) (90 190.80) (635.02)wil50 50 48 816 150 000 48 996 49 828 49 343.88 232.61 48 918 (49 214) 49 071.12 68.26wil100 100 273 038 150 000 280 634 283 190 281 779.56 596.49 274 618 276 278 275 291.16 345.024 与其他进化算法比较CRO中能量守恒类似于GA的自然选择，能量在分子间的交换和能量从一种形式转换到另一种形式组成了其算法规则。根据能量守恒定律，我们使用随机序列来产生初始解决方案。两个无效碰撞实现本地搜索，同时分解和合成实现多样化。一个适当的本地搜索和多样化组合进行有效搜索并获得最优解。从广义上说，CRO是一个算法框架，这里只定义通用的操作代理（分子）和能量管理方案，允许对某些实现细节进行调整已适应问题的特点。根据用户需求，CRO具有很强的灵活性。CRO还吸取模因算法（MA）和模拟退火算法（SA）中的有效技术。CRO中的基本单元是分子，每个分子都有其某些属性，如势能、动能、分子结构等，因此可以很容易的用C+和JAVA来编写CRO程序。用类来描述分子属性及用方法描述初等反应。在分子初始化和分解时，创建此类的一个新对象。在分子发生合成反应时，摧毁一个相应对象。CRO的并行化也很容易实现。当解决一个问题需要实现多个CROs时，不需要强调CROs间的高度同步。与其他算法相比，CRO没有定义迭代次数，且每次迭代只涉及分子的一个子集。每个CRO行为运行不需要另一个的完成。CRO的并行化操作参考文献9。针对二次分配问题，把CRO算法与其他三种算法比较，充分说明了CRO算法的有效性能。如表1所示。（表中带括号的数据表示已知的最优解）由表可知，对于各个基准函数，与FANT，ISA，TABU算法相比，CRO算法大都能够快速的达到目前已知的最优解，而且具有很好的收敛性。总的来说，CRO算法有以下有利因素：CRO算法是一个设计框架，允许设置不同参数来适应相应的问题。种群可变性使系统更加自主的适应相应问题。能量的转换和转变使得CRO更有潜力解决那些现今还没有解决的问题。其他特有属性也可以很容易的纳入分子中，这使设计更加灵活。CRO算法还具有SA和GA的优点。CRO算法可以很容易进行编程。用类定义一个分子，方法定义四种基本反应。因为种群的可变性以及不需要同步计算，CRO的并行化也容易修改和实现。5 CRO算法的应用5.1 用于离散优化问题的算法基本CRO版本最先适用于离散优化问题，并依次产生了许多高级版本。与许多现有的进化算法相比，CRO表现出很强的竞争性甚至更优越的性能。5.1.1 二次分配问题二次分配问题是运筹学中的基本组合问题，指根据分配设施位置的不同，最小化所花费的运输总成本。在6，13中，Lam和Li提出了带有同步通信策略的CRO算法。在许多测试实例中，与原始版本的CRO和一些变异进化算法相比，此版本CRO表现出了更优越的性能。与之前的CRO版本相比，其计算时间和并行实现的质量都有明显改善。5.1.2 资源受限项目调度问题RCPSP问题是研究具有优先关系约束活动的项目在资源受限的条件下使某些管理目标最优的调度问题。本章的RCPSP在操作上涉及到项目管理，资源分配和家具制造过程7。在大多数基准问题实例中，CRO都可以实现已知的全局最小值。5.1.3 无线网状网络中的信道分配问题 无线网状网络是由无线路由器与无线接入点通过多跳链接的方式组成，是一种无线终端接入internet的交友竞争力的解决方案。信道分配问题要求分配给路由器的信道不能超过接口设置规定的数量。这是一个NP-hard组合问题，CRO可以提高现有解决方案的性能6。 5.1.4 认知无线电频谱分配问题 认知无线电的频谱分配是一个复杂的最优化问题,需要在最大化频谱利用率的同时考虑干扰的最小化和接入的公平性。CRO显示出超过其他现有方法的性能8。5.1.5 网格任务调度问题网格任务调度是指将n个相互独立的任务分配到m个异构的可用资源上，使得总任务的完成时间最少以及资源得到充分地利用。Lam和Li根据不同的解形式和初等反应的优先级，提出了几种变异的CRO版本10,11。在大多数测试实例中，CRO优于现有的许多进化算法。5.1.6 股票投资选择问题投资股票的选择，顾名思义就是为了在金融投资中减少风险。总是存在一个权衡：最小风险以及最大回报。股票投资选择的研究就是基于这两个相互矛盾的目标构建一个有效地投资组合。这是一个多目标NP-hard问题。文献12中，Lam和Li提出基于Markowitz模型与Sharpe 比率的CRO来解决此问题。5.1.7 人工神经网络训练人工神经网络是一种模仿生物神经网络结构和功能的计算模型。神经网络有大量人工神经元联结进行计算，能在外界信息的基础上改变内部结构，是一种自适应系统。为了模拟一个神经网络系统，需要一组用于训练的数据发展网络结构和优化权重。文献15中，CRO用于训练神经网络，取得了较好的测试误差率。5.1.8 网络编码优化问题网络编码是Ahlswede等人在2000年提出的一种网络数据传输方式，基本思想是允许网络中间节点参与编码。在传统路由网络中，网络节点只执行数据导入存储于转发。而网络编码可以显著改善网络性能，如提升网络吞吐量、节约宽带资源、均衡网络负载、增强网络路版型和安全性等，但也增加了编码的操作成本。网络编码优化问题就是在保持一定传输速率基础上，最小化编码链接数量。这也是一个NP-hard问题。在文献9中，CRO显示出超越现有进化算法的性能。5.2 用于连续优化问题的算法Lam和Li等人于2012年又提出用于解决连续优化问题的CRO算法7，即RCCRO。并根据不同邻域搜索算子和操作算子提出RCCRO1，RCCRO2，RCCRO3，RCCRO4。与许多现有进化算法CEP、FES、RCBBO相比， RCCRO版本在测试标准基准问题14（高维单目标问题、高维多目标问题和低维多目标函数）上显示了优异性能。文献7中还提出一种改变步长的自适应CRO方案。CRO算法 与其他进化算法一样, 能用于求解离散域与连续域中的大多数优化问题。在这些领域中, 最具潜力的有系统设计、多目标优化、模式识别、信号处理、人工神经网络、决策制定、模拟和证明等。还包括路由选择19、调度问题18、旅行商问题16和图像分割17等。6 CRO算法研究展望（1）算法理论基础研究：与相对鲜明的生物社会特性基础相比, CRO 的数学基础显得相对薄弱, 缺乏深刻且具有普遍意义的理论分析。因此,数学基础的研究非常重要, 包括对不同搜索问题的收敛性、收敛速度估计、预防陷入局部最优值和参数设置影响等。（2）应用领域的拓展：CRO虽已经被成功地应用于离散与连续领域22中，但更多领域的应用报道不多，还处于研究阶段。从应用广度和深度上拓展CRO是很有价值的工作。（3）算法的参数确定：CRO中一些参数如，步长以及迭代次数等往往依赖于具体问题，需要根据应用经验，经多次测试去确定，并不具有通用性。因此，对参数自适应的CRO算法是当前迫切需要研究的问题。（4）算法的改进研究：由于实际问题的多样性与复杂性，现已出现的许多改进的算法远不能满足应用需要。研究新的改进算法用以解决实际问题也是很有意义的。就目前来看，将CRO与其他进化算法如ACO、FES,PSO20,21等相结合，根据不同问题提出相应的改进算法是CRO的热点。对以上问题的研究必会促进CRO算法理论和应用的发展，CRO算法也定将会在智能设计领域中有一席之地，有着更大的发展前景。参考文献1 Lam AYS, Li VOK .Chemical-reaction-inspired metaheuristic for optimizationJ. IEEE Trans Evol Comput ,2010,14(3):381399.2 Cela E .The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers, Dordrecht, The Netherlands,1998.3 Demeulemeester EL, Herroelen WS .Project scheduling: aresearch handbook. Academic Publishers, Boston, MA, USA,2002.4 Eiben AE . Evolutionary algorithms and constraint satisfaction: definitions , survey, methodology, and research directions. Theoretical aspects of evolutionary computingJ. Springer, London, 2001,pp 1330.5 Lam AYS, Li VOK () Chemical-reaction-inspired metaheuristic for optimizationJ. IEEE Trans Evol Comput,2010,14(3):381399.6 Lam AYS, Xu J, Li VOK. Chemical reaction optimization for population transition in peer-to-peer live streaming. In: Proceedings of the IEEE congress on evolutionary computation. Barcelona, Spain,2010.7 Lam AYS, Li VOK, Yu JJQ . Real-coded chemical reaction optimization. IEEE Trans Evol Comput,2012,16(3):339-353.8 Lam AYS, Li VOK .Chemical reaction optimization for cognitive radio spectrum allocation. In: Proceedings of the IEEE Global Communications Conference. Miami, FL, USA,2010.9 Pan B, Lam AYS, Li VOK. Network coding optimization based on chemical reaction optimization. In: Proceedings of the IEEE global communications conference. Houston, TX, USA,2011.10 Xu J, Lam AYS, Li VOK.Chemical reaction optimization for the grid scheduling problem. In: Proceedings of the IEEE international conference on communications. Cape Town, South Africa,2010.11 Xu J, Lam AYS, Li VOK .Chemical reaction optimization for task scheduling in grid computingJ. IEEE Trans Parallel Distrib Syst, 2011,22(10):16241631.12 Xu J, Lam AYS, Li VOK . Stock portfolio selection using chemical reaction optimization. In: Proceedings of the international conference on operations research and financial eng