人工智能前沿：组合优化问题的机器学习求解人工智能启发式算法的优点

发表时间：2023-07-03 21:03:14

人工智能前沿：组合优化问题的机器学习求解

2）启发式算法，包括近似算法、贪婪算法等，这类算法优点是存在最差解的质量保证，缺点是求解时间比较长，并且这类近似算法很难构造；

3）元启发式算法，如遗传算法、蚁群算法、模拟退火算法等，这类算法优点是比较容易实现，求解时间也不会太长，很快得到一个可行解，缺点在于该类算法对参数比较敏感，不同的实例都需要重新调整参数；

4)机器学习方法，包括监督学习、强化学习以及图神经网络等，该类方法优点是能从同分布的数据中学习到通用的规律，能快速求解同一类问题。

总之，前三类算法可以看成是人类学习如何去设计算法，该类算法规模适中、模型相对稳定、能求解一些经典问题同时也存在理论保证，而最后一类方法是通过机器学习方法去学习如何设计组合优化算法，该类算法能求解超大规模问题，是实时变化的，能处理复杂系统，唯一的缺点是该类算法是一种弱最优性。除了上述四类优化算法以外，也存在一些组合优化的求解器，包括商用求解器，Gurobi、CPLEX等以及开源求解器，SCIP以及LP_Solve等。

目前机器学习组合优化是人工智能的前沿方向，可以通过使用不同的机器学习方法来解决不同的组合优化问题，如图优化以及离散优化等。

图1组合优化与机器学习

目前组合优化问题的机器学习求解范式可以分为两类：

1）基于端到端求解，输入是问题的实例输出是问题的结果，使用自回归或者非自回归的方法学习一些启发式的策略；

2）局部改进求解，包括改进精确算法或者启发式算法等，将这些算法中比较耗时的模块转换成一个学习问题，从而加快求解的速度，如对于分支定界算法，可以将传统的使用强连通量进行分支转换成一个二分类的学习问题。

什么是组合优化|集智百科

二、图上的组合优化问题求解

图上的组合优化问题是组合优化问题中很重要的部分，很多图上的组合优化问题都是NPC问题，只要证明任意一个NPC问题存在精确的多项式算法，那么所有的NP问题就都解决了，那么P=NP。

什么是P问题、NP问题和NPC问题？

图上的组合优化问题的一般性求解框架具体分为两个阶段：第一个阶段进行图的表示学习，学习节点或边的表示向量；第二个阶段基于表示向量求解组合优化问题，可以使用非自回归方法结合启发式搜索规则，或者基于强化学习的自回归进行优化求解。下面分别具体介绍这两类方法。

图2组合优化问题的一般性求解框架

1.非自回归方法

CombinatorialOptimizationwithGraphConvolutionalNetworksandGuidedTreeSearch

https://arxiv.org/abs/1810.10659

CombinatorialOptimizationwithGraphConvolutionalNetworksandGuidedTreeSearch

https://arxiv.org/abs/1810.10659

该论文尝试解决最小支配集、最小节点覆盖以及最大割这样的NPC问题，使用监督学习算法结合树搜索以及图论技巧来学习。具体来说，模型输入一个图，然后对图进行约简，将约简后的等价图输入GCN中学习每个节点选中与否的概率，然后结合树搜索算法以及图论的局部搜索算法选择最优的结果，输出图中的每个节点是否被选中。损失函数是一个交叉熵损失，表示第i个训练图的第j个节点的标签，表示GCN输出的第j个节点选中与否的概率。为了解决组合优化解不唯一的情况，作者使用hindsightloss优化GCN输出多个loss的最小值。其中通过后面的实验发现图论技巧对于性能的提升占了很大比重，去掉局部搜索的技巧，预测的性能显著降低。但是该类算法的缺点在于泛化效果比较差，除非加很多领域的专业技巧才能提高性能。

图3基于图卷积网络和引导树搜索的组合优化算法流程图

2.自回归方法

第二类为自回归算法，其框架主要就是结合图表示学习和强化学习来优化目标。下面主要介绍三个工作，S2V-DQN(NIPS2017)、FINDER(NMI2020)以及DIRAC(NC2023)。

S2V-DQN

