A hybrid genetic search for graph partitioning based on lock gain
Yong-Hyuk Kim, Byung-Ro Moon · 2000
Anewhybrid genetic algorithm for graph bisection is proposed. The algorithm includes a new local optimization heuristic. Based on the traditional framework of the Kernighan-Lin algorithm, the local optimization uses a new type of gain as the primary measure for vertex movement. The new algorithm showed signi cant or dramatic improvement over the state-of-the-art algorithms. 1