可比较的优化器分级和评分： 一种现代化优化技术性能分析方法外文翻译资料

 2022-10-27 10:10

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

可比较的优化器分级和评分：

一种现代化优化技术性能分析方法

摘要

优化技术的性能分析对于理解每一种技术的优缺点意义重大。找到一种在各种优化问题中表现相同的优化技术的情况并不常见，而且常见性能测试得出的数值、函数值(适应度)和函数求解次数并不具有代表性。比如，报告某优化技术O在基准函数B通过几次评估E达到适应度F在语义上并没有意义。这样的报告存在一些逻辑问题：a)其他的技术在同样的基准下表现如何，以及b)这个基准的特征是什么(例如，模态和可分性)。可比较的优化器分级和评分(CORS)提出一种易于应用和解释的方法用于研究优化技术的解决问题能力。CORS提供了八种基于基本性能测试(即达到的适应度，功能评估的数量以及消耗的时间)建立的新性能测试。CORS性能测试表现了某优化技术在同一基准上和其他技术的表现的对比，这使得结果更有意义。此外，这些性能测试结果都被标准化为从1到100的值，使得这些结果具有较好的可解释性。同时，所有的CORS性能测试都是可整合的，这些结果很容易在常见的特征定义优化问题(如维度，模态和可分性)中整合和表示，而不是按各基准函数来表示(如F1， F2和F3)。为了验证CORS的有效性，它被应用到八种近期提出的内启发式新型优化技术的性能数据，即，蝙蝠算法(BA)，杜鹃搜索(CS)，差分搜索(DS)，萤火虫算法(FA)，引力搜索算法(GSA)，一阶杜鹃搜索(ORCS)，可分离自然进化策略(SNES)以及指数自然进化策略(xNES)。这些性能数据是在16种基准函数和6个维度下的96次测试中生成的。除了基本性能数据和CORS性能数据还同时得出了整合的CORS结果，以帮助了解被检测的技术的性能。

  1. 引言

优化设计在应用科学、工程学以及经济金融中具有广泛应用，由于资源和时间的限制，高效利用能得到的最佳工具非常重要。

优化问题在不同的方面会有显著的不同，这使得构建优化技术的任务更加困难。这些方面可以看作定义一个优化问题的通用特征(Molgaamp;Smutnicki, 2005; Qing, 2009; Tangetal, 2007)，包括但不限于，维度，模态以及可分性。最成功的技术是那些可以在最宽的问题范围内实现更多令人满意的性能结果的优化技术。

问题的维度是指要优化的维数(输入变量或参数)。随着维数的增加问题的复杂度会急剧增加。

优化问题的模态通常被定义为多模态或单模态。如果一个问题除了具有全局最优解之外还有局部最优解，则可定义为多模态；反之如果只具有全局最优解而不具有局部最优解则可定义为单模态。多模态问题通常更具欺骗性，因此更加复杂。

优化问题的可分离性通常被定义为不可分离或可分离。一个问题被定义为不可分离表示它的维度间具有相关性；问题被定义为可分离则否定了这些维度之间的相关性，这解释了可分离性问题各维度可以分别优化的原因。不可分离性问题更加困难，因为优化技术需要保证好几个维度在正确的路径上(或接近正确的路径)。

每年有很多新的研究内容被提出来探究现存或新提出的优化技术的性能潜力。除了少数例外情况，这些性能结果通常都在一个基准或测试函数的基础上表示，这分别为各个基准函数提供了大量的统计数据和统计信息。依靠这样的数据表示方式来为现实问题选择最合适的优化技术并不是一个简单的任务。在明确地决定使用哪种技术之前，研究者需要用他们的问题去衡量一种或多种共用常见特征的基准函数，自行比较不同技术的性能结果。对于这样的常见场景，用一种基于常用优化问题定义特征(比如，低维数，多模态或不可分离)的更加明晰易用的结果表示来代替基于单个基准函数的数据表示(如，F1，F2和F3)，可以让我们更好的理解这些优化技术以及它们的性能。

优化技术性能分析的两种最有趣和相关的平台是通过比较连续优化器(COCO)平台(“COCO，” 2015)实现的黑盒优化基准(BBOB)工厂和黑盒优化竞赛(BBComp) (“BBComp,” 2015)，它们都采用了通过问题特征来表示性能结果的概念。BBOB和BBComp都是按照遗传和进化计算会议(GECCO)和IEEE进化计算国际大会(CEC)来组织的。它们集中了多种优化技术，这些技术通过了一系列限定在特定实验设定下的预置了包含不同特征(Hansen, Auger, Finck, amp;Ros, 2013; Lietal., 2013; Liang, Qu, amp;Suganthan, 2013)的基准函数的测试。性能结果在测试后通过表格或图形表示。这些结果可按一种特定的基准函数表示或按一组具有特定特性的基准(例如，维度或模态)表示。

