求解多目标旅行商问题的分布估计算法研究

多目标TSP(MTSP)是TSP的推广，在难度上远超TSP，不仅有重大的理论意义，而且有重要而又广阔的应用前景。其复杂特性决定了只有启发式算法才能逼近MTSP的Pareto解集。然而，目前还没有能较好解决此类问题的进化算法。本项目拟采用分布估计算法(EDA)来求解大规模、目标高维、带约束的MTSP。核心思想是将MTSP问题特征和机器学习方法相结合设计高效算法。在分析其Pareto解集的分布特征的基础上，EDA采用适当的概率分布模型来描述该分布，使用机器学习算法来提取解集分布并采样新解。如何学习并用概率模型来描述MTSP的Pareto解集分布是本项目成功的关键。基于连续多目标优化问题规则特性和Glover的Proximate Optimality Principle原理，我们可以解决这些关键问题。通过本项目研究，设计求解MTSP高效算法，并为解决其它多目标组合优化问题提供借鉴。