若干图划分问题基于学习的多层进化算法研究

图划分问题是一类具有大量现实应用的、NP难的组合优化问题，其应用背景包括并行计算、大规模集成电路设计(VLSI)、图像分割等。目前，现有图划分算法的性能有待进一步改进。本项目致力于系统地研究以下4个紧密相关的图划分问题：最小割的均衡图划分、最小最大块边界的均衡图划分、最小割的非均衡图划分、有容量下界约束的均衡图划分，并为其分别设计基于学习的多层进化算法。算法的主要研究内容包括：(1) 多层优化算法的图粗化方法；(2) 进化算法的局部搜索程序、杂交算子与种群更新策略；(3) 进化算法的学习机制。本项目不仅能促进基于学习的智能优化算法的研究与发展，也能为许多现实应用提供高效的优化工具。

Graph partitioning problems are a kind of NP-hard combinatorial optimization problems with a number of real-world applications, such as parallel computing, very large scale integration (VLSI), image segmentation, etc. At present, the existing algorithms need to be further improved in the performance. This project is dedicated to investigating systemically four graph partitioning problems which are closely related to each other, i.e., the balanced graph partitioning problem with a minimum cut, the balanced graph partitioning problem minimizing the maximum domain boundary, the non-uniform graph partitioning problem with a minimum cut, and the balanced graph partitioning problem with a lower bound constraint on the capacities of subsets of vertex set, and devising respectively a learning-based multi-level evolutionary algorithm for each of them. The main researching contents in the algorithm design are as follows: (1) the coarsening methods of graph for the multi-level optimization methods; (2) the local search methods, the crossover operators, and the population updating strategies for the evolutionary algorithms; (3) the learning mechanisms for the evolutionary algorithms. This project is not only able to promote the study and development of the learning-based intelligent optimization algorithms, but also to provide the highly efficient optimization tools for many real-world applications.