主页 > 教育论文 > 数学论文 > 数学模型论文 > 正文

数学模型论文 TSP问题数学模型构建及其求解方法研究

2019-02-26 01:37:01来源:论文阁作者:佚名

导读: 关于数学模型、混合整数规划及遗传算法和交叉的论文《数学模型论文 TSP问题数学模型构建及其求解方法研究》,TSP问题是一个经典的组合优化问题,即已知有n个城市,也知道每个城市之间的距离,现有一个推销员必须都经过这n个城市,每个城市仅访问一次

关于数学模型、混合整数规划及遗传算法和交叉的论文《数学模型论文 TSP问题数学模型构建及其求解方法研究》

TSP问题是一个经典的组合优化问题,即已知有n个城市,也知道每个城市之间的距离,现有一个推销员必须都经过这n个城市,每个城市仅访问一次并且最终要回到出发城市,要如何安排行程路线才能使旅行路线的总长度最短。这类问题的大型实例不能用精确算法求解,必须寻找有效的近似算法来进行求解。本文首先构建TSP问题的数学模型,针对小规模的TSP问题,研究其基于LINGO软件的求解方法。将TSP数学模型转化成混合整数规划模型,然后运行LINGO程序求解,得出最短路径及其旅行路线;针对大规模的问题,采用MATLAB软件编程,研究其基于遗传算法的的求解方法。将n个城市编码看做染色体,通过适应度函数值的大小来选择判断优劣质染色体,函数值越大代表越优质,路径越短。然后通过选择、交叉、变异的操作不断地筛选优质染色体,最终得到最优解。

关键词:数学模型、混合整数规划、遗传算法、交叉、变异

1 前言

1.1 选题背景及意义

旅行商问题(Traveling Salesman Problem,TSP) 是一个组合优化问题,经过长期的研究,该问题已被证明具有NP计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。典型的NP完全问题,即其最坏情况下的时间复杂度随着问题规模的扩大呈指数方式迅速增长。这类问题的大型实例不能用精确算法求解,必须寻找有效的近似算法来进行求解。

TSP问题可描述为:已知n个城市相互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,如何安排才使其所走路线最短。简言之,就是寻找一条最短的遍历n个城市的路径。

TSP的研究历史很久,最早开始的雏形是1759年欧拉研究的骑士环游问题,即对于国际象棋棋盘中的64个方格,走遍64个方格一次且仅一次,并且最终返回到最初的起始方格。TSP问题的概念由美国RAND公司于1948年引入,该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。 1954年,Geo~eDanzig等人使用线性规划的方法取得了旅行商问题的历史性突破——解决了美国49个城市的巡回问题,这就是割平面法的使用,这种方法在整数规划问题上应用也非常广泛。后来他们还提出了一种方法叫做分枝定界法,所谓定界,就是求出问题解的上界和下界,通过目前得到的上下界值排除一部分次优解,为最终获得最优解提示方向。每次搜索下界最小的分枝,可以减小计算量 。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出,并且是在最优化领域中进行了深入的研究。很多的优化方法都用它作为一个测试地衡量基准。尽管这个问题在计算上非常的困难,但是已经有了大量的启发式算法和精确方法来求解规模数量巨大的实例,并且能将误差尽量的控制在1%内。Applegate, Bixby, Chavatal和Cook分别在1994年,1998.年和2001年解决了数量规模为7397,13509和15112的旅行商问题。2004年, polegate,Bixby等找到了一个解决数量规模为24987个城市的旅行商问题的最短路径,这是到自前为止精确的找到最短路径的最大规模的旅行商问题。

旅行商问题具有重要的实际意义和工程背景。最开始的时候旅行商问题是为交通运输而提出的,比如飞机航线的安排、送邮件的行程、快递送达的行程、设计校车的最短行进路线等等。实际上许多其他领域也都逐渐地应用到了旅行商问题。下面举几个实例。印制电路板转孔是就是旅行商问题应用的成功案例,在一块电路板上打上千百个孔,转头不停地在这些孔之间移动,相当于对之前打的所有孔进行一次整体巡回。因此就可以把这个问题转化为旅行商问题,这些孔相当于城市,孔到孔之间的移动时间就是城市相互之间的距离。在人类基因排序工作中,美国国家卫生协会用TSP的方法来绘制放射性杂交图。他们把DNA片段作为城市,DNA之间的相似程度作为城市相互间的距离。法国科学家也使用这种方法最终得到了老鼠的放射性杂交图。

此外,旅行商问题在电缆和光缆布线、晶体结构分析、数据串聚类等其它非常多的领域都得到了很好的应用。更重要的是,它为人们研究组合优化问题提供了一个很好的思路和理想的平台。很多组合优化问题,比如背包问题、分配问题、车间调度问题都和旅行商问题都属于NP完全问题,它们都是具有同等难度的问题。如果其中一个问题可以使用多项式确定性算法来解决,那么其他所有的NP完全问题也能用相似的算法来进行求解。有很多方法本身是从TSP问题借鉴发展起来的,后来慢慢的推广到其他地NP完全问题上去。

1.2 国内外研究现状

TSP问题是人们研究和应用最广泛的组合优化问题之一,目前国内外求解TSP问题的常用智能算法以及现阶段研究的成果如下:

1.2.1 国内研究现状

人工免疫系统( Artificial Immune System)对生物免疫系统中的学习和认知功能进行了模仿,黎湖广、王伟等提出一种基于改进的人工免疫算法来对旅行商问题进行求解,这种算法模拟了抗体的蛋白质多肽链结构、免疫系统的克隆选择机制以及浓度调节机制,使用了一种新的抗体间的相似性判断方法。针对旅行商问题数学建模中的最关键的之处——如何避免“分割”现象, 王继强提出了三种不同的解决方法, 这些方法很好的避开了计算NP问题的复杂性,并最终给出了基于LINGO软件的实证分析。王娜针对一类特殊的大规模旅行商问题提出了一种新的聚类策略,将大规模的旅行商问题转化为若干个小规模的问题,使用了一种新的连接方法,最后得到了如何求解这类特殊的大规模旅行商问题的有效解法。李炳宇等提出了小窗口蚁群算法,用它与基于模式的蚁群算法相结合,通过提取模式和改变计算的粒度设计出了一个更加高效的蚁群算法。高尚利用混沌运动的遍历性、随机性和规律性等特点,提出了一种新的混沌蚁群算法。蒋荣提出了一种基于优化策略和遗传算法的求解TSP问题的混合算法,算法中设计出了两种新的交叉算子并且将两种交叉算子进行结合,使子代更好地继承了父代的优秀基因。邓丽芳提出了异位交叉补码变异的遗传算法,具体分析了两种异位交叉算子,分别使用传统的遗传算法和改进后的遗传算法对旅行商问题进行了求解。

栏目分类