《智能优化算法解析》 课件 第4章-基于化学原理的智能优化算法

智能优化算法解析第4章基于化学原理的智能优化算法4.1化学反应优化算法4.2人工化学反应优化算法4.3材料生成算法主要内容CONTENTS4.1化学反应优化算法44.1.1

算法原理化学反应优化算法的核心思想是借鉴了化学反应的原理。化学反应的本质是系统不断寻找更稳定的状态，这个过程伴随着能量的释放。而优化问题的目标也是找到最优解，也就是目标函数的最小值。所以受此启发，2009年，Lam等人提出了化学反应优化(ChemicalReactionOptimization，CRO)算法，用于解决非确定性的优化问题。算法的实现是通过模拟化学反应中的分子运动、碰撞和反应过程，逐步逼近最优解。算法背景54.1.2

算法描述CRO算法本质上是模拟容器中分子发生化学反应的过程。算法通过模拟化学反应中分子的碰撞、分解、合成等过程，来搜索解空间并寻找最优解。主要组成部分为分子和基本反应。其中，分子包括分子结构、势能和动能。基本反应包括壁面无效碰撞、分解反应、分子间无效碰撞和合成反应。算法描述64.1.2

算法描述

分子74.1.2

算法描述在化学反应过程中，分子之间会发生一系列碰撞。分子可以彼此碰撞，也可以与容器的壁面发生碰撞。不同条件下的碰撞会引发不同的基本反应，每种反应都有其独特的方式来操纵涉及的分子能量。在CRO中实现了四种类型的基本反应(如图示)包括：壁面无效碰撞、分解反应、分子间无效碰撞和合成反应。基本反应84.1.2

算法描述

壁面无效碰撞

94.1.2

算法描述

分解反应104.1.2

算法描述

分解反应

114.1.2

算法描述

分解反应124.1.2

算法描述

分子间无效碰撞134.1.2

算法描述

合成反应144.1.2

算法描述壁面无效碰撞和分子间无效碰撞是单分子反应，前者在分子与容器壁碰撞时发生，后者则在分子间碰撞时发生。分解和合成反应涉及多个分子，且分解和合成的反应活性较高。无效碰撞通常导致小的势能变化，而分解和合成则可能导致显著的势能变化。在优化算法中，强化搜索(如壁面无效碰撞和分子间无效碰撞)侧重于已知的高质量区域，多样化搜索(如分解和合成)则允许算法探索新的、可能较远的区域，从而优化搜索过程。总结154.1.3

算法流程步骤1：初始化基本参数。步骤2：随机生成初始化种群。步骤3：决定是否发生碰撞。步骤4：决定执行分解或合成。步骤5：保存最优解。步骤6：判断是否达到最大迭代次数，若达到，则输出最优解，否则重复步骤2-6。算法流程图164.1.3

算法流程CRO是一种元启发式搜索算法，能够通过分解和合成操作来动态调整解的数量。分解将一个分子拆分为多个，而合成将多个分子合并为一个。算法基于能量守恒的原则，利用不同的操作在分子间重新分配能量。具体来说，壁面无效碰撞和分子间无效碰撞用于局部搜索，通过引入buffer来减少分子逃离局部最小值的能力；而分解和合成操作则提供全局搜索，帮助避免陷入局部最小值。CRO算法的基本单位是分子，适合使用面向对象的编程语言实现，如C++和Java，通过创建和管理分子对象来执行不同的基本反应。总的来说，CRO算法通过组合和扩展不同的元启发式组件，为各种优化问题提供了一个灵活且有效的解决框架。算法特点174.1.3

算法流程CRO算法的灵感来自化学反应的“基本原理”，这与SA算法的“冶金退火”物理过程不同。CRO算法从微观上考察事物，而SA算法模仿的是宏观系统。CRO算法主要关注的是在不同分子之间从PE到KE的能量重新分配问题。而SA算法的核心是Metropolis条件。CRO算法是一种特殊的元启发式算法，其获得的最优解数量可能不止一个，并且解能够根据优化问题进行变化。然而，SA算法一次只保留一个最优解。与模拟退火算法的差异184.1.4

典型问题求解案例

求解最小值194.1.4

典型问题求解案例求解过程(1)分解操作函数(1)非有效碰撞操作函数204.1.4

典型问题求解案例求解过程(3)合成操作函数(4)间接非有效碰撞操作函数及非线性函数214.1.4

典型问题求解案例求解过程(5)参数初始化设置224.1.4

典型问题求解案例求解过程(6)CRO算法主循环234.1.4

典型问题求解案例求解过程244.1.4

典型问题求解案例求解过程(7)绘制收敛曲线254.3.4

典型问题求解案例

