摘要： 遗传算法求解大规模皇后问题的耗时长、速度慢。为此,在分析现有N皇后问题求解方案和并行遗传算法的基础上,将动态规划引入到局部搜索策略中,在多核平台实现粗粒度并行遗传算法(CPGA)用于求解N皇后问题,避免传统的粗粒度并行种群迁移、通信等开销。针对并行化后多个子种群解趋同、迭代慢等问题,提出改进的面向遗传算子并行化的遗传算法(OOPGA)。实验结果表明,改进后的OOPGA算法在运行时间、加速比等方面均比CPGA算法好。
关键词:
片上多核,
遗传算法,
并行计算,
粗粒度,
N皇后问题,
遗传算子并行化
Abstract: The number of queens is becoming large,and the time consuming of Genetic Algorithm(GA) is becoming intolerant.In order to reduce the run time,parallel GA is applied to resolve N-queens problem based on the existed resolution.And dynamic programming algorithm is used in local search.Based on Simple Genetic Algorithm(SGA),a Coarse-grained Parallel Genetic Algorithm(CPGA) for solving the N-queens problem is implemented in the multi-core platform.Unlike traditional CPGA,population migration and message communication are avoided.After many times generation,the sub-populations are becoming more similar and the iterative speed is slowing.So a new Operator-oriented Parallel Genetic Algorithm(OOPGA) is proposed in this paper and it is also applied to solve N-queens problem.Experimental results show that OOPGA is better than CPGA in time-consuming and speedup.
Key words:
on-chip multi-core,
Genetic Algorithm(GA),
parallel computing,
coarse-grained,
N-queens problem,
genetic operator parallelization
中图分类号: