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

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.

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

图划分问题与0-1组合优化问题是运筹学与计算机领域的两类经典的优化问题，具有重要的理论价值和应用背景。本项目对若干图划分问题和0-1组合优化问题进行了深入的研究，这些问题包括最大多样性分组问题、电网解列问题、约束的聚类问题、多维背包问题、多需求多维背包问题和公平疏散问题。本项目的主要研究成果包括：1）为图划分问题和聚类问题提出了一种具有较高通用性的邻域分解技术，并基于该技术提出了若干高性能的优化算法；2）为0-1组合优化问题发展了若干基于解的禁忌搜索策略；3）为0-1组合优化问题提出了若干高性能的混合进化算法。本项目提出的优化策略和优化技术具有较好的通用性，可为其他组合优化问题的求解提供借鉴作用。本项目提出的图划分算法、0-1组合优化算法可应用于并行计算、大规模集成电路设计、设施选址等领域。