基于改进遗传算法的多目标TSP问题研究

论文摘要

TSP（Traveling salesman Problem,旅行商问题）是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个NP-hard问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题（Traveling salesman Problem,Tsp）,实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。本文主要对遗传算法求解多目标TSP问题进行了研究。多目标TSP是从通信、物流等应用领域中提出的一类新的NP-hard的数学理论模型,它属于演化计算的一个新的研究领域。与经典的TSP相比,多目标TSP更复杂,具有更大的挑战性。多目标TSP的研究将推动一些实际问题的解决,如投资问题。投资者一般希望所投入的资金量最少,风险最小,且获得的收益最大。所以研究多目标TSP具有重大的理论意义和应用价值。关于多目标问题的研究在国内外都刚起步,鉴于以上研究现状,本文提出了一种多目标遗传算法。主要包括以下工作:1.介绍了TSP的研究现状、基本知识和遗传算法的基础理论知识。2.介绍了作者对多目标TSP取得的研究成果:针对传统遗传算法求解的缺陷及多目标TSP问题解的特性,进行了一系列的改进,首先采用Grefenstettet编码对候选初始解进行编码,引进了一个线性函数来计算选择概率,提出了一种改进的交叉和变异算子,建立多目标旅行商问题模型,设计出了一种能够较好求解多目标TSP问题的遗传算法。计算机仿真实验验证了该算法的有效性。最后,本文对所做的工作以及进一步的研究方向做了总结和展望。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.1.1 最优化问题简述
• 1.1.2 多目标问题简述
• 1.2 研究现状及存在的问题
• 1.3 本文采用的理论方法和主要研究内容
• 1.3.1 理论方法
• 1.3.2 主要研究内容
• 1.4 本章小结
• 第2章 TSP问题的简介
• 2.1 TSP问题的定义
• 2.1.1 TSP问题的一般性描述
• 2.1.2 TSP问题的数学模型
• 2.1.3 TSP问题的意义
• 2.2 TSP问题的传统解决方法
• 2.2.1 精确算法
• 2.2.2 近似算法
• 2.3 本章小结
• 第3章 遗传算法的基本理论
• 3.1 遗传算法的起源与发展
• 3.2 遗传算法的基本思想
• 3.2.1 遗传算法的构成要素
• 3.2.2 遗传算法的一般结构
• 3.3 遗传算法的实现技术
• 3.3.1 编码
• 3.3.2 初始群体
• 3.3.3 适应度函数
• 3.3.4 选择算子
• 3.3.5 交叉算子
• 3.3.6 变异算子
• 3.3.7 遗传算法的运行参数
• 3.4 遗传算法的特点
• 3.5 遗传算法的应用
• 3.6 本章小结
• 第4章 基于遗传算法的多目标TSP问题
• 4.1 多目标TSP问题描述
• 4.1.1 多目标问题的概念
• 4.1.2 MOTSP问题的研究现状
• 4.1.3 MOTSP的数学模型
• 4.2 用改进的遗传算法求解MOTSP问题
• 4.2.1 遗传算法的基本流程
• 4.2.2 标准GA算法的改进
• 4.3 算例分析
• 4.3.1 编程语言
• 4.3.2 计算机仿真结果及分析
• 4.4 本章小结
• 第5章 总结与展望
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢
• 附录