Proposes a hybrid genetic algorithm (GA) for the graph-balancedbi-partition problem, a challenging NP-hard combinatorial optimizationproblem arising in many practical applications. The hybrid character ofthe GA lies in the application of a heuristic procedure to improvecandidate solutions. The basic idea behind our heuristic is to identifyand exploit clusters, i.e. subgraphs with a relatively high edgedensity. The resulting hybrid genetic algorithm turns out to be veryeffective, both in terms of quality of solutions and running time. On alarge class of benchmark families of graphs, our hybrid geneticalgorithm yields results of the same or better quality than thoseobtained by all other heuristic algorithms we are aware of, forcomparable running times
展开▼