到目前为止，除了两个主要不同点外，CORS和BBOB及BBComp采用了相同的工作理念。第一个不同，CORS主要是一个性能分析方法，而不是一个分析平台。也就是说，它并不是脱离特定的基准和实验设定来工作。与之相反，它可以被应用到任何基准及分析优化技术性能的研究中，包括BBOB和BBComp。第二个不同是分析优化技术性能的方法。与BBOB和BBComp采用的方法不同，CORS提出了一种改进的可以克服常用性能分析方法的限制的新方法。

在COCO系统中，预计运行时间(ERT) (Augeramp;Hansen, 2005; Price, 1997)是评估被测优化技术的主要测量内容。ERT描述了达到目标函数(例如，某基准函数的最优适应度)的预计函数执行量。ERT的计算方式如Eq.(1)所示，其中RTS和RTUS分别是实验成功和实验失败的平均函数执行数，ps是成功实验数的分数。

(1)

在BBComp中，核心的评估方法和一级方程评分系统类似，即最好的10个等级在1到25分之间打分，其它的等级打零分(“BBComp,” 2015, “Formula One regulations,” 2015)。性能由在给定性能预算内得到的最佳函数值决定(例如，最大适应度函数执行次数)。考虑一个CEC大规模全局优化的例子(Li, Tang, Yang, amp;Molina, 2015)，用中位数来给相应优化技术来打分，其中25级排在第一位，第6级排在第七位。Eq.(2)使用了一种基于被测优化技术数量的更具适应性的系统。，其中n为优化技术的数量，k为从1(表现最好者)到n(表现最差者)的不同等级。

(2)

COCO使用固定目标的测试场景来计算ERT，而BBComp使用固定开销的测试场景来进行打分系统的计算。在固定目标的测试方法中，优化技术会持续运行直到达到特定的目标。在固定开销的测试方法中，优化技术会持续运行到允许的资源预算消耗完毕。在使用固定目标测试方法时，需要额外使用一个次级停止判据来防止优化技术无限运行下去。在这种情况下，ERT会把这次实验当作失败，相应的优化技术即使十分接近目标也不会得到奖励。而能够克服这项限制将会很有意义。在另一方面，BBComp打分系统中用到的固定开销测试方式并不考虑所测优化技术的函数结果之间的实际差别大小。考虑一个n = 25(优化技术数量)的例子，最好的和第二好的测试技术总会被分别打分为2.56和1.87，而不会考虑它们的函数值间的差别是否会过小或过大。而且，如果多个优化技术得到同样的最有函数值，它们将会共同被定为第一级。此外，所有的等级大于等于n/2的优化技术都不会被奖励，而且被评为零分。这些限制值得被考虑。尽管COCO和BBComp可以提供其它性能测试，ERT和一级方程打分系统是比较被测优化技术性能的主要因素(“BBComp: FAQ,” 2015; Hansen et al., 2013)。

本论文的目标是定义一种用于优化技术性能分析的新方法，并将它应用于所选的一些优化技术的实证性能结果。这篇论文的剩余部分如下组织：第2章是对所选的技术的综述，第3章是所选技术的性能比较，第4章是本文提出方法的介绍和应用，第5章是讨论，第6章是结论。

  1. 所选技术的概念综述

优化算法可以用几种不同的方法来分类。从简单的角度来看，这些算法可被分类为确定性的和随机性的。如果一种算法按照机械方式运作，不包含任何随机性，则被称为确定性的。如果算法中具有一些随机性，则被称为随机性的，如遗传算法(GA) (Goldberg, 1989)和粒子群算法(PSO)(Kennedy amp; Eberhart, 1995; Poli, Kennedy, amp; Blackwell, 2007)。在近期的文献中，具有随机分量的算法通常被称作启发式或元启发式(Glover amp; Kochenberger, 2003; Talbi, 2009)。本论文选择了八种自然元启发式算法作为探究的示例。

    1. 蝙蝠算法(BA)