KhalilE,DaiH,ZhangY,etal.Learningcombinatorialoptimizationalgorithmsovergraphs[J].Advancesinneuralinformationprocessingsystems,2017,30.

该工作是机器学习组合优化领域的里程碑式工作，引领并启发了该领域后续许多的研究。该方法的整体框架是输入一个图，然后使用多层的GraphEmbedding方法得到每个节点的表示向量，然后通过Q-Learning算法为每个节点算一个Q-value作为节点选择的长期收益，收益最大的节点被选中，然后重复GraphEmbedding和Q-Learning直到满足终止条件。其中这里的GraphEmbedding使用Struct2Vector算法。

算法训练过程主要包括四个部分：1）生成训练图数据；2）探索和利用选择节点；3）更新节点的状态；4）构建损失函数优化模型参数。该方法在最小节点覆盖、最大割以及旅行商问题中进行了实验。在最小节点覆盖实验中，相比CPLEX求解器得到的最优解，该方法的性能几乎接近最优解，同时该方法也具有很好的泛化性，在小规模图中进行训练，然后可以用来在大图中进行测试。在最大割问题中，相比于基准算法来说也是更优的。在TSP问题中,对于大图的优化性能稍微逊色些。

图4S2V-DQN算法流程图

通过可视化的方式对算法进行可解释分析，发现相比其他算法，如每步选择节点度最大的节点，该算法每次都倾向于选择那些能覆盖更多节点，同时避免破坏连通性的节点，从长远看，需要的节点更少，这也正是强化学习的优势，可以启发我们选择更加高效的贪婪算法。该算法提供了一个统一框架，适用多种图上的组合优化问题。

FINDER

FanC,ZengL,SunY,etal.Findingkeyplayersincomplexnetworksthroughdeepreinforcementlearning[J].Naturemachineintelligence,2020,2(6):317-324.

论文解读：用强化学习寻找关键节点——复杂网络研究新范式

FanC,ZengL,SunY,etal.Findingkeyplayersincomplexnetworksthroughdeepreinforcementlearning[J].Naturemachineintelligence,2020,2(6):317-324.

论文解读：用强化学习寻找关键节点——复杂网络研究新范式

虽然S2V-DQN方法已经具有很好的优化效果，但是在更大规模上的泛化能力还有待提高。因此，范长俊等人提出一种通用且可扩展的深度学习求解框架，适用于不同的瓦解场景，同时继续提升了模型的泛化能力，使得模型能在上千万节点规模的网络中都能有很好的性能。该工作尝试在网络瓦解问题上面实验，希望找到能使网络瓦解的最少节点集合。其中衡量模型的好坏可以使用ANC曲线下的面积来表示，纵轴表示复杂网路功能，横轴表示移除节点的比例。复杂网络功能又可以使用结构性功能指标（包括最大连通片规模等）和非结构性功能指标（如军事中的体系预警规模等）来衡量。

FINDER算法的框架同样采取了类似S2V-DQN这种结合图表示学习和强化学习的算法框架，但是存在一些不同，区别如下所示:

主要区别S2V-DQNFINDER节点表示Struct2VecGraphSAGE状态表示简单的节点嵌入之和表示状态引入虚拟节点表示状态动作值函数Q计算状态和动作向量的拼接状态和动作向量的交叉积训练损失函数贝尔曼损失贝尔曼损失加上图重构损失测试策略一步测试选择一个节点一步测试选择一批节点

对于实验部分，作者使用两种连通性的计算方法（CN，ND）以及三种节点赋权方式（无权、度权以及随机权），共六种实验场景。在六种不同的网络瓦解场景中效果平均提升28.7%。此外，该方法具有很好的泛化能力，可以使用小规模模拟图上训练的模型来测试大规模真实的网络，这说明模型学到了网络瓦解的内在的策略。同时FINDER的计算效率也提升超过两个数量级，FINDER算法自己发现了更快瓦解复杂网络的策略。在加权网络中，FINDER优先选择cost-effective的节点，即代价不那么大，却能达到相同的瓦解效果。

DIRAC

FanC,ShenM,NussinovZ,etal.Searchingforspinglassgroundstatesthroughdeepreinforcementlearning[J].NatureCommunications,2023,14(1):725.

论文解读：Nat.Commun.前沿：深度强化学习搜索自旋玻璃基态

