论文部分内容阅读
近年来,仿生算法得到了学术界的高度重视和长足的发展,并且涌现了很多新的算法,如粒子群算法、分布估值算法和Memetic算法等等。同时,仿生算法在广度和深度方面也有进一步的发展,尤其是在并行化方面,出现了许多新的尝试和成功案例。例如,先后有基于超级计算机、工作站集群、多核处理器、GPU和网格计算等的并行化实现。近几年云计算的出现和迅速发展,尤其是MapReduce编程模型的出现,为仿生算法的并行化提供了新的发展方向,本论文正是在此背景下提出的,具体的研究内容和创新点有:1)首先介绍了几种仿生算法和它们的发展现状、基本原理和应用领域,并总结了它们的收敛性和发散性的机理。启发式仿生算法,本质上都是随机搜索算法,对于复杂优化问题的性能不高和容易出现停滞现象,学术界一直致力于寻找发散与收敛之间的平衡点,一方面利用并行计算方法提高它们的性能,同时也采用各种优化方法提高解的质量。本文试图用最新的云平台Hadoop和Haloop来提高仿生算法的效率,并且优化了其中两种仿生算法的并行化策略。2)仿生算法并行化主要是提高算法的运算性能,让原来串行的算法变为可以并发执行的并行算法,从而缩短算法执行时间。但往往忽略了解质量问题,即停顿和陷入局部极值问题。本文提出的并行化试图在提高运算性能的同时,尽可能地扩大搜索空间,即被处理数据的并行化。如蚁群算法就提出动态正反馈和动态正负反馈来改进发散性和收敛性。蚁群被分成为若干子群,在算法前期,子群之间信息素相互“排斥”,而后期相互“吸引”,从竞争转为合作,这相当于前期各子群的搜索空间是相互独立的小岛。随着时间的推进,群间信息素逐渐融合,小岛的界限也逐渐消失,最终融合成一个大岛。这种改进可以保证算法前期搜索空间尽可能发散,后期则尽快收敛到全局最优解,并通过吸收态Markov模型对算法的收敛性进行了初步分析。3)沿用蚁群算法并行化优化的思路,对粒子群算法也采用动态反馈机制,并建立卫星模型。在算法前期,减小全局最优粒子的“引力”,让各个粒子子群尽可能地发散飞行,扩大搜索空间,即类似卫星的“自转‖;而随着算法不断地迭代发展,“引力”不断加强,让群的所有粒子尽快收敛到全局最优解,即类似卫星的“公转”。通过对其收敛性进行了详细分析,得出各参数的合理取值范围,也从理论上证明了算法的有效性。实验数据表明,改进算法更适合求解一定规模、较为复杂的优化问题。4)接下来介绍Hadoop和Haloop平台的特点,尤其是它们的核心部分―MapReduce框架的实现和工作机制,同时也对推测执行进行了介绍,尤其重点说明了Haloop改进的功能点和改进内容。5)在详细分析和对照Haloop现有的调度算法之后,本文针对Haloop的任务调度进行了改进。为了提高数据的本地性,分别给出了针对Map任务的二分图最大匹配算法和针对Reduce任务的加权二分图最佳匹配算法,尽可能地提高Map任务和Reduce任务的数据本地性,减少数据的网络传输,―移动计算比移动数据更划算‖。6)最后,结合Haloop平台API的特点和要求,用MapReduce编程模式分别实现了蚁群算法和粒子群算法的并行化。由于Haloop是组建在普通PC基础之上的,成本低廉,同时支持大规模的动态扩展,很适合应用仿生算法解决大规模的NP完全问题。通过仿真实验,初步确定算法改进的有效性和Haloop对仿生算法并行化的适应性。