基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法
关键字：布谷鸟搜索、元启发式算法、多目标、最优化
摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。
1.简介
在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及
设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。
另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。
从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些
有利的求和方法将多目标问题归结到单一目标问题中去，在优化的过程中，我们需要大量的修改工作，除此之外，更困难的更具挑战性的是，怎样总结这些方法，使其有着足够的多样性，这样的话，这种新的解决方法就可以成为有效利用搜索空间的实例。而且，在真实的生活中，优化问题往往包含了一些不确定性和干扰性，例如，材料的适应性对于一个产品的设计往往有着很重要的影响，一个优化的设计问题应该足够的完美使得对于设计者和决策者可以对很多不同种的东西提供一些更好的选择。
尽管存在着这些挑战性，多目标优化问题仍存在着许多有效的算法使其在很多问题中有着成功的应用，此外元启发算法开始作为解决多目标优化问题的主角出现在大众面前，优化算法设计者以及科学家们经常模拟自然界中一些成功的范例来解决问题，例如，生物系统，很多新的算法也都开始出现并且在问题的解决中也有着很重要的应用。
目前，有一种新的由杨新社教授和Suach Deb教授在2009年提出的元启发算法，名为布谷鸟算法，对于此种算法，在最初的研究中就可以看出，其具有很高的前瞻性，比现有的PSO算法有着更好的性能，在本篇论文中我们将会对CS作以延伸，以便其可以解决多目标优化问题，而且可以建立一个基于多目标的布谷鸟搜索算法。第一步我们将通过建立一个多目标的检验函数来使问题具体化，然后我们会将其应用到工程优化问题中，包括双目标的光路设计和制动器设计。同时，我们也将讨论被提出的
算法中其独有的特性，并且对文章做以进一步的研究。
2.多目标的布谷鸟搜索
为了对CS算法做以延伸来解决多目标的问题，我们在此先对布谷鸟有趣的繁殖行为规律做以简要的回顾，然后，我们将会对此算法的基本观点和步骤以及实际的算法过程作以概述。
2.1 布谷鸟的繁殖行为
布谷鸟是一种有趣的鸟，它的有趣不仅是因为它动听的歌声，还因为其具有侵略性的繁殖策略。像美洲黑杜鹃这一种鸟类，它们会将自己的卵产在公共的巢穴中，并且，它们会将其他鸟类的蛋移出巢外以提高自己的蛋被孵化的几率，大多数鸟类通过产卵于其他寄主的巢中这种寄生性规律来完成自己孵化的任务，目前，存在着三种最基本的寄生性行为：种内产卵寄生性、合作式寄生性、巢穴接管。一些寄主可以直接发现这些入侵者，并与入侵的鸟类发生冲突，如果寄主发现其巢中的蛋不是自己的，它们便会扔掉这些蛋或者直接遗弃这个巢穴，在别处重新建立一个新的巢穴。一些像the New World brood parasitic Tapera 也通过类似的途径进行繁殖，这些雌性寄生性布谷鸟经常在颜色和新寄生的选择模式方法上有着特殊的一面。这些就降低了它们的蛋被遗弃的概率，从而提高了它们的繁殖率。
2.2 levy飞行的有效性
在自然界中，动物存在着随机的或者类似随机的觅食行为，一般，动物的这种觅食行为的路径为一个有效的随机游走过程，
因为下一次的出发路径是建立在当前的位置和去下一个位置的可能性上的，它们方向的选择是建立在对于可被算术的模型化的可能性的基础上的，例如，一系列的研究已经可以表明很多动物和昆虫的飞行行为有着典型的levy 飞行的特征。
近期由Reynolds 和Frye 提出的一项研究表明，普通果蝇和黑腹果蝇的活动路径为一个直线型的飞行路线，并且在这一个路线中有很多 90的转角，成了一个间歇性的levy 飞行模型，甚至这种飞行与levy 飞行有着一定的关系，随后，这一种行为已经被应用于优化问题和发现最优解的研究当中，初期的结果表明，这种行为有着很好的前景。
大体上说，levy 飞行是一个随机的游走策略，它的步长可以由levy 分布所决定，一般是根据一个简单有效的式子来决定的，即：
?????---=0)(1])(2exp[2),,(23μμγπ
γμγs s s L 0,0,≤∞<<
在这里，0>μ是一个最小的步长，γ为一个控制参数，显然，当∞→s 时，我们可得：
???≈2312),,(s s L πγμγ （2）
可以看出，这是levy 飞行的一个特殊情况。
一般，levy 分布可以通过一系列的傅里叶函数来定义，即 20],||exp[)(≤<-=βαβk k F （3） 这里，α是一个控制参数，由于它没有解析结构，所以它
的反常积分不易得出，但是不排除一些特殊情况。
当2=β时，我们有
][)(2k k F α-= （4） 它的反常积分可以相应的转化为一个高斯分布，另一个特殊情况为当1=β，此时，我们有：
|]|exp[)(k k F α-=
（5） 此时，可转化为一个柯西分布：
22)(1),,(μγγ
πμγ-+=x x p
（6） 这里μ是一个局部参数，γ控制整个分布的规模。
对于一般的情况，相应的反常积分为：
dk k ks s L ])||exp[()cos(1)(0?∞
-=βαπ
（7） 此式只有当s 最大时才可以被估计，即有：
∞→Γ→+s s s L ,||)
2sin()()(1βππββαβ
（8） 这里的)(z Γ是一个伽马函数
dt e t z t z --∞?=Γ1
0)(
（
9） 当其中的z=n ,为整数时，我们有)!1()(-=Γn n
当图2表明他们在100步之内的飞行路线时，图1则表示他们飞行100个步长所遵循的levy 分布图。这一情况指出levy 飞行比布朗随机游动在发现事物方面的能力要有效的多，以内其有着较大的搜索范围。对于他的有效性，又很多原因可以作为解释，其中一种是由于levy 的方差比布朗运动的线性关系有着更快的增长率。
,21,~)(32≤≤-βσβt t （10）
2.3 多布标布谷鸟搜索算法
在最初由杨新社教授和Deb 教授提出的单一目标的布谷鸟优化算法中使用了三条基本的准则：
（1）每一只布谷鸟一次只产一个蛋，然后会将你这一只蛋丢到随机选择的一个巢穴中。
（2）在一个最佳的巢中，有着质量最优的蛋，这会使下一代更好的繁殖下去。
（3）可供选择的寄主巢穴的数量是有限的，而且寄主也会发现异种蛋，这样的几率为]1,0[∈a p ，也会扔掉这些异种的蛋，或者直接丢弃自己原本的巢穴而去建一个新的巢。
对于k 个不同目标的多目标优化问题，我们可以将以上规则做以修改，使得此规则可以同时用于多目标的需要。
（1）每一个布谷鸟一次只产一个蛋，然后将这些蛋放入随机选择的巢中，第k 个蛋代表第k 个目标。
（2）每一个巢中的蛋都会以
p的几率被遗弃，同样一个有k个
a
蛋的巢也会根据蛋的相似性和区别以
p的几率被重建。有时，随
a
机的混合也会用于其中。
简单的说，这个最后的假设可以近似的看成一个分数
p，而
a
且这n个巢也会被新的巢所取代，对于目标的最大化，一个解决方法的适应性和可行性可以简单地归结为一些目标函数的求解问题，而且不受限制的方法也应该被广泛的发现。
用数学的语言来说，第一条规则可以修改为一个随机过程，这样的话，一个新的算法策略就可以随机的由随机游走或者levy 飞行来总结得出。同时，有局限性的数字序列可以由算法决定，也可以想象为一个交叉的过程，对于每一个巢，可以有k种如（11）式的解决方法，本质上说，第二条规则则可以被修改为精英策略，这样最佳的解决策略就可以用于下一代中，而且，这样的选择也可以帮助我们确认此算法过程的正确性。除此之外，第三条规则可以被类似的考虑为变异，这样最差的解决方法就可以以一定几率被丢弃，新的解决策略就可以根据解决策略之间的相似性被我们发现。这样也就可以将levy飞行与不同结果的解决策略相结合，从而使得这样的变异变得向量化。这种独特的结合过程可以很好的确认算法的有效性。
基于这三种规则，多目标布谷鸟搜索算法的基本步骤可以总结为如表3的一系列伪代码，
当我们发现新的)1(+t x 可以用于解决策略时，用i 表示布谷鸟，那么一个levy 飞行就可以用以下式子来表示
)()()1(βαlevy x x t i t i ⊕+=+ （11） 此时0>α是一个步长，在大多数情况下，我们可以使用)1(O =α。为了使不同的解决策略可以有很好的适应性，我们也可以使用如下式子：
)()()(0t i t j x x -=αα （12）
这里的0α为一个常数，当两个不同的随机解决策略在一个时
期内相一致时，这种模拟就可以看出巢中的蛋被发现的几率就会很小。
这里的⊕表示被选择的目标，当其中的随机步长由levy 分布中的最大步长决定时，levy 飞行有效的提供了一个随机游走的模型：
)20(,~1≤<=--ββt u levy （13） 此式有一个无穷大的方差，且有无限种可能，在这里，有着连续的跳跃点或步长的布谷鸟的本质，其实是一个遵循规定步长的分布。
另外，最差巢穴会以比率a p 被遗弃，所以新的巢穴可以通过
随机的游走和混合来被重新建立，被混合的蛋可以通过一些数字序列与寄主的蛋之间的相似性和区别来给出。
显然，步长大小s 的决定不是通过levy 飞行给出的一般值，一个应经被杨新社教授研究过的一个设计问题可以简单的总结如下：
)(||01.0~)()()()(
1)()(
0t i t j t i t j x x v u levy x x s -⊕-=ββα （14）
当u 和v 都服从正交的分布时，即：
),0(~2u N u σ ),0(~2v N v σ （15）
1,2]2/)1[()2/sin)()1(/12/)1(=??????+Γ+Γ=-v u σββπββσββ
此时，Γ为标准的伽马分布函数。
3. 数值结果
3.1 参数研究
现在被提及的多目标布谷鸟搜索是用Matlab 来实现的，其
计算时间在一到两分钟之内，我们已经通过一系列变化的参数对其进行了测试，例如:种群规模n、levy飞行参数β、发现几率
p。
a
我们让这些参数分别取不同的值：让n=5,10,15一直取到50,100,150,200,250,300,400,500.让β=0.5,1,1.5,2.让
p=0.1.0.2...,0.5...,0.9，我们可以发现应用到实际中的最佳参数值a
分别是：n=25-50，
p=0.25-0.5，β=1或1.5.另外参数0α可以去
a
0.01到0.5之间的值，且
α最佳的取值为0.1。
3.2 多目标测试函数
我们对于多目标优化问题，有很多不同的测试函数，但是，我们仍需要建立一个更为广泛的函数使得其可以包含Pareto front分布和Pareto 优化问题。为了得到多目标布谷鸟搜索算法，我们需要在这些函数中选择的建立一个凸函数、非凸函数和非连续的Pareto front 分布函数。我们也需要建立一个包含复杂的Pareto 函数，为了更为具体的说明本文的问题，我们测试了如下的五个函数:
在通过多目标布谷鸟搜索算法整理了200个Pareto点后，我们可以对Pareto front 与Pareto 作如图4的对比:
我们可以定义距离或者两个函数分布之间的误差估计如下式子：
∑=-
=
-
=
N
j
t e
j
t
e
f
PF PF
PF
PF
E
12
2
)
(（24）
当N表示数值的点时，正确的集合可以由以下的循环来得出，如图5：
图5,表明参数
E根据左边循环与右边对数关系的下降趋势。
f
我们可以清楚的看到我们的布谷鸟搜索算法实际上对于大多数参数都收敛。所有测试函数的测试结果我们在表1做出了总结。关于Pareto 分布的相关函数结果如图6和图7所示：
为了把之前提过的多目标布谷鸟搜索算法和其他已经建立的多目标函数做以对比，我们认真的选取了文献中一些可用的结果，在那些不适用额结果中，我们尝试着用一些已被证明的算法来对这些结果做以重新的研究，特别的，我们也将其他算法做了相关的对比，包括矢量估计遗传算法VEGA、矢量估计遗传算2、多目标进化差分算法MODE、多目标优化进化遗传算法DEMO、多目标蜂群算法、强Pareto 算法。这些算法的性能总计如表2：
4.优化设计
优化设计，特别是设计结构优化，在工业和工程中有很多的应用。在文献中对此的研究有很多不同的评价标准。其中包括对于梁的焊接标准和制动器的设计。在本篇文章的最后，我们将运用多目标布谷鸟搜索算法对这两种设计标准做以研究。
4.1 梁的焊接设计
关于梁的焊接设计是一个已经被很多研究者解决的经典设计问题。此问题中有4个设计变量：宽（w）、长（L）、深度（d）、整个梁的厚度（h）。我们的设计目标是使得制造的成本和产品的倾斜度 达到最小。
这个问题可以用数学语言来表示为：
具体过程：
我们对此做的简单的限制为：0.2
≥h
≤
L
≥
d
w
10
,
,1.0≤
125
.0
,
通过使用MOCS，我们对这一问题做出了解决。关于近似的Pareto front 问题我们在图8中根据50种非限制性经过1000次
迭代对此问题作了相关的总结。
为了了解我们提出的MOCS怎样在实际的设计问题中使用，我们同样将其运用到其他的类似问题中，在图9中我们把绘制的图像的指数收敛速度作了对比，通过对比，我发现MOCS的收敛速度在指数收敛的算法中收敛速度最快。
4.2 制动器设计
通过多目标优化算法设计一个多用的制动器需要另一个设计标准。我们的目标是其质量和制动时间达到最小，其中的参数有内直径r、外直径R、推力F、表面摩擦力S。这些都是在转矩、压力、温度和制动距离这些的限制下设计的，这个设计问题可以
用式子表示为：
Pareto front问题,通过MOCS进行1000此迭代之后选择的50个点如图10，我们可以看出它的曲线是光滑的，比之前的结果更优。
图11中绘制了关于指数收敛的收敛速度的比较图，我们从这两个图中看出MOCS的收敛速度在两种情况下都比较快，这也就再一次的说明了MOCS为我们提供了一个更为有效的解决优化设计问题的方法。
基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法 关键字：布谷鸟搜索、元启发式算法、多目标、最优化 摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。 1.简介 在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及
设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。 另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。 从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些
基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法 关键字：布谷鸟搜索、元启发式算法、多目标、最优化 摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。 1.简介 在设计问题中经常会考虑到很多多重的复杂问题，而且这些问题往往都具有很高的非线性性。在实际中，不同的目标之间往往会有分歧和冲突，有时候，实际的最优化解决方案往往不存在，而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外，设计问题还会受到不同设计目标的约束，而且还会被设计代码、设计标准、材料适应性、和可用资源的选择，以及
设计花费等所限制，甚至是关于单一目标的全局最优问题也是如此，如果设计函数有着高度的非线性性，那么全局最优解是很难达到的，而且，很多现实世界中的问题经常是NP-hard的，这就意味着没有一个行之有效的算法可以解决我们提出的问题，因此，对于一个已经提出的问题，启发式算法和科学技术与具体的学科交叉知识经常被用于其中，用来作为解决问题的向导。 另一方面，元启发算法在解决此类优化问题方面是非常有效的，而且已经在很多刊物和书籍中得以运用，与单一目标的优化问题相反的是，多目标优化问题具有典型的复杂性和困难性，在单一目标的优化问题中我们必须去找出一个最优化的解决方法，此方法在问题的解决中存在着一个单一的点，并且在此问题中不包括那些多重的、平均优化的点，对于一个多目标的优化问题，存在着名为Pareto-front的多重的复杂的优化问题，为了了解我们所不熟悉的Pareto-front问题，我们需要收集并整理很多不同的方法，从而，此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上，此类解决方法应包括问题并且应相对的有一致无分歧的分布情况，然而，还没有科学的方法可以证明这种解决方法可以在实际中得以应用。 从问题的出发点我们可以得知，算法可以在单一目标优化问题中运行的很好，但是却不能在多目标的优化问题中直接的运用，除非是在特殊的环境与条件下才可以应用。例如，使用一些
布谷鸟算法
今天我要讲的内容是布谷鸟算法，英文叫做Cuckoo search (CS algorithm)。首先还是同样，介绍一下这个算法的英文含义，Cuckoo是布谷鸟的意思，啥是布谷鸟呢，是一种叫做布谷的鸟，o(∩_∩)o ，这种鸟她妈很懒，自己生蛋自己不养，一般把它的宝宝扔到别的种类鸟的鸟巢去。但是呢，当孵化后，遇到聪明的鸟妈妈，一看就知道不是亲生的，直接就被鸟妈妈给杀了。于是这群布谷鸟宝宝为了保命，它们就模仿别的种类的鸟叫，让智商或者情商极低的鸟妈妈误认为是自己的亲宝宝，这样它就活下来了。Search指的是搜索，这搜索可不是谷歌一下，你就知道。而是搜索最优值，举个简单的例子，y=(x-0.5)^2+1，它的最小值是1，位置是(0.5,1)，我们要搜索的就是这个位置。 现在我们应该清楚它是干嘛的了吧，它就是为了寻找最小值而产生的一种算法，有些好装X的人会说，你傻X啊，最小值不是-2a/b吗，用你找啊? 说的不错，确实是，但是要是我们的函数变成y=sin(x^3+x^2)+e^cos(x^3)+log(tan(x) +10，你怎么办吶？你解不了，就算你求导数，但是你知道怎么解导数等于0吗？所以我们就得引入先进的东西来求最小值。 为了使大家容易理解，我还是用y=(x-0.5)^2+1来举例子，例如我们有4个布谷鸟蛋（也就是4个x坐标），鸟妈妈发现不是自己的宝宝的概率是0.25，我们x的取值范围是[0,1]之间，于是我们就可以开始计算了。 目标：求x在[0,1]之内的函数y=(x-0.5)^2+1最小值 （1）初始化x的位置，随机生成4个x坐标，x1=0.4，x2=0.6，x3=0.8，x4 =0.3 ——> X=[0.4, 0.6 ,0.8, 0.3]
布谷鸟算法
布谷鸟算法 1、概述 布谷鸟搜索算法[CuckooSearch（CS）],也叫杜鹃搜索,是由剑桥大学Xin-SheYang(杨新社)教授和S.Deb于2009年提出的一种新兴启发算法CS算法通过模拟某些种属布谷鸟(CuckooSpecies)的寄生育雏(BroodParasitism)来有效地求解最优化问题的算法.同时，CS也采用相关的Levy飞行搜索机制。 2、优点 全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强，以及很好的通用性、鲁棒性等特点，同时其特有的莱维特性能够有效地扩大搜索范围，是一种高效的全局随机搜索算法．并且实例测试结果证明了它比遗传算法、粒子群算法、萤火虫算法具有更高寻优性能。 布谷鸟搜索算法凭借参数少，算法简单，易于实现的特点被广泛应用在各个领域，是群体智能算法中的一个新亮点 3、应用领域 布谷鸟算法自提出之后引起了许多学者的关注，并在许多项目调度、工程优化问题、求解置换流水车间调度和计算智能方面得到了应用。 在工程设计领域，布谷鸟算法对于一系列连续优化问题如弹簧设计和焊接梁设计等问题有着优于其他算法的性能。Vazquez利用布谷鸟算法训练脉冲神经网络模型，Chifu等人利用布谷鸟算法优化语义
Web服务组合流程, Bhargava等人在求解复杂相平衡问题中，用布谷鸟算法获得了可靠的热力学计算。 在组合优化问题方面，Tein和Ramli针对护士调度问题提出了离散化的布谷鸟算法，布谷鸟算法还成功的应用于软件测试中数据生成程序问题独立路径的产生。Speed修改了CS并成功应用于处理大规模问题。Moravej和Akhlaghi用CS研究了分布式网络中的DG分配问题。 对于多目标问题的研究，Deb针对工程应用提出了多目标CS算法，Simon等人则利用CS算法针对多目标调度问题取得了很好的效果。 综上所述，虽然布谷鸟算法于2009年才刚刚提出，但己经被成功应用到各个领域的优化问题中，布谷鸟算法可以求解大部分优化问题，或者是可以转化为优化问题进行求解的问题。 4、应用延伸 4.1车辆调度、路径最优 《求解带时间窗车辆路径问题的混合智能算法》文中提出：基于布谷鸟搜索算法和单亲遗传算法，设计了一种求解带时间窗车辆路径问题的混合智能算法。该算法首先对客户位置进行聚类分析，然后再进行各区域的路径优化。混合智能算法不仅改进了布谷鸟搜索算法中当鸟卵被鸟窝主人发现后需要随机改变整个鸟窝位置的操作，同时引入的单亲遗传算法加快了最优配送路线的搜索速度。 4.2 项目调度
基于蚁群算法的多目标优化
基于蚁群算法的多目标优化 池元成;蔡国飙 【期刊名称】《计算机工程》 【年(卷),期】2009(035)015 【摘要】Aiming at multi-objective optimization problem, this paper proposes an Ant Colony Algorithm(ACA) for solving Multi-objective Optimization Problem(MOPACA). An improved pheromone updating process based on continuous space is described. Two moving strategies are used in the searching process to ensure better solutions. Convergence property of the algorithm is analyzed. Preliminary simulation results of two benchmark functions show the feasibility of the algorithm.%针对多目标优化问题,提出一种用于求解多目标优化问题的蚁群算法.该算法定义连续空间内求解多目标优化问题的蚁群算法的信息素更新方式,根据信息素的概率转移和随机选择转移策略指导蚂蚁进行搜索,保证获得的Pareto前沿的均匀性以及Pareto解集的多样性.对算法的收敛性进行分析,利用2个测试函数验证算法的有效性. 【总页数】3页(168-169,172) 【关键词】蚁群算法;多目标优化;收敛性分析 【作者】池元成;蔡国飙 【作者单位】北京航空航天大学宇航学院,北京100083;北京航空航天大学宇航学院,北京100083 【正文语种】中文
布谷鸟搜索算法简介
布谷鸟搜索算法 维基百科，自由的百科全书 布谷鸟搜索（Cuckoo Search，缩写 CS），也叫杜鹃搜索，是由剑桥大学杨新社（音译自：Xin-She Yang）教授和S.戴布（S.Deb）于2009年提出的一种新兴启发算法[1]。 CS算法是通过模拟某些种属布谷鸟的寄生育雏（Brood Parasitism），来有效地求解最优化问题的算法。同时，CS也采用相关的Levy飞行搜索机制。研究表明，布谷鸟搜索比其他群体优化算法更有效。 布谷鸟搜索 布谷鸟搜索（CS）使用蛋巢代表解。最简单情况是，每巢有一个蛋，布谷鸟的蛋代表了一种新的解。其目的是使用新的和潜在的更好的解，以取代不那么好的解。该算法基于三个理想化的规则： ?每个杜鹃下一个蛋，堆放在一个随机选择的巢中； ?最好的高品质蛋巢将转到下一代； ?巢的数量是固定的，布谷鸟的蛋被发现的概率为。 实际应用 布谷鸟搜索到工程优化问题中的应用已经表现出其高优效率，经过几年的发展，为了进一步提高算法的性能，CS算法的很多变体与改进逐步涌现。瓦尔顿（Walton）等提出了修正布谷鸟搜索（Modified Cuckoo Search，缩写 MCS）；伐立安（Valian）等提出了一种可变参数的改进CS算法，提高了收敛速度，并将改进算法应用于前馈神经网络训练中；马里切尔凡姆（Marichelvam）将一种混合CS算法应用于流水车间调度问题求解中；钱德拉塞卡兰（Chandrasekaran）等将集成了模糊系统的混合CS算法应用于机组组合问题。 杨（Yang）和戴布（Deb）提出多目标布谷鸟搜索（Multiobjective Cuckoo Search，缩写 MOCS），应用到工程优化并取得很好的效果；詹（Zhang）等通过对种群分组，并根据搜索的不同阶段对搜索步长进行预先设置，提出了修正调适布谷鸟搜索（Modified Adaptive Cuckoo Search，缩写 MACS），提高了CS的性能。
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
（多目标优化模型）
蚁群算法在旅行商问题中的应用 摘要 本文将对蚁群算法的仿真学原理进行概要介绍和对蚁群算法产生、发展、优化进行介绍以及阐述蚁群算法的几点重要基本规则，并对蚁群算法的优缺点进行讨论。蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用。 关键字：蚁群算法；旅行商问题；仿真；多目标优化
一、问题重述 旅行商问题(TSP)是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton 回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个N P完全问题。随着问题规模的增大，人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下发展起来的。本文将使用一种近似算法或启发式算法—蚁族算法。 1、蚁群算法的提出 蚁群算法(Ant Colony Optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 2、蚁群算法的仿生学原理 蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特征启发而得出的。蚂蚁是一种群居昆虫，在觅食、清理巢穴征启发而得出的。蚂蚁是一种群居昆虫，在觅食、等活动中，彼此依赖、相互协作共同完成特定的任务。等活动中，彼此依赖、相互协作共同完成特定的任务。就个体来讲，单个蚂蚁的智力和体力是极其有限的，体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、在完成任务过程中所体现的自组织特征等反应出蚁群具有较高的智能和自我管理能力，具有很高层次组织性，高的智能和自我管理能力，具有很高层次组织性，这使得蚁群能够完成一些复杂的任务。群能够完成一些复杂的任务。 蚁群的行为是整体协作，相互分工，蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为.当蚂蚁出外寻找食物时，会在自己走过的路径上释放一种称为信息家的物质，径上释放一种称为信息家的物质，后续的蚂蚁一般更愿意走那些信息素强度更高的路径。这样，那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多(浓度更高) 通过的蚂蚁数目较多，留下的信息素也较多(浓度更高)，对蚂蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这就形成了一个正反馈机制，就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到食物源的最短路径. 食物源的最短路径. 3、蚁群算法实现的重要规则 （1）范围 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范
基于K―means和布谷鸟算法的流程模型聚类
基于K―means和布谷鸟算法的流程模型聚类 摘要：流程模型聚类是流程管理领域的一个热门话题。本文提出一种基于布谷鸟算法的K-means算法，该算法弥补了K-means算法的依赖初始解、易陷入局部最优等缺点。本文从流程模型结构性能、成本、效率、顾客满意度以及质量等五个方面模拟数据集，并选择权重较高的属性进行试验操作，结果表明算法的具有较高的可行性和有效性。 Abstract：Process model clustering is a hot topic in the field of process management. This paper presents a new K-means algorithm based on cuckoo algorithm，which compensates drawbacks of traditional K-means algorithm，such as relying on initial solution and being easily trapped in local optimums. In this paper，simulated data sets consist of five features （process model structure performance，cost，efficiency，customer satisfaction and quality），but experiments are conducted by only two indicators with higher weight. Experimental results show that the method has relatively higher feasibility and effectiveness. 关键词：布谷鸟算法;K-means算法;流程模型聚类 Key words：cuckoo algorithm;K-means;process model
多目标蚁群算法及其实现
多目标蚁群算法及其实现 李首帅（2012101020019） 指导老师：张勇 【摘要】多目标优化问题对于现阶段来说，是十分热门的。本文将对多目标规划当中的旅行商问题，通过基于MATLAB的蚁群算法来解决，对多目标问题进行局部优化。 【关键词】旅行商问题；蚁群算法；MATLAB 一、背景介绍 旅行商问题是物流领域当中的典型问题，它的求解十分重要。蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体的模拟进化算法,属于随机搜索算法。M. Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性,通过人工模拟蚁群搜索食物的行为(即蚂蚁个体之间通过间接通讯与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP问题。为区别于真实蚁群,称算法中的蚂蚁为“人工蚂蚁”。人们经过大量研究发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递,从而能相互协作,完成复杂的任务。蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度,并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。 二、蚁群算法原理介绍 1.蚁群在路径上释放信息素； 2.碰到还没走过的路口，就随机挑选一条路走。同时释放与路径长度有关的信息素； 3.信息素浓度与路长成反比； 4.最优路径上的信息浓度越来越大； 5.最终蚁群找到最优路径。 其实自然界中，蚁群这种寻找路径的过程表现是一种正反馈的过程，与人工蚁群的优化算法很相近。所以我们简单功能的工作单元视为蚂蚁，则上述的搜寻路径过程可以用来解释人工蚁群搜寻过程。 人工蚁群和自然界蚁群各具特点。人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径。而自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者
改进二进制布谷鸟搜索算法求解TSP问题
改进二进制布谷鸟搜索算法求解TSP问题 ：According to the characteristics TSP problem ，we design an improved TSP problem solving binary cuckoo algorithm. The algorithm uses a binary code string showing the location of the nest ，the nest of the cuckoo to find a new flight path of Levi binary code conversion ，this paper introduces the binary coded control coefficient transform binary coding mixed update ，the paper retains the cuckoo egg method being eliminated mechanisms ，and introduces greedy thought ，this article will search for new and efficient cuckoo （CS）algorithm to improve a binary search cuckoo （BCS）algorithm. The BCSalgorithm for solving TSP. By testing multiple sets of data ，compared to "TSP problem of data collection catalog （standard test set ），" The results show that better than tabu search algorithm ，genetic algorithm ，ant colony algorithm ，particle swarm optimization. Keywords：Binary ；Cuckoo search algorithm ；traveling salesman problem ；greedy algorithm 1 引言 TSP（旅行商）问题是指已知n个城市之间的相互距离，寻
多目标优化的求解方法
多目标优化的求解方法 多目标优化(MOP)就是数学规划的一个重要分支,就是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下: 多目标优化方法本质就是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法: （1）评价函数法。常用的方法有:线性加权与法、极大极小法、理想点法。评价函数法的实质就是通过构造评价函数式把多目标转化为单目标。 (2)交互规划法。不直接使用评价函数的表达式,而就是使决策者参与到求解过程,控制优化的进行过程,使分析与决策交替进行,这种方法称为交互规划法。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权与法等。 (3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。 而这些主要就是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法与蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都就是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其她若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少与总的运输费用最低, 这就是含有两个目标的优化问题。利用首次适配递减算法与标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合
多目标优化进化算法比较综述
龙源期刊网 https://www.wendangku.net/doc/088151615.html, 多目标优化进化算法比较综述 作者：刘玲源 来源：《决策与信息·下旬刊》2013年第07期 摘要多目标优化是最优化领域的一个重要研究方向，本文简要介绍了多目标优化的模型和几种多目标优化的进化算法，并对算法进行了简要比较。 关键词多目标优化粒子群遗传算法蚁群算法人工免疫系统 中图分类号：TP391 文献标识码：A 一、背景 多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。 二、不同算法介绍 （一）多目标遗传算法。 假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。 （二）人工免疫系统。 人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。 （三）多目标PSO约束算法。
逐维改进的布谷鸟搜索算法
软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/088151615.html, Journal of Software,2013,24(11):2687?2698 [doi: 10.3724/SP.J.1001.2013.04476] https://www.wendangku.net/doc/088151615.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 逐维改进的布谷鸟搜索算法 王李进1,2, 尹义龙2, 钟一文1 1(福建农林大学计算机与信息学院,福建福州 350002) 2(山东大学计算机科学与技术学院,山东济南 250101) 通讯作者: 尹义龙, E-mail: ylyin@https://www.wendangku.net/doc/088151615.html,, https://www.wendangku.net/doc/088151615.html,/ylyin.html 摘要: 布谷鸟搜索(cuckoo search,简称CS)算法是一种新兴的仿生智能算法,对解采用整体更新评价策略.在求 解多维函数优化问题时,由于各维之间相互干扰,采用整体更新评价策略将恶化算法的收敛速度和解的质量.为了弥 补此缺陷,提出了基于逐维改进的布谷鸟搜索算法.在改进算法的迭代过程中,针对解采用逐维更新评价策略.该策 略将各维的更新值与其他维的值组合成新的解,并采用贪婪方式接受能够改善解质量的更新值.实验结果说明,改进 策略能够有效地提高CS算法的收敛速度并改善解的质量.与相关的改进布谷鸟搜索算法以及其他演化算法的比较 结果表明,改进算法在求解连续函数优化问题上是具有竞争力的. 关键词: 布谷鸟搜索算法;逐维改进;函数优化;多维函数;干扰现象 中图法分类号: TP183文献标识码: A 中文引用格式: 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法.软件学报,2013,24(11):2687?2698.https://www.wendangku.net/doc/088151615.html,/ 1000-9825/4476.htm 英文引用格式: Wang LJ, Yin YL, Zhong YW. Cuckoo search algorithm with dimension by dimension improvement. Ruan Jian Xue Bao/Journal of Software, 2013,24(11):2687?2698 (in Chinese).https://www.wendangku.net/doc/088151615.html,/1000-9825/4476.htm Cuckoo Search Algorithm with Dimension by Dimension Improvement WANG Li-Jin1,2, YIN Yi-Long2, ZHONG Yi-Wen1 1(School of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China) 2(School of Computer Science and Technology, Shandong University, Ji’nan 250101, China) Corresponding author: YIN Yi-Long, E-mail: ylyin@https://www.wendangku.net/doc/088151615.html,, https://www.wendangku.net/doc/088151615.html,/ylyin.html Abstract: Cuckoo search (CS) is a new nature-inspired intelligent algorithm which uses the whole update and evaluation strategy on solutions. For solving multi-dimension function optimization problems, this strategy may deteriorate the convergence speed and the quality of solution of algorithm due to interference phenomena among dimensions. To overcome this shortage, a dimension by dimension improvement based cuckoo search algorithm is proposed. In the progress of iteration of improved algorithm, a dimension by dimension based update and evaluation strategy on solutions is used. The proposed strategy combines an updated value of one dimension with values of other dimensions into a new solution, and greedily accepts any updated values that can improve the solution. The simulation experiments show that the proposed strategy can improve the convergence speed and the quality of the solutions effectively. Meanwhile, the results also reveal the proposed algorithm is competitive for continuous function optimization problems compared with other improved cuckoo search algorithms and other evolution algorithms. Key words: cuckoo search algorithm; dimension by dimension improvement; function optimization; multi-dimension function; interference phenomena 自20世纪以来,人们利用蚂蚁、鸟类等群居生物的自组织行为,提出了粒子群算法(particle swarm ?基金项目: 新世纪优秀人才支持计划(NCET-11-0315); NSFC-广东联合基金重点支持项目(U1201258); 福建省自然科学基金 (2011J05044, 2013J01216); 山东省自然科学杰出青年基金(2013JQE27038) 收稿时间:2013-04-27; 修改时间: 2013-07-17; 定稿时间: 2013-08-27
09第九章 多目标优化算法
第九章多目标优化算法习题与答案 1. 填空题 （1）多目标优化问题由于存在目标，使得同时优化的对象增多。由于目标之间往往相互冲突，某一目标性能的提高会引起其他目标性能的，因此只能通过的方法使所有目标尽可能达到最优。 （2）多目标优化问题需要求解一个由不同程度折中的组成的解集，并且需要保证解集的和，这就导致多目标优化问题的求解难度远远大于单目标优化问题。 解释： 本题考查多目标优化算法的基础知识。 具体内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： （1）多个，降低，权衡折中 （2）最优解，收敛性，均匀性 2.如何理解多目标优化问题？ 解释： 本题考查多目标优化问题的形式和实质。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 多目标优化问题由于存在多个目标，优化对象增多，且目标之间往往是相互冲突的，某一目标性能的提高会引起其他目标性能的降低，因此只能通过权衡折中的方法使所有目标尽可能达到最优。不同于单目标优化只需求得一个最优解，多目标优化需要求解一个由不同程度折中的最优解组成的解集，且需同时保证解集的收敛性和均匀性。例如，购买汽车时考虑到汽车性能和价格两个方面，往往
当性能较好时性能优良且价格昂贵，而性能较差时价格低廉，人们总是想得到价格便宜同时性能又好的汽车，但这两方面往往不能同时兼优，只能在某一方面有所偏重，这就形成了一个以汽车性能（比如百米加速时间）和价格为两个冲突目标的多目标优化问题。 3. 试举例说明Pareto 支配关系具有传递性。 解释： 本题考查Pareto 支配关系的性质。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 假设两目标最小优化的三个个体，123=(2,2)=(3,3)=(4,4)C C C ，，，则1 2C C ， 2 3C C ，又因为1 3C C ，所以Pareto 支配关系具有传递性。 4. 考虑一个具有两个目标最小化问题，20个个体的进化群体，进行Pareto 非支配排序分层。20个个体定义如下：C 1=(9,1)，C 2=(7,2)，C 3= (5,4)，C 4=(4,5)，C 5=(3,6)，C 6=(2,7)，C 7=(1,9)，C 8=(10,1)，C 9=(8,5)，C 10=(7,6)，C 11=(5,7)，C 12=(4,8)，C 13=(3,9)，C 14=(10,5)，C 15=(9,6)，C 16=(8,7)，C 17=(7,9)，C 18=(10,6)，C 19=(9,7)，C 20=(8,9) 解释： 本题考查基于Pareto 支配的排序方法。 内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案： 由于{}18C C ；{}2349,,C C C C ；{}234510,,,C C C C C ；{}345611,,,C C C C C ； {} 45612 ,,C C C C ； {} 56713 ,,C C C C ； {} 12348914 ,,,,,C C C C C C C ；{} 1234591015 ,,,,,,C C C C C C C C ； {} 234569101116 ,,,,,,,C C C C C C C C C ；
多目标优化的求解方法
多目标优化的求解方法 多目标优化（MOP）是数学规划的一个重要分支，是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下： 多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。目前主要有以下方法： （1）评价函数法。常用的方法有:线性加权和法、极大极小法、理想点法。评价函数法的实质是通过构造评价函数式把多目标转化为单目标。 （2）交互规划法。不直接使用评价函数的表达式，而是使决策者参与到求解过程，控制优化的进行过程，使分析和决策交替进行，这种方法称为交互规划法。常用的方法有：逐步宽容法、权衡比替代法，逐次线性加权和法等。 （3）分层求解法。按目标函数的重要程度进行排序，然后按这个排序依次进行单目标的优化求解，以最终得到的解作为多目标优化的最优解。 而这些主要是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。
在工程应用、生产管理以及国防建设等实际问题中很多优化问题都是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其他若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少和总的运输费用最低, 这是含有两个目标的优化问题。利用首次适配递减算法和标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺的优化。Chung等人也成功应用遗传算法对锻件工艺进行了优化。 3)投资 假设某决策部门有一笔资金要分配给若干个建设项目, 在确定投资方案时, 决策者总希望做到投资少收益大。Branke等人采用基于信封的多目标进化算法成功地解决了计划投资地选择问题。 4)模拟移动床过程优化与控制 一个工业化模拟移动床正常运行时, 一般有七股物料进、出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值的变化。根据实际生产要求通常包括生产率、产品纯度、吸附剂消耗量等多个目标。模拟移动床分离过程由于其过程操作变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁多性, 需要众多学者对其操作优化和过程控制进行深入的研究。Huang等人利用TPS 算法解决了模拟移动床多个冲突目标的最大最小的问题, 并与NSGA2 算法的结果进行了比较。吴献东等人运用粒子群算法开发出一种非线性模拟移动床( SMB )色谱分离过程的优化策略。 5)生产调度 在离散制造生产系统中, 一个工件一般经过一系列的工序加工完成, 每道工序需要特定机器和其他资源共同完成, 各工件在各机器上的加工顺序(称技术约束条件)通常是事先给定的。车间调度的作用
布谷鸟算法的杂七杂八
关于布谷鸟算法的相关说法 又是一个不大常见的拥有一定的自带机制可以对付局部极小值点的算法，但是这个年代还是不大多见。 布谷鸟搜索（Cuckoo Search，CS）是由Xin-She Yang 和Suash Deb 于2009 年开发的自然启发式算法。CS 基于布谷鸟的寄生性育雏（brood parasitism，又巢寄生）行为。该算法可以通过所谓的Levy 飞行来增强，而不是简单的各向同性随机游走。研究表明，该算法可能比遗传算法、PSO 以及其他算法更有效。 不过这也是看具体的数据集的。 1 关于鸟类的育雏行为 布谷鸟（杜鹃）是一种神奇的鸟，不仅因为它们动听的啼鸣，还因它们的积极的繁殖策略。杜鹃科中的犀鹃（Ani Cuckoo）和圭拉鹃（Guira Cuckoo），将它们的蛋放在其他鸟的巢中，通过去除其他鸟（寄主）的蛋来增加自己蛋的孵化几率。有相当多种类的鸟都有将自己的蛋放在其他鸟的巢中这种寄生性育雏行为。这种方法使得一些科学家突发奇想，于是就有了现在的布谷鸟算法 寄生性育雏分为三种：种内寄生（intraspecific brood parasitism）、合作养育（cooperative breeding）和巢占据（nest takeover）。一些寄主鸟会与入侵的布谷鸟发生直接冲突。如果一个寄主鸟发现这些蛋不是他们自己的，那么他们要么将这些外来蛋清除掉。这是比较温和的生物，有的物种就比较暴脾气，他们直接放弃整个巢穴，在别处建造一个新的巢。一些布谷鸟，例如New World brood-parasitic Tapera，已经进化成这样一种方式，雌杜鹃通常非常善于模仿几种特定寄主的卵的颜色和纹理。这减少了它们蛋被遗弃的可能性，从而增加了它们的繁殖力。这种物种对产蛋时机的把握也非常到位。布谷鸟通常会选择那些寄主刚刚产下自己蛋的巢。一般来说，布谷鸟蛋的孵化时间要比寄主蛋的孵化时间要早一些。一旦第一只布谷鸟雏鸟孵化出来，第一个本能的动作就是通过盲目地推动将其他蛋从巢中推出，从而增加寄主对布谷鸟雏鸟的食物供给。研究还表明，杜鹃雏鸟还可以模仿寄主雏鸟的叫声，以获得更多的被喂食机会。 2 Levy飞行 Levy是征收的意思，同著名的枪战动漫《黑礁》的女主Revy要区分开。 另一方面，各种研究表明，许多动物和昆虫的飞行行为表现出了具有幂律规律的Lévy 飞行的典型特征。Reynolds 和Frye 最近的一项研究表明，如同很多像我一样的RTS玩家的习惯一样，很多人在开始探路开视野的时候喜欢无规律的乱画路径进行探路操作，在生物圈中，有的生物也有这种奇怪的习惯，诸如果蝇（或Drosophila melanogaster）利用一系列直线飞行路径和突然的90°转弯来探索景观，从而产生Lévy飞行式的间歇无标度搜索模式。针对人类行为的研究也表明，如Ju hoansi 狩猎采集觅食模式等也表现出了Lévy 飞行的典型特征。即使是光线也与Lévy 飞行有联系。另外，该行为已被应用于优化搜索，结果表明其具有潜力。