FanC,ShenM,NussinovZ,etal.Searchingforspinglassgroundstatesthroughdeepreinforcementlearning[J].NatureCommunications,2023,14(1):725.

论文解读：Nat.Commun.前沿：深度强化学习搜索自旋玻璃基态

该工作尝试提出一种强化学习方法（DIRAC）来解决自旋玻璃的基态求解问题，确定最优的节点状态使得目标函数值最低，其中目标函数为表示节点i的状态，每条边的权重，直线表示正权边，折线表示负权边，边的宽度与

呈正比，蓝色阴影部分表示边的能量

。

该方法同样基于图表示学习与强化学习框架，其中每个部分都有小的改动以适用自旋玻璃的基态求解问题。其中，基态求解问题受边权的影响很大，边权直接影响最终基态的分布，所以这里采用两阶段的嵌入方式，首先基于两端节点的嵌入向量更新边的嵌入向量，然后再基于相邻的边的表示更新节点的表示，这种方式能更好地捕捉边的特征与权重。

此外，最关键的是添加了规范变换的技巧（Gaugetransformation）。引入变换在于，传统的强化学习工作流程存在缺点，只能从某个状态出发，逐步增加元素（动作选择）构建解集，直到满足终止条件，每个节点选择且只能选择一次，但是，这种方式最大的问题在于动作不可重复选择，即只能产生单个“最佳猜测”。然而，组合优化问题巨大的探索空间要求智能体能够重复多次“试错探索”以避免陷入局部最优，该工作提出的规范变换能够将任意状态转化为指定的状态，从而适合智能体的重复探索。规范变换带来如下好处：1）允许模型在一次探索（DIRAC1）结束后接着继续探索（DIRACm）；2）允许模型从多个不同初态出发，从而取得更优的结果；3）允许模型和任意启发式算法结合，从而进一步提高启发式算法的结果；对性能的提升作用很大。

图5自旋玻璃的基态示意图

实验结果上，在大尺寸系统中（基态未知），DIRAC相比目前最先进的退火算法，可以取得更低的能量。在小尺寸系统中（基态已知），DIRAC均能求出全局最优解。此外，通过模型的可解释分析发现，该模型是通过牺牲短期收益，获取长远收益，这也是强化学习的优势所在。

该问题是揭开自旋玻璃奇怪而复杂行为的关键，有助于解决许多组合优化难题，有助于神经网络优化工具的开发。该算法具有以下优点：1）精度高，中等尺寸的系统可以达到全局最优解，且适用于三维及以上的高维系统；2）可扩展性强，最大系统尺寸达到三维的L=20，这是目前研究最大的系统；3）可以和任意退火算法等启发式算法结合，并进一步提高这些算法的表现。

总之自回归方法中基于图表示学习加上强化学习是目前一种主流的研究范式，优点在于模型泛化性能好、模型效果好且具有一定的可解释性。但是存在模型设计、学习难以及实现困难等缺点。因此，作者也正在开发一种基于图表示学习和深度强化学习的图上组合优化问题求解工具（OptiGNN）来降低我们的学习门槛。

三、研究进展

1.如何与精确算法结合？

SolvingMixedIntegerProgramsUsingNeuralNetworks

https://arxiv.org/abs/2012.13349

SolvingMixedIntegerProgramsUsingNeuralNetworks

https://arxiv.org/abs/2012.13349

对于求解混合整数规划问题（MIP），最常见的精确算法就是分支定界算法，然而对于具体如何分支计算是很复杂的，传统的方法都是把它松弛到线性规划，然后用线性规划求边界，再选择相应的值。然而这样的方法计算量就非常大。现在可以使用机器学习方法把分支问题看成是一个二分类问题。如DeepMind提出用神经网络求解混合整数规划，包括NeuralDiving以及NeuralBranching两个部分，NeuralDiving训练一个深度神经网络来产生MIP问题部分整数变量的赋值，剩余未赋值的变量定义了一个更小的“子MIP”，这个子问题使用现成的MIP求解器（如SCIP）来求解，进而产生一个高质量的联合变量赋值；NeuralBranching训练一个深度神经网络，在经典求解器进行分支定界的过程中，针对给定节点模仿专家的分支变量选择策略进行分支变量的选择。

