基于化学反应优化的混合元启发式算法

摘要

近年来，在工业、金融、科学研究、工程实践等领域中为了解决多目标优化问题都面临了诸多的挑战。优化问题的初衷是优化系统给用户提供相对满意的决策。通俗的讲，优化问题可以归纳为寻求目标函数最大值或最小值最优解或解集的过程。目前，有很多基于全局的优化算法，在工业工程、计算化学和数学等研究领域中都取得了很好的效果。
　　例如，大部分优化问题可以归纳为在合理的时间范围内，通过全局数值优化方法找到尽可能找到所有近似最优解。优化问题又可以分为单目标优化问题和多目标优化问题，通常单目标优化问题是追求单个目标函数的最优解。相应的，多目标优化问题是要求多个目标函数尽可能接近最优解，但是往往存在优化目标函数间冲突的现象。
　　各种元启发式算法在解决复杂优化问题上已经取得了很好的效果，这其中既有基于单目标优化又有基于多目标优化。在过去的几年中，基于种群优化的遗传算法EA取得了很大的成功。EA主要是受到物理学、生物学、化学等自然科学的启发，并解决实际的优化问题。
　　CRO优化算法是一种模拟化学反应中分子间相互作用，寻求最小系统势能以达到稳定状态的低延迟算法。CRO优化算法原理比较简单，并且不需要去理解每个步骤的具体细节。通常，CRO优化算法遵循以下两个热力学定律：
　　1.能量守恒定律：能量不能凭空产生亦不能凭空消失，它只能从一种形式转化成另一种形式。一个化学反应系统包含化学物质及其周围物质，化学物质的能量由势能和动能两部分组成，周围物质的能量可以用CRO中心缓冲器能量象征性地表示。化学反应系统从周围物质获得初始能量来启动化学反应，这是个吸热的过程。化学物质向周围物质释放能量，这是个放热的过程。这两种反应可以通过初始缓冲器来表征：当其为阳性时，反应是吸热的;当其为零时，反应是放热的。
　　2.熵增定律：系统总是朝着熵增加的趋势发展，其中熵是无序程度的量度。势能是储存在分子内部的能量，当分子内部的能量转换成其他形式能量时整个系统将会变成无序的状态。例如，当系统内部势能转化成系统动能时，分子的移动速度加快，系统将变得无序，熵随之增加。因此，几乎所有的化学反应都有系统势能下降到最小的趋势。在CRO中，通过捕捉系统势能转化成动能并且化学分子终止获取周围物质能量的现象。
　　CRO是一种多代理算法，算法的基本操作是处于分子层面。每个分子有多重属性，有些属性对于CRO算法操作起到了至关重要的作用。关键的属性包括：(a)分子结构(ω)；(b)内能(PE);(c)分子动能(KE)。剩余部分依靠于算法的运算符，以及它们为特定问题构建不同的变体，来适应不同的反应。在已发表的文章中，我们可以看到其他可选的属性：(d)碰撞数(NumHit);(e)最小PE(MinPE);(f)最小结构(MinStruct);(g)最小碰撞数(MinHit)。上述属性列表如下：
　　1）分子结构ω：代表一个问题的解，它不需要特定的存在形式：可以是一个常数、向量甚至是一个矩阵。例如，我把问题的解空间定义为五个实数组成的向量。
　　2）内能PE：定义为由分子结构ω对应的目标函数值，如果f是目标函数，则PE=f(ω)。
　　3）动能KE：一个非负数，它量化了与现有系统的容差。
　　4）碰撞次数NumHit：当分子发生碰撞时，将触发一个基本的反应，并且分子结构有可能发生改变，NunHit是记录分子总共发生碰撞的次数。
　　5）最小结构MinStruct：反应到目前为止系统中ω对应的内能PE最小。分子经过多次碰撞后，其分子结构会发生很多次变化。
　　6）最小内能MinPotentialPower：当分子到达最小结构时，其对应于最小内能。
　　7）最小碰撞次数MinHitNum：分子达到最小内能所需最小的碰撞次数。
　　CRO优化算法存在四种基本反应，CRO每次迭代时，四种反应将依次地执行：单分子无效碰撞、分子间无效碰撞、分子分解和分子合成。
　　单分子无效碰撞是指分子在化学反应时反复碰撞容器内壁，稍微改变分子结构ω，将会出现不等式PEω+KEω≥PE?。通过获取和存储KE的特定部分来更新中央能量缓冲器，分子结构更新为KE?=(PEω?PE?+KEω)×r,r是[KELossRate,1]区间内的随机数，然后利用ω或?来更新PE。
　　分子间无效碰撞是指两个或多个分子间彼此碰撞并且发生分离，当 PEω1+PEω2+KEω1+KEω2≥ PE?1+PE?2时，分子结构和中央能量缓冲器得到更新。碰撞后分子的数量保持不变，分子结构由它们邻域产生。和分子间碰撞相似，该反应也稍微改变了分子结构。
　　分子分解是指分子撞击容器内壁时分裂成两个或多个分子，这个反应模拟了本地搜索和其他区域的搜索。当PEω+KEω≥PE?1+PE?2并且能量缓冲器能量充足时，分子结构和中央能量缓冲器将改变。该反应明显改变了分子的结构。
　　分子合成是指两个或多个分子碰撞并合并成一个分子的情况。当PEω+KEω≥PE?1+PE?2时，分子结构和中央能量缓冲器将改变。该反应强烈地改变了分子的结构。
　　CRO总共分为三个基本步骤：初始化、迭代和最后一步，计算机会依次按照三个步骤执行CRO。在每一次运行中，算法从初始化开始，执行一定数量的迭代并在最终阶段终止。在初始化时定义一些初始解空间和函数，并给变量和控制变量赋予初始值。CRO是基于种群的元启发式优化算法，但是存储器中保存的解空间可能会发生改变，这可能是来自分子分解和合成操作的影响。首先，在解空间中随机初始化PopSize大小的初始种群。在迭代过程中，将进行一定次数的迭代。每次迭代中，碰撞产生一个在区间[0,1]中随机数p，如果p大于MoleColl，则本次为无效碰撞。
　　否则将会发生分子间的碰撞，我们可以发现，如果种群中只剩下一个分子，那么任何碰撞都是无效的。紧接着我们从种群中选取合适数量的分子，事实上，一个分子是否被选中很大程度上取决于分子在容器中所处的物理位置。接下来，通过分析分解和合成的标准来判断分子将发生何种类型的碰撞。在找到任何新的最小点之后把它们记录下来。迭代最终以执行到最大代数或最大的CPU使用时间作为结束条件。最后一步，输出目标函数f的最小值解。
　　实数编码化学反应优化(RCCRO)可以有效地解决大规模连续问题，其中RCCRO的调参过程对算法能否成功解决问题起着至关重要的作用。为了使算法性能达到满意的性能，可能会花费很多时间去找到最优的参数组合。因此，如果算法的能够随着问题的变化自适应地调整参数，那么算法的效率将能得到大幅度地提高。
　　与RCCRO算法相比，一种基于PSO和CRO混合的算法HP-CRO效果更加显著。HP-CRO算法分为三步：初始化、迭代和最后阶段的CRO算法。在初始化时，定义解空间、算法函数、变量值和约束参数。HP-CRO是一种典型的基于种群的元启发式算法，但是PSO更新的效率将决定内存中保存解决方案的数量。
　　OCRO算法结合CRO和量化正交交叉算法(QOX)，将CRO单分子无效碰撞和分子间无效碰撞的局部搜索策略同QOX全局搜索策略相结合。OCRO算法并没有采用分子分解和分子合成策略，因此，OCRO种群大小是维持不变的，相应的去除一些参数设置，剩余的参数和RCCRO算法大体一致。与RCCRO和HPCRO相比，尽管OCRO在处理高维函数中有很好的表现，但是在处理低维函数时并不占优势。
　　本文拟提出一种基于CRO的混合算法，通过与原有RCCRO、HP-CRO、OCRO等算法进行仿真对比，发现本文方法在解决优化问题时具有更高的鲁棒性。本文采用混合元启发式化学反应算法，主要有以下创新点：
　　1.提出一种化学反应优化算法与遗传变异相结合的CRO-MA算法，引入遗传变异机制来增强化学反应优化算法全局搜索能力，同时兼顾局部搜索。在实践中，全局搜索和局部搜索有时会存在冲突。虽然CRO算法是很好的优化算法，但是它具有有限的四个基本单元反应。
　　生物学中，突变是通过改变个体DNA序列来产生新个体，突变算子已经应用于通过交换信息并产生后代模拟生物自然进化过程。基因突变是生物、病毒或染色体遗传因子基因组核苷酸序列的改变。辐射或化学诱变可能造成DNA或RNA基因组不可修复的基因变异，在染色体复制过程中DNA交叉重组也会可能造成基因突变的情况。基因突变不一定会造成生物可观察表征的明显变化，但突变对于正常生物的进化和免疫过程起着关键的作用。
　　在GA算法中，变异是一个遗传操作，为了维持当代种群到下一代种群的多样性，这类似于生物的遗传变异。变异改变了初始状态染色体中一个或多个序列，甚至变异会完全改变初始状态的解空间。因此，GA算法通过变异产生了很多不错的解。用户可以通过设置不同的变异率来控制演化过程中变异的概率，往往这个变异率会设置比较低，一旦高的变异率带来的后果是算法几乎等同于随机搜索。
　　本研究基于这样的假设：突变算子的优点可以提高CRO四个基本单元反应的局部和全局搜索能力。CRO-MA算法，利用突变算子产生各种分子结构以产生好的结果并提高收敛速度。
　　和一般的优化算法一样，CRO-MA也是由三部分组成：初始化、迭代和最终的输出部分。初始化主要进行算法参数的设置，迭代过程主要进行算法的搜索，最终结束输出迭代的最优解。为了使算法达到很好的效果，我们分别在CRO算法中尝试了三种不同的变异方式。
　　CRO-MA变异操作首先合并初始化并进行四个基本的迭代反应：分子间无效碰撞、分解、分子内无效碰撞和合成。

