面向大规模多目标组合优化问题的元启发式算法和元学习算法研究

Combinatorial optimization problem (COP) is a kind of optimization problem that widely appears in the industrial field and scientific field. It is also an important subject in operational research. Most COPs are NP-hard, e.g., the Traveling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP). When the NP-hard problems are relatively large, classical optimization algorithm is unable to find the optimal solution within acceptable time, while metaheuristics are widely used to quickly find sub-optimal solutions. When a COP has more than one objectives, it becomes a Multiobjective COP (MCOP). In the era of big data, large-scale MCOPs become more and more common, hence, it is necessary to design metaheuristics specifically for large-scale MCOPs...The challenges of large-scale MCOPs are: (1) They have a very large search space with very little prior knowledge known by people; (2) Function evaluation is relatively time-consuming; (3) When the objective number becomes large, most of the candidate solutions in the solution space are non-dominated to each other; (4) Lacking a universal algorithm which can perform well on different kinds of problems. This project aims to overcome those challenges by deeply investigating the features of selected large-scale MCOPs and designing targeted metaheuristics, which combines the techniques of algorithm parallelization, surrogate model, multiobjective decomposition, and meta-learning. We hope that the proposed metaheuristics can perform better (or in the same level) than the state-of-the-art algorithms on some practical large-scale MCOPs, e.g., the large-scale MCOPs in the area of express industry, financial industry and internet industry.

组合优化问题是物流、金融、互联网等领域中常见的一类优化问题，对于NP难的组合优化问题，一般使用元启发式算法来快速求得问题的次优解。随着大数据时代的来临，人们面对的组合优化问题朝着规模更大、目标更多的趋势发展，而目前缺少专门针对大规模多目标组合优化问题的元启发式算法，本项目旨在设计算法填补这一不足。针对此类问题搜索空间大、先验知识少的难点，本项目拟在充分分析问题特性的基础上，设计并行的元启发式算法以充分利用多核计算机的计算资源；针对一些大规模多目标组合优化问题的函数评估较为耗时的难点，本项目拟引入代理模型来快速估计目标函数值。针对当问题目标数较多时非支配解变多这一难点，本项目拟采用多目标分解技术以帮助筛选优化过程中遇到的非支配解。针对元启发式算法在不同类型问题上通用性较差的缺点，本项目拟引入人工智能中的元学习技术，让算法从过往的优化过程中学习和积累知识，进而能够快速应对新涌现的组合优化问题。

组合优化问题是物流、金融、互联网等领域中常见的一类优化问题，对于NP难的组合优化问题，一般使用元启发式算法来快速求得问题的次优解。随着大数据时代的来临，人们面对的组合优化问题朝着规模更大、目标更多的趋势发展，而目前缺少专门针对大规模多目标组合优化问题的元启发式算法。本项目针对一些具有代表性的多目标组合优化问题（如多目标旅行商问题，多目标01二次规划问题等），通过深入研究问题特性，灵活运用并行化技术、代理模型、多目标分解技术、元学习技术等技术，提出了若干大规模多目标元启发式优化算法，所提出的算法在所针对的问题类型上达到了国际领先的优化性能。