具体来说，可以将MIP建模为一个二部图，决策变量和约束看成图中的两类节点，其中变量前的系数和约束作为节点和边的特征。然后使用图神经网络生成部分解，具体来说可以将构建的二部图输入图卷积神经网络得到每个节点的表示向量，接着经过MLP输出各个变量为某个值的概率。此外，在分支定界过程中，为了提高决策质量，使用模仿学习，来学习strongbranching的专家经验。模型在速度和精度均取得出色的表现。

图6神经MIP求解器算法流程图

2.如何与启发式算法结合？

Mills,KyleandRonagh,PooyaandTamblyn,Isaac.FindingthegroundstateofspinHamiltonianswithreinforcementlearning.NatureMachineIntelligence,2020.

该工作尝试结合启发式算法解决自旋玻璃的基态求解问题，我们知道对于模拟退火方法，有个关键问题就是温度如何下降，为了克服这个问题，该方法利用强化学习学习模拟退火算法的最佳退火策略，然后使用最佳退火策略来求解自旋玻璃的基态。然而，该方法的实验结果并没有那么好。

图7基于强化学习寻找自旋哈密顿量的基态算法流程图

3.如何提高在大规模实例的泛化表现？

GeneralizeaSmallPre-trainedModeltoArbitrarilyLargeTSPInstances

https://ojs.aaai.org/index.php/AAAI/article/view/16916

GeneralizeaSmallPre-trainedModeltoArbitrarilyLargeTSPInstances

https://ojs.aaai.org/index.php/AAAI/article/view/16916

对于如何提高大模型实例的泛化能力，下面讲解两个工作：

第一个工作使用监督学习解决经典的TSP问题，文章提出的是一种混合算法，级联了SL和RL模块。SL模块运用预训练的模型与三种图技巧（包括图采样、图转换、图合并）为任意规模的TSP构建热力图。热力图刻画了节点之间每条边属于该TSP最优环游的概率。随后，热力图将作为RL模块的重要输入。RL算法将进一步使用蒙特卡洛搜索寻找最优解，输出TSP的最优环游。该工作具有很好的泛化能力具体体现在如下操作，训练一个小规模网络的预训练模型，对于任意大规模的图输入都可以通过对图进行采样构建子图，然后分别通过学习好的预训练模型，最后将子图合并成原始的大图，解决了训练和测试图的尺寸不一致的情况。但是该方法应用也有限，该方法无法与强化学习方法进行结合。

图8解决TSP算法的流程图

第二个工作是前文提到的FINDER算法框架。在FINDER方法中，作者也尝试使用配置模型来提高模型的泛化能力，即定制匹配目标网络的训练数据，可以根据目标网络的度分布采样构建一个小规模图，然后在这些生成的图上训练模型。实验发现该方法能提升一些性能但是提升不是很大，同时针对特定的网络都要重新训练增加了模型计算量。

总之，这两个工作一定程度上提升了大模型的泛化能力，但是也带来了计算量的增加等问题，需要进一步的完善。

4.如何处理复杂的约束？

DC3:Alearningmethodforoptimizationwithhardconstraints

https://arxiv.org/abs/2104.12225

DC3:Alearningmethodforoptimizationwithhardconstraints

https://arxiv.org/abs/2104.12225

DC3这个工作尝试解决带有复杂约束的优化问题，这里的变量都是连续的，同时存在等式约束以及不等式约束。具体来说，如果决策变量有N个，同时存在M个等式约束，那么一开始我们使用神经网络先求得N-M个符合要求的解，然后使用等式约束求出其余的变量值，同时使用不等式约束来修正得到的解，最后计算损失函数反向更新参数来优化模型，其中损失函数具体包括三部分：目标函数、不等式约束以及等式约束损失。该方法的优点在于计算时间非常快，缺点在于目前的约束还是停留在线性约束上面，如何拓展到非线性约束也是一大挑战。

图9DC3框架示意图

5.如何与成熟的求解器结合？

对于与成熟的求解器结合结合解决组合优化问题也是一大研究热点，下面具体介绍两个工作：

DifferentiationofBlackboxCombinatorialSolvers

https://openreview.net/forum?id=BkevoJSYPB

DifferentiationofBlackboxCombinatorialSolvers

https://openreview.net/forum?id=BkevoJSYPB

