大逃杀优化：Battle Royale Optimizer的二进制版本在离散问题中的应用

软件影响12（2022）100274原始软件出版物Battle Royale Optimizer用于解决二进制优化问题Taymaz Akana，b，Saeid Agahianc，Rahim Dehkharghanid，a伊斯坦布尔Ayvansaray大学，土耳其伊斯坦布尔b捷克共和国帕尔杜比采，帕尔杜比采大学，电气工程和信息学院c土耳其埃尔祖鲁姆技术大学d土耳其伊斯坦布尔Istanbik大学计算机工程系A R T I C L E I N F O关键词：优化离散优化大逃杀优化Binary Battle Royale优化A B标准Battle Royale Optimizer（BRO）是最近提出的一种仅用于连续问题空间的元启发式优化算法。BinBRO是BRO的二进制版本。BinBRO算法采用差分表达式，该差分表达式利用二进制向量之间的相异性度量而不是原始BRO算法中用于找到最近邻的向量减法运算符。为了评估BinBRO，我们将其应用于两个流行的基准数据集：无容量限制的设施定位问题（UFLP）和最大割（Max-Cut）图问题。BinBRO的开源MATLAB实现可在CodeOcean和GitHub网站上获得代码元数据当前代码版本V1.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2022-12可再生胶囊的永久链接https://codeocean.com/capsule/8988211/tree/v1法律代码许可证MIT许可证使用MATLAB R2020b创建的代码版本控制系统使用MATLAB的软件代码语言、工具和服务编译要求、操作环境依赖性如果可用，链接到开发人员文档/手册https://github.com/tami64/BinBRO_Max_UFLP/问题支持电子邮件taymazakan@ayvansaray.edu.trsaeid. erzurum.edu.trrahim.isikun.edu.tr1. 介绍从给定问题的一组候选解中选择最佳潜在解的过程称为优化[1];确定性或随机方法可以进行这种选择。确定性方法导航问题的整个状态空间并找到最优解;然而，这些方法对于具有非多项式（NP）性质的问题来说将是昂贵的。随机方法是处理这个问题的一种替代方法。科学和工业领域的许多现实问题都可以通过优化技术解决。在过去的二十年里，元启发式算法经常被用来解决优化问题[2]。进化算法（EA）、物理现象算法和群体智能（SI）是三种主要的随机元优化工具。达尔文模拟电磁力、重力、惯性力等物理定律，本文中的代码（和数据）已由Code Ocean认证为可复制：（https://codeocean.com/）。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。*通讯：Istanbul，34980，Istanbul，Istanbul，34980，Turkey，Istanbul大学计算机工程系电子邮件地址：taymazakan@topkapi.edu.tr（T. Akan），saeid. erzurum.edu.tr（S. Agahian），rahim. isikun.edu.tr（R.Dehkharghani）。https://doi.org/10.1016/j.simpa.2022.100274接收日期：2022年2月20日;接收日期：2022年3月12日;接受日期：2022年3月24日2665-9638/©2022作者。由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表软件影响杂志 首页：www.journals.elsevier.com/software-impactsT. Akan，S.Agahian和R.代哈尔加尼软件影响12（2022）1002742图1.一、BinB R O 管 道 软 件 程 序 的流程图。物理现象算法这些定律表现了个体最后，动物和昆虫等不同生物的群体活动激发了群体智能算法的发明。BRO算法不仅是一种基于人口的算法;它在2020年的创建为优化算法增加了一个新的类别，称为基于游戏的优化算法[17]。在基于游戏的算法中，玩家探索他们的表面，并与他们的邻居竞争作为潜在的解决方案。与基于SI的算法不同，玩家不合作以实现共同的目标;相反，他们试图击败所有对手并单独赢得比赛。在这项工作中，一个开源的MATLAB实现的BinBRO应用于无容量限制的设施选址问题（UFLP）和最大割图（最大割）二进制问题已被详细解释。 完整的源代码和数据集，结果和图表最近已在CodeOcean和GitHub上发布[18，19]。2. BinBRO算法BinBRO方法与其他优化算法类似，使用统一的分布随机地选择候选解（候选解），就好像玩家从零开始随机地分散在游戏场上一样。在均匀分布中，如果生成的随机值小于0.5，则给定的设施将被初始化为0或1。设施的数量等于解决方案的数量。每一个解都是一个d维的二进制向量，_=（_1，_ 2，������������对于不同的问题，这个向量可以有不同的解释;例如，在UFLP中，对应于解决���方案的设施（0表示关闭，1表示打开）。������������然后重复该过程多次迭代。在每次迭代中，将每个CS与其最近的邻居进行比较最近的邻居是使用Jaccard的相似系数[ 20 ]确定的当一个CS与其最近的邻居进行比较时，具有更大适应度值的解决方案（由适应度函数生成）将被命名为赢家，另一个被命名为输家。BinBRO算法采用各种策略来处理赢家和输家。该算法总是将一个变异任务应用于胜利者，就像在大逃杀游戏中一样当前获胜者的位置将被改变，以帮助他成为最终的获胜者。只有两个随机选择的比特的赢家解决方案将被翻转在突变过程中，为这个目的。另一方面，BinBRO算法[21]在失败者解决方案上执行交叉任务，如果它没有达到最大损失次数（如果它还没有死亡）。“最大丢失数”是一个必须提前定义的BinBRO参数。这种交叉已被用于三种配置：单点，两点和均匀。如果失败者在游戏中达到了最大的失败次数或死亡次数，它将在完成一个主要的变异任务后重新产生。死亡的玩家将在球场上的另一个合法位置重新产生，就像在大逃杀游戏中一样。这种基本突变取决于迭代，即，突变强度在初始阶段较高，但随着博弈场的缩小而降低。BinBRO算法将失败者（死亡）解决方案的位从1翻转为0，反之亦然。这背后的直觉是，就像大逃杀游戏一样，BinBRO通过减少解决方案相互竞争的空间来重复此过程，直到找到可接受的解决方案或满足“最大迭代次数”标准。请注意，在迄今为止找到的失败者或获胜者解决方案的每次解决方案更新之后，将2位突变应用于最佳解决方案。如果在此变异之后可以实现更优的适应度值，则最优解将被修改;否则，它将保持不变。3. 软件描述BinBRO算法已在MATLAB中实现。该方法已被应用到两个著名的基准数据集：无容量限制的设施位置和最大割图二进制优化问题。BinBRO流水线的流程图如图所示。1.一、该程序• Get_Dataset函数返回文件地址和所需的最佳值。������• creat_model函数返回一���个实例的结构���• BRO_Fun函数将BinBRO算法应用于编译���器实例，并返回结构和收敛曲线。该结构是一组绩效评估标准的项目• write_on_text函数生成一个文本文件，用于计算实例，并在运行预定数量的算法������• write_on_text_all函数为所有实例生成一个文本文件，并在运行预定次数的算法后将所有性能标准存储在其中。4. 影响BinBRO算法是最新的优化算法之一[21];它是解决二进制优化问题的可靠技术。该算法已应用于两个基准数据集，在下面的小节中解释。然而，为了利用该软件来解决其他二进制优化问题，（给定目标函数的）MATLAB函数文件应该被添加到包括“main_all. m”的文件夹中Eval=@MaxCut;"，在同一个文件夹中。4.1. 无容量限制设施选址问题在无容量限制的设施选址问题（UFLP）中，目标是确定哪一个设施站点应该开放的一组预定的设施站点，哪一个应该关闭。这些设施应该为预定的客户提供服务，这些客户将从最近的设施获得服务。我们关心的是使总成本最小化这一服务。该成本包括开设设施的成本加上客户端与设施的距离。在UFLP问题中，也称为因此，我们使用其二进制版本BinBRO算法来解决二进制优化问题，而不是使用Battle Royale算法的连续版本。BinBRO算法已经被T. Akan，S.Agahian和R.代哈尔加尼软件影响12（2022）1002743表1对UFLP中三个实例的结果进行定量评价Cap-71Cap-101第131章两点932615.8 932615.8 932615.8 0 1 0 851.64 0.11制服932615.8932615.8932615.8 0 1 0371.440.6单点796786.08 796648.4 797508.73 321.89 0.84 0.02 28631.96 11.37两点796751.67 796648.4 797508.73 285.325 0.88 0.01 30040.72 4.95制服796648.4796648.4796648.401 0 11010.163.33单点793749.27 793439.6 794299.9 421.453 0.64 0.04 73540.2 22.01两点793680.44 793439.6 794299.9 394.233 0.72 0.03 64445.68 22.12制服793508.4793439.6 794299.9 238.2030.92 0.01 44500.28 15.90表2对UFLP中三个实例的结果进行定量评价1000 - 100.00.05 - 100.009 - 100.0两点1973.619861940 13.24357347.9 2163.45制服1954.720001918 21.9457270.6 2099.07单点8076.381667973 54.805 57271.2 2484.92两点8074.9 81648013 42.45957356.20 2193.63制服8085.38160 7986 48.79257271.4 2159.05单点13485.7 13567 13367 67.335 57307.7 1971.88两点13494.913558 13398 51.898 57304.2 2080.49制服13477.1 13551 13411 42.354 57241.9 2936.37在标准的、可公开访问的来自OR-Lib的UFLP数据集上进行测试[22]。表1显示了从一些基准套件获得的各种性能测量的不同类型的交叉（单点，两点和均匀）的BinBRO的数值结果。所得结果表明，Bin-BRO算法对UFLP问题有较好的求解效果。我们只提供了一个子集的结果的基准数据集。在此表中，每行中的最佳值以粗体显示。第一列包括取自OR-Lib的基准套装的名称;第二列表示交叉类型，其他列显示每个性能标准的获得值4.2. 最大割问题图中的最大切割是至少是任何其他切割的大小的切割。换句话说，它是将图的顶点划分为两个互补集合S和T，两个集合之间有尽可能多的边。这个问题可以表述如下：目标是找到顶点集的子集S，该子集S在其自身和互补子集之间具有尽可能多的边。或者，需要具有尽可能多的边的二部子图。Binbro已经 还在OR-Lib的标准公开访问Max-Cut数据集上进行了测试[22]。表2显示了BinBRO在不同交叉类型下获得的数值结果，这些结果用于从一些基准套件中获得的各种性能测量。我们只提供了一个子集的基准数据集所获得的结果。所获得的结果表明，Bin-BRO可以产生有希望的结果最大切割。在此表中，每行中的最佳值以粗体显示。第一列包括取自OR-Lib的基准套装的名称;第二列表示交叉类型，其他列显示每个性能标准的获得值竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]R.D.诺顿，P.B.哈泽尔，《农业经济分析的数学规划》，麦克米伦出版社，1986年。[2]A. Lazar，使用遗传算法和粗糙集启发式和优化知识发现的考古数据的启发式知识发现，IGI全球，2002年，第100页。263-278。[3] J. Holland ， Adaptation in Natural and Artificial Systems ： AnIntroduction Analysiswith Application to Biology ， Control Artiff. 内 特 尔（1975年）。[4]H.- P. Schwefel ， Evolution strategies ： A family of non-linear optimizationtechniquesbased on immigrating some principles of organic evolution，Ann. Oper.Res.1（2）（1984）165[5]F. Glover ， Future paths for integer programming and links to artificialintelligence，Comput.操作员13（5）（1986）533-http://dx.doi.org/10.1016/[6]P.J. Van Laarhoven，E.H. Aarts，《模拟退火：理论与应用》，Springer，1987，pp. 7比15[7]D. Simon，基于生物地理学的优化，IEEE Trans. Evol. Comput. 12（6）（2008）702http://dx.doi.org/10.1109/TEVC.2008.919004[8]R.A. Formato，中心力优化，Prog.电磁铁。第77（2007）号决议第425-491段。[9]E. Rashedi，H. Nezamabadi-pour，S. Saryazdi，Gsa：引力搜索算法，Inform。Sci. 179（13）（2009）2232 http://dx.doi.org/10.1016/j.ins。2009年3月4日。[10] A. Husseinzadeh Kashan，A new metaheuristic for optimization：Optics inspiredoptimization（oio），Comput.操作员Res. 55（2015）99 http://dx.doi.org/10。1016/j.cor.2014.10.011。[11] A. Kaveh ， T. Bakhshpoori ， 水 蒸 发 优 化 ： 一 种 新 的 物 理 启 发 优 化 算 法 ，Comput。Struct.167（2016）69-85，http：//dx.doi.org/10.1016/j.compstruc.2016.01.008网站。[12] A. Hatamlou，黑洞：一种新的启发式数据聚类优化方法。Sci. 222（2013）175http://dx.doi.org/10.1016/j.ins。2012.08.023。[13] A. Kaveh，S. Talatahari，A novel heuristic optimization method：Charged systemsearch，Acta Mech.213（3）（2010）267-http://dx.doi.org/10.1007/s00707-[14] V. Punnathanam，P. Kotecha，Yin-yang-pair optimization：A novel lightweightoptimization algorithm，Eng. Appl. Artif.内特尔54（2016）62 http://dx.doi。org/10.1016/j.engappai.2016.04.004。[15] A. Kaveh，A.陈晓，一种新的热交换优化算法。110（2017）69http://dx.doi.org/[16] H. Abedinpourshotorban，S. Mariyam Shamsuddin，Z.贝赫什蒂，DNA Jawawi，电磁场优化：一种物理启发的元启发式优化算法，Swarm Evol。Comput. 26（2016）8 http://dx.doi.org/10.1016/j。swevo.2015.07.002网站。[17] T. Rahkar Farshi ， 大 逃 杀 优 化 算 法 ， 神 经 计 算 。 （ 2020 ）http://dx.doi.org/10.1007/s00521-020-05004-4。交叉是说最好最糟糕STD击中间隙NFE时间单点932615.8932615.8932615.8010430.360.05实例交叉是说最好最糟糕STDNFE时间单点1948.11988190134.95957300.92181.9T. Akan，S.Agahian和R.代哈尔加尼软件影响12（2022）1002744[18] T. Akan，S.阿加希安河Dehkharghani，Binbro：Binary battle royale optimizeralgorithm [source code]，2022，http://dx.doi.org/10.24433/CO.3120150.v1.[19] T. Akan，S.阿加希安河Dehkharghani，Binbro_uflp，2022，检索自https：//github.com/tami64/BinBRO_Max_UFLP网站。[20] P.H. Saud，关于细菌分类的一些想法，微生物学17（1）（1957）184-200。[21] T. Akan，S.阿加希安河Dehkharghani，Binbro：Binary battle royale optimizeralgorithm ， Expert Syst. Appl. （ 2022 ） http://dx.doi.org/10.1016/j.eswa.2022.116599。[22] 比 斯 利 ·J·E· ， Or-library ： Distributing test problems by electronic mail ，J.Oper. Res. Soc. 41（11）（1990）1069