《基于优化问题的多目标布谷鸟搜索算法毕业论文.doc》由会员分享，可在线阅读，更多相关《基于优化问题的多目标布谷鸟搜索算法毕业论文.doc（24页珍藏版）》请在三一办公上搜索。
1、基于优化问题的多目标布谷鸟搜索算法关键字：布谷鸟搜索、元启发式算法、多目标、最优化摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用
2、做了相关的分析。1. 简介在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个
3、已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的 Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近
4、似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些有利的求和方法将多目标问题归结到单一目标问题中去，在优化的过程中，我们需要大量的修改工作，除此之外，更困难的更具挑战性的是，怎样总结这些方法，使其有着足够的多样性，这样的话，这种新的解决方法就可以成为有效利用搜索空间的实例。而且，在真实的生活中
5、，优化问题往往包含了一些不确定性和干扰性，例如，材料的适应性对于一个产品的设计往往有着很重要的影响，一个优化的设计问题应该足够的完美使得对于设计者和决策者可以对很多不同种的东西提供一些更好的选择。尽管存在着这些挑战性，多目标优化问题仍存在着许多有效的算法使其在很多问题中有着成功的应用，此外元启发算法开始作为解决多目标优化问题的主角出现在大众面前，优化算法设计者以及科学家们经常模拟自然界中一些成功的范例来解决问题，例如，生物系统，很多新的算法也都开始出现并且在问题的解决中也有着很重要的应用。目前，有一种新的由杨新社教授和Suach Deb教授在2009年提出的元启发算法，名为布谷鸟算法，对于此种
6、算法，在最初的研究中就可以看出，其具有很高的前瞻性，比现有的PSO算法有着更好的性能，在本篇论文中我们将会对CS作以延伸，以便其可以解决多目标优化问题，而且可以建立一个基于多目标的布谷鸟搜索算法。第一步我们将通过建立一个多目标的检验函数来使问题具体化，然后我们会将其应用到工程优化问题中，包括双目标的光路设计和制动器设计。同时，我们也将讨论被提出的算法中其独有的特性，并且对文章做以进一步的研究。2. 多目标的布谷鸟搜索 为了对CS算法做以延伸来解决多目标的问题，我们在此先对布谷鸟有趣的繁殖行为规律做以简要的回顾，然后，我们将会对此算法的基本观点和步骤以及实际的算法过程作以概述。2.1 布谷鸟的繁
7、殖行为布谷鸟是一种有趣的鸟，它的有趣不仅是因为它动听的歌声，还因为其具有侵略性的繁殖策略。像美洲黑杜鹃这一种鸟类，它们会将自己的卵产在公共的巢穴中，并且，它们会将其他鸟类的蛋移出巢外以提高自己的蛋被孵化的几率，大多数鸟类通过产卵于其他寄主的巢中这种寄生性规律来完成自己孵化的任务，目前，存在着三种最基本的寄生性行为：种内产卵寄生性、合作式寄生性、巢穴接管。一些寄主可以直接发现这些入侵者，并与入侵的鸟类发生冲突，如果寄主发现其巢中的蛋不是自己的，它们便会扔掉这些蛋或者直接遗弃这个巢穴，在别处重新建立一个新的巢穴。一些像the New World brood parasitic Tapera 也通过
8、类似的途径进行繁殖，这些雌性寄生性布谷鸟经常在颜色和新寄生的选择模式方法上有着特殊的一面。这些就降低了它们的蛋被遗弃的概率，从而提高了它们的繁殖率。2.2 levy飞行的有效性在自然界中，动物存在着随机的或者类似随机的觅食行为，一般，动物的这种觅食行为的路径为一个有效的随机游走过程，因为下一次的出发路径是建立在当前的位置和去下一个位置的可能性上的，它们方向的选择是建立在对于可被算术的模型化的可能性的基础上的，例如，一系列的研究已经可以表明很多动物和昆虫的飞行行为有着典型的levy飞行的特征。近期由Reynolds和Frye提出的一项研究表明，普通果蝇和黑腹果蝇的活动路径为一个直线型的飞行路线，
9、并且在这一个路线中有很多的转角，成了一个间歇性的levy飞行模型，甚至这种飞行与levy飞行有着一定的关系，随后，这一种行为已经被应用于优化问题和发现最优解的研究当中，初期的结果表明，这种行为有着很好的前景。大体上说，levy飞行是一个随机的游走策略，它的步长可以由levy分布所决定，一般是根据一个简单有效的式子来决定的，即： （1） 在这里，是一个最小的步长，为一个控制参数，显然，当时，我们可得： （2）可以看出，这是levy飞行的一个特殊情况。 一般，levy分布可以通过一系列的傅里叶函数来定义，即 （3） 这里，是一个控制参数，由于它没有解析结构，所以它的反常积分不易得出，但是不排除一些
10、特殊情况。当时，我们有 （4）它的反常积分可以相应的转化为一个高斯分布，另一个特殊情况为当，此时，我们有： （5）此时，可转化为一个柯西分布： （6）这里是一个局部参数，控制整个分布的规模。对于一般的情况，相应的反常积分为： （7）此式只有当s最大时才可以被估计，即有： （8）这里的是一个伽马函数 （9）当其中的z=n ,为整数时，我们有 当图2表明他们在100步之内的飞行路线时，图1则表示他们飞行100个步长所遵循的levy分布图。这一情况指出levy飞行比布朗随机游动在发现事物方面的能力要有效的多，以内其有着较大的搜索范围。对于他的有效性，又很多原因可以作为解释，其中一种是由于levy的方
11、差比布朗运动的线性关系有着更快的增长率。 （10）2.3 多布标布谷鸟搜索算法在最初由杨新社教授和Deb教授提出的单一目标的布谷鸟优化算法中使用了三条基本的准则：（1） 每一只布谷鸟一次只产一个蛋，然后会将你这一只蛋丢到随机选择的一个巢穴中。（2） 在一个最佳的巢中，有着质量最优的蛋，这会使下一代更好的繁殖下去。（3） 可供选择的寄主巢穴的数量是有限的，而且寄主也会发现异种蛋，这样的几率为，也会扔掉这些异种的蛋，或者直接丢弃自己原本的巢穴而去建一个新的巢。对于k个不同目标的多目标优化问题，我们可以将以上规则做以修改，使得此规则可以同时用于多目标的需要。（1） 每一个布谷鸟一次只产一个蛋，然后将
12、这些蛋放入随机选择的巢中，第k个蛋代表第k个目标。（2） 每一个巢中的蛋都会以的几率被遗弃，同样一个有k个蛋的巢也会根据蛋的相似性和区别以的几率被重建。有时，随机的混合也会用于其中。简单的说，这个最后的假设可以近似的看成一个分数，而且这n个巢也会被新的巢所取代，对于目标的最大化，一个解决方法的适应性和可行性可以简单地归结为一些目标函数的求解问题，而且不受限制的方法也应该被广泛的发现。用数学的语言来说，第一条规则可以修改为一个随机过程，这样的话，一个新的算法策略就可以随机的由随机游走或者levy飞行来总结得出。同时，有局限性的数字序列可以由算法决定，也可以想象为一个交叉的过程，对于每一个巢，可以
13、有k种如（11）式的解决方法，本质上说，第二条规则则可以被修改为精英策略，这样最佳的解决策略就可以用于下一代中，而且，这样的选择也可以帮助我们确认此算法过程的正确性。除此之外，第三条规则可以被类似的考虑为变异，这样最差的解决方法就可以以一定几率被丢弃，新的解决策略就可以根据解决策略之间的相似性被我们发现。这样也就可以将levy飞行与不同结果的解决策略相结合，从而使得这样的变异变得向量化。这种独特的结合过程可以很好的确认算法的有效性。基于这三种规则，多目标布谷鸟搜索算法的基本步骤可以总结为如表3的一系列伪代码，当我们发现新的可以用于解决策略时，用i表示布谷鸟，那么一个levy飞行就可以用以下式子
14、来表示 （11） 此时是一个步长，在大多数情况下，我们可以使用。为了使不同的解决策略可以有很好的适应性，我们也可以使用如下式子： （12）这里的为一个常数，当两个不同的随机解决策略在一个时期内相一致时，这种模拟就可以看出巢中的蛋被发现的几率就会很小。这里的表示被选择的目标，当其中的随机步长由levy分布中的最大步长决定时，levy飞行有效的提供了一个随机游走的模型： （13）此式有一个无穷大的方差，且有无限种可能，在这里，有着连续的跳跃点或步长的布谷鸟的本质，其实是一个遵循规定步长的分布。另外，最差巢穴会以比率被遗弃，所以新的巢穴可以通过随机的游走和混合来被重新建立，被混合的蛋可以通过一些数字
15、序列与寄主的蛋之间的相似性和区别来给出。显然，步长大小s的决定不是通过levy飞行给出的一般值，一个应经被杨新社教授研究过的一个设计问题可以简单的总结如下： （14）当u和v都服从正交的分布时，即： （15）此时，为标准的伽马分布函数。3. 数值结果3.1 参数研究现在被提及的多目标布谷鸟搜索是用Matlab来实现的，其计算时间在一到两分钟之内，我们已经通过一系列变化的参数对其进行了测试，例如:种群规模n、levy飞行参数、发现几率。我们让这些参数分别取不同的值：让n=5,10,15一直取到50,100,150,200,250,300,400,500.让=0.5,1,1.5,2.让=0.1.0
16、.2.,0.5.,0.9，我们可以发现应用到实际中的最佳参数值分别是：n=25-50，=0.25-0.5，=1或1.5.另外参数可以去0.01到0.5之间的值，且最佳的取值为0.1。3.2 多目标测试函数我们对于多目标优化问题，有很多不同的测试函数，但是，我们仍需要建立一个更为广泛的函数使得其可以包含Pareto front分布和Pareto 优化问题。为了得到多目标布谷鸟搜索算法，我们需要在这些函数中选择的建立一个凸函数、非凸函数和非连续的Pareto front 分布函数。我们也需要建立一个包含复杂的Pareto 函数，为了更为具体的说明本文的问题，我们测试了如下的五个函数: 在通过多目标
17、布谷鸟搜索算法整理了200个Pareto点后，我们可以对Pareto front 与Pareto 作如图4的对比:我们可以定义距离或者两个函数分布之间的误差估计如下式子： （24）当N表示数值的点时，正确的集合可以由以下的循环来得出，如图5：图5,表明参数根据左边循环与右边对数关系的下降趋势。我们可以清楚的看到我们的布谷鸟搜索算法实际上对于大多数参数都收敛。所有测试函数的测试结果我们在表1做出了总结。关于Pareto 分布的相关函数结果如图6和图7所示：为了把之前提过的多目标布谷鸟搜索算法和其他已经建立的多目标函数做以对比，我们认真的选取了文献中一些可用的结果，在那些不适用额结果中，我们尝试着
18、用一些已被证明的算法来对这些结果做以重新的研究，特别的，我们也将其他算法做了相关的对比，包括矢量估计遗传算法VEGA、矢量估计遗传算2、多目标进化差分算法MODE、多目标优化进化遗传算法DEMO、多目标蜂群算法、强Pareto 算法。这些算法的性能总计如表2：4. 优化设计优化设计，特别是设计结构优化，在工业和工程中有很多的应用。在文献中对此的研究有很多不同的评价标准。其中包括对于梁的焊接标准和制动器的设计。在本篇文章的最后，我们将运用多目标布谷鸟搜索算法对这两种设计标准做以研究。4.1 梁的焊接设计关于梁的焊接设计是一个已经被很多研究者解决的经典设计问题。此问题中有4个设计变量：宽（w）、长
19、（L）、深度（d）、整个梁的厚度（h）。我们的设计目标是使得制造的成本和产品的倾斜度达到最小。这个问题可以用数学语言来表示为：具体过程：我们对此做的简单的限制为：通过使用MOCS，我们对这一问题做出了解决。关于近似的Pareto front 问题我们在图8中根据50种非限制性经过1000次迭代对此问题作了相关的总结。为了了解我们提出的MOCS怎样在实际的设计问题中使用，我们同样将其运用到其他的类似问题中，在图9中我们把绘制的图像的指数收敛速度作了对比，通过对比，我发现MOCS的收敛速度在指数收敛的算法中收敛速度最快。4.2 制动器设计 通过多目标优化算法设计一个多用的制动器需要另一个设计标准。
20、我们的目标是其质量和制动时间达到最小，其中的参数有内直径r、外直径R、推力F、表面摩擦力S。这些都是在转矩、压力、温度和制动距离这些的限制下设计的，这个设计问题可以用式子表示为：Pareto front问题,通过MOCS进行1000此迭代之后选择的50个点如图10，我们可以看出它的曲线是光滑的，比之前的结果更优。图11中绘制了关于指数收敛的收敛速度的比较图，我们从这两个图中看出MOCS的收敛速度在两种情况下都比较快，这也就再一次的说明了MOCS为我们提供了一个更为有效的解决优化设计问题的方法。 对于这三种基准问题和测试函数的模拟表明，MOCS确实是一种对于多目标优化问题而言非常有效的算法，它可
21、以解决很多高度非线性的有许多复杂限制条件的问题。5. 总结我们知道，基于多目标的优化问题本身是很难得以解决的，在本篇文章中，我们成功的对此问题建立了一个新的算法，称之为多目标布谷鸟搜索算法。我们提出的这个MOCS已经通过一系列测试函数对其有效性和准确性做了相关的测试研究，并且将此算法运用到了很多工程结构问题当中，结果表明，此算法是一个行之有效的算法。在与其他算法的比较中，布谷鸟搜索算法在很多测试中都有着较好的表现，这要归结于布谷鸟算法将其他优秀算法的结合能力上。例如，levy飞行、精英策略、变量变换、交叉变异。此外不是特别优秀的算法往往会被好的算法所取代，因此所有这些算法之间的平衡与巧妙结合的机制也非常重要，显然，通过一系列测试函数确认的算法将会有一个很好的发展前景。被提出的其他的测试函数和比较规则也是非常必要的，在我们未来的工作中，我们将会关注一系列测试问题中的参数研究，包括非连续的和混合的优化问题，我们将努力测试出Pareto front 问题的多样性，以提高算法不同的适应性，其实更好的适应于更多不同的问题。有很多有效的科学技术可以使得Pareto front 问题更具多样性，而一些技术之间的相互结合可以很好地提高MOCS的有效性。以后我们更进一步的研究就会更在意多目标优化问题的算法与其他主流方法的不同，另外，这也会使得其他的算法可以由更加令人满意的效果。
