云环境中基于布谷鸟搜索算法的多目标任务调度方案_吴国芳

收稿日期：2014-06-21；修回日期：2014-08-04基金项目：浙江省教育厅高等学校访问学者专业发展项目（FX2013236）；浙江省教育厅

科研项目（Y201225529）

作者简介：吴国芳（1978-），女，浙江东阳人，讲师，硕士，主要研究方向为智能信息处理、数据库技术、图形图像处理（wgf_1978@126．com ）．

云环境中基于布谷鸟搜索算法的

多目标任务调度方案

*

吴国芳

1，2

（1．绍兴职业技术学院，浙江绍兴312000；2．浙江工业大学，杭州312024）

摘

要：效率往往是任务调度的首要目标，对于数据中心而言，能耗问题也是十分重要的因素。在布谷鸟搜索

（cuckoo search ，CS ）算法的基础上提出了一种多目标任务调度方案———MOCS ，以实现云环境下任务调度效率和能耗的Pareto 最优。布谷鸟搜索算法是一种启发式算法，利用Lévy flight （莱维飞行）通常能较快地寻找到全局最优解。利用CloudSim 云仿真平台将所提方案与采用遗传算法的多目标任务调度方案进行对比，仿真实验证明所提方案优于采用遗传算法的方案。

关键词：云计算；布谷鸟搜索；多目标优化；任务调度；莱维飞行中图分类号：TP301.6

文献标志码：A

文章编号：1001-3695（2015）09-2674-04

doi ：10．3969/j．issn．1001-3695．2015．09．027

Multi-objective task scheduling scheme based on cuckoo search

algorithm in cloud environment

Wu Guofang 1，

2

（1．Shaoxing Vocational ＆Technical College ，Shaoxing Zhejiang 312000，China ；2．Zhejiang University of Technology ，Hangzhou 312024，China ）

Abstract ：Effectiveness was always the primary goal of task scheduling ，for data centers ，power consumption was also very important factor．Based on the cuckoo search algorithm ，this paper proposed a multi-objective scheduling scheme-MOCS to a-chieve the Pareto optimization between low power consumption and efficiency of scheduling in cloud environment．Cuckoo search algorithm was a heuristic algorithm and could find global optima quickly．It used the CloudSim platform to compare the proposed scheme with the scheme employing genetic algorithms．Simulation results show that the proposed scheme outperforms the scheme employing genetic algorithms．

Key words ：cloud computing ；cuckoo search ；multi-objective optimization ；task scheduling ；Lévy flight

0引言

云计算是一种全新的计算模式，它采用虚拟化技术将异构

的硬件资源进行统一管理和分配，当用户将任务提交到数据中心时，数据中心则将任务分配到虚拟化后的硬件资源上处理并最终返回处理结果。当某一时刻待处理的任务量较大时，数据中心所承受的负载将进一步加剧，

功耗进一步增大，导致散热压力大，因此如何高效而节能地将任务分配调度到硬件资源上对于云计算的高效性是一个关键问题。

本文主要聚焦于效率和能耗的角度研究云环境下的任务调度，这涉及到多目标优化问题。多目标优化问题在工程界也得到广泛关注，最优方案往往需要考虑多种因素，而多种因素之间往往存在冲突，不能满足全部最优，因此如何解决多目标优化问题非常重要。云环境下的任务调度期望能在效率和能耗上得到双赢，满足用户需要的同时实现数据中心的可持续发展。

多目标优化问题

［1］

往往采用启发式算法解决，本文在布

谷鸟搜索算法（CS ）［2］

的基础上提出了一种多目标调度方案

（MOCS ）。该算法是一种元启发式算法，类似于遗传算法，用

数学方法描述来模拟自然界的某种特性，应用到优化问题中通常能得到较为满意的解。在云环境下任务量通常很大，因此解集将会非常大，布谷鸟算法与同类算法如遗传算法相比的优点则体现在解集大的情况下能够快速找到最优解。

为了验证所提方案的可行性及高效性，本文采用云仿真平台CloudSim3．0

［3］

作为实验平台，

通过模拟真实环境下的任务和虚拟机来实现调度方案，同时实现了采用遗传算法的调度方案以进行对比，实验结果证明了所提方案优于采用遗传算法的多目标任务调度方案。

1云环境任务调度建模

在云计算中，用户提交的任务到达数据中心时，由于短时

间内任务量较多，在为任务分配相应的计算资源时有多种方案，为了更高效地利用计算资源同时满足用户的要求，合理进行任务调度十分重要。本文根据真实云环境建立调度模型，对待解决的问题进行描述。1．1

调度模型

如图1所示为云平台下的任务调度模型结构，其中数据中

第32卷第9期2015年9月计算机应用研究

Application Research of Computers Vol.32No.9Sep．2015

心中的计算资源即计算节点，它将处理能力不同的计算节点（单机或服务器）虚拟化为虚拟机（VM ），这是云计算最大的特点，即采用虚拟化技术。在该结构图中，用户请求即用户提交的计算任务，期望能在计算资源上计算并返回计算结果。任务调度即根据效率和能耗等多方面综合考虑，将任务分配到相应的计算资源对应的任务队列中，等待处理，此处的任务调度将是本文的研究重点