求解过程实验结果如图所示。从收敛曲线可以看出，CRO算法在迭代初期，目标函数值先增加，然后迅速降低，并在后续迭代中保持了较好的稳定性264.1.5

前沿进展2014年，Bechikh等人提出了一种非支配排序化学反应优化算法，通过结合非支配排序和化学反应优化来解决多目标优化问题，设计了一个准线性时间复杂度的快速非支配排序算法以提高计算效率。2020年，Arijit等人开发了一种基于化学反应优化的动态船舶泊位分配算法，结合混合整数线性规划考虑了等待时间和燃料成本，有效地解决了船舶在锚地等待的问题。前沿进展274.1.5

前沿进展2021年，Kiani等人利用化学反应优化算法实现了虚拟机到物理机的高效功耗映射，采用了基于排列和分组的编码方式，并为每种编码方式设计了特有的操作算子。2023年，Islam等人提出了一种基于化学反应优化的最大覆盖选址算法，通过重新设计CRO的基本反应并添加修复算子，提升了算法跳出局部极大值点的能力，从而提高了找到全局最优解的概率。前沿进展4.2人工化学反应优化算法294.2.1

基本概念与原理人工化学反应优化算法的灵感来自化学反应的类型和过程。化学反应是反应物转化为生成物的过程，速度因反应类型不同而异。常见的反应类型包括连续反应和竞争反应，涉及化学键的形成与断裂。反应物是参与反应的物质，生成物是通过反应产生的新物质。人工化学反应优化算法304.2.1

基本概念与原理化学反应中几常见的基本过程包括：合成、单置换、双置换和分解人工化学反应优化算法314.2.1

基本概念与原理

常见化学反应324.2.1

基本概念与原理单置换反应：单置换反应是指一个元素与化合物中的另一个元素交换位置的过程。Cl2+2KBr→2KCl+Br2氧化还原反应：氧化还原反应是从一种反应物向另一种反应物转移(失去或获得)电子的过程。Fe+Cu+2→Fe+2+Cu常见化学反应334.2.1

基本概念与原理

常见化学反应344.2.2

算法描述在二维粘性流体中，原子和分子通过移动和碰撞进行相互作用，化学反应是原子间的互动。人工化学反应优化(ACROA)模拟了反应物在固定体积容器内的化学反应过程。ACROA通过编码反应物(可为二进制、实数等)，根据化学反应规则迭代消耗反应物并生成新的反应物，目标是寻找焓更低的新解，直到达到终止条件，算法结束。算法的主要机制354.2.2

算法描述ACROA算法可大致分为以下几个步骤：首先根据所需求解的问题，对反应物进行编码。然后初始反应物根据化学反应规则，消耗反应物并产生新的反应物。此过程不断迭代，算法不断搜索具有更低焓的新反应物。当算法达到终止条件时，算法结束。算法的主要机制364.2.2

算法描述在执行算法之前，首先需要明确要解决的问题，例如：单目标优化或多目标优化问题。接下来，设定ACROA的唯一参数，即反应物数量(ReacNum)。问题定义和算法参数初始化设置反应物和评估在此步骤中，初始反应物在可行解空间内均匀初始化。一般来说，空间中的所有解可以通过决策变量的线性组合获得。ACROA中采用基于分割和生成范式的方法来生成初始反应物，以获得高质量的初始解。374.2.2

算法描述

设置初始反应物和评估384.2.2

算法描述假设种群规模为|P|，生成的反应物集合R中的决策变量数量为|R|。如果|R|<|P|，则k的值增加1，并且R0和R1被分成三部分，此时生成6个反应物，并且这些反应物不在R中。以上是ACROA设置初始反应物的具体方法，接下来将介绍反应物通过应用化学反应，获得生成物的过程。设置初始反应物和评估394.2.2

算法描述

应用化学反应-双分子反应404.2.2

算法描述合成反应：首先，确定两个反应物的不匹配位。然后，依次从第一个反应物的不匹配位和第二个反应物的不匹配位中选择一个位，以形成新的反应物。应用化学反应-双分子反应414.2.2

算法描述置换反应：根据一个随机生成的掩码，类似于均匀交叉掩码，考虑两个反应物字符串的每个位位置进行信息交换。如果字符串中相应位位置的掩码值为1，则反应物的位不交换。应用化学反应-双分子反应424.2.2

算法描述氧化还原2反应：随机选择两点，并交换这两点之间反应物的位，类似于遗传算法中使用的二点交叉。应用化学反应-双分子反应434.2.2

算法描述分解反应：

在反应物字符串中随机选择两个点，然后反转这两点之间的位。应用化学反应-单分子反应氧化还原1反应：随机选择一个位，并将其从0变为1或从1变为0。双分子和单分子的反应考虑了算法局部利用和全局勘探的搜索平衡，具有一定跳出局部最优解的能力。444.2.2

