logo资料库

布谷鸟搜索算法:最近的进展和应用（论文）.docx

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.05M 资料格式：docx 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    布谷鸟搜索算法:最近的进展和应用
    1介绍
    布谷鸟搜索算法:最近的进展和应用 摘要 布谷鸟搜索(CS)是由 Yang 和 Deb 在 2009 年开发的一种相对较新的算法，在解决全局优 化问题上具有同样的效率。本文回顾了布谷鸟搜索的基本思想和最新的发展情况及其应用。 我们对算法进行了分析，并对其搜索机制进行了深入的分析，并找出了其有效的原因。我们 还讨论了算法的本质及其与自组织系统的联系，最后提出了进一步研究的一些重要课题。 1 介绍 优化涉及许多领域，应用范围很广。随着时间的推移，金钱和资源总是有限的，优化变得越 来越重要。例如，许多工业问题的节能设计和绿色解决方案需要思维和设计实践的范式转换。 另一方面，人们想要智能和智能的产品，而计算智能已经成为一个很有潜力的领域，可能产 生广泛的影响。目前机器学习经常使用优化算法来提高学习性能，而优化也借鉴了机器学习 的思想，如统计学习理论和神经网络。在这篇文章中，我们将重点介绍布谷鸟搜索作为一种 强大的、受自然启发的元启发式算法，用于优化和计算智能。 在几乎所有的工程和工业的应用中，我们总是试图优化某些东西——无论是最小化成本和能 源消耗，还是最大化利润、产出、性能和效率[19,37,40]。任何种类的可用资源的最佳使用 都需要科学思维范式的转变;这是因为大多数实际应用程序都有更复杂的因素和参数来影响 系统的行为。对于任何优化问题，优化过程的集成组件都是优化算法、高效的数值仿真器和 我们希望建模和优化的物理过程的现实表示。这通常是一个耗时的过程，在许多情况下，计 算成本通常很高。一旦我们有了一个好的模型，整体的计算成本由用于搜索的优化算法和用 于模拟的数值求解器来确定。 优化算法是求解优化问题的工具和技术，目的是找到其最优性，但这种最优性并不总是可达 到的。由于不确定性几乎总是存在于现实世界的系统中，因此对最优性的搜索更加复杂。因 此，我们不仅要寻求最优设计，而且要在工程和工业上进行稳健的设计。最优的解决方案不 够健壮，在现实中是不切实际的。在这种情况下，次优解或良好的鲁棒解决方案通常是选择。 优化问题可以用很多方法来表述。例如，常用的最小二乘方法是一种极大似然公式的特例。 到目前为止，最广泛的公式是将非线性优化问题写成：
    其中 fi、hj 和 gk 均为非线性函数。这里，设计向量或设计变量 x＝（x1,x2……xd）可以是 连续的、离散的或混合的一维空间。函数 fi 称为目标函数或成本函数，当 M>1，优化是多 目标或多值[37]时。将不同的目标合并成一个单一的目标是可能的，尽管多目标优化可以提 供更多的信息和对问题的洞察。值得指出的是，在这里我们把问题写成一个最小的优化方法， 它也可以被写成一个最大化的方法，只是用 fi( x)的方法来代替-fi( x)。 当所有的函数都是非线性时，我们处理的是非线性约束问题。在某些特殊情况下，当 fi、hj 和 gk 是线性时，问题就变成线性的，我们可以使用像单纯形法这样广泛的线性规划技术。 当一些设计变量只能取离散值(通常为整数)时，当其他变量是实数连续时，问题是混合类型， 这通常很难解决，特别是对于大规模优化问题。 2 优化算法的本质。 2.1 优化算法 优化是寻找一个特定问题的最优解的过程，而这个搜索过程可以使用多个代理来进行，这些 代理本质上形成了一个演化代理的系统。这个系统可以根据一组规则或数学方程来迭代。因 此，这样的系统将会显示出一些突现的特征，从而导致自组织状态对应于搜索空间中的一些 最佳的条件。一旦达到自组织状态，我们说系统收敛。因此，设计一种高效的优化算法等价 于模拟自组织系统的演化[1,17]。 2.2 算法的本质。 从数学上讲，算法是一种为给定的输入集生成输出的过程。从优化的角度,优化算法生成一 个新的解决方案 x^(t+1)给定问题从一个已知的解决方案 xt 在迭代或时间 t。式子如下 其中 A 是一个从给定的解 x^t 维向量到一个新的解向量 x^(t+1)的非线性映射。算法 A 具有 k 算法相关参数 pt=(p1，……pk)可与时间有关,因此可以进行调优。 为了找到一个给定的最优化问题的最优解 x，在一个常无限的状态下，根据一些预定义的标 准，从所有的状态中选择一些期望的状态。
    在这里，最终的收敛状态/对应于问题的最优解决方案 x。设计的系统状态空间的选择是由运 行优化算法 a 算法的行为控制的参数 p,最初的解决方案 x^(t=0)和停止标准 D .我们可以查看 组合 S+A(t)作为一个复杂系统的自组织能力。 状态的变化或感兴趣的问题的解决方案是通过算法 a 在很多经典算法如爬山、年代的问题 是使用梯度信息,选择国家,说,景观的最小值,和停止标准可以给定公差或准确性,或零梯度 等。 一个算法可以像一个工具来调整一个复杂的系统。如果一个算法不使用任何问题的状态信 息，那么算法就更有可能是通用的处理多种类型的问题。然而，这种黑盒方法也暗示着，算 法可能没有效率，因为它可能是一种特定类型的问题。例如，如果优化问题是凸的，使用这 种凸性信息的算法比不使用这些信息的算法效率更高。为了有效地选择状态/解决方案，应 该使用搜索过程中的信息来增强搜索过程。在许多情况下，这些信息通常被输入到算法的选 择机制中。到目前为止，最广泛使用的选择机制是选择或保留目前为止发现的最好的解决方 案。这就是“适者生存”的最简单形式。 从优化过程的示意图(5)中可以看出，算法的性能也可能取决于它所解决的问题类型。另一 方面，最终的全局最优性是可以实现的(在一定数量的迭代中)也取决于所使用的算法。这可 能是另一种表述所谓的不自由午餐定理的方法。 优化算法可以是非常多样化的，有几十个被广泛使用。不同算法的主要特征仅依赖于 A(t) 的实际的、非线性的、经常隐式的形式(t)及其参数 p(t)。 2.3 算法的效率。 一种高效的优化算法对于保证最优解的可达性非常重要。算法的本质是正确实现搜索或优化 过程，从而实现所需的搜索(虽然不一定有效)。它可以与其他建模组件集成和链接。文献中 有许多优化算法，没有一种算法适用于所有问题[36]。 算法可以分为确定性的或随机的。如果一种算法以一种机械的、没有任何随机性的方式工作， 它叫做确定性。对于这样的算法，如果我们从相同的起始点开始，它将到达相同的最终解决 方案。爬山和下坡单纯形是确定性算法的好例子。另一方面，如果算法中有一些随机性，算 法每次运行算法时通常会到达不同的点，即使我们从相同的起始点开始。遗传算法和随机重 新启动的爬坡是随机算法的好例子。 对当前的元启发式算法进行了更详细的分析，我们可以找出特定算法所采用的随机性的类 型。例如，最简单且通常非常有效的方法是引入一个确定算法的随机起点。著名的爬坡与随 机重启是一个很好的例子。这种简单的策略在大多数情况下都是有效的，并且在实践中很容 易实现。在算法中引入随机性的一种更为复杂的方法是在算法的不同部分中使用随机性，在 这种情况下，我们通常称这种算法为启发式算法，或者更常见的称为元启发式[37,38]。 元启发式算法通常是由自然激发的，它们现在是最广泛使用的优化算法之一。它们比集合算 法有很多优势[13,37]。元启发式算法非常多样化，包括遗传算法、模拟退火、差分进化、
    蚂蚁和蜜蜂算法、bat 算法、粒子群优化、和谐搜索、萤火虫算法、布谷鸟搜索等[14、18、 38、39、41]。这里，我们将详细介绍布谷鸟搜索。 3 布谷鸟搜索与分析。 3.1 布谷鸟搜索 Cuckoo search (CS)是由 Xin-She Yang 和 Suash Deb[42-44]于 2009 年开发的最新的自然 启发的元启发式算法之一。CS 是基于一些布谷鸟属的寄生寄生。此外，这种算法通过所谓 的 Levy 飞行[24]，而不是简单的各向同性随机游动来增强。最近的研究表明，CS 可能比 PSO 和遗传算法更有效[42]。布谷鸟是一种迷人的鸟类，不仅因为它们能发出动听的声音， 还因为它们具有侵略性的繁殖策略。一些物种，如 ani 和 Guira cuckoos，在公共巢穴中产 卵，尽管它们可能会移除其他的卵，以增加它们自己卵的孵化概率。相当多的物种通过将卵 产在其他寄主鸟类的巢穴(通常是其他物种)中，来参与这种寄生的孵育寄生。 为了简单地描述标准布谷鸟搜索，我们现在使用以下三个理想化的规则: 1.每只布谷鸟每次下一个蛋，并将其放入随机选择的巢中。 2.具有优质蛋的最佳巢会被带到下一代。 3.可用的寄主巢数量是固定的，且寄主以概率 Pa∈(0,1) 发现布谷鸟放的蛋，在这种情况下， 寄主可以消灭该蛋或放弃旧巢另建新巢。 作为进一步的近似值，最后的假设可以用新巢所代替的 n 个主巢的分数 pa 来近似(用新的随 机解)。对于一个最大化问题，解决方案的质量或适合度可以与目标函数的值成正比。其他 形式的适应度可以用类似于遗传算法的适应度函数来定义。 实施的角度来看,我们可以使用以下简单的表示,每个蛋巢中代表一个解决方案,并且每个布 谷鸟只能躺一个蛋(因此代表一个解决方案),其目的是使用新的和潜在的更好的解决方案(布 谷鸟)来取代一个不好解决的巢穴。显然，这个算法可以扩展到更复杂的情况下，每个蚁巢 都有多个代表一组解决方案的卵。对于目前的介绍，我们将使用最简单的方法，每个巢只有 一个蛋。在这种情况下，蛋、巢和布谷鸟之间没有区别，因为每个巢对应一个蛋，也代表一 个布谷鸟。 该算法采用局部随机游走和全局探索性随机游走的平衡组合，由开关参数 pa 控制。本地随 机漫步可以写成: xtj 和 xtk 是随机排列随机选择的两个不同的解，H(u)是一个维数函数，是从均匀分布中抽取 的随机数，s 是步长。另一方面,随机游走是由使用列维飞行
    这里，a>0 是步骤大小比例因子，它应该与兴趣问题的规模相关。在大多数情况下，我们可 以使用 a = O(L/10)，其中 L 是感兴趣问题的特征尺度，而在某些情况下，a = O(L/100)可以 更有效，避免飞得太远。上面的方程本质上是随机游走的随机方程。一般来说，随机游走是 一个马尔可夫链，它的下一个状态/位置只取决于当前位置(上式中第一项)和转移概率(第二 项)。然而，大量的新解决方案应该由远场随机化产生，它们的位置应该远远超过目前最好 的解决方案;这将确保系统不会陷入局部最优[42,43]。 布谷鸟搜索的文献正在迅速扩大。有很多关注和最近的研究使用布谷鸟搜索的不同范围的应 用[5,6,9 - 11,13,16,45]。Walton 等人通过制定改进的布谷鸟搜索算法[34]改进了算法[0]，而 Yang 和 Deb 将其扩展到多目标的优化问题[44]。 3.2 为什么布谷鸟搜索如此高效? 粒子群优化的理论研究表明，粒子群算法可以快速收敛到目前最好的解决方案，但不一定是 全局最好的解决方案[7,15,35]。实际上，一些分析表明，PSO 更新方程不能满足全局收敛 条件，因而不能保证全局收敛性[26]。另一方面，它证明了布谷搜索满足全局收敛要求，从 而保证了全局收敛性[35]。这意味着对于多模态优化，PSO 可能会过早地收敛到局部最优， 而布谷鸟搜索通常会收敛到全局最优性。 此外，布谷鸟搜索有两个搜索功能:局部搜索和全局搜索，由切换/发现概率控制。如第 3.1 节所述，本地搜索非常密集，约占搜索时间的 1/4 (pa = 0.25)，而全局搜索约占总搜索时间 的 3/4。这使得在全球范围内可以更有效地探索搜索空间，并且可以通过更高的概率找到全 局最优性。 布谷鸟搜索的另一个优势是，它的全球搜索使用的是列维飞行或过程，而不是标准的随机漫 步。作为列维飞行有无限的均值和方差,布谷鸟可以探索更有效地搜索空间比标准算法的高 斯过程。这一优势，结合本地和搜索能力，保证了全球的融合，使得布谷鸟搜索非常高效。 事实上，各种研究和应用表明布谷鸟搜索非常有效[8,13,14,28,34,43]。 4 应用程序 布谷鸟搜索已在许多优化和计算智能领域中应用，并具有良好的应用前景。例如，在工程设 计应用中，布谷鸟搜索在一系列连续优化问题上优于其他算法，如弹簧设计和焊接梁设计问 题[13,14,43]。 另外，沃尔顿等人[34]所做的一个修正的布谷鸟搜索结果表明，它对于解决网格生成等非线 性问题是非常有效的。Vazquez[33]使用布谷鸟搜索来训练神经网络模型，而 Chifu 等[5]利 用布谷鸟搜索优化语义 web 服务组合过程。此外，Kumar 和 Chakarverty[20]利用布谷搜索
    实现了可靠的嵌入式系统的优化设计，Kaveh 和 Bakhshpoori[16]利用 CS 成功设计了钢架。 Yildiz[45]利用 CS 在铣削操作中选择最优的机器参数，得到了增强的结果，而郑和周[46]用 高斯过程提供了布谷鸟搜索的变体。 另一方面，由 Tein 和 Ramli[30]提出了离散布谷鸟搜索算法来解决护士排班问题。布谷鸟搜 索也被用来为软件测试和测试数据生成提供独立的路径[6,25,28]。在数据融合和无线传感器 网络的背景下，布谷鸟搜索已经被证明是非常有效的[9,10]。此外，还开发了一种与量子方 法结合的布谷鸟搜索方法，有效地解决了背包问题[21]。从算法分析的角度出发，通过 Civicioglu 和 Desdo[8]对布谷鸟搜索与粒子群优化(PSO)、微分进化(DE)、人工蜜蜂群(ABC) 的概念比较，提出布谷鸟搜索和差分进化算法比 PSO 和 ABC 的结果更可靠。Gandomi 等[13] 为解决各种结构优化问题提供了更广泛的比较研究，并得出结论:布谷鸟搜索比其他算法(如 PSO 和遗传算法)获得更好的结果。Speed[27]修改了 Le vy cuckoo search，表明 CS 可以 处理非常大的问题。在不同的应用程序中，通过使用 cuckoo search 来训练神经网络，得到 了一个有趣的性能增强，如 Valian 等[31]和可靠性优化问题[32]。 对于复杂的相平衡应用，Bhargava 等[2]已经表明布谷鸟搜索提供了一种可靠的方法来求解 热力学计算。与此同时，Bulatovic 等[3]利用布谷库搜索解决了一个六杆双稳态联动问题， Moravej 和 Akhlaghi[22]已经解决了分布网络中具有良好收敛速度和性能的 DG 分配问题。 Taweewat 和 Wutiwiwatchai 联合布谷鸟搜索和监督神经网络来估计音乐音高的大小和准确 性[29]。 作为进一步的扩展，Yang 和 Deb[44]为设计工程应用程序设计了一个多目标的布谷鸟搜索。 对于多目标调度问题，Chandrasekaran 和 Simon[4]利用布谷鸟搜索算法取得了显著的进 展，这使得他们提出的方法的优越性被忽略了。 最近的研究表明，在许多应用程序中，布谷鸟搜索的性能明显优于其他算法[13,23,45,46]。 5 讨论和结束语。 基于群体智能的算法，如布谷鸟搜索和粒子群优化算法，在解决各种非线性优化问题上具有 十分重要的意义，在科学和工程领域有着广泛的应用。一些算法(如布谷鸟搜索)可以有很好 的全局收敛性。然而，在未来的研究中仍有一些需要解决的问题。 一个关键的问题是理论和实践之间存在着巨大的差距。大多数的元启发式算法在实际应用中 都有很好的应用，但对这些算法的数学分析还远远不够。事实上，除了对粒子群算法、遗传 算法和布谷鸟搜索等算法的收敛性和稳定性的一些有限结果之外，许多算法都没有理论分 析。因此，我们可能知道他们在实践中可以很好地工作，我们很难理解它为什么会起作用， 以及如何通过对其工作机制的良好理解来提高他们。 另一个重要的问题是，所有的元启发式算法都有基于算法的参数，这些参数的实际值/设置 将在很大程度上影响算法的性能。因此，适当的参数优化本身就成为一个优化问题。实际上， 参数调优是研究的一个重要领域[12]，值得更多的研究关注。
    此外，即使有很多算法很好的应用程序，这些应用程序中的大多数设计变量的数量都只有几 百个。如果变量的数量可以增加到数千甚至数百万，那么它将更有利于实际应用程序。 所有这些具有挑战性的问题可能在不久的将来激发更多的研究。毫无疑问，在未来的几年里， 越来越多的文学作品将会出现布谷鸟搜索的应用。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料