。

图1

任务调度模型

1．2问题描述

在本文的模型中，用户请求是指采用云资源执行的云计算

任务的工作集合。假设A =（a 1，

a 2，…，a M ）为某一时期客户提交的任务集合。在调度过程中，用户为任务a i （1≤i ≤M ）提交一个服务请求，该任务的资源需求表示为三元组（t i ，n i ，d i ），其中t i 表示虚拟机（VM ）执行分配到的任务a i 所需要的时间，虚拟机是云计算中采用虚拟化技术产生的虚拟计算单元；n i 表示a i 所需要的虚拟计算单元个数。同时在实际的计算服务平台中，客户往往期望任务能在规定的时间完成，本文假设每项任务提交时都有对应的截止完成时间d i ，即限定在开始执行后的时间d i 内完成该任务，否则认为是未成功完成任务。

本文需要解决的问题是如何调度M 项任务到给定的N 个虚拟计算节点（虚拟机）上，满足客户要求在规定的时间完成所有任务，同时运营商能够在规定时间内高效率完成，保证低能耗，做到绿色节能。其中N 个虚拟计算节点即为分布在不同地理位置的云数据中心内的计算节点。1．3

性能指标

云环境下的任务调度往往将效率作为首要目标，目前的处理能力在硬件条件的支持下已不再是问题，关键问题是数据中心的大量处理机器运算会耗费大量电能，这对于分布了大量主机的数据中心十分不利，不仅浪费能源增加成本，而且造成数据中心散热问题。如果数据中心在最快时间内执行完所提交的任务时，单位时间内数据中心积累的热量会迅速增加，则需要投入更多的成本来完成散热工作；当将能耗降到最低时，效率往往得不到保证。所以在保证高效处理任务的同时，云计算应该聚焦于降低数据中心的能耗。

基于以上原因，本文所提方案考虑的性能指标主要包括效率和能耗。效率体现在执行完用户提交的所有任务的总时间，能耗即执行完这些任务的数据中心所消耗的能量。总执行时间表示为

time total =max V －1v =0∑n －1

t =0VM （v ，t ）

（1）

其中：V 为虚拟机个数；VM （v ，

t ）即为虚拟机v 执行任务t 所需要的时间；n 为分配到该虚拟机上任务的个数。

总能耗主要考虑的是虚拟机在处理任务时所耗用的电量，它与任务的复杂程度和虚拟机的处理能力有关。利用虚拟机执行该任务时的功率可以得出单个任务的耗能，然后求和则可以得出总任务耗能，它可以表示为

energy total =∑V －1v =0

（∑N －1t =0

（VM （v ，t ）?（power a （v ）－power d （v ）））+

power d （v ）?time total ）

（2）

其中：V 是虚拟机个数；VM （v ，

t ）即为虚拟机v 执行任务t 所需要的时间；N 为分配到该虚拟机上任务的个数；power a （v ）为虚拟机v 执行任务时的功率；power d （v ）为虚拟机v 空闲状态下的功率。虚拟机功率power （v ）与虚拟机v 的宿主机此时的利用率成比例，利用率越高，功率越大。1．4

Pareto 最优

多目标问题的结果可以表示为Pareto 最优解，它提供了各种不同的解

［4］

。本文中采用的多目标任务调度方案即是根据

需求从Pareto 解中寻找最优解。为了表示一个特定目标的权重，本文引进了一个二维向量，分别表示两种目标的权重。

如图2所示是三个二维向量的实例，其中p 1 p 5是经过实验产生的五组解，v 1=（0，1），v 2=（槡2/2，槡

2/2），v 2=（1，0）分别表示三种不同的需求。例如p 1是向量v 1对应的最优解，p 3是向量v 2对应的最优解，p 5是向量v 3对应的最优解。

这里可以根据用户或服务提供商的需求设置向量以产生最优解。

图2Pareto 最优模型

2MOCS 调度方案设计

任务调度问题是NP 难问题，对于该类问题，

采用启发式算法经过多次迭代往往能找到相对满意的解，如常见的遗传算

法（GA ）［5］、粒子群算法（PSO ）［6］、蚁群算法（ACO ）

［7］是常见的用来解决任务调度的算法。本文提出的布谷鸟调度算法是近几年来最新元启发式算法中较为优秀的算法之一，研究表明布谷鸟算法在大多数情况下相对于遗传算法和粒子群算法更高效［8］

。

2．1

布谷鸟搜索算法

布谷鸟搜索算法（cuckoo search ）是由Xin 等人在2009年

提出的一种优化算法［2］

。该算法模拟了自然界中布谷鸟的特

性，布谷鸟从不筑巢，而是将其他鸟类的巢穴作为下蛋的地方，当宿主鸟发现了这些蛋不是自己所下的蛋时，有的宿主鸟会丢弃这些外来的蛋，而有的则会丢弃鸟巢而在别处重新建筑一个新的鸟窝。由上可知，

