论文部分内容阅读
粒子群优化算法(PSO)出现以来,在理论分析、收敛性能的提高、算法的应用等各个方面都已经出现了大量的研究。在PSO的运行过程中,需要迭代地对种群中的各个粒子进行适应度评价、速度和位置更新等处理,计算代价较高。事实上,PSO种群中各个粒子之间具有很高的独立性,存在良好的潜在并行能力。然而,目前的PSO算法大都是基于串行平台实现的,未能充分利用PSO的并行性,从而导致算法运行速度过慢,限制了PSO在实际优化问题中的应用。 本论文的研究目的在于,基于当前迅速发展并广受关注的图形处理器(GPU)这一并行计算平台,设计并实现具有良好收敛性能的新型并行单目标、多目标PSO,加快其运行速度,以达到运用粒子群优化算法又快又好地求解各类实际优化问题的目的。 本论文的研究内容包括:单目标PSO变种的研究,基于GPU的并行单目标PSO的研究,基于GPU的并行多目标PSO的研究。其中对单目标PSO的变种的研究是一大难点,需要对PSO的收敛特性有深入的研究,同时保证不丢失并行性。 我们按照如下的思路展开研究。首先,在保证不破坏PSO的潜在并行性的前提下,向PSO中引入增加种群多样性的机制以提高PSO的收敛性能。接着,采用一系列的标准测试函数对新型的PSO算法进行性能测试,验证其对收敛性能的改进。然后基于GPU实现设计出的新型并行单目标及多目标PSO算法,以加快其运行速度,并通过比较CPU与GPU上的相应PSO算法的运行速度来检验加速的效果。 本论文取得了如下三个主要成果: 提出了一种带触发式变异的PSO。设计出了一种判断PSO陷入停滞的准则。在根据该准则判断PSO种群陷入停滞时,对所有粒子的位置和速度应用均匀变异,以提高种群的多样性,增强其全局搜索能力。该机制使种群能摆脱出停滞状态,收敛性能得到较大的提高。我们还基于GPU实现了本算法,最高可达到25倍的加速比(GPU比CPU运行快的倍速)。本成果发表在2010ACM遗传与进化计算会议(GECCO)上,题为“Particle Swarm Optimization with Triggered Mutation and Its Implementation based on GPU(带触发变异的粒子群优化算法及其基于GPU的实现)”。 基于GPU实现了采用环形拓扑结构的并行单目标PSO。在NVIDIAGeforce8600GT显卡上进行的实验表明,基于GPU实现的PSO取得了10倍以上的加速比,大幅地提升了PSO的运行速度。本成果发表在2009年进化计算会议(CEC2009)上,题为“GPU-based Parallel Particle Swarm Optimization(基于GPU的并行粒子群优化算法)”。该成果也被作为一个章节发表在“Handbook of Swarm Intelligence”上。 提出了一种基于GPU实现的多目标PSO算法。该算法采用两个种群来分别优化两个目标,具有良好的并行性。基于GPU实现的多目标PSO算法达到了近5倍的加速比,同时保持着良好的收敛特性。本成果发表在国际人工智能杂志(IJAI2011)上,题为“GPU-based Parallel Multi-objective Particle Swarm Optimization(基于GPU的并行多目标优化粒子群算法)”。 总之,本论文从PSO算法收敛性能改进、并行PSO算法设计及其基于GPU的实现等多个方面展开研究,提出了改进PSO收敛性能和提高其运行速度的方法以及实现手段,为推动PSO在实际中的应用具有较大的价值。