一种求解最大独立集的自学习进化算法

Self-learning evolution algorithm for the maximum independent set

为了求解最大独立集问题,通过对求解最大团问题EA/G算法的分析,从初始解选取、种群的构成、遗传策略等方面对EA/G算法进行了改进,提出了自学习进化算法,并在DIMACS基准图上进行了大量的实验.实验结果表明,该算法运算结果比EA/G算法所求结果有很好的改善.

In order to solve the problems concerning the maximum independent set, the EA/G algorithm was improved by analyzing the algorithm for the solutions to the maximum clique problems from the aspects of selecting the initial solution, constructing populations and genetic strategies. A self-learning evolution algorithm was put forward. After abundant experiments were performed on DIMACS benchmark. The experimental results show that the results obtained by the selflearning evolution algorithm are much better than those by the EA/G algorithm.