计算机科学与探索 ›› 2014, Vol. 8 ›› Issue (2): 179-185.DOI: 10.3778/j.issn.1673-9418.1306021

• 人工智能与模式识别 • 上一篇    下一篇

求解动态优化问题的多种群热力学遗传算法

李志杰1,2+,李元香1   

  1. 1. 武汉大学 计算机学院 软件工程国家重点实验室,武汉 430072
    2. 湖南理工学院 计算机学院,湖南 岳阳 414006
  • 出版日期:2014-02-01 发布日期:2014-01-26

Multi-Population Based Thermodynamic Genetic Algorithm for Solving Dynamic Optimization Problems

LI Zhijie1,2+, LI Yuanxiang1   

  1. 1. State Key Laboratory of Software Engineering, School of Computer, Wuhan University, Wuhan 430072, China
    2. School of Computer, Hunan Institute of Science and Technology, Yueyang, Hunan 414006, China
  • Online:2014-02-01 Published:2014-01-26

摘要: 多种群方法已被证明是提高演化算法动态优化性能的重要方法之一。提出了多种群热力学遗传算法(multi-population based thermodynamic genetic algorithm,MPTDGA)。该算法使用一个概率向量在热力学遗传算法迭代过程中不断演化优化与竞争学习,环境变化时分化成三个概率向量,并分别抽样产生原对偶和随机迁入三个子种群,依据这三个种群和记忆种群最好解的情况,选择新的工作概率向量进入新环境进行学习。在动态背包问题上的实验结果表明,MPTDGA比原对偶遗传算法跟踪最优解的能力更强,有很好的多样性,非常适合求解0-1动态优化问题。

关键词: 动态环境, 多种群热力学遗传算法(MPTDGA), 多样性, 概率向量, 分化, 动态背包问题

Abstract: Using multi-population instead of one population has proved to be a good approach for improving the performance of evolutionary algorithms (EAs) for dynamic optimization problems. This paper proposes a multi-population based thermodynamic genetic algorithm (MPTDGA). This algorithm forks the working probability vector while the environment is detected to be changed. At each iteration, the working probability vector is a combination of evolutionary optimization and competitive learning until the environment changes, at which the forked probability vectors are sampled to generate three sub-populations independently, and new working probability vector is selected according to the best fitness of three sub-populations (primal-dual, random immigrants) and memory population. The experimental results on dynamic knapsack problems show that MPTDGA can comprehensively explore the search space and rapidly find changing optimal solution. Compared with primal-dual genetic algorithm (PDGA), this algorithm can maintain better diversity and be more suitable to solve 0-1 dynamic problems.

Key words: dynamic environment, multi-population based thermodynamic genetic algorithm (MPTDGA), diversity, probability vector, forking, dynamic knapsack problems