BlackBox这个工作尝试将组合优化求解器变成深度学习模型中的可微构建块。具体来说，由于一个输入如图像等经过神经网络会得到连续的表征，然而求解器需要离散的输入。因此，该工作的重点是考虑如何将连续的表征转换成求解器的输入，反向梯度更新时又能将求解器的离散输出转换为神经网络的连续输入，训练一个端到端的框架。该工作的优点在于如果需要求出图片中两个点之间的距离，只需要输入一张图片，不需要对图像进行栅格化等额外操作，模型直接输出两个点之间的最短路径。

图10黑盒组合求解器算法流程图

Networkplanningwithdeepreinforcementlearning

https://dl.acm.org/doi/10.1145/3452296.3472902

Networkplanningwithdeepreinforcementlearning

https://dl.acm.org/doi/10.1145/3452296.3472902

该工作提出一个两阶段的优化方法尝试结合深度强化学习与精确求解器（NeuroPlan）来解决一个资源调度问题。为了克服精确求解器无法求解大规模的优化问题的困难，作者将优化过程分为两个阶段：第一个阶段使用强化学习方法学习一个离最优解较近的结果，缩小搜索空间的范围；第二阶段使用精确求解器求得最优解。在小规模优化任务中，对比只使用强化学习的方法，该方法能有更好的优化效果，同时能媲美精确求解器方法。此外，在大规模优化任务中，该方法同样能取得了最好的优化效果，然而对于精确求解器来说，超出了其求解规模导致无法计算。

图11NeuroPlan的两阶段混合方法示意图

6.如何处理更自然的原始输入？

在与成熟的求解器结合的工作中，可以处理图像输入，那么随着ChatGPT的出现，其能够理解自然语言的问题需求，使得以后根据问题理解直接自动建模并调用求解器求解成为了可能。

扫码阅读并收藏完整斑图路径：

斑图链接：https://pattern.swarma.org/article/240

讲者介绍

范长俊：国防科技大学系统工程学院副教授。研究方向包括图深度学习、组合优化、强化学习及其在智能决策、复杂系统和指挥控制中的应用。以第一作者或通讯作者在NatureMachineIntelligence、NatureCommunications、AAAI等顶级期刊和会议发表论文多篇。

图神经网络与组合优化读书会启动

现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。

为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在AIforScience中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚19:00-21:00举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！

详情请见：

加速经典算法效率，突破现实技术瓶颈：图神经网络与组合优化读书会启动

大模型热潮之后的未来新方向：图神经网络与组合优化|文献汇总

1.解码薛定谔的猫：量子物理和人工智能的新颖交叉

2.人工智能的黎明：从信息动力学的角度看ChatGPT

3.智能是什么？范畴论为通用人工智能提供普适框架

4.《张江·复杂科学前沿27讲》完整上线！

5.成为集智VIP，解锁全站课程／读书会

6.加入集智，一起复杂！

点击“阅读原文”，观看读书会回放返回搜狐，查看更多

【智能优化算法】蝴蝶优化算法

前言

算法原理

条件假设

香味

蝴蝶自然行为的数学模型

优缺点

伪代码

算法优化

改进的蝴蝶优化算法

编码方法

评价函数

重新定义迭代公式

轮盘赌选择

交叉操作

变异操作编辑

IBOA实施步骤

编辑

实验分析

实验环境与参数设置

测试实例结果比较

结论

参考文献编辑

代码

MATLAB

前言

蝴蝶优化算法(butterflyoptimizationalgorithm,BOA)是Arora等人于2019年提出的一种元启发式智能算法。该算法受到了蝴蝶觅食和交配行为的启发，蝴蝶接收/感知并分析空气中的气味，以确定食物来源/交配伙伴的潜在方向。蝴蝶利用它们的嗅觉、视觉、味觉、触觉和听觉来寻找食物和伴侣，这些感觉也有助于它们从一个地方迁徙到另一个地方，逃离捕食者并在合适的地方产卵。在所有感觉中，嗅觉是最重要的，它帮助蝴蝶寻找食物（通常是花蜜）。蝴蝶的嗅觉感受器分散在蝴蝶的身体部位，如触角、腿、触须等。这些感受器实际上是蝴蝶体表的神经细胞，被称为化学感受器。它引导蝴蝶寻找最佳的交配对象，以延续强大的遗传基因。雄性蝴蝶能够通过信息素识别雌性蝴蝶，信息素是雌性蝴蝶发出的气味分泌物，会引起特定的反应。通过观察，发现蝴蝶对这些来源的位置有非常准确的判断。此外，它们可以辨识出不同的香味，并感知它们的强度。蝴蝶会产生与其适应度相关的某种强度的香味，即当蝴蝶从一个位置移动到另一个位置时，它的适应度会相应地变化。当蝴蝶感觉到另一只蝴蝶在这个区域散发出更多的香味时，就会去靠近，这个阶段被称为全局搜索。另外一种情况，当蝴蝶不能感知大于它自己的香味时，它会随机移动，这个阶段称为局部搜索。