最优解就相当于那些最不容易被发现的鸟蛋，在这个过程中，不断优化，最后得以生存，直至孵出幼鸟。这在一定程度上和遗传算法很相似，优胜劣汰，因此布谷鸟算法也是一种启发式算法，它在解集中寻找一个全局最优解。布谷鸟算法满足以下三种特征：

a ）每个布谷鸟每次下一枚蛋到一个随机算子的鸟巢中。

b ）具有高质量鸟蛋（解）的鸟巢将保留到下次迭代中。

c ）鸟巢数是固定的，宿主鸟发现外来蛋的概率是p α∈（0，1），发现后宿主鸟会丢弃该蛋或舍弃该鸟巢并重新创建一个鸟巢并下蛋。

在产生新的鸟蛋（解）时，布谷鸟算法采用Lévy flight ［9］

进

·

5762·第9期吴国芳：云环境中基于布谷鸟搜索算法的多目标任务调度方案

行随机优化。Lévy flights 是模仿自然界的一种随机移动方式。在自然界中，动物寻找食物往往采用一种随机的形式行走，包括方向和步长。通常，动物的觅食路径是一种高效的随机行走方式，因为下一步的移动是基于目前位置/状态和到下一方向的转换概率。Lévy flight 正是遵循该种规律的一种随机分布。

相对于高斯分布和统一分布，

Lévy flight 更遵循自然规律，当解集很大时，Lévy flight 往往更具有优势，因此该特点适用于任务调度解集较多的情况中。设x （t ）

i 为鸟巢i 第t 次迭代的鸟

蛋即解，则新的鸟蛋x

（t +1）

i

可以通过如下形式进行Lévy flight ：

x （t +1）

i =

x （t ）

i +α⊕Levy （β）

（3）

其中：⊕表示正交相乘；α＞0是步长，它与问题集的规模有关，通常设置α=O （1），为了调整求解质量之间的差别，本文设置为

α=α0（x （t ）j －x （t ）i ）

（4）

其中：α0是步长因子，是算法中仅需设置的几个参数之一；x （t ）

j 和x （t ）

i

是第t 次迭代随机选取的两个解，

这模拟了相似的蛋不容易发现的自然规律，因此新解是根据它们差的比例产生的。

Lévy flight 提供一种随机行走，它的步长根据莱维分布得到

Levy u =t －1－β

0＜β≤2

（5）

其中：β为常数，通常设置为β=3/2，因此由式（4）和（5）可总结出

α0（x （t ）j －x （t ）i ）⊕Levy （β） 0．01

u

|v |β

（x （t ）j －x （t ）i ）（6）

其中：u 和v 都服从正态分布。

u N （0，σ2u ），v N （0，σ2v ）

（7）

其中：σu 和σv 分别满足

σu =

Γ（1+β）sin （πβ/2）Γ（1+β）/[]2β2（β－1）/{}

2

1/β

，σv =1

（8）

其中：Γ是伽马函数

Γ（z ）=

∫

?

t z －1e －t d t （9）

综合以上公式可知，相对于遗传算法等著名启发式算法，布谷鸟的参数更少，因此大大削弱了参数对实验效果的影响，较方便地调控参数便能得到理想的结果。同时布谷鸟算法通过全局随机化来拓展，在现有基础上采用模拟自然的Lévy flight 进行优化，优化效果明显而不易陷入局部优化，能够更快地找到全局最优解。2．2

多目标优化

多目标布谷鸟搜索算法（MOCS ）［10］

的主要思想是通过对

鸟巢里的蛋综合多种因素分析来判断解是否为Pareto 最优，这类似于现实中宿主鸟根据大小、颜色、光泽来判断鸟蛋是否是鸟巢中原来的蛋。为了有效评估解的优秀程度，需要将目标函数转换为可以评估的数值，定义为相似度，可采用如下公式评估鸟蛋i ：

S 1（x （t ）i ）=1/time total （x （t ）i ）（10）S 2（x （t ）i ）=1/energy total （x （t ）i ）

（11）

其中：S 1（x （t ）

i ）、

S 2（x （t ）i ）均为相似度，即最接近理想解的程度，通过取倒数得到，因为期望时间和能耗越小越好。S 1（x （t ）

i ）和

S 2（x （t ）i ）的整合对于评估最优解十分重要，由于它们可能不在一个数量级上，

必须对它们进行处理，以达到在同一数量级上。本文采用如下方式进行处理：

P 1（x （t ）i ）=S 1（x （t ）i ）

∑scale －1

i =0

S 1（x （t ）i ）

（12）

P 2（x （t ）i ）=S 2（x （t ）i ）

∑i =0

S 2（x （t ）i ）

（13）

其中：scale 表示鸟巢的个数，由公式可知∑scale －1i =0

P 2（x （t ）

i ）=1，∑scale －1i =0

P 2（x （t ）

i ）=1，

P （i ）越大，则该解越优秀。接下来需要基于Pareto 模型对P 1（x （t ）i ）和P 2（x （t ）

i ）进行

整合