蝙蝠算法是在2010年基于蝙蝠(或迷你蝙蝠)的回声定位行为提出来的(Yang, 2010a)。蝙蝠在搜寻猎物时在位置(解)Xi随机以速度Vi飞行，并且会根据猎物的距离调节声波的频率Q，响度A和脉冲发射率r。当一个新的位置被发现时，这个位置立即会被和它的相关位置及全局最优位置比较，以此来决定蝙蝠下一步运动的最佳位置。BA算法也可以被视为PSO算法和和声搜索算法(HS)(Geem, Kim, amp; Loganathan, 2001)的拓展应用，因为将A和r固定在特定值会产生非常接近标准PSO算法或HS算法的行为(Yang, 2010a; Yang amp; Gandomi, 2012)。BA算法和其他算法如GA算法，PSO算法以及HS算法的性能比较显示BA算法可能比这些算法更加强大(Yang, 2010a; Yang amp; Gandomi, 2012)。

    1. 杜鹃搜索(CS)

CS算法在2009年被提出(Yang amp; Deb, 2009)，它的启发来自某些杜鹃鸟种的育雏寄生现象和莱维飞行随机漫步模型(Barthelemy, Bertolotti, amp; Wiersma, 2008; Fogedby, 1994; Pavlyukevich, 2007)。杜鹃的侵略性繁殖策略引起了科学家的兴趣，某些品种的杜鹃会将蛋下在其它宿主鸟(大多数是其他鸟种)的窝里并将这些宿主鸟的蛋推出窝外来提高自己的蛋的孵化率。CS算法是这些行为的理想化，每只杜鹃一次只下一个蛋并把蛋随机放在某个巢(解)里，最好的巢和高质量的蛋才可以孵出下一代。杜鹃可找到的宿主巢数量是固定的，宿主鸟有一定概率因为发现杜鹃蛋而扔掉它们或放弃旧巢去建新巢。最近的研究表明CS算法可能比GA算法，PSO算法和差分进化算法(DE)DE)(Price, Storn, amp; Lampinen, 2005; Storn amp; Price, 1997)效率更高(Civicioglu amp; Besdok, 2013; Yang amp; Deb, 2009, 2010)。

    1. 差分搜索(DS)

DS算法在2012年被提出(Pinar Civicioglu, 2012)，它的启发来自超级有机体在一年内随着环境的变化而进行的迁移，还采用了布朗随机漫步模型的概念(Pinar Civicioglu, 2012; Mohd Herwan, 2013)。有机体在迁移到新的区域前会尝试寻找所在区域的更肥沃的区域(解)。有趣的是，CS算法，DS算法和ORCS算法(Tawfik, Badr, amp; Abdel-Rahman, 2013)都结合了随机行走理论如莱维飞行、布朗运动和均匀/高斯分布随机采样的优势，而且它们选择进入下一次搜索迭代的最优解的方法十分接近。据研究，DS算法解决问题的性能与人工蜂群算法(ABC)(Basturk amp; Karaboga, 2006; Karaboga amp; Basturk, 2007)，协方差矩阵自适应进化策略(CMA-ES)(Hansen, Muuml;ller, amp; Koumoutsakos, 2003)，DE算法的一些变种，GSA算法(Rashedi, Nezamabadi-Pour, amp; Saryazdi, 2009)以及PSO算法(Civicioglu, 2012; MohdHerwan, 2013)的一种变种接近。

    1. 萤火虫算法(FA)

萤火虫算法是在2008年基于萤火虫的闪光行为提出的(Yang, 2010b, 2010c)。基本的FA算法规则很直接，所有的萤火虫都是双性的，所以一只萤火虫(解)可以被其它任何一只萤火虫吸引。两只萤火虫之间的吸引力与亮度相关，对于任意两只萤火虫，闪光亮度低的那一只会向着闪光更亮的那一只移动，而且它们可能会随着相互距离的增加而降低自身闪光亮度。萤火虫的闪光亮度(质量)由它们的定义域(即，要优化的问题的目标函数)确定。FA算法和PSO算法在步骤上具有相似性，但是FA算法采用了一些额外的步骤来帮助提升算法的搜索性能(Yang, 2010b)。GA算法，PSO算法和FA算法的模拟结果显示FA算法要优于其它两种算法(Yang, 2009, 2010b)。

    1. 重力搜索算法(GSA)

重力搜索算法是在2007年根据万有引力定律和质量相互作用提出的Rashedietal., 2009)。GSA算法的搜索媒介是一系列孤立的质量块，这些质量块根据牛顿引力与运动规律互相作用以及受到其它质量块形成的引力环境的作用。经过测试，GSA算法在一些标准基准上比PSO和其他算法性能表现更好(Chatterjee, Mahanti, amp; Pathak, 201

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153818]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章