算法原理条件假设

蝴蝶的觅食、交尾

蝴蝶优化算法是模拟蝴蝶的觅食行为,该思想的条件假设如下:

1)所有的蝴蝶都应该散发出某种香味,使蝴蝶能够互相吸引.

2)每只蝴蝶都会随机移动,或朝着散发出更多香味的最佳蝴蝶移动.

3)蝴蝶的刺激强度受目标函数值的影响或决定.

当蝴蝶能感觉到其他任何蝴蝶的香味时并朝它移动,在该算法中,该阶段称为全局搜索.在另一种情况下,当蝴蝶不能感觉周围的香味时,然后它会随机移动这个阶段称为局部搜索.利用转换概率控制全局和局部搜索过程,其迭代公式为:

基于上述描述,蝴蝶优化算法的实施步骤如下:

香味

为了理解算法中“香味”是如何定义的，我们首先要理解气味、声音、光、温度等模态是如何引入算法的。原文中提出了三个名词：感觉模态c、刺激强度I 和幂指数a。在蝴蝶的感觉模态中，感觉意味着判断模态的形式并以类似方式对其进行处理，这里的“模态”是指能量的输入。模态的形态可以是气味，声音，光线，温度，但就BOA而言，模态对应的是香味。I 是物理刺激的大小，其与蝴蝶的适应度相关。那么这就好理解了，当一只蝴蝶散发出的香味更浓（适应度值更优）时，周围的其他蝴蝶可以感知并被其吸引。幂指数a 是强度增加的指数，其可以为正则表达式、线性响应和响应压缩：

a.响应扩展:当I 增加时，香味(f )比I 增长更快;

b.响应压缩:当I 增加时，f 比I 增长慢;

c.线性响应:当I 增加时，f 成比例地增加。

经实验证明，有时随着刺激的增强，昆虫对刺激变化的敏感性变得越来越低，也就是产生了抗性。因此为了估计I 的大小，在BOA中使用了响应压缩。

蝴蝶的自然行为主要基于两个点：I 的变化和f 的表示。l 与适应度的变化有关；f 是相对的，应该由蝴蝶相互之间感知而得。原文提到，当I 较弱的蝴蝶向I 较强的蝴蝶移动时，f 比I 增加得更快。因此，香味被表示为刺激物强度的函数：

其中c、a 为[0,1]内一随机值；a=1这种极端情况意味着一只蝴蝶发出的香味浓度会被其他蝴蝶以同样的能力感知，这相当于香味是在理想化的环境中传播，因此可以很容易地达到全局最优值；若a=0，这意味着任何一只蝴蝶散发出的香味都不会被其他蝴蝶感觉到，也就不存在“吸引”这个概念了。原文中将c 设为0.01，a 设为0.1。

蝴蝶自然行为的数学模型

结合前文内容，将蝴蝶的上述特征理想化：

a.所有的蝴蝶都可以发出气味，这使得蝴蝶间可以相互吸引。

b.每只蝴蝶都会随机移动或朝更香的蝴蝶移动，进而散发出更多的芳香。

c.蝴蝶的刺激强度受目标函数的影响或决定。

在全局搜索阶段，蝴蝶向更香的蝴蝶移动：

其中，g∗表示在当前最优解，r 是[0,1]内一随机数。局部搜索阶段可以表示为：

其中，xj、xk为解空间中的两个随机个体。在算法中，蝴蝶寻找食物、交尾可以在局部和全局范围内发生。因此，BOA中使用切换概率p 以在全局搜索和局部搜索之间进行切换，p 通常为0.8。