fitness （x （t ）i ）=v ?（P 1（x （t ）i ），P 2（x （t ）i ））

（14）

其中：fitness （x （t ）i ）是评价解x （t ）i 的数值基准，

综合体现解x （t ）

i 在时间效率和能耗方面的优越性，它越大则解x （t ）

i 越优。

2．3

实现

在启发式算法中，往往采用一种特定的编码方式来表示调度方案，然后根据该编码进行操作，迭代到最后得到较为优秀的解，即为最优调度方案。实现的过程中往往采用数组的形式

表示解x t

i ，显然用二维数组表示所有的解集。其中进行Lévy

flight 全部针对数组进行计算，产生的结果更新到数组中并重新进行新一轮的计算，所有采用数组对于实现本文所提算法十分有利。

如图3所示为解集个体的表示形式，可以看到，第一项任务分配到序号为5的虚拟机上执行，依此类推，每个任务都分配了相应的虚拟机

。

图3

解集个体

本文所提方案执行过程采用伪代码描述，具体如下所示：算法1

基于布谷鸟搜索算法的多目标任务调度方案

1设置算法参数，随机产生scale 个鸟窝的初始鸟蛋x t i （i =1，

2，…，scale ），t =1；

2While （t ≤scale or 满足停止条件）

3由式（14）计算x t i 的适应度，记录当前最优解；

4保留最优x t i ，利用式（3）对其他x t i 通过Lévy flight 计算

x t +1i ；

5对x t +1i 与x t i 进行适应度对比，

若优则更新为x t +1i ；6随机产生（0，

1）之间的常数R 作为宿主鸟发现外来鸟蛋的可能性并与丢弃概率p α进行比较；

7if （R ＞p α）

8基于其他解产生新的x t +1i ；9end if 10t ←t +1；11end while

12

处理并输出最终解，并按照解将任务分配到虚拟机任务队列中。3实验与结果

本文所提的布谷鸟调度算法和对比的采用遗传算法的调

度方案均在CloudSim 3．0下实现和进行仿真。3．1

CloudSim

CloudSim ［10］是由墨尔本大学网格实验室开发的框架平台，它允许在设计的云计算设施上开展无缝的建模、仿真和实验。CloudSim 是一种完备的框架，可以用来对一个大规模云平台进行数据中心、服务代理、调度和分配策略建模。它提供了一种虚

·

6762·计算机应用研究

第32卷

拟引擎技术，建立在同样由网格实验室开发的GridSim 之上。3．2

实验设置

为了体现云计算资源的异构性，本文设置了不同处理能力的虚拟机，每台虚拟机拥有不同的处理能力，不同的虚拟机对应着不同的利用率，此时机器的功率也不同，如表1所示。

表1

实验平台参数设置

实体类型参数值任务（cloudlet ）

任务长度1000 20000任务总数100 1000

虚拟机总数

50MIPS

500 2000虚拟机（VM ）内存256 2048带宽500 1000核数

1 4数据中心

数量10（datacenter ）

主机数

2 6

如表2所示为MOCS 方案的算法参数设置，该参数是经过多次实验对比所选取的参数。

表2

MOCS 参数设置

参数值解集规模scale 100迭代次数1000丢弃因子p α0．25步长因子α0

10

3．3性能评估

为了研究选择向量对于MOCS 方案的影响，本文选择了三

组向量，并在任务数为1000的相同条件下分别开展了30组实验，取均值（保留一位小数），如表3所示。本文对比的遗传算法（GA ）方案和MOCS 方案采用相同的适应度函数。

表3

选择不同向量的能耗、时间

选择向量能耗/kWh 时间/s v 1=（0，1）42．3547．3v 2=（槡22，

槡2

2）48．9425．5v 3=（1，0）

57．8

375．3

根据表3可知，当选择向量取v 2时，两种解能得到较为平衡的解，取v 1和v 3时能分别得到时间和效率方面的最优解。因此其他实验选择v 2作为选择向量进行时间和能耗的多目标优化。

如图4所示是MOCS 和GA 两种方案在相同条件下的任务执行总时间迭代对比情况，其中MOCS 方案找到最优解的迭代次数相比于GA 方案提前了200次

，而且执行完所有任务所需要的时间要少70s 。

图4MOCS 与GA 时间迭代对比

如图5所示是不同任务数情况下MOCS 方案在时间方面与GA 方案的对比图。由图可知在不同的任务数下，MOCS 方案的效率高于GA 方案，特别是对于任务数越来越多的情况下，这说明布谷鸟算法在解集较大时更能体现出优势。

如图6所示是不同任务数情况下MOCS 方案在能耗方面与GA 方案的对比图。由图可知在不同的任务数下

，MOCS 的能耗始终低于GA 。

图

5MOCS 与GA 效率对比图6MOCS 与GA 的能耗对比

由以上实验结果可看出，本文所提MOCS 方案相比于GA 方案性能更加优秀，同时能够实现双目标的优化，无论是效率还是能耗方面都优于采用遗传算法的调度方案。云环境下的任务量通常会非常大，根据以上规律，若将本文的调度方案应用到云环境中进行任务调度，将会进一步提高效率和降低能耗。

