A Study On Maximum Independent Set Problem For The Evolution Algorithm

The maximum independent set problem is a classical problem in combinatorial optimization. It has been proved to be a NP-complete problem with high complexity of computation. In this paper we give a survey of results concerning application, bounds, algorithms and heuristics.Based on the summary, first of all, an upper bound is shown. Then by the analysis of the character of the maximum independent sets and the colligation of meta-heuristic algorithm, a new algorithm—fake neighbor-field greedy algorithm is given. It can be solved in polynomial time and a low bound is given after analyzing the running process. Second the EA/G algorithm, the best genetic algorithm found so far, is introduced in detail. Then the paper analyzes the shortcomings of EA/G algorithm and proposes an approved EA/G algorithm. Moreover, experiments on DIMACS benchmarks are run and the results show that the fake neighbor-field greedy algorithm has good performance when the outcomes are maximal independent sets, that the approved EA/G algorithm has good performance in maximum independent sets. After abundant experiments, we know that if the parameters are appropriate, we can find the best solutions for most graphs with the approved EA/G algorithm. This shows adequately that the algorithm presented in the thesis is efficacious.