论文部分内容阅读
遗传算法是模拟生物界的进化过程而产生的一种现代人工智能算法,它具有天然的并行性,在求解复杂、大规模、非线性、不可微的优化问题中具有较高的性能。当今单核计算机现在已经逐渐淘汰,多核机器的价格正在迅速下降,计算机的体系结构已逐渐向多核化方向发展,这为并行遗传算法的实现与应用提供了基础。并行遗传算法己经被越来越多的学者所关注、研究。本论文正是基于这种研究趋势,通过理论分析与实验相结合,提出了一种基于自适应迁移策略的并行遗传算法(AMPGA),该算法能够在当前个人计算机体系结构上实现,并能获得较好的效果,很大程度地提高了传统并行遗传算法的计算性能。本论文的主要工作和创新点:(1)提出了一种适合在当前多核计算机上运行的并行遗传算法实现方法,该方法将遗传算法同当前个人计算机体系结构相结合,使新的并行遗传算法在主流计算机上并行执行,加快算法的收敛速度,充分挖掘出计算机的计算能力。(2)提出了一种自适应种群迁移策略,该迁移策略根据当前的演化状态动态、有条件地迁移,有效地提高了个体迁移的效率和算法的收敛速度,减少了因为无效迁移造成的通信及同步开销,又保证了各子种群之间的优良个体有效迅速地传播,充分发挥了优良个体的导向作用,避免了传统并行遗传算法迁移时的盲目性,固定性,提高了传统并行遗传算法的全局寻优能力以及求解精度和收敛速度。(3)提出了接受算子和迁移算子策略。通过执行这两个算子,当在种群中个体差异程度较大,与全局最优值较远时,可以从其他子种群中接受一个优良个体,发挥优良个体的导向作用,加快收敛速度。当在种群中个体差异程度很小,且算法容易陷入局部最优值,将要导致早熟时,接受能够提高种群多样性的个体,从而跳出局部最优值,有效地避免早熟。(4)将AMPGA算法运用到一些Benchmark函数的优化问题中,通过数据仿真实验来测试AMPGA算法的计算性能,并对AMPGA在求解这些问题时的并行效率与传统并行算法进行对比分析。实验结果表明AMPGA算法比传统的并行遗传算法相比其收敛速度快、求解精度高,并行效率也明显比传统并行遗传算法更高。