多核CPU环境下小生境混合遗传算法的研究

Research on niche hybrid genetic algorithm based on multi-core CPU

为克服遗传算法的缺点,利用小生境的启发作用,引入改进的模拟退火操作,构造了一个兼顾全局搜索与局部探测的混合遗传算法。针对该算法内在的良好并行性及串行计算难以发挥多核CPU计算优势的问题,将遗传操作和模拟退火操作设计成并行计算形式,利用OpenMP将其线程化。对TSP的求解验证了该算法的有效性,并行算法的加速比和计算效率随着TSP规模的增加而显著提高。

To conquer the shortcoming of genetic algorithm, this paper proposed a hybrid genetic algorithm by combining improved simulated annealing operator under the enlighten impact of niche. The proposed considers both effects of global search and local exploration and was parallelized in its basic genetic operators and SA operator for their nice concurrency and serial form hard to make use of the computing capability of multi-core CPU. Used OpenMP when threading the hybrid algorithm. Solved some different TSPs and the results show the designed algorithm＇ s validity. The speedup of the parallelized algorithm increases observably with increasing scale and also the computing efficiency.