求解N皇后问题的片上多核并行混合遗传算法

摘要：

遗传算法求解大规模皇后问题的耗时长、速度慢.为此,在分析现有N皇后问题求解方案和并行遗传算法的基础上,将动态规划引入到局部搜索策略中,在多核平台实现粗粒度并行遗传算法(CPGA)用于求解N皇后问题,避免传统的粗粒度并行种群迁移、通信等开销.针对并行化后多个子种群解趋同、迭代慢等问题,提出改进的面向遗传算子并行化的遗传算法(OOPGA).实验结果表明,改进后的OOPGA算法在运行时间、加速比等方面均比CPGA算法好.

关键词：片上多核、遗传算法、并行计算、粗粒度、N皇后问题、遗传算子并行化

所属期刊栏目：41

分类号：TP391(计算技术、计算机技术)

资助基金：安徽省自然科学基金资助项目10040606Q42;安徽高校省级自然科学研究基金资助重点项目KJ2013A177

在线出版日期：2015-09-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：199-203