关键词: 图划分, 遗传算法, 最佳匹配, 优良基因, 禁忌搜索

Abstract: Aming at the problem of  the computational complexity caused by the exponential increase in the number of partitioning schemes with the number of vertices in large-scale graph partitioning problems, and the inefficiency and imprecision of traditional genetic algorithms when dealing with large-scale problems, we proposed a hybrid genetic algorithm. Firstly, the algorithm  performed optimal matching on individuals encoded in binary, identified and screened out good genes,  effectively narrowing down the search range and focusing on more promising search areas. Secondly, in order to avoid the illegal solutions that might arise from traditional crossover operations, the algorithm abandoned the random crossover strategy and only generated one potential solution. Finally, by introducing a tabu search operator in the mutation operation to generate complete individuals, thereby enhancing  local search capability of the algorithm and achieving a dynamic balance between global and local searches. Experimental results of applying this hybrid genetic algorithm to the partitioning problem of ultra large-scale integrated circuits show that the algorithm can effectively improve the quality of solutions for large-scale graph partitioning problems.

Key words: graph partitioning, genetic algorithm, optimal matching, good gene, tabu search