论文部分内容阅读
日渐复杂的现实生活优化问题给进化计算带来了新的挑战,分布式优化算法作为解决这一挑战的有效手段在过去的十年得到了广泛关注。Map Reduce作为云计算的代表性平台,能够和优化算法相结合,有效的推动了分布式进化算法的发展。粒子群优化算法是一种经典的进化优化算法,从它被提出开始,就得到了各界学者的关注,并相继提出了多种改进方案。协同粒子群优化算法与量子行为粒子群优化算法作为改进算法中的经典之作,从不同的角度着手提升了原始粒子群优化算法的性能。本文在总结相关领域已有成果的基础上,从Map Reduce原型入手,提出了一种新的适合优化算法的分布式模型,并通过两种改进的粒子群优化算法为例展示了分布式算法的性能,具体内容如下:(1)简单介绍了文章的研究背景,提出了大数据、云计算的现实问题,引出了分布式进化算法。在背景的基础上,进一步介绍了分布式进化算法、粒子群优化算法和云平台与Map Reduce的研究方向与已经取得的成果。随后过渡到本文的主要研究内容与章节安排。(2)通过编程模式、具体实现、相对优势以及Hadoop相关内容,详细介绍了Map Reduce模型。在基本模型之上,本文提出了一种新的进化算法模型,称之为MREA模型。MREA从可行域入手,将搜索空间分割成大量的不相互重叠的子空间,Map函数在由子空间组成的数据块上进行进化计算,得到各个子空间的相对最优解传递给Reduce函数;随后由Reduce函数进行对比筛选,选出全局最优解。提出的模型适用于绝大多数具有并行潜质的优化算法,移植操作简单便捷,对于大规模复杂问题的求解能够大大提高求解质量和计算效率。(3)提出了基于Map Reduce的协同粒子群优化算法。协同粒子群优化算法是一种维度分布的进化算法,它将原始种群的高维度种群分解为多个低维度子种群,通过种群降低维度在一定程度上避免了“维度灾难”,但是仍然受到早熟现象的困扰。将原始的协同粒子群优化算法移植到MREA模型上,新提出的算法既降低了种群的维度,又分割了定义域,缩小了单个进化算法的粒子搜索范围。“双重简化”促使新的并行算法不论在求解质量还是运行时间上都有显著的提升,并通过与CEC 2013的获奖算法相比,展示出了强劲的竞争力。(4)提出了基于Map Reduce的量子行为的粒子群优化算法。量子行为的粒子群优化算法通过将定义域从原始的经典空间转移到量子空间,搜索粒子可以出现在定义域的各个位置,粒子分布的广泛即能够克服标准粒子群优化算法所自带的早熟现象。然而随着问题规模的扩大,原始的串行算法在计算资源上受到了极大的克制。本文将量子行为的粒子群优化算法移植到了MREA模型上,实现了算法的并行化,大大提升了算法的效率,大幅度缩短了算法的运行时间,并在求解质量上有了一定的提高。