周一至周五 | 9:00—22:00

期刊论文网 > 自然科学论文 > 数学论文 > 数学模型论文 TSP问题数学模型构建及其求解方法研究

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

2018-12-27 13:24:23来源:组稿人论文网作者:婷婷

  摘 要

  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问题的混合算法,算法中设计出了两种新的交叉算子并且将两种交叉算子进行结合,使子代更好地继承了父代的优秀基因。邓丽芳提出了异位交叉补码变异的遗传算法,具体分析了两种异位交叉算子,分别使用传统的遗传算法和改进后的遗传算法对旅行商问题进行了求解。

  1.2.1 国外研究现状

  遗传算法( Genetic algorithm)参考了自然环境中生物种群“物竞天择,适者生存”的规律,通过遗传和自然选择使生物种群不断进化的方式来用于具体问题的求解,Whiled、 Stark weather和 Fuquay D等人在研究遗传算法的同时提出了一种边重组(ER)交叉操作,使子代个体能够从父代个体中继承95%以上的边信息,ER操作是根据继承两个父代个体中定义的旅程中城市间的相邻关系而生成的子代个体。Hong Qu等人结合胜者全取 (winner—take—all)的竞争机制设计了一个柱形竞争的神经网络模型来求解MTSP问题,并对网络收敛于可行解进行了分析和论证。粒子群优化算法( Particle Swam Optimization)模拟了鸟群在觅食迁徙时个体与群体之间相互协调一致的原理,Seoul、 Korea在《 Proceedings of the Congress on Evolutionary Computation》一文中提出交换粒子和交换构造的粒子群算法来求解旅行商问题,并对其进行了优化与改进;

  2 TSP问题及研究方法

  2.1 TSP问题概述

  旅行商问题( Traveling Salesman Problem,简称TSP)经典说法为:有这样一名旅行推销商,从某一个城市出发,要访问很多个城市各一次且仅一次,最后返回到原出发城市(将能经过每个城市一次且仅一次的旅行路线称作为一个巡回),要如何安排行程路线才能使旅行的总路线最短。旅行商问题是组合数学中一个历史悠久而又难以求解的问题,它虽然易于描述但是至今尚未找到彻底解决该问题的有效方法,现在已经将其归入到经典的NP-hard组合优化问题之中。该问题在图论的意义下就是所谓的最小Hami1ton图问题,由于可以广泛的应用到许多其它领域,所以寻找出实际而有效的解决方法就显得尤为重要了。

  2.2 TSP问题数学模型

  假设从城市i到城市j的旅费为Cij,引入整数变量xij(i≠j): xij=1表示路线从i到j,xij=0表示不走i到j路线,

  则目标函数为:

  min i=1nj=1ncijxij(2.1)

  约束条件为:

  j=1nxij=1,i=1,…,n,j≠i(保证恰好离开每个城市一次)

  i=1nxij=1,j=1,…,n,i≠j,(保证恰好进入每个城市一次)

  xij=0,1;i,j=1,…,n

  则TSP数学模型为

  min i=1nj=1ncijxij

  s.t. j=1nxij=1,i=1,…,n,j≠i,i=1nxij=1,j=1,…,n,i≠j,xij=0,1;i,j=1,…,n不含子巡回

  2.3 TSP问题的几种求解方法

  TSP问题描述虽然很简单,但是解决起来却非常的困难,最简单的求解方法就是用穷举法把所有可能存在的巡回路径全部罗列出来,再计算每一个路线的长度,最短的一个就是最短路径也就是最优解,但是这样只能解决规模特别小的旅行商问题,对于城市规模大的旅行商问题就束手无策了。假设有n座城市,那么巡回路径一共有n-1!⁄2条。当城市数n=20时,巡回路径有1.2×1018种;当n=100时,巡回路径就有多达4.6×10155条。所以在求解TSP的算法的过程中,对于大规模的旅行商问题,人们一直在寻找切实有效的解决方法,按照出现时间的先后顺序排序大致可分为两种:传统算法和智能演化算法。传统算法包括精确算法和近似优化算法,精确算法又分为分支限界法、动态规划法和线性规划法等,而近似算法又有插入法、最近邻算法、r-opt算法、混合算法、概率算法等。虽然传统算法能够求解出TSP问题的最短路径,但随着城市规模的不断增大,传统算法算法所需要耗费的的时间与精力也非常巨大,因此只适用于求解城市规模较小的旅行商问题。

  自20世纪80年代以来,智能优化算法出现在了人们的视野之内,如人工神经网络、禁忌搜索算法、遗传算法、蚁群算法、模拟退火算法、粒子群算法等,这些算法通过揭示或者模拟某些自然现象(或过程)而得到了应用与发展,这些算法的内容和思想涉及到了物理学、生物遗传进化、生物科学、人工智能、数学和统计力学等方面,它们为解决复杂问题提供了新的思路和方法。因为这些算法通过对自然机理构造的直观性与可行性,通常被称作为智能演化算法,或者是现代启发式算法。使用智能演化算法可以解决大规模的旅行商问题,在求解的同时也可以避免陷入局部最优解,从而在整体中得到最优解。

  模拟退火算法

  模拟退火算法最初起源于上世纪的五十年代,它是一种随机搜索算法,八十年代才开始逐渐应用到组合优化问题的求解中,这种算法的思路是将组合优化问题模拟成统计力学中的热平衡现象,把需要优化的目标函数当做热平衡中的能量函数,模仿物理学中对固体物质进行的退火处理,先对固体物质进行加温,使之具有足够高的能量,固体内部的粒子随着温度的上升而变得无序,然后再对其进行逐渐降温的操作,这时其内部的能量也会相应的下降,粒子逐渐变得有序,达到平衡态。如果退火步骤操作恰当的话,最后在常温的时候就会形成最低能量的基态,这时固体内部的能量也是最低的。在求解最优化问题时,模拟退火算法不仅接受使目标函数(也就是热平衡中的能量函数)优化的状态,还会以某种概率接受使目标函数恶化的状态,从而可以使目标函数避免过早的收敛到某个局部极值点,也正是这种概率性的扰动能够使之避免陷入局部极值点,因此这种算法得到的解一般都是最优解。

  模拟退火算法可以一个近似解不断地逼近最优解,是一种适用于解决大规模组合优化问题通用而又有效的智能算法。这种算法具有描述简单、运行效率高、鲁棒性强和通用易实现等优点。但是这种算法在寻找最优解的过程中通常要求有较高的初始温度、较慢的降温速率和较低的终止温度,而且需要在各个温度下进行足够多次的抽样,因此模拟退火算法在优化过程中耗费时间较长,这也是模拟退火算法相较于其它智能算法一个较大的缺陷。

  遗传算法

  遗传算法(Genetic Algorithm,简称GA)是基于自然环境中生物遗传和进化的规律演化而来的具有通用性的全局优化算法。遗传算法起初是在1975年,美国Holland教授受到了进化论的启发而提出的。它借鉴了生物学中基因遗传和自然环境中优胜劣汰的生物进化思想,将组合优化问题的求解看作成基因遗传的进化过程。一般来说,遗传算法是以一群随机产生的可行解组成初始种群而开始的,每个可行解都用一串编码表示为个体染色体,通过组合优化问题的目标函数来生成适应度函数,这种函数确定了个体的适应度,作为衡量标准对种群中的个体进行筛选。然后通过交叉、变异等操作对种群重新进行组合从而产生下一代个体,逐步向最优解靠近。

  遗传算法的主要特点是:从问题解的整体初始种群开始搜索,而不是从某一个解开始,这是遗传算法与传统算法的最大的区别。传统算法是从挑选单个初始值,通过迭代的方式来求出最优解的,这样容易误入局部最优解;而遗传算法不在单个初始值上寻找最优解,而是从整个生物种群中通过适应度函数逐渐选择适应力强的个体不断产生新的种群,从而求出最优解。这种方法针对于群体中的所有个体,覆盖面广,利于全局择优。

  禁忌搜索算法

  禁忌搜索(Tabu Search,简称TS)算法又被称为爬山启发式算法,是一种元启发式随机搜索算法。最早在1986年,Glover提出了禁忌搜索的思想。这种算法对人类大脑的记忆功能进行了模拟,将局部搜索进行了修正与扩展,是一种全局逐步择优算法,它从某一个初始可行解开始,挑选出很多搜索方向并沿着这些方向进行搜索,最终选择那个使目标函数值变化最大的方向,然后再重复操作。但是这样的话容易陷入局部最优解,因此禁忌搜索算法模仿人类大脑的记忆功能采用了一种更加有效地记忆方法―建立Tabu表。Tabu表将之前已经优化过的路程与方向进行记录,再慢慢筛选出下一步的搜索方向,保证多样化的有效搜索从而慢慢的逼近最优解。

  禁忌搜索算法是一种全局逐步择优算法,是对局部搜索算法的推广,在解决组合优化问题中使用非常的广泛。这种方法的特点是具有灵活的记忆功能,通过Tabu表可以避免重复之前的工作,跳出局部最优解,从而更快的找到全局最优解。缺点是初始可行解的选择很重要,一个好的可行解能够以很快的速度找到最优解,但是一个差的可行解则会导致禁忌搜索的速度降低,搜索到的解也会相对较差。而且禁忌长度的选取也很重要,具有技术性。

  蚁群算法

  20世纪90年代,意大利学者Dorigo等人通过研究蚂蚁觅食的过程而首次提出了蚁群算法。他们发现单个蚂蚁的行为并没有规律,但是整个蚂蚁群体却可以进行一些智能的行为。例如蚁群可以在不同的环境中,找到食物来源的最短路线。这是因为蚁群内的蚂蚁可以通过一种特殊的信息机制来实现信息的传递。后来经过进一步的研究发现,在经过路线的同时,蚂蚁会在自己经过的路线上留下一种叫 “信息素”的物质,而蚁群内所有的蚂蚁对“信息素”都具有感知能力,它们会优先选择沿着“信息素”更多的路径前进,而且每只蚂蚁都会在经过的路上留下“信息素”,这就形成了一种类似正反馈的机制。这样经过一段时间后,蚁群就可以通过信息素来寻找到最短路径到达食物源了。

  蚁群算法也可以对组合优化问题进行求解,基本思路为:将蚂蚁的行走路径当做待优化问题的可行解,这样整个蚂蚁群体的所有行走路径就构成了待优化问题的总体解空间。同只蚂蚁经过较长和较短路径所留下的“信息素”浓度是不同的,路径越短的话留下的“信息素”浓度越高。随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,后来的蚂蚁会优先选择沿着“信息素”浓度高的路径行走。最终,在正反馈机制的作用下整个蚂蚁群体会聚集到最短的路径上行走,那这条路径对应的可行解则是待优化问题的最优解。

  人工神经网络

  人工神经网络( Artificial Neural Network,简称ANN)是自20世纪80年代在智能演化算法领域的一种新兴算法。它是对人体大脑神经元网络进行抽象模仿,由大量的节点即神经元(Neurons)相互连接而构成简单的神经元模型。它是一种简化和模拟的工程系统,反映出了人体大脑的基本特性。人工神经网络具有特殊的非线性适应性信息处理能力,改进了传统智能演化方法对于直觉、语音识别、非结构化信息处理等方面的不足,具有自适应、实时学习的特点,使之在组合优化问题、经济、医学等领域都取得了得到显著的成效。近年来,人工神经网络成为人工智能的一种重要的研究方向,人们尝试将其与遗传算法、进化机制等结合起来形成计算智能。

  神经元模型作为人工神经网络的基本单元,它具备三个基本要素:第一是它用神经元之间的相互连接表示内部神经元的联接强度,也可以将之称为权值,权值的取值范围可以是正值也可以是负值;其二是它有一个激励函数可以用于限制神经元的输出;其三是具有输入信息叠代器可以反映生物神经元的时空整合功能。

  粒子群算法

  粒子群算法也称粒子群优化算法(Particle Swarm Optimization,简称PSO),是由Kennedy和Eberhart在1995年提出的一种并行算法。这种算法对鸟群和鱼群活动行为进行了观察与优化改进,群体中的所有个体可以进行信息共享,粒子在解空间内可以跟随最优的粒子进行搜索,产生从无序到有序的演化过程,从而获得最优解。

  在粒子群算法中,每个组合优化问题的可行解都可以当作搜索空间里的一个“粒子”,每一个“粒子”都有特定的行进速度和方向,这个行进速度在飞行过程中会进行动态调整。而且粒子群算法中有一个被优化的函数决定的适应值(fitness value)来判断粒子当前的位置好坏,然后粒子们就追随当前的最优粒子在解空间中搜索。

  PSO初始种群为一群随机“粒子”(优化问题的随机可行解)。然后通过迭代逐步找到最优解。在每一次迭代过程中,粒子通过跟随两个“极值”来优化自己。第一个是个体极值(pBest),也就是粒子本身所找到的最优解。另一个极值是全局极值(gBest),这是目前在整个种群中找到的最优解。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。

  本文针对TSP问题构建其数学模型,针对小规模的TSP问题,我们把TSP模型转化成混合整数规划,研究其基于LINGO软件的求解方法;针对大规模的问题,用MATLAB软件编程研究其基于遗传算法的求解方法。

  3 LINGO在TSP问题的应用

  3.1 LINGO软件简述

  1980年,美国芝加哥大学的Linus Schrage教授开发了LINGO软件,后来他成立了LINDO系统公司(Lindo System Inc)。随后又相继开发了其它的求解数学规划的软件,包括GINO,LINDO,What’s Best等。LINGO的主要功能是求解大型线性规划和非线性规划的问题,同时也可以用于整数规划问题的求解。LINGO软件在Windows系统运行窗口如图 3.1所示

  图 3.1 LINGO运行窗口

  它的主要功能特色为:

  (1)将需要优化的问题引入编程语言表示,将实际问题转换为 LINGO模型进行求解;

  (2)允许决策变量是整数;

  (3)执行速度快,运算效率高;

  (4)方便灵活,可以与Excel、数据库等其他软件交换数据;

  (5)适用范围广,线性规划、非线性规划和整数规划等问题都可以求解;

  (6)内置建模语言,提供数十个内部函数,可以用相对简单、直观的方法来描述较大规模的优化模型。

  3.2 混合整数规划

  TSP数学模型为: min i=1nj=1ncijxij

  s.t. j=1nxij=1,i=1,…,n,j≠i,i=1nxij=1,j=1,…,n,i≠j,xij=0,1;i,j=1,…,n不含子巡回

  在旅行商问题中,我们将能经过每个城市一次且仅一次的旅行路线称作为一个巡回,可以分为整体巡回和子巡回。因为我们需要求解经过所有城市的最短路径,所以不应该存在子巡回。假设有八座城市,这八座城市的旅行路线为1→2→3→4→1和5→6→7→8→5,则这两条路线虽然满足TSP模型中的前三个约束条件,但是它存在两个子巡回,并没有构成整体巡回路线,因此增加了“不含子巡回”的约束条件,用数学表达式表示为:增加变量ai(1,2,…,n),并附加约束条件:

  ai-aj+nxij≤n-1,ai,aj≥0,i=1,…,n,j=2,3,…,n,且i≠j

  下面证明:(1)不管ai如何取值,上述约束条件对任何含有子巡回的路线都不成立;(2)只要ai取适当的值,对于只有一条整体巡回路线,不包含子巡回的路线,上述约束条件都可以成立。

  用反证法证明(1),如果八座城市中存在子巡回,那至少应该存在两条子巡回路线。假设出发城市记为城市1,则肯定有一条子巡回不经过出发城市1,例如子巡回5→6→7→8→5,将上述约束条件用于该子巡回,用数学表达式表示为a5-a6+n≤n-1,a6-a7+n≤n-1,a7-a8+n≤n-1, a8-a5+n≤n-1,把这四个不等式相加起来可以得到n≤n-1,显然这是不成立的。而对整体巡回,因为附加约束中j≥2,不包含起点城市1,故不会发生矛盾。

  对于整体巡回路线,只要ai取适当值,都可以满足上述约束条件:(1)对于整体巡回上的边,xij=1,ai大小取整数:起点a=0,第一个到达的城市a=1,每到一个城市a加1,则必有ai-aj=-1,上述约束条件变成:-1+n≤n-1,必然成立;(2)对于不是整体巡回上的边,xij=0,上述约束条件变成:-1≤n-1,必然成立。

  根据以上证明可以得出:上述约束条件只对子巡回进行限制,并不影响整体巡回路线,于是TSP模型就可以转化为一个混合整数线性规划模型,进而可以用LINGO来对具体问题进行求解。

  3.3 LINGO程序求解

  假设已知六个城市之间的距离矩阵,求从城市1出发最终回到城市1的TSP路线。编写LINGO程序如下:

  MODEL:

  SETS: city/1…6/: u;

  link( city, city): dist, x;

  ENDSETS

  DATA:

  Dist= 0 702 454 842 2396 1196

  702 0 324 1093 2163 764

  454 324 0 1137 2180 798

  842 1093 1137 0 1616 1857

  2396 2136 2180 1616 0 2900

  1196 764 798 1857 2900 0;

  ENDDATA

  n=@SIZE(city); MIN=@SUM(link: dist * x);

  @FOR(city( k): @SUM(city(I)|I#NE# K: x(I,K))=1;

  @SUM(city(J)|J#NE#K:x(K,J))=1;);

  @FOR(city(I): @FOR(city(J)|J#GT#1 #AND# I#NE# J:u(I)-u(J)+n*x(I,J)<=n-1););

  @FOR(city(I): u(I)<=n-1);

  @FOR(link: @BIN(x));

  END

  LINGO程序运行截图如下:

  图1 LINGO程序运行

  3.4 测试结果

  测试结果如上图所示,目标函数值为6610,最优路线为:1→3→6→2→5→4→1。

  4 遗传算法在TSP问题的应用

  4.1 遗传算法概述及流程图

  4.1.1 遗传算法起源和发展

  遗传算法(Genetic Algorithm,GA)是一种借鉴生物学中“适者生存,优胜劣汰”的遗传进化机制演变而来的启发式搜索算法。

  在上世纪60年代,美国密西根大学的Holland教授从达尔文进化论中得到了灵感与启迪,发现人工智能自适应系统可以类比为自然环境中生物体的遗传和自然进化的方式进行。在研究和设计人工自适应系统时,他借鉴了生物的遗传进化机制,通过群体的方式进行自适应搜索。1967年,Holland教授的学生Bagley发表了关于遗传算法的博士论文,在他的博士论文中首次运用了“遗传算法”这个词语。他提出采用双倍体编码的方式来发展遗传算法,创造了复制、交叉、变异等遗传算子。与此同时他还发现了防止早熟收敛机理的重要性,由此还进一步发展了遗传算法的理论概念。1975年,Holland教授出版了他的著名专著―《自然系统和人工系统的适配》,这是第一本对遗传算法进行详细介绍的专著,Holland教授在这本书中系统地阐述了遗传算法的基本原理和方法,并提出了对遗传算法研究具有历史性意义的模式理论,为遗传算法的实现与发展打下了基础。同年,De Jong在他的博士论文《一类遗传自适应系统的行为分析》中将Holland的模式定理和他的实验结合起来,将选择、交叉、变异等操作进一步改善和优化,又提出了代沟等新的遗传算子。他的研究工作为遗传算法的应用打下了坚实的基础,被看作是遗传算法发展的里程碑,至今仍然具有普遍的指导意义。

  国内对于遗传算法的研究较晚,从上世纪九十年代开始一直处于不断上升的阶段。近年来,遗传算法的应用在许多领域都取得了令人瞩目的成果。例如在2002年,戴晓明等利用多种群遗传并行进化的思想,用不同的遗传策略和变异因子对不同生物种群进行变量空间搜索。并利用种群之间迁移算子来进行遗传信息交流,从而解决了经典遗传算法易陷入局部最优解的问题。由于相对简单的遗传算法在求解大规模组合优化问题时搜索效率较低,在2004年,赵宏立等人提出一种新的基于基因块编码的并行遗传算法。此方法以处理度并行遗传算法作为基本框架,在染色体的群体中识别出可能的基因块,把新的基因块作为基因单位,然后以新的基因单位重新编码染色体,最终生成了较短长度染色体的新一代种群,然后以相同方式逐步得到最优解。2005年,江雷等人使用并行遗传算法求解旅行商问题,发现了可以使用“弹性策略”来维持群体的多样性,从而可以跳出局部最优解的限制,向全局最优解方向进化。

  遗传算法自诞生以来就受到许多专家学者的关注。经过30多年的不断研究与发展,在算法设计研究和基础理论上都取得了显著的进步,尤其是在越来越多的领域中都得到了成功应用并取得了不错的成效。遗传算法作为一种仿生优化算法,为复杂系统优化提供解決方案,通过实例证明其应用效果非常显著,因此被认为是21世纪有关智能算法中的关键性技术之一。

  4.1.2 遗传算法的基本原理

  遗传算法是将优化问题的可行解比作生物遗传中的染色体(Chromosome)。遗传算法的实现从初始种群(Population)开始种群是由经过基因编码(Coding)后一定数目的个体组成的。每个个体实际上都可以当做是带有特征的染色体。在生物学上,染色体是遗传物质的主要载体,由多个基因组合而成。基因组合则决定着该生物在自然环境中的适应能力。按照优胜劣汰、适者生存的原理,从初始种群开始逐代演化产生出适应能力越来越高的个体。在每一代中,根据适应度(fitness)函数的大小来选择个体,适应能力越强的个体越有几率被选择。然后通过对遗传算子(Genetic Operators)进行交叉(Grossover)和变异(Mutation)等操作,产生出代表新的解集组成的种群。这个过程像生物的自然进化一样,随着个体的不断更新,后代种群比前代适应能力更加强大,更容易适应于自然环境中,最末代种群中适应能力最强的个体经过解码(Decoding)以后可以作为组合优化问题的近似最优解。

  遗传算法主要通过选择、交叉、变异操作来实现。与传统搜索算法不同,遗传算法是从一组随机产生的初始解展开搜索过程。种群中的每个个体是问题的一个可行解,称为染色体,染色体是一串编号,通过编码操作完成。这些染色体在后续迭代中不断进化,称为遗传。衡量个体适应度的函数被称为适应度函数,在每一代中用适应度函数来测量染色体的好坏,适应度函数值越大的个体越优质。生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过选择、交叉或者变异运算形成的。新一代形成中,根据适应度函数值的大小选择部分更加优质的后代,淘汰部分劣质的后代,从而保持种群大小的稳定性。这样,经过若干代之后,算法逐渐向越来越优质的染色体进行收敛,最后的结果很大可能就是问题的最优解。

  4.1.3 遗传算法流程图

  图4.1 遗传算法流程图

  4.2 编码

  编码操作参考生物遗传时从染色体中基因排列的顺序,将研究对象当作为由很多特定符号按一定顺序排成的组合。我们采用整数排列编码方法,对于TSP问题,假设有n个城市,则将染色体分为同等数量的n段,其中每一段代表着某一座城市的编号。例如对10个城市的TSP问题(1,2,3,4,5,6,7,8,9,10),则∣10∣3∣5∣6∣9∣4∣1∣2∣7∣8∣就可以看作是一个染色体,从左到右代表依次经过的城市顺序。

  4.3 种群初始化

  在完成染色体编码以后,随机产生一定数量的个体组成一个初始种群,作为问题的起始解,所以首先需要决定初始化种群的数目。一般情况下初始种群的数量根据城市规模的大小来确定,初始种群个数越多,得到最优解的希望越大。

  4.4 适应度函数

  在生物学中,适应度这个词语用来衡量某个物种对环境的适应能力,适应能力越强则适应度越高。遵循优胜劣汰的自然规律,适应度越高的生物会得到越多生存与繁殖的机会,从而导致适应度低的生物逐渐被淘汰,衡量物种适应度大小的函数就被称为适应度函数。设A1∣A2∣…∣Ai∣…∣An∣为一个采用整数编码的染色体,BAiAj为城市Ai到城市Aj的距离,则该个体的适应度函数为

  fitness=1i=1n-1BAiAj+BAnA1

  即适应度函数为经过n个城市一次且仅一次,最终再回到出发城市的总路线距离的倒数。求解最短路径则需要适应度函数值越大越好,适应度函数值越大代表路径越短,染色体越优质,有更大的几率被选择;适应度函数值越小则代表路径越长,染色体越劣质,有很大的几率被淘汰。

  4.5 选择操作

  遗传算法通过适应度函数值的大小来衡量个体的适应能力,然后遵循优胜劣汰的原则对群体中的个体进行选择操作。即从旧群体中以一定概率选择个体到新群体中,个体被选中的概率跟适应度函数值有关,个体适应度函数值越大,代表适应能力越强,路径越短,则被选中的概率就越大。

  4.6 交叉操作

  由于本文用整数排列编码的方法进行编码操作,若采取简单的一点交叉或者多点交叉的方法进行交叉操作,会有极大的概率导致生成的路线不能经过所有的城市。例如随机选择两个父代个体(假设城市数量为10)选择一点交叉的方法,在[1,10]区间内随机生成一个整数C1,确定交叉点位置,如C1=5

  1 6 5 4 3 ∣ 2 8 7 9 10

  2 4 5 7 3 ∣ 1 6 8 10 9

  交叉后为

  1 6 5 4 3 ∣1 6 8 10 9

  2 4 5 7 3 ∣2 8 7 9 10

  显然生成的两个子代个体都没有全部经过10座城市,因此本文采用部分匹配交叉法。采用部分映射杂交,确定交叉操作的父代染色体,将父代样本两两分组,每组重复以下过程:

  (1)在[1,10]区间内随机生成两个整数C1和C2,确定两个位置,对两个位置中间的数据进行交叉,如C1=4,C2=7

  1 5 6 ∣ 3 4 2 8 ∣ 7 9 10

  2 4 5 ∣ 7 3 1 6 ∣ 8 10 9

  交叉后为

  * 5 * ∣ 7 3 1 6 ∣ * 9 10

  * * 5 ∣ 3 4 2 8 ∣ * 10 9

  (2)交叉后,同一个个体中有重复的城市编号,不重复的数字保留,有重复的数字(带*位置)采用部分映射的方法消除冲突,即利用中间段的对应关系进行映射。结果为

  2 5 8 ∣ 7 3 1 6 ∣4 9 10

  1 7 5 ∣ 3 4 2 8 ∣6 10 9

  4.7 变异操作

  变异操作即从父代个体中随机选择两个点,将其对换位置。在区间内随机生成两个整数C1和C2,确定两个位置,将其对换位置,如C1=4,C2=7

  2 5 8 ∣7∣ 3 1 ∣6∣4 9 10

  变异后为

  2 5 8 ∣6∣ 3 1 ∣7∣4 9 10

  对种群中的每一个个体都进行交叉变异操作,然后代入适应度函数中对适应度函数值进行评估,选择出适应度函数值较大的个体进行下一代的交叉变异操作,不满足条件重新编码代入适应度函数中进行计算,重复交叉变异操作,直到生成最优解。

  我们使用具体实例通过MATLAB软件实现遗传算法,假设存在14座城市,已知每个城市相互之间的距离,求解经过每个城市一次且仅一次并且最终回到出发城市的最短路径。编写MATLAB编程代码如下

  %遗传算法求解TSP问题

  %输入:

  %D 距离矩阵

  %NIND 种群个数

  %X 参数是城市坐标

  %MAXGEN 停止代数,遗传到第MAXGEN代时程序停止,MAXGEN的具体取值根据问题的规模和耗费的时间而定

  %m 适应度函数值淘汰加速指数,最好取为1,2,3,4,不宜太大

  %Pc 交叉概率

  %Pm 变异概率

  %输出

  %R 最短路径

  %Rlength 路径长度

  clear

  clc

  close all

  %% 加载数据

  load data

  X=[ 16.47,96.10

  16.47,94.44

  20.09,92.54

  22.39,93.37

  25.23,97.24

  22.00,96.05

  20.47,97.02

  17.20,96.29

  16.30,97.38

  14.05,98.12

  16.53,97.38

  21.52,95.59

  19.41,97.13

  20.09,92.55] %各城市坐标位置

  %遗传参数

  NIND=100; %种群大小

  MAXGEN=200; %最大遗传代数

  Pc=0.9; %交叉概率

  Pm=0.05; %变异概率

  GGAP=0.9; %代沟

  %%初始化种群

  Chrom=InitPop(NIND,N);

  %% 画出随机解的路径图

  DrawPath(Chrom(1,:),X)

  pause(0.0001)

  %% 输出随机解的路径和总距离

  disp('初始种群中的一个随机值:')

  OutputPath(Chrom(1,:));

  Rlength=PathLength(D,Chrom(1,:));

  disp(['总距离:',num2str(Rlength)]);

  disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')

  %%优化

  gen=0;

  figure;

  hold on;box on

  xlim([0,MAXGEN])

  title('优化过程')

  xlabel('代数')

  ylabel('最优值')

  ObjV=PathLength(D,Chrom); %计算路径长度

  preObjV=min(ObjV);

  while gen<MAXGEN< p>

  %% 计算适应度

  ObjV=PathLength(D,Chrom); %计算路径长度

  % fprintf('%d %1.10f\n',gen,min(ObjV))

  line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)

  preObjV=min(ObjV);

  FitnV=Fitness(ObjV);

  %% 选择

  SelCh=Select(Chrom,FitnV,GGAP);

  %% 交叉

  SelCh=Recombin(SelCh,Pc);

  %% 变异

  SelCh=Mutate(SelCh,Pm);

  %% 重新插入子代的新种群

  Chrom=Reins(Chrom,SelCh,ObjV);

  %%更新迭代次数

  gen=gen+1 ;

  end

  %% 画出最优的路径图

  ObjV=PathLength(D,Chrom); %计算路径长度

  [minObjV,minInd]=min(ObjV);

  DrawPath(Chrom(minInd(1),:),X)

  %% 输出最优解的路径和总距离

  disp('最优解')

  p=OutputPath(Chrom(minInd(1),:));

  disp(['总距离',num2str(ObjV(minInd(1)))]);

  disp('-------------------------------------------------------------')

  4.8 测试结果

  优化前的一个随机路线轨迹图如图4.2所示

  图4.2 随机路线轨迹图

  如图4.2所示,生成的随机路线为6→3→11→7→14→8→5→12→4→13→9→10→12→6,总距离为66.607。

  优化后的路线轨迹图如图4.2所示

  图4.3 最优解路线轨迹图

  如图4-2所示,最终生成的最优解路线为13→7→12→6→5→4→3→14→2→1→10→9→11→8→13,总距离为29.3405。

  优化迭代图如图4.3所示

  图4.4 遗传算法进化过程图

  由图4.4遗传算法进化过程图可以看出,优化后的路径长度相较于优化前有了很大的改进,从0代开始路径长度不断缩短,直到80代以后的路径长度已经保持不变了,可以认为是最优解了,总距离由优化前的66.607变为29.3405,因此本案例的最短路径为29.3405。

  5 结论

  本文因为城市规模的不同,研究了两种不同的方法对TSP问题进行求解,并最终都得到了最优解。

  (1)本文针对小规模的TSP问题,将其数学模型转化为混合整数规划模型,然后用LINGO软件进行求解。最关键的是需要对TSP模型附加约束条件,构成整体巡回路线的同时不存在子巡回,这样就避开了问题本身的NP困难性,使问题的求解更加高效快捷。

  (2)本文针对大规模的TSP问题,通过MATLAB软件研究其基于遗传算法的求解方法,遗传算法的实现有以下三个关键点:一是染色体的编码方式,串的长度和编码形式对算法的收敛影响极大;二是适应度函数的确定,为之后的选择操作提供了度量标准,不断重复操作最终获得最优解;三是算法自身参数的确定,群体大小,交叉概率,变异概率和遗传代数等对问题的收敛速度和求解精度都有着极大的影响,最优的参数可以提高问题的收敛速度和得到最优解。

栏目分类