目录

声明

DEDICATION

CHAPTER 1:INTRODUCTION

1.1 Background

1.2Motivation of the dissertation

1.3Contributionof theThesis

1.4Organization of theThesis

CHAPTER 2:SYNOPSIS OFRELATED OPTIMIZATION FRAMEWORK

2.1 Introduction

2.2 CRO meta-heuristic

2.3 Bat algorithm

2.4Mutation Operator

2.5 Chapter Summary

CHAPTER 3:A DISCUSSION OFMUTATION OPERATIONSENHANCING CHEMICAL REACTION OPTIMIZATION

3.1 Introduction

3.2Combination CRO and Mutation operator approach

3.3Applicationofcomparisonmutation operator algorithms

3.4Evaluation Metrics and Experimental Parameters

3.5Experimentalresultsand discussionamongthree mutation operator

3.6 Chapter Summary

CHAPTER 4:A HYBRIDMUTATIONCHEMICAL REACTION OPTIMIZATION ALGORITHM FOR GLOBAL NUMERICAL OPTIMIZATION

4.1 Introduction

4.2 Proposed algorithm description

4.3Minimization and Maximization operation

4.4Evaluation metrics and experimental parameters

4.5MCRO fulfill theweaknessof CRO-MA

4.6Simulationresultsforminimizing optimization

4.7Simulationresults for maximizing optimization

4.8The Effect of Turning operator

4.9 Chapter Summary

CHAPTER 5:BAT–MUTATION CHEMICAL REACTION OPTIMIZATION ALGORITHM FOR SOLVING CONFLICT OPTIMIZATION PROBLEMS

5.1 Introduction

5.2BAT algorithm\(BA\)

5.3Proposed algorithm: BMCRO

5.4EvaluationEnvironmentand Parameters

5.5 Experimental

5.6Chapter Summary

CHAPTER 6:ENHANCE REAL-WORLD PROBLEMSOLVING: CASE OF BANDWIDTH UTILIZATION

6.1Background of Bandwidth utilization

6.2Benchmark for Bandwidth Utilization

6.3Algorithm Configuration

6.4Experimental Resultsof Conflicting Scenario

6.5Experimental Results of SingleObjectiveOptimization

6.6Chapter Summary

CHAPTER 7:CONCLUSIONAND FUTURE WORK

7.1Summary of the Work

7.2Future Works

致谢

参考文献

APPENDIX: PUBLICATIONS