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

On-chip Multi-core Parallel Hybrid Genetic Algorithm for Solving N-queens Problem

作　　者：张步忠[1] 程玉胜[1] 王一宾[1] 

机构地区：[1]安庆师范学院计算机与信息学院,安徽安庆246013

出　　处：《计算机工程》2015年第7期199-203,共5页Computer Engineering

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

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]