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

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

项目编号： No.61005050

项目类型： 青年科学基金项目

立项/批准年度： 2011

项目学科： 金属学与金属工艺

项目作者： 周爱民

作者单位： 华东师范大学

项目金额： 7万元

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

中文关键词： 多目标优化;旅行商问题;TSP;分布估计算法;进化计算

英文摘要：

英文关键词：