4结束语

本文提出的任务调度方案解决了云环境下任务调度在时

间和能耗方面的多目标优化问题，其性能优于采用遗传算法的多目标调度方案。本文首先介绍了云环境下的任务调度模型和问题，通过采用布谷鸟搜索算法，结合Pareto 最优模型，完成多目标优化任务调度，实现效率与能耗的双赢。本文工作未考虑负载均衡，在未来的工作中将致力于研究包括负载均衡的布谷鸟多目标优化问题。参考文献：

［1］Yang Xinshe ，Suash D．Cuckoo search via Lévy flights ［C ］//Proc of

World Congress on Nature ＆Biologically Inspired Computing．［S．l．］：IEEE Press ，

2009．［2］Calheiros R N ，Ranjan R ，Beloglazov A ，et al．CloudSim ：a toolkit

for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms ［J ］．Software ：Prac-tice and Experience ，2011，41（1）：23-50．

［3］Renaud H ，Pierre S．A support-based algorithm for the bi-objective

Pareto constraint ［C ］//Proc of AAAI．2014：2674-2679．

［4］Xu Yuming ，Li Kenli ，Hu Jingtong ，et al ．A genetic algorithm for

task scheduling on heterogeneous computing systems using multiple priority queues ［J ］．Information Science ，2014，270：255-287．［5］Sadasivam G S ，Selvaraj D．A novel parallel hybrid PSO-GA using

MapReduce to schedule jobs in Hadoop data grids ［C ］//Proc of NaBIC．2010：377-382．

［6］李锋华．基于蚁群算法的云计算资源负载均衡调度算法研究

［D ］．昆明：云南大学，2013．

［7］Gandomi A H ，Yang X S ，Alavi A H．Cuckoo search algorithm ：a

metaheuristic approach to solve structural optimization problems ［J ］．Engineering with Computers ，2013，29（1）：17-35．

［8］Jamil M ，Zepernick H J ，Yang Xinshe．Lévy flight based cuckoo

search algorithm for synthesizing cross-ambiguity functions ［C ］//Proc of Military Communications Conference．San Diego ：IEEE Press ，2013．

［9］Yang Xinshe ，Deb S．Multiobjective cuckoo search for design optimi-zation ［J ］．Computers ＆Operations Research ，2013，40（6）：1616-1624．

［10］Kumar R ，Sahoo G．Cloud computing simulation using CloudSim ［J ］．

International Journal of Engineering Trends and Technology ，2014，8（2）：82-86．

·

7762·第9期吴国芳：云环境中基于布谷鸟搜索算法的多目标任务调度方案

云计算数据中心调度算法研究

云计算数据中心资源调度关键技术研究 项目背景 云计算是建立在计算机界长期的技术积累基础之上，包括软件和平台作为一种 服务，虚拟化技术和大规模的数据中心技术等关键技术。数据中心（可能是分布在 不同地理位置的多个系统）是容纳计算设备资源的集中之地同时负责对计算设备的能源提供和空调维护等。数据中心可以是单独建设也可以置于其他建筑之内。动态分配管理虚拟和共享资源在新的应用环境--云计算数据中心里面临新的挑战，因为云计算应用平台的资源可能分布广泛而且种类多样，加之用户需求的实时动态变化 很难准确预测，以及需要考虑系统性能和成本等因素使得问题非常复杂。需要设计高效的云计算数据中心调度算法以适应不同的业务需求和满足不同的商业目标。目前的数据中心调度算法依据具体的应用（计算资源，存储，搜索，海量信息处理等）不同采用不同策略和算法。提高系统的响应速度和服务质量是数据中心的关键技术指标，然而随着数据中心规模的不断扩大，能源消耗成为日益严重和备受关注的问 题，因为能源消耗对成本和环境的影响都极大。总的发展趋势是从简单的粗旷的 满足功能/性能需求的方式向精细的优化节能的方向发展。

2云计算数据中心资源调度方案分析 2.1 Google 解决方案 Google 也许是业界最早使用和发起云计算的厂家之一。因商业保密，其大部 分技术实现内容并未被外界了解。 从其公开发表的文献可及了解到其关于云数据中 心，搜索引擎网络设计,分布式文件系统以及并行处理模式 MapReduce 的概要设 计。Google 云计算平台架构，其基础平台是建立在 Map Reduce 结构之上。利用了 类似Hadoop 的资源调度管理方法。不过 Google 自己设计了文件系统（ GFS hunkserver ）,数据库系统（BigTable ）以及其它相关系统。 2.2 Amazo n 解决方案 Amazon 目前被认为推广云计算应用最为成功的厂家之一。 它成功地推出了 EC2（弹性云计算），SQS （简单消息存储服务），S3（简单存储服务），SimpleDB （简单 数据库）等近十种云服务。Amazon 的云计算平台体系结构，其中（EBS: Elastic Block Service, Providi ng the Block In terface, Stori ng Virtual Mach ine Images ）。 2.3 IBM 解决方案 的蟻㈱Q. 图一.多数据中心调度算法的参考体系结构

