英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
鲸鱼群算法对求解最优化函数的应用
曾兵，高亮，李新宇
中国，武汉，华中科技大学
摘要：现如今，受自然启发的元启发式算法由于自身存在优于经典数值算法的优势，越来越多的被应用于解决现实生活中的最优化问题。本文对于求解最优化函数问题提出了一种新的受自然启发的元启发式算法——鲸鱼群算法。该算法来源于鲸鱼通过超声波交流进而实现的狩猎行为。本文将该算法与几种流行的元启发式算法进行了比较。实验结果表明，与其他算法相比，鲸群算法具有较强的优势。
关键词：鲸鱼群算法 超声波 自然启发 元启发式方法 最优化函数
- 绪论
自然启发式算法在解决数值优化方面彰显了越来越强大的功能，特别是在旅行商问题、车辆路径规划、分类问题、无线传感器网络路由问题和多处理机调度问题等NP难问题。这些实际的优化问题通常可能来自给定数学模型的多个全局或局部最优（即，目标函数）。如果将一个逐点的经典数值优化方法用于解决该类问题，经典方法每次[6]都要将花费大量的时间寻找不同的最优解，使得工作量大幅增加，工作效率降低。因此，受自然启发的元启发式算法凭借其易于实现，并且更快收敛到全局最优的优势，已然成为一个热门的研究课题。本文提出了一种基于鲸鱼群通过超声波进行的狩猎行为的新型受自然启发的元启发式算法——鲸鱼群算法，下文将对该算法进行阐述。
遗传算法(GA)最初由Holland提出，以解决数值优化问题[7]，它模拟了达尔文的基因选择和自然淘汰的生物进化过程，并揭开了自然启发的元启发式算法的序幕。该方法主要通过个体（染色体）选择、交叉和变异来尽可能寻找全局最优解。其中，通过结合两个个体的部分来创造新的个体的交叉算子显著地影响了遗传系统的性能[8]。时至今日，对于不同的优化问题，研究人员提出了不同的交叉算子来解决。例如，在处理调度优化问题时，Syswerda提出了一种基于顺序交叉算子(OBX)的置换编码方法[9]。从参考文献[10]可以看出对置换编码的交叉算子的详细回顾。突变是遗传算法中的另一个重要的算子，它在种群中提供随机的多样性[11]，从而防止算法的过早收敛。Michalewicz提出了随机(均匀)突变和非均匀突变[12]来解决数值优化问题。Deb提出的多项式变异算子是最广泛使用的变异算子之一[13]。从参考文献[14]可以看到对变异算子的全面介绍。总之，在处理不同的优化问题时，选择或设计合适的选择、交叉和变异算子是非常重要的。
Storn和Price提出的微分进化(DE)算法，以尽量减少可能的非线性和不可微的连续空间函数[15]。它包含与遗传算法不同的三个关键的操作，即突变、交叉和选择。首先，在微分进化算法的变异阶段产生一个与目标矢量的每个成员矢量相对应的供体矢量。然后，交叉操作发生在目标矢量和供体矢量之间，其中试验矢量是通过从供体矢量或具有交叉概率的目标矢量中选择分量而产生的。选择过程决定了目标矢量或试验矢量能否在下一代中存活。如果试验矢量更好，它将取代目标矢量;否则，目标矢量将继续保持在群体中。自方案提出以来，DE算法在解决许多实际的优化问题中越来越受到研究者和工程师的欢迎[16,17]，针对不同的实际问题衍生出了各种解决方案[18]。一般惯例用于命名不同微分进化算法是“DE/ x / y / z”,其中DE表示“微分进化”,x代表一个字符串指示基矢量的扰动程度,例如,它可以设置为“最佳”和“随机”,y表示扰乱x的矢量总数，z代表交叉操作的类型,z可以是二项式或指数形式[18]。常用的微分进化算法方案有DE/best/1/bin, DE/best/1/exp, DE/rand/1/bin, DE/best/2/exp, E/rand/2/exp等。
粒子群优化(PSO)是由肯尼迪和埃伯哈特提出的一种基于群体智能的算法，该算法的灵感来自于鸟类群集的社会行为[19]。自该算法被提出以来，已经被应用于解决许多复杂且困难的实际优化问题[20,21]。在传统的PSO算法中，每一个粒子都根据其速度和位置的更新，移动到一个新的位置，粒子位于该更新位置的速度与它的认知最佳位置和社会最佳位置有关。到目前为止，针对不同的优化问题科研工作者提出了大量的PSO变体模型。例如Shi和Eberhart在PSO (PSO- ldiw)[22]中引入了线性减少惯性权重[0]，它可以平衡全局搜索和局部搜索，用于函数优化；Zhan等提出了函数优化的自适应PSO (APSO)[23]，实现了参数的自动控制，提高了搜索效率和收敛速度，并采用了一种精英学习策略，跳出了可能的局部最优解；Qu提出了基于距离的局部通知PSO(LIPS)，消除了指定任何niching参数的需要，增强了PSO对多模态函数优化的精细搜索能力[6]等。
除此之外，还有大量其他的自然启发算法，如蚁群优化(蚁群算法)[24]、蜜蜂群优化(BSO)[25]和大爆炸(BB-BC)[26]等。对自然启发算法的全面综述已经超出了本文的范围，从[27,28]可以看到关于该主题的详细参考。
本文其余章节安排如下：第二章详细描述了所提议的鲸鱼群算法。第三章对实验装置进行主要介绍。第四章根据实验结果，对所提出的算法进行评价。第五章为全文总结和工作展望。
- 鲸鱼群算法
本章将首先介绍鲸鱼的行为，特别是鲸鱼的捕猎行为。随后进行鲸鱼群算法设计，并对该算法进行详细介绍。
2.1鲸的行为
鲸鱼是水生哺乳动物，拥有极高智力和强大的身体机能。目前，在海洋中大约生存着80种鲸鱼。它们是典型的群居动物，如怀孕的雌鲸会和其他雌鲸聚集在一起，以增强防御能力。抹香鲸经常在15到20个鲸的群体中，如图1所示。鲸的声音在海洋中是美妙的歌声，它们的音域非常宽广。迄今为止，科学家们已经发现了34种鲸类的声音，如吹口哨、吱吱声、呻吟、渴望、咆哮、颤音、滴答声、嗡嗡声、嘈杂声、交谈声、号角声等。这些声音通常与重要的功能联系在一起，比如它们的迁徙、觅食和交配模式。更重要的是，鲸鱼发出的声音很大程度上超出了人类的听觉范围，它们通过超声波确定食物的方位，并与彼此保持距离。
当鲸鱼找到食物来源时，它会发出声音通知附近的其他鲸鱼食物的质量和数量。因此，每只鲸鱼都会收到大量来自邻居的通知，然后根据这些通知移动到合适的位置寻找食物。鲸鱼通过声音相互交流的行为激励我们开发一种新的元启发式算法来解决函数优化问题。在本节的其余部分，我们将详细讨论鲸群算法的实现。
2.2鲸鱼群算法
为了研究鲸鱼群算法在求解函数优化问题中的应用，我们对鲸的一些捕猎规则进行了理想化的研究。为了简单描述我们的新鲸鱼群算法，我们采用了以下四种理想化的规则:（1）所有的鲸鱼在搜索区域都通过超声波进行交流;（2）每只鲸都有一定的计算能力来计算与其他鲸的距离;（3）每条鲸鱼发现的食物的质量和数量与其健康有关;（4）鲸的运动是由距离最近且健康状况更好的鲸所引导的，它被称为“最佳且最近的鲸鱼”。
迭代方程。无线电波和光波都是电磁波，没有任何介质可以传播。如果在水中传播，由于水的电导率高，它们会迅速衰减。然而，声波是一种机械波，它需要一种介质来传播，不管是水、空气、木材还是金属。超声波作为声波的一种，其传播速度和距离在很大程度上取决于介质。如超声波在水中的传播速度大约是1450米/秒，在空气中的传播速度大约是340米/秒。一些具有预先指定强度的超声波可以在水下100米左右移动，但只能在空中传输2米。这是因为机械波的强度被介质分子连续衰减，而在空气中传播的超声波的强度衰减得比水中快得多。公式表示超声波距声源距离d处的强度为：
（1）
其中为声源处超声波强度，表示自然常数，是衰减系数,取决于介质的物理化学性质和超声波本身的特点(如超声波频率)[29]。
由公式1可知,当衰减系数一定,超声波的强度rho;会随着传递距离d的增加呈指数级减少，这意味着当距离很远时，鲸鱼利用超声波传递的信息有极大的概率发生扭曲。因此，当距离很远时，鲸鱼不确定距离较远的其他鲸鱼发出的信息是否正确，故向与之相反方向或向任意靠近“最佳且最近”的鲸鱼方向前进。
由以上论述可知，在捕猎时鲸鱼会积极地、随机地朝靠近它的较好的、最近的鲸鱼移动，并向远离它的鲸鱼进行消极的、随机的移动。基于此原理，鲸鱼群会在一段时间后形成。每只鲸鱼都是随机游动的。随机运动能够使其更好的搜寻猎物，也是鲸鱼行为的一个重要特征，许多其他动物如蚂蚁、鸟类等也有此行为。这些约束激励我们找到一个新的位置迭代方程，使算法能够避免快速陷入局部最优，提高种群的多样性和全局的勘探能力，并有助于定位多重全局最优。鲸鱼X在“最佳”鲸鱼Y的引导下进行的随机移动可描述如下，
（2）
其中，和分别是鲸鱼X在第t和t 1次迭代中点i的位置值，表示鲸鱼Y在第t次迭代后点i的位置，表示鲸鱼X和鲸鱼Y间的欧几里得距离，表示从0到生成一个随机数。大量实验结果显示=2可适应大部分情况。
根据上文的描述，衰减系数由介质的物理化学性质和超声波特性共同决定。针对函数优化问题，上述的影响因素可以联系到函数的相关特性，如函数向量空间的维度，变量范围和峰值分布。因此，对不同的目标函数设定恰当的eta;显得尤其重要。为了使WSA更加适应工程问题，eta;的初始近似值可依据实验结果按如下设定：首先，令=0.5，=2，即=0.5，为两条鲸鱼在搜索空间内的最大距离，表示为，n是适应度函数的维数，和分别代表第i个变量的上限和下限。该公式表示当鲸鱼X和鲸鱼Y间的距离为时，公式（2）中=0.5（描述鲸鱼X的移动范围）。然后，可得，如此即可调整eta;为最优值或基于初始近似值的算法值。
公式2表明，如果鲸鱼的距离很小，那么它就会朝着它的“最佳”鲸鱼的方向移动。否则，它将向其“最佳”鲸鱼呈负向和随机移动，当适应度函数的维数为2时，可以用图2来说明。在图2中，红色的星星表示全局最优，圆圈代表鲸鱼，而假想线构成的矩形区域对应当前迭代中鲸鱼可到达的区域。
图2 鲸鱼运动的示意图，以它的“最佳”鲸鱼为指导
鲸鱼群算法的一般框架 基于上述规则，WSA的总体框架可以归纳为如图3所示。图中第六行的代表中群体的数量，即群体大小。第七行中的代表中的第i条鲸鱼。从图3可以看出，迭代计算之前的步骤是一些初始化步骤，包括初始化配置参数、初始化个体的位置和对每个个体进行评估，这与大多数其他的元启发式算法是相似的。在这里，所有的鲸鱼都被随机分配到搜索区域。接下来是WSA的核心步骤:鲸鱼移动(第5-13行)。即每只鲸鱼都需要通过集体合作来获得更好的食物。首先，一条鲸鱼应该找到它的“最佳”鲸鱼(第7行)，如图4所示，在第5行中的代表鲸的适应度值，位于第六行的dist(, )，表示和之间的距离。如果它的“最佳”鲸鱼存在，那么它将在“最佳”鲸鱼的指导下移动(图3的第9行)。如上所述，WSA的框架相当简单，这便于应用WSA解决实际的优化问题。
图3 WSA的总体框架
图4 寻找鲸鱼更好的和最近的鲸鱼的伪代码
- 实验装置
所提议的WSA和其他算法都是通过Microsoft visual studio 2015实现的c 编程语言，并在PC上执行，其中有2.3 GHz Intel core i7 3610QM处理器，8 GB RAM和Microsoft Windows 10操作系统。WSA的源代码可以从网站“https://drive.google.com/open?id=0B8qyXW8tulBqeGFUUmtKOV9sYWc”中下载。除了结合精英算法的遗传算法，非均匀算术交叉和基本位变异策略，DE/best/1/bin [30]和PSO与惯性权重[22]，以下4种流行的多模态优化算法也与WSA进行比较：最近被提出的PSO（LIPS）算法[6]，Speciation-based DE (SDE)[31] ， The original crowding DE (CDE) [32]和 The original crowding DE (CDE) [33]。在本文中，我们利用函数估算的次数作为这些算法的停止标准来测试它们的性能。
3.1测试函数
为了验证鲸鱼群算法的性能，本文引用Deb[34]、Michalewicz[12]、Li[35]和Thomsen[32]的研究，对12个基准测试函数进行了比较实验。测试函数F1-F8是具有多个全局或局部最优的多模态函数(F1-F6和F7-F10分别是低维和高维多模态函数)。F11和F12是具有100维的高维单峰函数。这些测试函数的基本信息见表1。函数F2-F6以找到全局最优值为目标，其余函数目标则是避免陷入局部最优(如果存在)，以寻找到全局最优解。所有的测试函数都是最小化问题。从表1可以看出,F7,F9,F11和F12全部于(0,0,hellip;,0)得到全局最优解，F10于（1,1，hellip;，1）得到全局最优解，均位于靠近可行域中间的部分。如我们所知，一些算法在优化函数时，最优解接近于可行域的中间部位时(特别是接近于零)是有效的，但当最优值不在可行域的中间时，其性能会很差。为了使实验结果更真实，我们在指定范围内随机生成数据赋予F7--F12.
表1.测试函数
表1.测试函数
3.2参数设置
虽然这些测试函数的全局最优值可以通过推导的方法得到，但它们仍然应该被视为黑盒问题，即这些测试函数的已知全局最优解在迭代过程中不能在WSA算法中使用，从而比较它们的性能。表1列出了每个函数的适应度值和全局最优值。设定一个适当的误差值（精度适当）检验所得解是否为全局最优解，若所得解与已知全局最优之差小于，则判断该解为全局最优解。表2中对误差，种群大小，鲸鱼群算法函数估计最大值及前文所提7种算法进行了比较。值得注意的是，一个具有更优级或更高维度的函数需要更大的种群规模和更多的函数评估。
表2
全文共8521字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13743]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
