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

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

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