基于优化问题的多目标布谷鸟搜索算法

基于优化问题的多目标布谷鸟搜索算法 关键字：布谷鸟搜索、元启发式算法、多目标、最优化 摘要：在工程设计方面，很多问题都是典型的多目标问题，而且，都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题，使得与单一目标问题的解决有明显的区别，计算结果和函数值有可能会增加多目标问题的特性。此时，元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中，我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验，发现它可以应用于解决结构设计等问题中去，例如：光路设计、制动器设计等。另外，我么还对该算法的主要特性和应用做了相关的分析。 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 项目调度

一种改进的实时混合任务调度算法

一种改进的实时混合任务调度算法 谢建平1，阮幼林1,2 1武汉理工大学信息工程学院，武汉（430070） 2南京大学计算机软件新技术国家重点实验室，南京（210093） E-mail：xjp_1997@https://www.wendangku.net/doc/5514344155.html, 摘要：文章提出了结合TBS（总带宽服务器法）算法和DMS（时限单调算法）算法的实时混合任务的调度算法，该方法能保证周期任务满足时限的要求，还能缩短非周期任务的响应时间。基于TBS服务器思想将非周期任务转换成有时限要求的硬实时任务，然后基于DMS 调度周期任务和非周期任务。由于是使用静态的DMS算法，不仅可以减小任务的切换开销，而且对系统的瞬时过载有一定的适应性。 关键词：实时系统；任务调度；时限单调算法；总带宽服务器算法 1. 概述 随着计算机技术的飞速发展与普及，实时系统已经成为人们生产和生活中不可或缺的组成部分。实时系统具有及时响应、高可靠性、专用性、少人工干预等特征[1]，被广泛应用于工业控制、信息通讯、网络传输、媒体处理、军事等领域。实时系统的正确性不仅依赖于计算的逻辑结果，还取决于获得计算结果的时间的正确性。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。 由于实时系统的应用面非常广，所以实时系统的分类方法很多。通常按照系统中任务的周期性或者任务对截止期限的要求进行划分。实时任务按照周期性划分可以分为周期实时任务（periodic task）和非周期实时任务（aperiodic task）；按照对截止期限的要求可以分为硬实时任务和软实时任务[1]。 本文提出了结合TBS（总带宽服务器法）算法[5]和DMS（时限单调算法）[6]算法的实时混合任务的调度算法，该方法能保证周期任务满足时限的要求，还能缩短非周期任务的响应时间。算法将非周期任务赋予一个假想的时限，然后整个实时系统采用DMS算法调度。由于是使用静态的DMS算法，不仅可以减小任务的切换开销，而且对系统的瞬时过载有一定的适应性。 2. 实时系统的任务调度 由于实时调度是保障实时系统满足时间约束的重要手段，所以一直是实时计算研究领域中倍受关注的热点问题。调度的实质是资源的分配，包括处理器和其他运算、交互、存储资源，调度就是来用来将这些资源合理地分配给各个实时任务的一种方法。 根据调度顺序产生的时机和方式可以分为静态调度和动态调度[1]。若调度算法是在编译的时候就做出决定从就绪任务队列中选择哪个任务来运行的，则这样的调度是静态的。这类调度算法假设系统中实时任务的特性(如：截止期，WCET等)是事先知道的。它脱机地进行可调度性分析，并产生一个调度表。静态调度算法的优点是运行开销小，可预测性强。但是，由于静态调度算法一旦做出调度决定后在运行期间就不能再改变了，所以它的灵活性较差。 如果调度器是在运行期间才决定选择哪个就绪任务来运行的，则这类调度被称为动态调度。动态调度算法能够对变化的环境做出反应，因此，这类调度算法比较灵活，适合于任务不断生成，且在任务生成前其特性并不清楚的动态实时系统。但是，动态调度算法的可预测性差且运行开销较前者大。

云计算中任务调度算法的研究综述

云计算中任务调度算法的研究综述-电子商务论文 云计算中任务调度算法的研究综述 文／张艳敏 摘要：云计算中任务调度算法的好坏直接影响云计算系统整体性能，也影响着云计算系统处理用户提交的任务的能力。本文归纳了云计算调度的特点和性能指标，总结了云计算中的任务调度算法，分析了云计算任务调度算法的研究现状及其进展。最后讨论了现有任务调度策略存在的问题，为云调度研究指明了方向和思路。 关键词：云计算；任务调度；遗传算法；蚁群算法 前言 云计算是一种基于互联网的新的服务模式，这种模式按使用量付费，提供可用的、便捷的、按需的网络访问，它将用户需求的计算任务分布在由大量计算机构成的数据中心，数据中心采用虚拟化技术，把各种软硬件资源抽象为虚拟化资源，再通过资源调度技术使各种应用能够根据需要获取计算能力、存储空间和信息服务。 在云计算环境中，一个大规模计算任务需要进行分布式并行处理，系统首先将逻辑上完整的一个大任务切分成多个子任务，然后根据任务的相应信息采取合适的调度算法，在不同的资源节点上运行这些子任务，所有的子任务处理完后进行汇总，最后将结果传给用户。云计算任务调度的目的是给需要的用户分配不同的资源，在某一特定的云环境下，依据某一种规则使用资源，在不同的用户之间平衡和调整资源，在满足用户需求的前提下，使得任务完成时间尽量小，且资源利用率尽量高。调度最终要实现时间跨度、服务质量、负载均衡、经济原则最

