Study On Maximum Independent Set Problem And Its Grown-Up Algorithm

The maximum independent set problem is a classical problem in combinatorial optimization. In this paper we give a survey of results concerning application, bounds, algorithms, and heuristics.Based on studying of Genetic Algorithms and organism grown-up, this paper give a new heuristics, called Grown-Up Algorithm (GUA). It divides evolutionary of solution of combinatorial optimization into two steps: birth and grown-up . Birth produce a approximation solution. Grown-up cultivate the solution to a acceptive solution. Its core is born and grown-up.This paper study application of GUA in MIS. The construction of born operator (IB), grown-up operator (IG) and the efficiency analysis of the heuristics are accomplished for solving MIS. Theheuristics is tested on benchmark graphs provided by DIMACS. Experiment shows that the performance of the heuristics outperforms that of HGA provided by [52].