计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (20): 73-81.DOI: 10.3778/j.issn.1002-8331.2009-0214

• 理论与研发 • 上一篇    下一篇

精英化岛屿种群引导的差分进化算法

钱峥远,曾国荪   

  1. 1.同济大学 计算机科学及技术系,上海 201804
    2.国家高性能计算机工程技术中心 同济分中心,上海 201804
  • 出版日期:2021-10-15 发布日期:2021-10-21

Differential Evolution Algorithm Guided by Elite Island Population

QIAN Zhengyuan, ZENG Guosun   

  1. 1.Department of Computer Science and Technology, Tongji University, Shanghai 201804, China
    2.Tongji Branch, National Engineering & Technology Center of High Performance Computer, Shanghai 201804, China
  • Online:2021-10-15 Published:2021-10-21

摘要:

针对差分进化算法常见的早熟收敛、搜索停滞和求解精度低的问题,研究一种精英化岛屿种群的差分进化算法(EIDE)。为了实现全局搜索与局部搜索能力并重,EIDE划分多个岛屿种群,根据迭代时的适应度情况,动态地将岛屿种群分类为精英岛屿和普通岛屿;针对精英岛屿,提出一种控制参数自适应方法,依据岛屿适应度情况,自适应地调整变异概率与交叉概率,同时算法利用增强局部搜索的变异策略,提高收敛速度与精度;针对普通岛屿,使用适合全局搜索的变异与交叉概率及变异策略,维护种群多样性。EIDE提出了一种可控的“移民”与“个体迁移”策略,控制优质基因流动,有效避免早熟收敛与搜索停滞问题。在9个benchmark函数上的测试结果表明,新算法具有较强的全局寻优能力与稳定性,且收敛速度较快。

关键词: 差分进化算法, 岛屿模型, 子种群分类, 参数自适应

Abstract:

A differential evolution algorithm based on elitist island population(EIDE) is proposed to solve the problems of premature convergence and search stagnation. In order to enhance both global search and local search ability, the algorithm divides the population into several island populations, and dynamically classifies types of these island populations according to the fitness. For the elite islands, an adaptive method of control parameters is proposed. The adaptive parameters are determined by the fitness of the mutation individuals and the whole island, so mutation operators and crossovers operator will be adjusted adaptively. And a mutation strategy to enhance local search is combined to improve convergence speed and accuracy. For common islands, mutation and crossover operators suitable for global search are used to maintain population diversity. The algorithm proposes two strategies to control the flow of high-quality genes, one is called a direction-controlled migration strategy, and the other is individual transfer strategy, so that the algorithm can effectively avoid premature convergence and search stagnation. By testing on 9 typical test functions, the results show that the proposed algorithm has strong global optimization ability, stability, and has quicker convergence speed.

Key words: differential evolutionary algorithm, island model, subpopulation classification, parameter adaptation