优等目标。云计算任务调度是云计算研究中的重点和难点。任务调度算法的优劣会影响到云计算系统处理任务的能力。近几年，研究者针对云环境下的资源调度做了很多研究，主要体现在以提高云计算数据中资源利用率为宗旨的资源管理与调度、以降低云计算数据中心的能耗为目标的资源分配与调度、经济学的云资源管理模型研究等方面。 本文综述了云环境下的任务调度算法，分析了近几年来典型的云计算任务调度算法的发展趋势，为相关领域的研究人员提供参考。 1、网格任务调度与云计算任务调度的比较 在网格计算和云计算中，虽然系统资源都是以数据池的形式呈现给用户，但它们之间的区别是网格用户的任务是通过实际的物理资源来执行，而云计算环境下的用户任务是通过逻辑意义上的虚拟资源来执行。对于以上两种计算方式，都是由用户将任务提交给计算中心，系统通过对任务的需求进行分析，然后来寻找合适的资源节点执行，此时的用户并不关心执行任务的是哪个节点。网格系统通过用户预先设定的任务并行执行算法，并结合自己的调度系统使用户任务实现跨物理节点并行执行[1]，云计算任务调度通常情况不会跨虚拟机并行调度。尽管云计算是在网格计算、分布式计算及并行计算的基础上发展起来的，但是云环境比较复杂，任务呈现多样性，而且是以商业服务作为宗旨。云计算任务调度策略不能照搬传统调度策略来满足用户提出的各种任务要求，必须考虑怎样在高效任务调度与资源分配同时提高经济效益、资源利用率以及用户体验等各方面的因素。可靠的云服务和各层次的用户公平使用资源的机会是云计算调度策略必须考虑的问题，此外还需要有一个调度策略来提供系统可以使用的资源，以便满足多样化的用户需求。因此虚拟化技术在云计算中的广泛应用、中间层与资源节点以

云计算中基于cloudsim的蚁群调度算法研究

龙源期刊网 https://www.wendangku.net/doc/5514344155.html, 云计算中基于cloudsim的蚁群调度算法研究 作者：张翰林谢晓燕 来源：《电脑知识与技术》2016年第03期 摘要：介绍了云计算仿真工具cloudsim，在描述其架构的基础上，实现了cloudsim模拟云环境下调度策略的过程。引入蚁群算法，并基于蚁群算法实现了对cloudsim中调度策略的拓展，并与轮循、贪心等传统代数算法进行对比分析测试。结果表明，蚁群算法在应对云计算中海量任务和数据处理时，由于传统代数算法。 关键词：云计算，cloudsim，蚁群算法 中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）03-0219-02 云计算按照服务类型，大致可以分为三类：将基础设置作为服务Iaas、将平台作为服务paas、将软件作为服务saas。然而，不管何种类型的云计算服务，都有不同的、负责的组件，配置环境和部署条件的要求，因此，在异构真实的云环境下，对云端调度分配策略的优劣的评价，以及由调度策略所带来的云端设备的复合、节能、系统规模性能进行量化、评价是非常不易的。所以，本文引入云计算仿真工具Cloudsim，构建一个云环境下的分布式系统模拟器来实现云计算试验的模拟。 与此同时，目前广泛应用于云计算的如先到先服务FCFS算法、Greedy贪心算法[2]等，由于算法本身的特点，均是传统代数算法静态建模完成的，并不能针对网络中各种不确定变化做出对应的调整。而蚁群优化算法作为一种智能算法，在经过多次迭代后，任务必然能分配给一个合理的虚拟机。因此，本文在介绍Cloudsim架构、工作原理的同时，通过cloudsim搭建了一个云计算平台，并在此平台下，对FCFS算法、Greedy贪心算法以及蚁群优化算法进行的对比测试和分析。结果证明蚁群优化算法对于网络中突发情况的应对是较优的。 1 cloudsim介绍 1.1 cloudsim体系结构 Cloudsim是澳大利亚墨尔本大学Rajkumar Buyya教授领导团队开发的云计算仿真器，是一个通用的、可拓展的支持建模和模拟的仿真框架，并能进行云计算基础设施和管理服务的实验。其体系结构[1]如图： 1.2 cloudsim技术实现

基于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

实时任务调度系统的RM调度算法算法研究与实现

