图着色若干变种问题的下界及其智能搜索算法的研究

The minimum sum coloring problem, the bandwidth coloring and bandwidth multicoloring problem these three variants of graph coloring problems are well known to their strong NP-hard and applicability to a wide range of important applications. In recent ten years, the field has witnessed significant progresses on practical solution algorithms for the upper bounds, but the research on the lower bounds is not so much. Based on the research on the upper bounds, this project aims to study the lower bounds of the variants of graph coloring problem and intelligent search algorithms, in order to find the optimal solutions for the large-scale benchmark by computational experiments. We provide a detailed presentation as follows: (1) Proposing the formulation for the lower bounds by using the constraints relaxing techniques; (2) Analyzing the distribution of high-quality solutions in the search space; (3) Designing efficient hybrid algorithms with periodically updating. This project will provide broad-mind for finding the optimal solutions of the large-scale variants of graph coloring, and promote the development of their real world applications.

图着色的最小和问题、带宽着色和带宽多重着色问题这三个图着色变种问题是强NP难问题，具有广泛的实际应用价值。图着色变种问题上界的现实求解算法的研究在近十年有所发展，但问题下界的研究尚在起步阶段。本项目在问题上界的研究基础上，提出对问题下界及其智能搜索算法的研究，以期通过计算实验方式找到大规模问题实例的最优解。具体研究内容包括：(1)拟通过放松约束条件提出问题下界的求解模型；(2)分析搜索空间内高质量的解的分布情况；(3)设计高效的周期性更新的双亲混合拟人算法。本项目为获得大规模的图着色变种问题的最优解提供更加广阔的思路，对相关实际应用领域的发展起到推动作用。

图着色及其变种问题是典型的NP难问题，在信号频率分配、人员排班、车辆调度、车间作业调度等科学和工程领域具有广泛的应用价值。本项目基于大规模邻域搜索算法和混合进化算法等智能搜索算法对图着色及其变种问题展开了深入研究，突破了当前研究对大规模问题实例的局限和不足之处。本项目的主要研究内容包括：从本质上分析大规模图问题的特性，提出了新颖有效的求解方案。设计了基于最大独立集抽取及回放迭代混合搜索的方法求解大规模图着色的最小和问题的上下界，通过计算实验方式找到大规模问题实例的最优解。该方法改进了19个大图的上界和12个下界，得到了目前国际上的最好结果。在问题模型方面，将拉丁方块补全问题转化成图着色问题，并使用图着色混合进化算法求解大规模算例，得到了比原问题求解方案更好的结果。增加了图着色求解方案的通用性，扩展了约束优化问题的求解途径。本项目的研究成果对混合进化算法在图着色问题及应用上将起到积极的推动作用，为获得大规模的组合优化问题的求解方案提供更加广阔的思路。