PBIL进化算法及其应用

PBIL Algorithm and Its Applications

进化计算是近年来发展起来的一种搜索方法，广泛用于求解各类优化问题。ＰＢＩＬ算法与传统的进化算法不同，将进化获得的知识——学习概率用以指导后代的产生，使搜索更具方向性，因而往往能取得更好的效果。本文结果：１）将ＰＢＩＬ算法由原来只使用二进制编码改成能直接使用任意整数的编码；２）使用了每个基因位取两个基因值的技巧；３）用系统熵作为进化计算结束的判据。这些改进使算法使用更方便与直观。最后是将该算法应用于解决二个实际问题：调度问题与ＴＳＰ问题。

In this paper, PBIL(Population Based Incremental Learning) Algorithm has been improved in two aspects:1)The values appearing at each gene location of the genome can be any integers. 2) Entropy is used as the termination condition. It is useful to estimate the degree of evolution process. Finally, two applications are presented: Scheduling problem and TSP.