毕业设计(论文)任务书 系专业___ _____班学生______________ 一、毕业设计(论文)题目实时任务调度系统的RM调度算法研究与实现 二、毕业设计(论文)工作自__2008_年_1_月_20__日起至_2008_年_5_月_30_日止。 三、毕业设计(论文)地点:上海杰普软件科技有限公司__________ 四、毕业设计(论文)内容要求: 1、课题的意义 提到调度算法, 就不得不提到RM调度算法。目前生产调度过程的响应和应用影响企业的生产力和企业核心竞争力，能够实现实时的优化调度系统的执行效率，直接决定了系统的有效作用。本课题要求能够通过RM调度算法实现任务调度系统，要求实现可配置的软件模块开发。 2、设计要求： 设计出灵活、便捷的用户操作界面，支持车间多用户并发访问，合理设计数据库对象，设计并使用RM调度算法进行调度任务规划，包括模块如下： ●系统初始化模块：调度对象初始化、调度对象的信息管理与配置、调度用户初 始化； ●调度过程管理模块：调度过程的实现与调度任务的控制管理。 ●调度评估管理模块：管理以往调度的实现和结果统计，产生对应报表。 3、知识体系要求 ●学习并掌握jdbc编程 ●学习并掌握socket编程 ●学习并掌握xml解析技术 ●学习掌握java gui程序构建 ●算法的研究与应用 4、需查阅的资料 ●Sun公司规范文档 ●搜索算法技术文档 5、设计任务的提交形式和要求 ●设计论文一份 ●翻译资料一份 ●设计作品(包括相关源代码一份)

6、总体进度安排 第1周：调研、学习、查询资料 第2-4周：需求分析与软件设计 第5-8周：系统设计，包括数据库设计和系统架构设计 第9-12周：软件实现及测试 第13-14周：论文 第15周：答辩 教研室指导教师 教研室主任______________ 接受任务日期________________ 批准日期_______________ 学生签名__________________

布谷鸟搜索算法简介

布谷鸟搜索算法 维基百科，自由的百科全书 布谷鸟搜索（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的性能。

算法导论_实验三 一个任务调度问题

实验三一个任务调度问题 1.问题描述: 在单处理器上具有期限和惩罚的单位时间任务调度问题. 2.算法原理: 考虑一个给定的调度. 我们说一个任务在调度迟了, 如果它在规定的时间之后完成; 否则, 这个任务在该调度中是早的. 一个任意的调度总可以安排成早任务优先的形式, 其中早的任务总是在迟的任务之前. 为了搞清这一点, 请注意如果某个早任务a(i)跟在某个迟任务a(j)之后, 就可以交换a(i)和a(j)的位置, 并不影响a(i)是早的a(j)是迟的状态. 类似的,任意一个调度可以安排成一个规范形式, 其中早的任务先于迟的任务, 且按期限单调递增顺序对早任务进行调度. 为了做到这一点, 将调度安排成早任务优先形式. 然而, 只要在该调度中有两个分别完成于时间k和k+1的早任务a(i)和a(j) 使得d(j)

逐维改进的布谷鸟搜索算法

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.wendangku.net/doc/5514344155.html, Journal of Software,2013,24(11):2687?2698 [doi: 10.3724/SP.J.1001.2013.04476] https://www.wendangku.net/doc/5514344155.html, +86-10-62562563 ?中国科学院软件研究所版权所有. Tel/Fax: ? 逐维改进的布谷鸟搜索算法 王李进1,2, 尹义龙2, 钟一文1 1(福建农林大学计算机与信息学院,福建福州 350002) 2(山东大学计算机科学与技术学院,山东济南 250101) 通讯作者: 尹义龙, E-mail: ylyin@https://www.wendangku.net/doc/5514344155.html,, https://www.wendangku.net/doc/5514344155.html,/ylyin.html 摘要: 布谷鸟搜索(cuckoo search,简称CS)算法是一种新兴的仿生智能算法,对解采用整体更新评价策略.在求 解多维函数优化问题时,由于各维之间相互干扰,采用整体更新评价策略将恶化算法的收敛速度和解的质量.为了弥 补此缺陷,提出了基于逐维改进的布谷鸟搜索算法.在改进算法的迭代过程中,针对解采用逐维更新评价策略.该策 略将各维的更新值与其他维的值组合成新的解,并采用贪婪方式接受能够改善解质量的更新值.实验结果说明,改进 策略能够有效地提高CS算法的收敛速度并改善解的质量.与相关的改进布谷鸟搜索算法以及其他演化算法的比较 结果表明,改进算法在求解连续函数优化问题上是具有竞争力的. 关键词: 布谷鸟搜索算法;逐维改进;函数优化;多维函数;干扰现象 中图法分类号: TP183文献标识码: A 中文引用格式: 王李进,尹义龙,钟一文.逐维改进的布谷鸟搜索算法.软件学报,2013,24(11):2687?2698.https://www.wendangku.net/doc/5514344155.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/5514344155.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/5514344155.html,, https://www.wendangku.net/doc/5514344155.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

布谷鸟算法的杂七杂八

关于布谷鸟算法的相关说法 又是一个不大常见的拥有一定的自带机制可以对付局部极小值点的算法，但是这个年代还是不大多见。 布谷鸟搜索（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 飞行有联系。另外，该行为已被应用于优化搜索，结果表明其具有潜力。