智能优化TSP旅行商问题

智能优化实验报告基于遗传算法的TSP问题求解研究 一、 问题描述1、TSP问题的概述 旅行商问题 (Traveling Salesman Problem，简称 TSP) 是一个经典的组合化问题。它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城出发需要经过所有城市后回到出发地，应如何选择行进路线以使总行程短。从图论的角度看，该问题实质是在一个带权完全无向图中找一个权值最的小回路。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。旅行商问题也是经典的组合数学的问题，生活中随处可见这类组合数学问题。例如，计算下列赛制下的总的比赛次数:n个球队比赛，每队只和其他队比赛一次。在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，一笔画出网络图。一个邮递员从邮局出发，要走完他所管辖的街道，他应该选择什么样的路径，这就是著名的“中国邮递员问题”。一个通调网络怎样布局最节省?美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题，这个问题直接关系到巨大的经济利益。库房和运输的管理也是典型的组合数学问题，怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取。上述的这些例子中，其中一部分就和旅行商问题有关系。2、TSP问题研究意义解决旅行商问题有着极其重要的理论和现实意义。从理论层面来讲，解 TSP不仅为其他算法提供了思想方法平台，使这些算法广泛地应用于各种组合优化问题；而且经常被用来测试算法的优劣，如模拟退火算法、禁忌搜索、神经网络、进化算法等，都可用旅行商问题来测试。从实际应用层面来讲，旅行商问题作为一个理想化的问题，尽管多数的研究成果不是为了直接的应用，但却被广泛地转化为许多组合优化问题，最直接的就是其在交通、物流和大规模生产中的应用。3、TSP问题的解决TSP问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效地解决TSP问题有着极高的实际应用价值。因此，从 1954年第一个42个城市的旅行商问题用线性规划的方法求得解以后，陆续产生了许多种算法用来求解旅行商问题。尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的失效，人们转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。纵观旅行商问题算法研究的发展历史，主要手段是通过设计一些思想性或构造性的启发式的搜索策略来寻求问题的解，由此产生了几种具有代表意义的近似算法:贪婪算法、插入法、多边交换调整法、支撑树加倍法、支撑树加匹配法等。在过去的20多年中，基于计算机的各种智能算法已在许多领域得到应用，新出现了的一些仿生类优化算法，如遗传算法，蚁群算法，这些算法与一些经典组合优化算法的有机结合在很大程度上改进了算法的收敛速度，提高了解的质量。二、 算法设计1、遗传算法的概述与特点遗传算法是基于达尔文适者生存、优胜劣汰的进化原则，通过对群体反复使用基本的遗传操作，不断生成新的群体，使种群不断进化，并以全局并行搜索技术来搜索优化群体中的最优个体，以求得满足要求的最优解的一种问题求解策略。由于遗传算法实现全局并行搜索，搜索空间大，并且在搜索过程中能够不断地向可能包含最优解的方向作搜索空间的调整，因此，易于寻找到最优解或准最优解。需要解决的问题越复杂，目标越不明确，遗传算法的优越性就越大。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法与传统的优化方法相比，主要有以下几个特点:(1)遗传算法不是直接作用在参变量集上，而是直接作用在参变量集的某种编码上；(2)遗传算法不是从单个点进行搜索，而是从一个初始群体开始搜索；(3)遗传算法利用适应度值信息，无须导数或其它信息；(4)遗传算法利用概率转移规则，而非确定性规则。2、遗传算法的基本概念与基本操作根据遗传理论，遗传算法的基本操作对象被称为染色体(Chromosome)或个体。每个个体是一个知识结构，代表了被求解问题的一个可行解。个体通常用字符串或位串表示，一定长度的位串被称为个体的基因(Gene)，基因表示了个体的某些特征。群体或种群(Population)是由一组个体构成的，它是个体的集合，描述了遗传算法搜索的遗传空间。种群的大小(Population size)是种群个体的数量。在搜索过程中，用适应度函数 (Fitness function)来评价每个个体的优劣，其值越大(适应度值大)，则相应的个体所代表的解越优。适应度函数的选择能够有效地指导搜索空间沿着最佳参数优化组合的方向逼近。利用遗传算法求解问题的第一步就是要对问题的解以某种形式编码，并将问题的解用遗传空间的解来表示，即用字符串构造个体的过程。与其相反的操作称为解码。另外，编码形式的选择也是影响遗传算法效率的重要因素之一。在对问题的解进行编码及对种群进行初始化后，对种群的遗传操作主要有以下三种:即选择操作、交叉操作和变异操作。选择(Selection)操作就是根据个体的适应度值，在群体中按一定的概率选择可作为父代的个体。选择的依据是:适应度值大的个体被选中的概率也大，即选择的过程是一种基于适应度值优胜劣汰的过程。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代以繁殖下一代子孙。主要的选择操作有轮盘赌方法和锦标赛方法等。交叉(Crossover)操作是按一定的概率随机地交换一对父个体的基因以形成新的子个体，这个过程又称基因重组。交叉操作是遗传算法的主要操作，通过交叉操作可得到新一代个体。主要的交叉操作有单点交叉、两点交叉等。变异(Mutation)操作是按一定的概率随机地改变某个个体的基因值，以形成新的子个体，它的目的是挖掘群体中个体的多样性，克服有可能陷于局部最优解的弊端。3、遗传算法的基本流程遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作和基本步骤如下：(l)选择编码策略，对所解决的问题进行编码，把参数集合X和域转化为位串结构空间S；(2)定义适应度函数f(x)，适应度大小表示了该个体的好坏；(3)确定遗传策略，包括确定种群大小、选择、交叉、变异方法，以及确定交叉概率Pc，变异概率Pm等遗传参数；(4)随机初始化种群P；(5)计算种群中个体位串解码后的适应度值；(6)按照遗传策略，运用选择、交叉和变异算子作用于种群，形成下一代种群；三、算例设计遗传算法求解TSP问题可包括:编码、种群初始化、适应度评价、遗传操作(选择、交叉、变异)、终止条件判定、解码等步骤:1、 染色体编码由于遗传算法不能直接处理解空间的数据，因此必须通过编码将它们表示成遗传空间的基因型串结构。编码应具备完备性、健全性.、非冗余性等特点。GA通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。对于TSP问题，主要有以下几种编码方式:(1)顺序表示1955年，Grefenstette等针对TSP问题提出了基于顺序表示(Ordinal Representation)的遗传算法基因编码36。顺序表示是指将所有城市依次排列构成一个顺序表 (order List)。对于一条旅程，可以依旅行顺序处理每个城市，每个城市在顺序表中的顺序就是一个遗传因子表示。每次处理完一个城市，从顺序表中去掉该城市。处理完所有的城市后，将每个城市的遗传因子表示依次连接起来，就成为一条旅程的基因表示。例如，顺序表C=(1，2，3，4，5，6，7，8，9)，如果一条旅程为1一2一4一3一8一5一9一6一7，则这条旅程的编码为:1。因为这种编码方式在进行单点杂交时，左侧部分的旅程没有发生变化，所以这种方法在适用性方面存在一定的问题。（2）近邻表示近邻表示(Adjacent Edges Representation)是将旅程表示成n个城市的一个排列，若在第i位的城市为j，则表明从i所到达的下一个城市为j。例如，设出发城市的编号为1，则排列(2，4，8，3，9，7，1，5，6)表示的旅程为:1一2一4一3一8一5一9一6一7。显然，每一条旅程都唯一对应一个近邻表示。然而，任意一个近邻排列却不一定都能对应于一个合法旅程，例如近邻排列(2，4，8，1，9，3，5，7，6)就导致了一个不完全回路1一2一4一1，产生了非法旅程，即小圈现象。针对小圈现象，需要在算法中加以修改，以得到合法的旅程。（3）矩阵表示矩阵表示 (Matrix Representation)是将一条旅程表示成为一个 nn矩阵，其存储量随城市规模的增加而迅速增加，其遗传操作比较复杂，并具有盲目性。本文采用此表示方法作为遗传算法的编码方式本程序解决的是10城市间的TSP问题，下面采用实数编码并给出了10个城市间距离矩阵，分别用数字0-9表示北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌10个城市。rij代表城市i与城市j之间的距离：北京天津武汉深圳长沙成都杭州西安拉萨南昌00123456789北京1011812722567165320971425117739471574天津2118012532511163320771369115739611518武汉3127212530146238014908218563660385深圳425672511146209222335156221653995993长沙51653163338092201700104111353870456成都6209720771490233517000231192021701920杭州714251369821156210412311014204290626西安811771157856216511359201420028701290拉萨93947396136603995387021704290287004090南昌01574151838599345619206261290409002、种群的初始化因遗传算法的群体型操作需求，必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体可以随机产生，也可以通过某种算法生成，但需要保证群体的多样性。在种群初始化时需要考虑以下几个方面的因素:（1）根据问题固有的知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机生成一定数目的个体，然后从中挑选出最好的个体加入初始群体。这一过程不断进行迭代，直到初始群体中个体数达到了预先确定的规模。群体的数量对遗传算法有着很大的影响。若群体过大，能够保证群体的多样性，但其计算量则相应地增加，而且高适应度的个体容易被淘汰;若群体过小，则计算量较少，但容易导致早熟现象。求解TSP的遗传算法确定初始群体的常用方法一般有两种，即随机产生初始个体组成初始群体，以及利用局部搜索算法修正后的个体组成初始群体。随机选取初始群体是被普遍采用的初始化方法，它具有速度快、并能保证群体多样性等特点。但随机产生的个体适应度值太低，它们需要更多的迭代次数的遗传操作来进行优化。遗传算法的主要遗传操作交叉操作，往往会使得群体中个体越来越趋于相同，致使种群在一定的迭代次数后很难得到进化，而此时的解离最优解可能相去甚远，这就使得这种初始化方法的优点丧失殆尽。局部搜索算法初始化群体可以解决随机化方法造成的问题，但局部搜索算法将增加整个算法的时间开销，特别是当种群规模较大时，初始化种群操作就将占用整个算法时间的很大比重，并使得算法无法在合理的时间内完成。针对上述两种方法的优缺点，采用快速的近似算法初始化种群将是一种折衷方案。一般采用的群体初始化方法有最近邻法等。3、适应度评估检测遗传算法在搜索进化过程中一般不需要其它外部信息，仅需要采用评估函数值(适应度函数值)来评估个体的优劣，并作为以后遗传操作的依据，适应度函数设计直接影响了遗传算法的性能。适应度评估检测可分如下步骤进行:(1) 目标函数到适应度函数的映射:由于适应度函数的非负性，不能直接用目标函数代替适应度函数，必须对目标函数作相应的转化，这就需要一个从目标函数到适应度函数的映射。(2)适应度函数的标定常用的标定方法有线性标定、s截断、乘幂标定等。在应用遗传算法时，群体中小规模异常个体的出现常常不利于群体的优化。在遗传初期，超常的个体往往会导致未成熟的收敛现象。在遗传进化过程中，往往出现群体平均适应度值接近最佳个体适应度值，使得优化过程趋于无目标的随机漫游过程。所以在遗传算法中，调整群体中个体的竞争水平是必要的，从而能够得到适应度较高的个体。对未成熟收敛现象，可通过缩小相应个体的适应度值以实现降低这些异常个体的竞争能力，从而避免未成熟现象的产生;对于随机漫游现象，则可通过放大适应度值以实现提高个体间竞争力的方法加以避免。常见的求解TSP问题的适应度函数为f=1/L，其中L为环路长度。4、交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 本程序中交叉算子实际上是将一段路径“串”逆序。5、 变异算子 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。（1）移位变异移位变异(Displacement Mutation，DM)是指随机选取一段路径，然后将该段路径插入到任意点之后。（2）交换变异交换变异(Exchange Mutation，EM)是指随机选取环路中的任意两点，然后进行交换。（3）插入变异插入变异(Insertion Mutation，ISM)是指从环路中随机选取一点，然后将该点插入到任意点之后。本程序中的变异算子实际上是将种群中某两个位置的节点值互换，即交换变异。例如： 4、选择策略 遗传算法对一个个体（解）的好坏用适值函数值来评价，适值函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。本文中选择算子采用轮盘赌选择方法。 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为： 轮盘赌选择方法的实现步骤：（1） 计算群体中所有个体的适应度函数值（需要解码）；（2） 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3） 采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。四、 仿真实验设计 开始产生初始种群计算每个染色体的适应值选择交叉变异满足终止条件?输出最优解结束 程序流程图： 五、 仿真实验结果分析 本程序迭代次数为200，得到最佳路径及最佳适应值。 仿真结果如下：六、 总结与展望这一现象与使用的是遗传算法有很大关系。遗传算法其本质是模拟生物进化过程，而生物进化的过程是一个很复杂的过程，并且进化本身就无法控制其精确向着最优结果进行。这也是遗传算法容易陷入局部最优的根本原因。附 录：#include #include #include using namespace std;#define PopSize 50 /种群类DNA个数 #define MaxGens 200 / 最大代数 #define N 10 / 问题规模#define PC 0.8 / 交叉概率#define PM 0.01 / 突变概率 int cityN; /有N个城市int begin_city=0; /出发城市double rNN= /N各个城市之间的权值，用一个矩阵表示 0,118,1272,2567,1653,2097,1425,1177,3947,1574, 118,0,1253,2511,1633,2077,1369,1157,3961,1518, 1272,1253,0,1462,380,1490,821,856,3660,385, 2567,2511,1462,0,922,2335,1562,2165,3995,933, 1653,1633,380,922,0,1700,1041,1135,3870,456, 2097,2077,1490,2335,1700,0,2311,920,2170,1920, 1425,1369,821,1562,1041,2311,0,1420,4290,626, 1177,1157,856,2165,1135,920,1420,0,2870,1290, 3947,3961,3660,3995,3870,2170,4290,2870,0,4090, 1574,1518,385,993,456,1920,626,1290,4090,0 ;int generation; / 当前代数int CurBest; / 最优个体struct GenoType int geneN; / 城市序列 double fitness; / 当前城市序列对应的适应值 double rfitness; / 适应率 double cfitness; / 轮盘对应的起始区间值;struct ResultType double best_val; /最佳适应度 double avg; /平均适应度 double stddev; /标准差 ;GenoType populationPopSize+1; / 种群GenoType newpopulationPopSize+1; /新种群ResultType resultMaxGens; /种群换代记录 /函数声明 void InitIndividual(); /初始化个体void Evaluate(); /评价函数 void Find_the_best(); /找出最优个体void Elitist();void Select(); /选择 void Crossover(); /交叉 void Mutate(); /变异 void Report(); /报告输出 int IntGenerate(); /产生一个城市节点 void swap(int *,int *); /交换两值 void swap(int *a,int *b)int temp;temp=*a;*a=*b;*b=temp;/* 产生一个0到10的数，作为城市编号*/ int IntGenerate() int RANGE_MIN = 0;int RANGE_MAX = N;int rand10 = (double) rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);return rand10; /*初始化种群*/void InitIndividual() int matrixN; /临时数组int x1, x2; /生成一个定值序列1到9 ，0点为开始点for(int i = 1; i N; i+)matrixi = i;for(int j = 0; j PopSize; j+) populationj.gene0 = begin_city; /gene0表示出发城市，i表示城市次序 for( i = 0; i N; i+) /N次交换，产生足够多的城市序列x1 = 0; x2 = 0;while(x1 = 0)x1 = IntGenerate(); /随机产生一个0到10的数while(x2 = 0)x2 = IntGenerate();swap(&matrixx1, &matrixx2);for(int i = 1; i N; i+) /将产生的临时数组赋给个体populationj.genei = matrixi;/* 评价函数：计算出该种群的适应性*/void Evaluate() int current_city = begin_city;int next_city;for(int mem = 0; mem PopSize; mem+)populationmem.fitness = 0;for(int i = 1; i N; i+) next_city = populationmem.genei; populationmem.fitness += rcurrent_citynext_city; current_city = next_city; populationmem.fitness += rcurrent_citybegin_city;/*找出该代种群中的最优个体，并将其存储.*/void Find_the_best()int mem, i;CurBest = 0; for(mem = 1; mem PopSize; mem+) if(populationmem.fitness populationCurBest.fitness) / 一次冒泡找出最优个体CurBest = mem;/找到最优个体后，将其存储起来 for(i = 0; i N; i+)populationPopSize.genei = populationCurBest.genei;populationPopSize.fitness = populationCurBest.fitness;/* 择优函数：将当代中的最优及最差个体保存下来,如果新种群中最优个体优于父代中最优个体， 则将其保存下来,否则，将当代中最差个体替换为父代中最优个体*/void Elitist() int i;double best, worst;int bestmem, worstmem;best = population0.fitness;worst = population0.fitness;/冒泡比较两个个体中的适应度，并可能选择较大的放入worst_mem和较小的放入best_mem for(i = 0; i PopSize-1; +i)if(populationi.fitness populationi+1.fitness)if(populationi.fitness = worst)worst = populationi+1.fitness;worstmem = i + 1;elseif(populationi.fitness = worst)worst = populationi.fitness;worstmem = i;if(populationi+1.fitness = best)best = populationi+1.fitness;bestmem = i + 1;/*如果新种群中最优个体优于父代中最优个体，则将其保存下来；*/* 否则，将当代中最差个体替换为父代中最优个体 */if(best = populationPopSize.fitness)for(i = 0; i N; i+)populationPopSize.genei = populationbestmem.genei;populationPopSize.fitness = populationbestmem.fitness; elsefor(i = 0; i N; i+)populationworstmem.genei = populationPopSize.genei;populationworstmem.fitness = populationPopSize.fitness;void Select() int mem, i, j; double sum = 0.0;double p;double xPopSize; for(mem = 0; mem PopSize; mem+)sum += populationmem.fitness; /由于此处选择应是fitness越小越好，for(mem = 0; mem PopSize; mem+)xmem = sum - populationmem.fitness;sum = 0.0; /求得传统适应总值for(mem = 0; mem PopSize; mem+)sum += xmem/求得适应率for(mem = 0; mem PopSize; mem+)populationmem.rfitness = xmem/sum;population0.cfitness = population0.rfitness;for(mem = 1; mem PopSize; mem+) populationmem.cfitness = populationmem-1.cfitness + populationmem.rfitness;for(i = 0; i PopSize; i+)p = rand()%1000/1000.0;if(p population0.cfitness)newpopulationi = population0; elsefor(j = 0; j = populationj.cfitness & p populationj+1.cfitness)newpopulationi = populationj+1; /将新种群中的个体复制到原种群中for(i = 0; i PopSize; i+)populationi = newpopulationi;/* 交叉：实质为将一段路径串逆序 */void Crossover()int i, j;int min, max, flag;double x;for(i = 0; i PopSize; i+) x = rand()%1000/1000.0;if(x PC)min = 0;max = 0;while(min = 0)min = IntGenerate();while(max = 0)max = IntGenerate();if(max min)int temp;temp = max;max = min;min = temp;flag = max;for(j = min; j = (max + min) / 2; j+)swap(&populationi.genej, &populationi.geneflag);flag = flag-1;/* 变异：将种群中两个位置的节点值互换*/变异操作 void Mutate()int i;double x;int x1, x2;for(i = 0; i PopSize; i+) x = (int)rand()%1000/1000.0;if(x PM)x1 = 0;x2 = 0;while(x1 = 0)x1 = IntGenerate();while(x2 = 0)x2 = IntGenerate();swap(&populationi.genex1, &populationi.genex2);/*报告输出：将过程记录在输出文件中*/void Report()int i;double best_val; /最佳适应度double avg; /种群平均适应度 double stddev; /种群适应度标准差 double sum_square; /适应度的平方和 double square_sum; double sum; /适应度总和 sum = 0.0;sum_square = 0.0;for(i = 0; i PopSize; i+)sum += populationi.fitness;sum_square += populationi.fitness * populationi.fitness;avg = sum * 1.0 / (1.0 * PopSize);square_sum = avg * avg * PopSize;stddev = sqrt(sum_square - square_sum) / (PopSize - 1);best_val = populationPopSize.fitness;resultgeneration - 1.best_val = best_val;resultgeneration - 1.avg = avg;resultgeneration - 1.stddev = stddev;/* 主函数：每一代都通过交叉、变异之后，通过评估函数评估.*/* 然后选择最好的个体，直至最大代数 */int main()int i; int ierr, myid, numprocs;cout 智能优化实验报告1101328李俊霞 n;cout 基于遗传算法的TSP问题 nn;coutnowNcityn begin:nn;cout the result：n;cout nGeneration Number | Best Value | Average Fitness | Standard Deviationn;generation = 0;srand( (unsigned)time( NULL ) ); InitIndividual();Evaluate();Find_the_best();while(generation MaxGens)generation+;Select();Crossover();Mutate();Report();Evaluate(); Elitist();for(i = 0 ; i MaxGens ; i+)cout i+1 resulti.best_val resulti.avg resulti.stddevendl; coutnn finishn;coutn The best route: n;coutcity1 = begin_cityendl; for (i = 1; i N; i+)coutcityi = populationPopSize.geneiendl; coutthe best fitness：populationPopSize.fitnessendl;cout(nn Finished program execution!nn);coutcompleted time:(double)clock()/1000sn;system(pause);return 0;