  Computing maximum independent sets in graphs is an important problem in
computer science. In this paper, we develop an evolutionary algorithm to tackle
the problem. The core innovations of the algorithm are very natural combine
operations based on graph partitioning and local search algorithms. More
precisely, we employ a state-of-the-art graph partitioner to derive operations
that enable us to quickly exchange whole blocks of given independent sets. To
enhance newly computed offsprings we combine our operators with a local search
algorithm. Our experimental evaluation indicates that we are able to outperform
state-of-the-art algorithms on a variety of instances.
