毕业论文--化学反应算法（CRO）.docx

湖南大学毕业设计(论文) 第38页摘要 化学反应算法（CRO）是一个功能强大的模拟化学反应中分子相互作用来搜索全局最优的元启发式算法。扰动函数在不同的连续问题的解决中极大地影响了CRO的性能。在本文中，我们用CRO的扰动功能研究四种不同的概率分布：高斯分布，柯西分布，指数分布和改性的瑞利分布，在解决方案中不同的分布有不同的影响。由一组众所周知的基准函数和其仿真结果表明分布函数的分布对具有不同特性的问题有不同的偏好。我们的研究提供了指导方针用于设计CRO的不同类型的优化问题。索引化学反应算法，高斯分布，柯西分布，指数分布，瑞利分布，进化算法第一章 绪论1.1化学反应算法定义及背景化学反应优化（CRO）是一个简单的并且功能强大的模拟化学反应中分子相互作用来搜索全局最优的启发式优化算法。CRO的目的是作为一个优化框架，它最初是专门解决离散优化问题的【1】【2】【3】。化学反应算法（CRO）是一种基于种群的元启发式算法。文献Chemical-reaction-inspired metaheuristic for optimization【4】用化学反应作为背景，模拟化学反应过程中分子碰撞引导反应向势能面上能量低且稳定的方向进行这一现象，根据能量守恒定律，提出了四种基本的碰撞反应算法结构，发现了化学反应（CRO）算法，化学反应优化算法模仿化学的动力学与化学热力学独有作用使算法拥有优秀的脱离局部最优解的能力，不会轻易出现“早熟”的问题【5】。化学反应算法模拟化学反应中的分子的变化现象，就是为了寻找到反应过程中能量变化最小的反应的路线。我们会碰到很多在日常生活与科学研究方面的关于优化的问题，这些方面的很多问题都难以快速求解，使用启发式算法去得到近似的最优秀解是我们常用的方式。关于优化的问题的种类非常多，但是大家共同认可的优化算法却非常少，因此我们急需寻找更多的优化算法去丰富这方面内容。由香港大学的Albert Y. S. Lam和Victor O.K. Li提出以模拟化学反应之中分子的运动的自然现象，提出名为CRO(Chemical Reaction Optimization)的元启发式的算法。 CRO为求解优化问题展现了一个非常新颖的解决思路，填补了其他优化算法不能够解决的问题的漏洞。 以量子力学与统计力学为参照，我们可以使用势能接口PES(potential energy surface)去帮助化学反应与分子间的相互碰撞建模，如下图1.1.1波恩一奥本海默近似限制着这个系统。图1.1.1展现出在化学反应系统之中，分子的势能跟谁原子的排列方式的变化来变化。Z轴代表PE值，X轴和Y轴表示化学物质之中的分子的结构，分子的结构和原子的位置与方向紧密相关，就是原子的位置或者方向不同那么分子的结构也会出现差异，对应到X, Y轴的值也会不同。PES允许是二维的，三维的，或者是多维的超曲面，这取决于化学反应系统的复杂的程度。在所有的化学反应之中，化学反应物由化学键的形成或者分解变换成新产品。在形成产品之前的反应中，反应物一般是转换成一系列相关的中间物质。这些很微弱的化学变化一般被称作基本步骤。在这些基本步骤之中，反应中的化学物质是处在过渡的状态中。图1.1.1展现出一个化学反应中所包括的三个基本步骤。实线是表示由一些过渡状态跟中间物质从反应物转变成产品的反应路径。 图1.1.1化学反应之中分子的势能变换图这个自然趋势我们能够用一个经验概括“找到一个最低的能量状态是所有的化学反应的宗旨”。这表示化学反应是要释放能量的，所以产品一般比反应物具有更低的能量状态。关于稳定性，能量低的物质结构比能量高的稳定。所以，产品一般来说都比比反应物更稳定。经过上面的讲述不是很难发现求解的最优化对应化学反应间的关系。他们的目的全都是寻找到全局最优的“解“(不同的只是目标)，并且全都是逐步演化的一个过程。根据以上发现，研究的人员们通过模拟化学反应之中分子的运动提出了一种以化学反应为基础的元启发式的算法被命名为CRO。1.2化学反应算法的发展现状及发展前景现在化学反应算法（CRO）已被应用到解决许多实际问题，如在对等网络流媒体中的人口变迁问题，网络编码优化问题，等。而后在2011年Lam等人提出了CRO的变体，命名为实数编码的化学反应优化（rccro），来解决连续优化问题。Rccro核心是以高斯分布函数为摄动函数和一些基于实数编码被设计来实现的rccro的机制。rccro已被证明在求解连续优化问题是有效的。CRO（例如，基元反应）中有四个重点：墙壁上的无效碰撞，分解，分子间的无效碰撞，与合成。CRO中墙壁上无效的碰撞和分子间的无效碰撞对应于局部搜索，同时分解合成对应于远程搜索。在传统的rccro中，高斯分布是部署在所有反应除了合成的邻域搜索算子中。在这些部部署了高斯分布的基本反应，分子通过高斯变异被扰动，检查分子的能量状态以决定是否应接受或拒绝的反应。RCCRO中高斯扰动通过加入一个零均值高斯随机数到现有的分子结构（即，解），以在附近找出新的解。对于其他优化方法，如进化规划算法（EP）和粒子群优化（PSO），研究人员还提出了除了高斯分布其他的扰动等功能。基于该柯西分布和利维分布的EP变异算法已经提出。 Krohling等人用指数，高斯定理，和柯西分布成功解出整合粒子群优化算法。然而，RCCRO性能的不同扰动分布的影响需要进一步研究。对于更好地了RCCRO的性能这样的研究是必要的。 在我们的日常生活和许多研究领域中我们都遇到许多的关于优化的问题，这些问题都难以求解，使用启发式算法来得到近似的最优解是常用的方法。关于优化的问题数目很多，然而大家都认可的优化算法却非常稀少，因此为了弥补这方面的缺失需要我们寻找更多的启发式算法。CRO求解优化问题是一种非常新颖的解决方案，为那些用公认的优化方法难以解决的问题提供了一个可行的方案【6】【7】【8】【9】【10】【11】【12】。1.3 TSP问题的相关介绍旅行商问题（Travelling Salesman Problem，TSP）又翻译成旅行推销员问题或者货郎担问题，是数图论中一个很重要的问题。假设有一个旅行商贩要到k个城市售卖，他需要选择他需要走的路线，路线的要求是每个城市只能去一次，并且最终需要回到最开始出发的城市。路线的选择目的是得到所选择的路线的所有行走路程为所有路线之中的最小值。旅行商问题是一个优化组合问题并且已经被证明具有NP计算复杂性，是一个非常经典的NP问题，凡是能简化TSP问题的求解的方法都会受到广泛关注。旅行商问题在计算机科学、运筹学和工程优化等方面有着重要研究意义。前几年，学者们受仿生学机理的启示，提出很多种用来解决旅行商问题的群智能优化算法，比如人工神经网络（ANN）、遗传算法（GA）、蚁群优化算法（ACO）、粒子群优化（PSO）与人工免疫算法（AIA）还有最近兴起的化学反应算法（CRO）。这些算法虽然不能确保在短时间内得到旅行商问题的最优解，但是可以先选择随机候选解，经过比对得到相对优秀的解，使得错误率小到使人们接受，现在已经成为求解TSP问题的最有效方法。1.4本文的主要内容我们将在第二章介绍化学反应算法的原理，包括化学反应算法的基本受控元素，即分子，基本反应的定义，和整体算法，以及四种概率分布。在第三章介绍化学反应算法的设计，包括分子的构建，分子的四种基本碰撞反应的构建和四种碰撞操作选择的准则。在第四章介绍了化学反应算法在TSP问题上的应用仿真。第二章 化学反应算法的原理2.1分子CRO是一种基于种群的元启发式算法。有分子群在一个附加能量缓冲器的容器内。每个分子的特征在于其分子结构（），势能（PE），动力学能量（KE），以及一些其他属性。表示优化问题的一个可行的解决方案，对应于该分子。PE表示的目标函数值，同时KE代表该分子的耐受性，以持有一个与现有的解相比大于目标函数值的更坏的解其他属性可用于控。其他属性可用于控制CRO流程，以确保CRO满足优化问题的特性。用户可以添加，更改或删除最佳的属性建立不同版本CRO的。 分子是由一些原子组成，其结构特征包括原子类型、键距、角度和转矩。当两个分子拥有不同的院子与不一样数量的原子时，一个分子就会区别于另外的一个分子。假如两个分子拥有的原子数量相同但是拥有不一样的分子属性(比如，转矩与角度和键距)，那么他们就是两个不相同的分子。使用分子结构的专业术语来描述这些属性，他们与数学领域里的解相对应对。这说明分子的结构由需要解决的问题来决定。举个例子，例如某个问题的有效解的集定义成n维的正实数Rn的集合，那么任意一个包含了n个正实数的向量都可以说是一个可行的分子结构，其中分子结构不可以有非正实数的值。改变分子的结构就相当于是转变成另一个有效的解。分子的基本属性包括：（a）分子结构（molecular structure,MS):代表解决目标问题的一个解；（b）势能（potential energy,PE):代表需要解决问题的目标函数值；（c）动能（kinetic energy,KE）：代表判断一个系统会不会出现分子反应的量化值；（d）碰撞数（Number of hits，Numhit）：意思是分子基本反应出现多少次；（e）最小碰撞数（The minimum hit number，MinHit）：代表得到现在最优的解时出现过的基本反应次数；（f）最低势能（The minimum PE，MinPE）：代表得到的目标函数最小值。 2.2基本反映在CRO中，分子的变化是通过不同的基本反应实现的。有四种基本的反应，即，对壁无效碰撞，分解，分子间的无效碰撞，与合成。前两个反应属于单分子反应而后两分类为类分子间反应。这些基本的反应改变的分子的分子结构和接受分子新的结构，根据能量守恒定律。CRO利用这些变化来探索解的范围和定位全局最佳 1 。我们基本上遵循 13 基本反应的定义，他们简述如下：2.2.1对壁无效碰撞分子的对壁无效碰撞示意图如图2.2.1。 图2.2.1 分子对壁无效碰撞一个壁无效碰撞发生在分子与容器的墙碰撞然后弹开。撞击中分子的一些属性会发生变化，因此，分子结构也会发生相应的变化。由于撞击不是很激烈，新的分子结构和原分子结构不会有太大的区别。这种反应有一分子作为输入并返回另一改性分子。这反应主要是用来进行局部搜索，从而使分子结构的变化变小。我们通常从中产生一个邻域结构 0。如我们定义的邻域函数： neighbor() = + e （ 1 ） 其中E为扰动因素，由一个预先定义的概率分布函数产生的，在 四-5部分进行了阐述.我们得到一个新的解决方案= neighbor() （2）它的新的势能公式为 PE=f （ 3 ） 其中F为目标函数。在此过程中，一部分被分子保留的动能将会转移到系统的能量缓冲器(EnBuff)中。我们有一个参数来LossRate控制这种能量损失率。分子新的动能将改变，根据 KE= (PE 0 PE+ KE) t, （ 4 ） 其中t LossRate，1是一个随机生成的数字。2.2.2分解反应如图2.2.2所示分子的分解是指一个分子撞击容器壁而后分解成为两个或者更多(假定这个系统之中是两个)部分。 图2.2.2 分解反应分子的撞击非常强烈以致分子分解成为两个部分。并且反应过后得到新的分子结构将会与原分子结构截然不同。分解时分子与容器壁碰撞而后断裂成两分子。这种反应主要是用于跳出局部极小值，因此分子结构的改变比上壁无效碰撞大。在这个过程中，没有动能转移到EnBuff中，但遵守能量守恒定律 7 。2.2.3分子间的无效碰撞如图2.2.3所示分之间无效碰撞反应描述了两个分子相撞然后弹开的情况。 图2.2.3分子间的无效碰撞分子之间能量交换的效果和对壁无效碰撞反应相似。分子间的无效碰撞发生时，两分子互相碰撞，然后分离。这一反应特征和目的类似对壁无效碰撞。在一般情况下，我们实现了两个分子结构1和2邻域搜索，即1= neighbor（1）和2= neighbor（2）（ 5 ）2.2.4合成如图2.2.4所示合成反应描述了超过一个分子(假定是两个分子)相撞并且结合在一起的情况。一个合成发生在两分子碰撞而后合并成一个分子时。通常来说，这种变化是剧烈的并且能帮助分子跳出来局部最小值。它的目的是保持种群的多样性。在这种算法中，新分子是由两个被给定的原分子和解的每个元素产生的，就像从每个原分子的相同位子被选中。2.3基本思想 尽可能地去摸索PES的不同部分从而找到最低的PE值，PES很大所以几乎不可能在搜索到PES的每个点。故而，只能局部的去搜索PES，而所谓的局部是指最小值最有可能属于的地方。一般是通过分子间的相互碰撞时间去搜索，借助于一些基本反应来让它们趋于能量最低的状态。一般有两种搜索方式来实现这个要求，即横向搜索与纵向搜索。每以个分子皆是从PES的某一个点开始的，横向搜索它的周边区域。如果已经不能从这个区域里找寻到更加低的能量状态的时候，便可以纵向搜索来跳到较远的区域里接着搜寻。在CRO当中，横向搜索最主要是通过撞墙反应与交换反应来体现的，然而分解与合成反应二者体现的是纵向搜索。与此同时，系统尝试着借助不同的方式来将分子之间的能量重新分配。 假设在执行一个化学反应。按照问题的类型去初始化这样一组反应分子，同时给它们以随机的分子结构以及其它的属性。所以，利用在PES上均匀的分布分子以减少遗漏一些重要区域的可能。再把反应物分子放在一个密闭的容器里面，让分子进行随机碰撞。按照基础条件来撞击以触发不同基本反应。然后仔细观察每一个事件中包含的能量转换。随事件的推移，分子“探索”PES不同的部分，再根据不同的基本反应让他们趋于能量状态最小化。每每获得比已有记录中的分子结构PE值还要小的分子结构时，便将当前分子结构记录下来。按照问题类型，能够决定合适的停止规则。每一次运行CRO得到的最小值便是整个过程中PE值最小的分子结构。2.4整体算法 CRO工作在一个随机生成分子的封闭容器中。该算法包含三阶段：初始化，迭代，和定型。当CRO开始时，分子以及一些系统参数，如EnBuff, CollRate, LossRate, DecThres, 和 SynThres 13 14 生成。在每次迭代过程中，系统会先根据一定标准随机选择一个反应类型。然后系统将根据它是单分子还是分子间的反应从容器中现有的分子中选择一个或者多个分子而后确定其能量状态。如果分解准则(对于单分子碰撞)和合成准则（对于分子间碰撞）的描述是正确的，则相应的反应发生。否则，对壁无效碰撞和分子间的无效碰撞将会发生。每次迭代的结尾是能量检测。评估和比较原分子，新生成或转化的分子有他们的目标函数。如果新的值能够满足能量守恒定律，新分子将被接受并放入容器中而原分子被丢弃。否则，新的分子被丢弃，表明没有反应。直到某些预定义的函数估计值的数量达到满足或者满足某个具体的停止标准，算法进入最终阶段，输出到目前为止的全局最优解。在这个问题上我们重点研究在邻域搜索算子和分解中CRO不同概率分布的绩效。2.5概率分布在本文中，我们考虑了四种不同类型的概率分布，即，高斯分布，柯西分布，指数分布，和瑞利分布。在本节中，我们将首先介绍四分布。然后介绍了CRO与这些分布的集成。 2.5.1高斯分布高斯分布有一个钟形概率密度函数，也被称为正常分布或非正式的钟形曲线 15 。它的密度函数为： fx;,=122.e-(x-)222 ( 6 ) 其中是期望，2是方差。不同的和2在图2.5.1中给出。我们可以通过修改2的值控制图形的形状，2值越大钟形越平坦。2.4.2柯西分布 柯西分布和高斯分布共享一个类似的钟形图形，柯西分布具有重要的物理应用。我们可以利用其特点进行详细的局部搜索。它的密度函数为： fx;x0,=1x-x02+2 ( 7 ) x0是位置参数，或平均分布。它类似于在高斯分布。是尺度参数即在最大值的一半时的半宽度（HWHM）。柯西分布不同的x0的值在图2.5.2中给出。图2.5.1 高斯分布 图2.5.2 柯西分布2.5.3指数分布指数分布描述泊松过程中事件之间的时间。不同于以上的两分布，指数分布没有钟形状。它的密度函数为： fx；x0，=e-(x-x0), &x00, &x0 ( 8 )参数x0定义出分布的发点，参数定图中曲线陡度。不同的x0和分布图2.5.3给出。 图2.5.3 指数分布 图2.5.4 瑞利分布注意，正常的指数分布，只有一个积极的一面，不为满足我们作为扰动函数的需求。类似于 16 ，我们在曲线X轴负方向做对称使成为在（，）上的连续函数。2.5.4、瑞利分布瑞利分布的函数如下：fx；2=xe2e-x222,x0 ( 9 )与高斯分布相比，唯一参数2控制形状的平面度。2值越大曲线越平坦。此外，曲线的最高点在在x =处。瑞利分布不同 2的值在图2.5.54中给出。像指数分布，瑞利分布只有在（0，）连续。本文介绍了一种新的方式使分布函数在（，）连续使之适用于扰动函数。修改后的公式如下：fx；2=+x2e-+x222stepx,-+-x2e-x2221-stepx,2 ( 10 )其中stepx,=1, &x0, &x0.5 （13）式中:i为区间1，lenM内的随机整数; lenM为分子特性向量的长度; rand0，1为区间0，1范围中平均分布的随机数; Mi表示分子的第i个特性，Mi为分子的第i个特性;下文之中类似的符号与此类似。3.2.2分子的分解 势能越大的分子的结构越不稳定，分子碰撞容器壁之后会分解成多个分子，这叫作分子的分解。简单化考虑，我们只考虑一个分子分解成2个分子，假定碰撞之前的分子是，碰撞之后分解变成和”。Mi=Mi+0.5Mi,maxMi=Mi+0.5Mi,max, Mi,max为偶数Mi=Mi+0.5Mi,maxMi=Mi+0.5Mi,max+1， Mi,max为奇数 （14） 式中:i1，lenM ;是向下取整的符号 分解操作:将选择最近的城市换成选择最远的城市，就是分子的所有特性都按照公式(14)分解。分子碰撞结束之后分子结构会发生很大的改变。假设Mi为1，那么分子碰撞结束之后Mi 、Mi分别为4, 4;假设Mi为1，所以碰撞结束之后Mi 、Mi分别为4, 5。如此就可以使得在势能面上分子分解后的分子结构与分解前的结构距离最远，这样有利于拥有很高势能的分子会在分子结构上出现很大的改变。分子的分解过程必须要满足下文所描述的能量的原则，如果不满足反应不成立。3.2.3分子间的无效碰撞 当多个分子发生碰撞时，如果分子具有很大的动能，并且碰撞之中分子相互交了换一些特性以后还能够分离，分子碰撞结束以后分子的特性会发生一定的改变，这叫作分子之间的无效碰撞。简化考虑，我们只考虑2个分子之间的无效碰撞。以提高算法的收敛速度为目的，定义某2个分子发生的无效碰撞是在一个拥有大动能的分子和一个优势分子b(势能最低)之中。Mi；=Mi1,rand0,1p ,i1,lenMMi=Mi1,rand0,1pMib,rand0,1Mi,maxMi,max+Mi,MiMi,min （17）式中: Mi,max为分子第i个特性的上限值; Mi,min为分子第i个特性的下限值。 另外反应过程中按下文判断能量原则之前需要对分子进行验证，来确定形成的分子是一个有效的分子，如果不是反应同样不成立。3.3四种碰撞的操作选择标准定义分子之间发生碰撞的概率是Ksw2，如果满足公式(18)，那么选择2个分子来进行分子间的碰撞操作，不满足就选择1个分子来碰撞容器壁;定义分子的合成准则为KEK，如果2个分子能够同时满足公式(19)，那么进行合成反应，如果不满足那么进行分子间的无效碰撞;定义分子的分解准则为KEP，如果选择的分子能够满足公式式(19)，那么进行分解反应，如果不满足就进行分子的对壁无效碰撞。rand0,1Ksw2 （18）jknKEK （19）jpnKEP （20）式中: jk是容器之中分子以动能的大小从小到大进行排序之后的序号; jp代表容器之中分子以势能的大小从小到大进行排序之后的序号;n代表容器之中分子的总数量。 为了保证反应容器中动能较小的分子发生合成反应，势能较大的分子发生分解反应，KEK应小于0.5 , KEP应大于0.5，即KEK (0,0.5) , KEP (0.5,1)，并且凡Ksw2 (0,1)。3.4求解算法的三个阶段【17】3.4.1 初始阶段初始阶段之中，我们要定义出解的空间和一些算法的函数，比如如分解函数和合成函数，并且需要对某些变量跟控制参数进行赋值。在定义好分子的结构（就是所求的问题的解的形式）和解的空间（即所要求的问题的解的空间）之后，还需要定义其他相关函数和一些参数，并进行初始赋值，具体如表1 表1 CRO算法的函数与参数3.4.2跌带阶段迭代阶段，即迭代一定的次数，每次迭代都会执行基本反应中的一个。主要流程如下：1） 辨别反应的类型。辨别是单分子进行反应还是多分子进行反应，会随机的产生一个，如 果（分子进行反应的类型的决定因子），那么执行单分子的反应过程，否则，进行多分子的反应过程。如果只有一个分子，那么执行单分子的反应。2） 根据第一步判断反应类型，从反应群体Pop中随机地选出相应数目的分子。3） 对单分子的反应而言，如果满足那么执行分子的分解反应，如果不满足那么执行分子的碰撞反应。对多分子的反应而言，如果满足那么执行分子的合成反应，如果不满足那么执行分子间的无效碰撞反映。4） 假如反应停止的条件还没有达到满足，则转到1.反应停止的条件可以根据具体需求由使用者确定，比如迭代次数达到了设定的最大值、执行时间结束等。3.4.3最终确认经过CRO迭代后，输出整个算法最小的PE值以及对其对应的分子（最优解）。3.5化学反应算法中分子碰撞所需要满足的能量的规则3.5.1 分子的对壁无效碰撞的能量原则 和分别为分子发生碰撞之前和之后的分子。如果分子是一个优势分子(就是分子的势能最低)，碰撞发生过程中能量需要满足公式(21)，碰撞成功以后新形成的分子的动能需要按照公式(22)进行计算。反应之前和之后的能量损失要按照式(23)，储存到中心能量缓冲区(central energy buffer CEB)之中，能量缓冲去的能量主要用于为后续的分子分解提供能量。EP，+EK,Ep. (21)EK,=qEP，+EK,-Ep. (22)ECBE =ECBE +1-qEP，+EK,-Ep. (23)q=randKElossRate,1 (24)式中: EP，代表分子的功能EK,代表分子的动能; Ep.代表分子的势能 EK,代表分子的动能; KElossRate代表碰撞过程动能损耗的比例下限;q代表碰撞过程动能损耗的比例。其他符号与此类似。如果分子是一个优势分子(记作b)，为了保证好的分子能够在反应中不丢失，碰撞反应过程中的能量需要满足公式（25）。发生碰撞成功之后新形成的分子的动能按照公式(22)进行计算。反应之前与之后能量的损耗按照公式(23)存入CEB中。如果不能满足公式(25)，那么分子b的势能将会维持不变，碰撞过程损耗的动能按照公式(26)存入CEB中，分子b的动能按照公式(27)进行修正。EP,Ep. (25)ECBE =ECBE +1-qEK,b (26)EK,b=qEK,b (27) 3.5.2分子分解的能量原则 为碰撞前的分子，、为碰撞后由分解的2个新分子。碰撞之前和之后如果能够满足公式(28)，那么分解反应成功，分子、的动能按照公式(29)进行计算，其中用于分子碰撞之后动能进行随机的分配。EP,+EK,EP,+EP, (28)EP,=EP,+EK,-EP,-EP,EP,=1-(EP,+EK,-EP,-EP,) (29)=rand0,1 (30) 如果碰撞之前和之后的能量关系并不能满足公式(28)，那么表明分子自身的动能是有限的。为了促进分子的分解，CEB中能量会鼓励分子分解。如果能量的关系可以满足公式(31)，那么表明分解成功，新分解行成的2个分子、的动能按照公式(32)进行计算，其中: 1、2、3、4都独立地按照公式(30)进行计算;CEB的能量将按照式(33)进行修正。EP,+EK,+ECBE EP,+EP, (31)EK,=12EP,+EK,+ECBE -EP,-EP,EK,=34(EP,+EK,+ECBE -EP,-EP, (32)ECBE =EP,+EK,+ECBE -EP,-EP,-EK,-EK, （33） 如果式(31)的能量关系同样达不到满足，那么表明分解反应失败，分子维持不变。 3.5.3分子之间的无效碰撞的能量原则。 1，b (即优势分子)代表碰撞发生之前的2个分子，、“代表碰撞发生之后所新产生的2个分子。如果碰撞之前和之后能量关的系能够同时满足公式(34), (35)，那么表明碰撞反应成功。碰撞发生后2个新的分子的动能按照公式(36)进行计算，公式(36)中的按照公式(30)进行计算。EP,1+EK,1+EP,b+EK,bEP,+EP, （34）min(EP, EP,)EP,b (35)EK,=(EP,1+EK,1+EP,b+EK,b-EP,-EP,)EK,=EP,+EK,-EP,-EP,-EK, (36) 如果只能满足公式(34)而不能满足公式(35)，那么将和“中拥有较大势能的分子用优势分子b进行替换，而替换后的2个分子分别记作g、g”，式中g”=b。如果可以满足公式(37)，那么分子g的动能按照公式(38)进行计算，如果不满足，分子1与b维持不变。EP,1+EK,1EP, (37)EK,g=EP,1+EK,1-EP, (38) 如果式(34)中的能量关系并不能满足，那么碰撞反应失败，分子1与b维持不变。 3.5.4分子合成的能量原则 1，2表示碰撞发生之前的2个分子，代表碰撞合成之后的1个新分子。如果碰撞发生之前的2个分子均不是优势分子，而且可以满足公式(39)那么合成成功，而分子的动能按照公式(40)进行计算，如果不满足那么合成失败，原分子维持不变。EP,1+EK,1+EP,2+EK,2EP, （39）EK,=EP,1+EK,1+EP,2+EK,2-EP, （40） 如果碰撞发生前的2个分子之中有1个为优势分子，那么满足公式(39)的同时也需要满足公式(41),如果不满足那么合成失败，而原分子维持不变。EP,bEP, （41）3.6算法设计化学反应算法模仿化学反应之中的分子的改变和运动，这些改变和运动能够促进分子在解的空间中向全局最优的点进行运动。化学反应一定是在一个包含一定数量的分子的容器中发生的。分子拥有一个分子解结构和动能跟势能。化学反应算法使用势能对优化方程的值进行模拟:PE=f()，公式中f代表优化方程, 代表分子解结构。化学反应算法的目标是用不同的化学反应方式使分子的势能最小化。其中反应方式包括有:对壁无效碰撞碰撞、分子的分解反应、分子见得无效碰撞和分子的合成反应。这些基础的反应方式均能够改变分子解的结构。CRO流程图如图3.6.1。图3.6.1 CRO流程图3.6.1编码的方式 化学反应算法中，一个可行的路径选择由一些数字来组成。这些数字将会分别表示不同的节点代码，其中路径的连接方案和方向由数字的顺序决定。为了确保一致性，全部的路径均由发射节点s出发，以回到节点r为结束。而在可行的路径选择中不可以出现回路现象，因此路径选择的长度需要比总活动节点的数量小。3.6.2对壁无效碰撞 这个算子只是在对壁无效碰撞发生之时改变了一个分子解的结构。所以它需要以现有的一个分子作为输入，而后输出新分子 。这个算子最重要的目的是在势能面上的小范围内进行细致的搜索，所以它需要在小范围之内对分子解的结构进行改变。在化学反应算法中，首先选择一个中的随机节点e，而后产生一个从e到r的随机路径。这样就产生了一个新的路线。要确保没有回路问题，我们同时要设计一个修复机制来删除回路。3.6.3分子的分解反应这个算子是使用已有的两个分子去生产两个新分子1与2。这个算子能够使分子逃脱区域最优。化学反应算法中，分解成两个新部分1和2，而后缺失的部分将会随机补充新形成的两个分子解的结构。3.6.4分子间的无效碰撞 算子在分子间发生无效碰撞的时候会随机地改变现有的2个分子1与2来形成2个新的分子1和2。该算子会随机的将现有的分子进行结合并且交换，因此潜在的最优解的不同部分有一定机会会交换到同一个分子解的结构之中。化学反应算法中，该算子触及到两个方面。第一，两个分子解的结构进行比较而后选择出一个都包含的节点。第二，以该节点为界限的四个部分互相交叉互换来形成新的分子解的结构。3.6.5分子的合成反应 该算子吸收两个现有的分子1与2来形成新的分子。化学反应算法中，该算子和分子间无效碰撞算子非常相近。而不相同的地方在于，第一步选择共有的节点以后，四个部分会发生两两配对来计算总资源的占用。而新分子解的结构必定是当中占用总资源最少的一个结构。第四章 化学反应算法在TSP问题上的应用4.1CRO在TSP问题上的仿真整体运行界面如图4.1.1：图4.1.1算法的运行界面现在以130个城市60次迭代为例，运行结果如下：进行第三次迭代时如图4.1.2：图4.1.2程序进行第三次迭代程序进行第28次迭代如图4.1.3：图4.1.3程序迭代28次时结果程序进行第48次迭代时的结果如图4.1.4：图4.1.4程序第48次迭代的结果程序进行完60次迭代的结果如图4.1.5：图4.1.5程序进行完60次迭代的结果当迭代次数更改为100次时结果如图4.1.6、4.1.7：图4.1.6图4.1.7迭代次数更改为150次时的结果如图4.1.8、4.1.9图4.1.8图4.1.9总结本文主要学习了CRO算法的概念和算法设计，并在此基础上针对TSP问题进行求解。在化学反应算法中，使用一个分子的结构来表示要求解问题的一个解，而分子势能则代表对应的目标的函数值。那么尽最大可能去搜索势能面中不同的部分寻找到的势能最低的点就是求解最优解。一般情况中，势能面是一个十分巨大大的不能够在一个短暂的时间内验证其中所有点的空间。这样就需要有选择行地搜索势能面内有高概率存在最小值的那些区域，详细方法为使用分子的碰撞和碰撞发生后的化学反应引导分子向大概率的最低能量状态运动来进行寻找。化学反应算法中提出了4种分子碰撞的方式，分别是分子的对壁无效碰撞反应、分子的无效的碰撞反应、分子分解反应和分子合成反应。最开始使用分子的对壁无效碰撞和分子间的无效碰撞形成的有效策略搜寻它的紧邻的区域;如果不能在相邻区域中继续搜索到能量更低的状态，则使用分子的分解反应和合成反应形成的多样化的策略跃迁到一个比较远的区域继续进行搜索。在寻找的过程中，使用多种交换的方式，能量会在分子之间不断地进行重新分配。伴随多核处理器技术的高速发展，单一芯片之中能够包括多个不相同的处理器核心，而且这成为了计算机向前发展的一种必然的方向。不过计算能力急速加快的同时，能耗的问题就会变成限制他进步和应用推广的巨大阻碍。但是接近顶点的低功耗的设计技术，抽象度也非常高，很大程度影响功耗。当今能够解决异构多核低功耗调度问题的算法时间的复杂度非常高同时传统的启发式算法也表现出局限性在应用中。研究之后证实解决这种问题最为可行的做法之一就是将他分解成任务划分与低功耗调度这两个子问题来进行解决。化学反应算法解的数目是跟随算法运行的变化而不断改变的。分解反应和合成反应能够对应地增多和减少反应容器之中的分子的数量。分子间无效碰撞和对壁无效碰撞能够高效搜索局部的最优值。使用能量缓冲器BE来存储动能KE，以削弱分子逃脱局部空间的能力。同时确保不让搜索被困在局部最优之中，合成反应和分解反应能够高可行的扩大搜索领域，来尽量的寻找到全局的最优解。 由于自己的理论知识水平有限，课题非常新，可供参考的中文文献非常稀少，外文文献阅读方面可能会出现理解不到位的问题，设计经验不足，在设计中难免存在一些问题。比如CRO算法在TSP问题的应用方面做的不够好。主要在于，相关学术问题比较多且理解不到位，解决方法少，同时问题考虑不周全。恳请各位老师批评指正，能让我在今后的相关设计中得以改进和提高。 致谢 随着论文的结束，也预示着四年大学生活的结束。回想过往，当初选择来湖南大学真的是一个明智的决定，这里有着没有围墙的校园，有着穿插在校园中的商场生活区，同时这里也有着自主的学习氛围，老师的学习的全力支持和学长学姐们对学弟学妹们的无私帮助。这里首先要感谢我的指导老师王炼红老师，在做毕业论文期间，老师给了我全方面的帮助。每个星期一次的见面确保我们能够及时解决发现的在做毕设期间的各种问题，同时能够及时传达院里和学院方面下发的各种通知，并且还会督促我们尽快写毕业论文，检查论文进度。老师也会在我们做毕设的各个极端提出宝贵的经验，并为我们指明方向。这才使得我能够及时完成毕业论文，也使我在其中受益匪浅。 也要感谢无私帮助我的林学姐，学姐有自己的学习任务要完成，但是还是会经常与我联系，询问我有没有什么论文上的问题，并给予解决。在前期阶段，学姐介绍了很多相关问题的文献，使我能够很好的理解我的题目。程序编写方面也给予了极大的帮助。感谢湖南大学岳麓书院讲习团，因为你，使我更加了解了这麓山之畔，湘水之湄，千年学府，弦歌不绝的岳麓书院。因为你，使我更加了解了湖湘文化，从而继承书院传统，弘扬人文精神。更因为你，让我收获了真挚的情谊，时时刻刻感受到身为一名社团人强烈的归属感。感谢湖大青年传媒以及曾在一起工作与奋斗的朋友们，在那里，我学会了什么叫做责任，以及何为担当。也正是因为在这样一个优秀的团队中，才让我更快速的成长与进步，感谢在此期间给予我帮助和指导的老师和朋友们。感谢我的爸爸和妈妈，假如我是一直翱翔在天际的风筝，但是无论我飞的多高多远，总有一根线，时时刻刻的牵挂着我，那就是我的父母。无论我做什么事，他们给予了我最大的信任和最强有力的支持。他们永远是我人生道路上激励我不断前行的永恒力量。我爱你们！最后要感谢的，是我所度过四年的大学生活，在这即将过去的四年中有很多精彩，也有一些