优缺点

BOF算法调节参数少,原理简单,易于实现，与常见的群智能优化算法一样容易陷入局部最优，后期迭代收敛速度较慢的特点。

伪代码

算法优化

参考郑洪清.改进的蝴蝶优化聚类算法的论文

改进的蝴蝶优化算法

由于基本的BOA算法聚类效果差,本文对其进行改进,提出一种改进的蝴蝶优化聚类算法.重新定义蝴蝶的局部搜索方式,同时结合轮盘赌选择、交叉操作和变异操作,提高算法的寻优能力,使聚类效果稳定.

编码方法

评价函数

重新定义迭代公式

轮盘赌选择

交叉操作

变异操作 IBOA实施步骤实验分析实验环境与参数设置

为了测试IBOA算法的正确性与有效性,选取6个基准测试函数来验证算法,包括1个人工数据集和5个从UCI( http://archive.ics.uci.edu/ml/index.php)数据库中选取了Iris、Wine、Glass、Cancer、CintraceptiveMethodChoice(简称CMC)5组实验数据,所有的实例均运行在处理器为Celeron(R)双核CPUT3100,1.90GHz、内存为4G的PC上,以MatlabR2010a编写代码.参数设置为:种群规模＝50、转换概率＝0.1、c的初值为0.01,迭代次数N_iter＝200和交叉概率pc＝0.85.在问题规模一致的情形下,这些算法的复杂度是相同的.

测试实例结果比较

(1)人工数据集1(set_data=250,d=3,K=5):为了展示IBOA的求解过程,分别计算第10代、第50代的求解结果如图1和图2中.并将算法独立运行20次的结果于表1中,Best表示最优解,Average表示平均解,Worst表示最差解,Std表示标准差.表1中其他算法与数据来源于文献[7],从表1中的计算结果可知IBOA的求解精度及鲁棒性均优于其他算法.

(2)UCI数据集:将算法独立运行20次,与近几年多种算法比较如表2–表7所示,其中表2–表6中的K-means、GA、ACO、PSO、HBMO、IDE算法数据来源于文献[3]且迭代次数为500时的计算结果,IBA算法数据来源于文献[7],IGSO算法数据来源于文献[2],BPFPA算法数据来源于文献[6];表7中K-means、PSO、ABC、BA和IBA算法数据来源于文献[7].从表2可知,IBOA算法求解效果与IBA、BPFPA相当,但比其余8种算法效果较好;从表3可知,IBOA算法与BPFPA求解效果相当,但比其余7种算法效果优越许多;文中的“－”表示未有相关数据.从表4可知,IBOA的求结果在迭代次数为200时优于IDE和其他算法;从表5可知,IBOA算法的精度和方差均优于其他算法;从表6可知,IBOA算法的求解效果差于IDE,与IBA、BPFPA效果相当,但优于其他算法;从表7可知,IBOA算法的求解效果与IBA、BPFPA相当,但优于其他算法.另外,图3展示了IBOA算法和BOA算法在Survival数据集的最优解收敛曲线图,从图3易知,IBOA算法的求解速度和精度较BOA算法高.IBOA求解Iris、Survival、CMC数据集的聚类效果图如图4–图6所示.

结论

将精英策略的思想重新定义蝴蝶优化算法的局部搜索迭代公式且遗传算法相结合提出了一种改进的蝴蝶优化聚类算法,通过求解1个人工数据集和5个UCI数据库中不同规模的数据,统计分析结果表明IBOA算法能够避免陷入局部最优,具有较快的收敛速度和较强的鲁棒性,能够有效解决聚类问题且与其他聚类算法相比具有一定优势.

参考文献代码MATLAB

BOA

function[fmin,best_pos,Convergence_curve]=BOA(n,N_iter,Lb,Ub,dim,fobj)%nisthepopulationsize%N_iterrepresnetstotalnumberofiterationsp=0.8;%probabibilityswitchpower_exponent=0.1;sensory_modality=0.01;%InitializethepositionsofsearchagentsSol=initialization(n,dim,Ub,Lb);fori=1:n,Fitness(i)=fobj(Sol(i,:));end%Findthecurrentbest_pos[fmin,I]=min(Fitness);best_pos=Sol(I,:);S=Sol;%Starttheiterations--ButterflyOptimizationAlgorithmfort=1:N_iter,fori=1:n,%Loopoverallbutterflies/solutions%CalculatefragranceofeachbutterflywhichiscorrelatedwithobjectivefunctionFnew=fobj(S(i,:));FP=(sensory_modality*(Fnew^power_exponent));%Globalorlocalsearchifrand

智能优化算法

智能优化算法-人工电场算法ArtificialElectricFieldAlgorithm（附Matlab代码）

CSDN-Ada助手:恭喜你成功写了第一篇博客！智能优化算法这个话题很有深度，你的文章解释得非常清晰，而且附带了Matlab代码，非常棒！我的建议是，你可以尝试更深入地探究这个领域，例如，可以写一些实际应用的案例分析，或是加入一些其他算法的对比分析等等，这样可以让读者更好地了解这个领域。期待你的下一篇文章！推荐【每天值得看】：https://bbs.csdn.net/forums/csdnnews?typeId=21804&utm_source=csdn_ai_ada_blog_reply1如果您持续创作，完成第三篇博客，并且质量分达到80分以上，在评论区就有机会获得红包奖励哦！

智能优化算法-白鲸优化算法Belugawhaleoptimization（附Matlab代码）

CSDN-Ada助手:非常感谢您分享的这篇博客，介绍了白鲸优化算法，让我对这种新的元启发式算法有了更深的了解。希望您能够继续分享自己的学习和研究成果，让更多人了解和受益。除此之外，如果您对深度学习、机器学习等相关领域有一定的了解，可以尝试将白鲸优化算法应用到这些领域中，探索更多的应用场景。同时，也可以关注一些其他的元启发式算法，比如遗传算法、粒子群算法等，不断拓展自己的知识和技能。再次感谢您的分享！如何写出更高质量的博客，请看该博主的分享：https://blog.csdn.net/lmy_520/article/details/128686434?utm_source=csdn_ai_ada_blog_reply2如果您持续创作，完成第三篇博客，并且质量分达到80分以上，在评论区就有机会获得红包奖励哦！

智能优化算法-猫和老鼠优化器CatandMouseBasedOptimizer（附Matlab代码）

CSDN-Ada助手:恭喜您又发布了一篇非常有价值的博客，介绍了猫和老鼠优化器的智能优化算法并附上了Matlab代码，这对于学习优化算法的读者们来说将会非常有帮助。希望您能够继续保持创作热情，分享更多有趣、实用的知识。建议您可以尝试探究一些新的优化算法，或者从实际应用场景出发，结合算法原理进行深入探讨。期待您的下一篇博客。CSDN正在通过评论红包奖励优秀博客，请看红包流：https://bbs.csdn.net/?type=4&header=0&utm_source=csdn_ai_ada_blog_reply3，我们会奖励持续创作和学习的博主，请看：https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply3

智能优化算法-袋獾优化算法TasmanianDevilOptimization（附Matlab代码）

CSDN-Ada助手:恭喜作者又一次分享了如此有价值的博客，学习了解到袋獾优化算法这种智能优化算法，收获颇丰。非常感谢作者提供了附带Matlab代码，让读者可以更深入地学习和实践。期待作者能够继续分享更多的优秀内容，可以考虑结合实际案例或是应用场景来分享，这样能够更好地帮助读者理解和应用。CSDN会根据你创作的前四篇博客的质量，给予优秀的博主博客红包奖励。请关注https://bbs.csdn.net/forums/csdnnews?typeId=116148&utm_source=csdn_ai_ada_blog_reply4看奖励名单。

智能优化算法-蜘蛛蜂优化器SpiderWaspOptimizer（附Matlab代码）

CSDN-Ada助手:非常感谢您分享这篇关于智能优化算法的博客，标题也很吸引人。恭喜您已经写了第5篇博客，持续创作是非常重要的，希望您能继续分享更多有价值的内容。下一步的创作建议是，可以尝试将这些算法应用于实际问题中，或者探索更多新颖的智能算法。期待您的下一篇作品！如何快速涨粉，请看该博主的分享：https://hope-wisdom.blog.csdn.net/article/details/130544967?utm_source=csdn_ai_ada_blog_reply5