论文部分内容阅读
群智能算法作为一种启发式随机算法,一直以来备受研究者的青睐。该类算法适用范围较广,它不要求目标对象具有特殊的结构,只需提供少量的信息就可以对目标对象进行求解,并且这类算法实现过程也比较简单。本文研究的果蝇优化算法(Fruit Fly Optimization Algorithm,FOA)也属于群智能算法中的一种,它是基于对果蝇觅食行为的模拟而总结出的一种仿生类群智能算法。目前,虽然FOA算法的研究与应用还处于起步阶段,其理论研究的深度与应用领域的广度都不及其他群智能算法。尽管如此,FOA也依然取得了一些不错的成果,例如,在经济领域内的企业绩效评估、交通领域内的道路规划及科学理论的研究等。果蝇优化算法的优点较为突出,它结构简单、易于理解及编程实现,并且全局寻优能力强、收敛速度快,但是,FOA算法的局限性也同样明显。首先,果蝇算法在迭代过程中,果蝇在可行域内的移动距离与方向都是随机的,造成算法的稳定性较差、寻优精度不高;其次,算法没有很好的利用果蝇群的历史信息,导致算法的效率较为低下,有较大的概率陷入局部极值点。因此,本文的一个重要研究内容就是针对FOA算法的局限性,设计出一种性能更加优越的果蝇优化算法,并将这种改进的果蝇优化算法在云工作流任务调度中进行了初步的应用研究。随着云计算产业的兴起与蓬勃发展,作为云计算的核心——云工作流任务调度算法的研究也越来越重要。任务调度问题是一个经典的NP-完全问题,智能算法一直是该研究领域的首选方案。其中,研究最多的智能算法为蚁群算法与粒子群算法,经过多年的研究蚁群算法或者粒子群算法在理论方面趋于完善,其在性能方面提升的空间越来越小。因而,急需在调度算法方面进行理论突破,或寻求一种新的算法来给调度策略提供其他的改进思路。具体地说,本文的主要工作内容总结如下:1、针对果蝇算法的稳定性、寻优精度及效率等问题,提出了基于群体协作与周期震荡衰减策略的果蝇优化算法。该改进算法从三个方面对原果蝇算法进行了理论上的改进:(1)采用群体协作方式,根据果蝇飞行能力的不同,将果蝇进行分群,提高了种群的多样性及算法的稳定性;(2)改进果蝇信息的更新策略,由最优个体决定子代果蝇的搜索域,转变为由一类最优果蝇群决定子代的搜索域,这种方式提高了果蝇群的利用率;(3)采用具有周期震荡递减性质的步长函数指导果蝇群的飞行,该函数使得果蝇既可以在全局域的搜索范围更广,又可以在局部域的搜索更加细化,提高了寻优的精度。2、为了验证改进果蝇算法的性能,本文选取了具有代表性的BenchMark函数作为测试用例,并将本文算法同其他群智能算法进行性能比较,综合地评价改进算法的性能。3、将本文提出的改进算法应用到云工作流任务调度领域中,采用亚马逊EC2计价模型,并将QoS约束中的成本、时间约束和用户的个性化需求等多目标优化问题,转变成一种新的、多角度反映调度策略优劣的单目标优化问题。并通过对任务DAG图进行重新建模,使其能更好地适用于改进的果蝇算法。