试论一种基于自适应迁移策略的并行遗传算法

《试论一种基于自适应迁移策略的并行遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：密级：公开学号：2007201单位代码：10407硕士学位论文论文题目:一种基于自适应迁移策略的并行遗传算法研究方向智能计算专业名称计算机应用技术研究生姓名郭肇禄导师姓名、职称李康顺教授二00九年十二月二十六日江西·赣州摘要遗传算法是模拟生物界的进化过程而产生的一种现代人工智能算法，它具有天然的并行性，在求解复杂、大规模、非线性、不可微的优化问题中具有较高的性能。当今单核计算机现在已经逐渐淘汰，多核机器的价格正在迅速下降，计算机的体系结构已逐渐向多核化方向发展，这为并行遗传算法的实现与应用提供了基础。并行遗传算法己经被越来越多的学者所关注、研究。本论文正是基于

2、这种研究趋势，通过理论分析与实验相结合，提出了一种基于自适应迁移策略的并行遗传算法(AMPGA)，该算法能够在当前个人计算机体系结构上实现，并能获得较好的效果，很大程度地提高了传统并行遗传算法的计算性能。本论文的主要工作和创新点：(1)提出了一种适合在当前多核计算机上运行的并行遗传算法实现方法，该方法将遗传算法同当前个人计算机体系结构相结合，使新的并行遗传算法在主流计算机上并行执行，加快算法的收敛速度，充分挖掘出计算机的计算能力。(2)提出了一种自适应种群迁移策略，该迁移策略根据当前的演化状态动态、有条件地迁移，有效地提高了个体迁移的效率和算法的收敛速度，减少了因为无

3、效迁移造成的通信及同步开销，又保证了各子种群之间的优良个体有效迅速地传播，充分发挥了优良个体的导向作用，避免了传统并行遗传算法迁移时的盲目性，固定性，提高了传统并行遗传算法的全局寻优能力以及求解精度和收敛速度。(3)提出了接受算子和迁移算子策略。通过执行这两个算子，当在种群中个体差异程度较大，与全局最优值较远时，可以从其他子种群中接受一个优良个体，发挥优良个体的导向作用，加快收敛速度。当在种群中个体差异程度很小，且算法容易陷入局部最优值，将要导致早熟时，接受能够提高种群多样性的个体，从而跳出局部最优值，有效地避免早熟。(4)将AMPGA算法运用到一些Benchmark

4、函数的优化问题中，通过数据仿真实验来测试AMPGA算法的计算性能，并对AMPGA在求解这些问题时的并行效率与传统并行算法进行对比分析。实验结果表明AMPGA算法比传统的并行遗传算法相比其收敛速度快、求解精度高，并行效率也明显比传统并行遗传算法更高。关键词：遗传算法；并行算法；自适应迁移策略；函数优化IAbstractGeneticAlgorithm,amodernartificialintelligencealgorithm,resultsfromtheprocessofsimulationbiologicalevolutionary.Ithasnaturalpara

5、llelismandhashighperformanceinsolvingcomplex,large-scale,non-linear,non-differentiableoptimizationproblems.Currently,thesingle-corecomputersarebeingphasedout,thepriceofmulti-coremachineisrapidlydecliningandcomputerarchitecturehasbeengoinginthemulti-coredirection,allofwhichprovidethebasi

6、sforimplementationandapplicationoftheParallelGeneticAlgorithm.Thus,ParallelGeneticAlgorithmisbeingresearchedbymoreandmoreresearchers.Basedonthistendency,aParallelGeneticAlgorithmbasedonadaptivemigrationstrategy(AMPGA)isproposedinthisthesis,throughtheoreticalanalysisandexperiment.AMPGAco

7、uldbeachievedonthecurrentcomputersarchitecture,andcouldobtaingoodresults,whichcouldimprovetheperformanceoftraditionalParallelGeneticAlgorithmtosomedegree.Themajorworkandinnovationsinthethesisareasfollows:(1)AnimprovedParallelGeneticAlgorithm,whichissuitableforrunningonthecurren