Population migration: a meta-heuristics for stochastic approaches to constraint satisfaction problems
Population migration: a meta-heuristics for stochastic approaches to constraint satisfaction problems
复制标题
人口迁移：约束满足问题随机方法的元启发式
作者：
Kazunori Mizuno;S. Nishihara;H. Kanoh;Isao Kishi
提出了一种跳出局部最优解求解约束满足问题的元算法，使温度的自适应动态控制能够调整随机搜索的局部性。在我们的方法中，制备了具有不同温度的几个基团。对于每个组，最初分配相同数量的候选解决方案。然后，重复主过程，直到该过程达到一定的收敛。主要过程包括两个阶段：随机搜索和种群调整。对于后一阶段，在评估每个组的适应值之后，诱导具有较低值的组中的一些候选解向具有较高值的组的迁移。人口迁移是模拟退火的一种并行版本，其中多个温度在空间上分布。通过实验验证了该方法在求解约束满足问题中的有效性。它也表明，人口迁移是非常有效的相变发生的关键区域。
A meta-heuristics for escaping from local optima to solve constraint satisfaction problems is proposed, which enables self-adaptive dynamic control of the temperature to adjust the locality of stochastic search. In our method, several groups with different temperatures are prepared. To each group the same number of candidate solutions are initially allotted. Then, the main process is repeated until the procedure comes to a certain convergence. The main process is composed of two phases: stochastic searching and population tuning. As for the latter phase, after evaluating the adaptation value of every group, migration of some number of candidate solutions in groups with lower values to groups with higher values are induced. Population migration is a kind ofparallel version of simulated annealing, where several temperatures are spatially distributed. Some experiments are performed to verify the efficiency of the method applied to constraint satisfaction problems. It is also demonstrated that population migration is exceptionally effective in the critical region where phase transitions occur.