基因学习算法及其在集合覆盖问题中的应用

Gene Learning Algorithm and Application on Set Convering Problem

在用传统方法解决一些复杂而规模较大的组合优化问题,尤其是NP难题,出现困难时,一些近似算法相继推出。启发式搜索法、模拟退火算法及进化算法等的出现,为解决这些优化问题提供了非常好的手段。近年来,出现了一种概率学习的进化计算模型,如Baluja的PBIL算法与Corno的自私基因算法。概率学习的进化计算模型通过不断地学习每一代的最优个体,最终收敛于最优或较优的解的等位基因概率,其过程描述如下:

A new algorithm called Gene Learnmg(GL) which is developed from PBIL and Selfish Algorithm is presented in this paper. GL begin with the initial alleles probability of every gene location and followed by a series of repeated processes of sampling, selecting and local search, probability learning until the final result is obtained. Application on Set Covering Problem(SCP) is presented in this paper.