Development of Many Population-based Differential Evolution for Combinatorial Optimization Problem and Its Application to Staff Rostering Problem

微分进化是进化算法的一部分，是一种基于种群的随机搜索技术，用于求解连续空间中的优化问题。在这项研究中，我们提出了一种新的DE算法来解决决策变量用离散值表示的组合优化问题。在此基础上，对基于孤岛的DE生成交替模型进行了改进，构建了多个可在并行计算平台上运行的基于种群的DE。在所提出的方法中，多个种群基于协同进化方法进行竞争进化。通过使用员工排班问题的基准问题进行数值实验，结果表明该方法能够在较短的时间内生成有用的排班。

Differential evolution (DE), classified as a part of evolutionary algorithm, is a population-based stochastic search technique for solving optimization problems in a continuous space. In this research, we propose new DE algorithm to solve combinatorial optimization where decision variables are represented as a discrete value. Furthermore, we modify island based generation alternation model for DE and construct many population-based DE which can work in parallel computing platform. In the proposed method, several populations evolve competitively based on coevolutionary approach. Through the numerical experiments using a benchmark problem of staff rostering problem, we show that the proposed method is able to generate a useful roster in short period of time.