算法描述反应物更新：如果新生成的反应物具有更低的焓，则将其加入最优解集。反之，执行可逆反应，还原初始具有更低焓的反应物。算法通过反应物更新过程，能够有效保留高质量解，进而获得满意解或最优解。判断终止条件：当算法满足终止条件(例如达到最大迭代次数)时，人工化学反应优化算法将终止。否则，将重复执行步骤应用化学反应和反应物更新。反应物更新与判断终止条件454.2.3

算法流程算法流程图464.2.3

算法流程算法流程图步骤1：初始化问题和算法参数。步骤2：设置初始反应物和评估。步骤3：应用化学反应：先判断单分子还是双分子反应，再判断化学反应类型。步骤4：反应物更新，判断焓是否降低。步骤5：判断终止条件，如果不满足则重复步骤3和步骤4。474.2.4

典型问题求解案例

求解最小值484.1.4

典型问题求解案例求解过程(1)参数初始化设置494.1.4

典型问题求解案例求解过程(2)ACROA主循环504.1.4

典型问题求解案例求解过程514.1.4

典型问题求解案例求解过程(3)绘制收敛曲线(4)计算分子的焓值(5)分解反应524.1.4

典型问题求解案例求解过程(6)氧化还原1反应(7)合成反应(8)取代反应(9)取代反应534.3.4

典型问题求解案例

求解过程实验结果如图所示。从收敛曲线可以看出，ACROA在迭代初期目标函数值就迅速降低了，并在后续迭代中保持了较好的稳定性。544.2.5

前沿进展2020年，王建辉等人提出了一种混合人工化学反应优化算法，用于有效地求解0-1背包问题。该方法首先把化学反应分成单分子和双分子两种反应类型，并对这两种类型中的不同化学反应进行二进制编码。接着，该方法引入一个贪婪算子来修正反应过程的随机选择所产生的非可行解，并通过局部和全局搜索来获得问题的最优解。2020年，Singh等人提出了一种混合人工化学反应优化算法用于解决传统人工化学反应优化算法收敛速度较慢的问题。此外，该方法还使用了遗传算法的交叉和变异算子来平衡收敛速度与搜索范围。2021年，张亚钏等人提出了一种将人工化学反应优化算法与狼群算法相结合的特征选择算法。该方法先模拟狼群的群体智能行为，然后使用人工化学反应优化算法改变人工狼的位置，进而使算法快速找到最优解。前沿进展554.2.5

前沿进展2020年，

Singh等人提出了一种混合人工化学反应优化算法用于解决传统人工化学反应优化算法收敛速度较慢的问题。此外，该方法还使用了遗传算法的交叉和变异算子来平衡收敛速度与搜索范围。2021年，张亚钏等人提出了一种将人工化学反应优化算法与狼群算法相结合的特征选择算法。该方法先模拟狼群的群体智能行为，然后使用人工化学反应优化算法改变人工狼的位置，进而使算法快速找到最优解。前沿进展4.3材料生成算法574.3.1

基本概念与原理算法背景材料生成算法(MaterialGenerationAlgorithm，MGA)是近年来提出的一种新的元启发式算法，通过模拟材料生成过程来解决工程优化问题。MGA的灵感来源于材料化学，特别是化学化合物的配置和化学反应的过程。MGA借鉴了化学材料生成过程中的元素配置、化学反应和稳定性等原理，使得算法能够在解空间中进行全面搜索，从而使其在处理复杂优化问题时，具有更高的效率和稳定性。其中材料化学包含三个核心部分：化学化合物、化学反应和化学反应稳定性。584.3.1

基本概念与原理化学化合物元素通过化学键及电子的转移或共享来结合多种化学物质，形成化合物，其结果可能是以下之一：1.当电子从一个元素的原子转移到另一个元素的原子时，会形成离子化合物。2.当不同元素的原子之间共享电子时，形成共价化合物。594.3.1

基本概念与原理化学反应化学反应是将一种材料转化为另一种材料的过程，通常用化学方程式来表示化学反应，其中生成物与反应物一般情况下具有不同的性质。在开发新材料时，需确保初始材料的电子转移或共享过程稳定进行，以生成在特定时间内性质稳定的产物，从而保障材料的化学稳定性。化学反应的稳定性604.3.2

算法描述基本原理

614.3.2

算法描述基本原理

624.3.2

算法描述化学化合物

634.3.2

算法描述化学化合物

接着，全局候选解可以更新为：644.3.2

算法描述化学化合物

654.3.2

算法描述化学反应

664.3.2

算法描述化学反应稳定性

算法将新产生材料的候选解的质量与初始材料进行比较，若新产生的材料稳定性更好，则其将代替初始材料候选解中适应度值最