【TSP问题】基于遗传算法求解旅行商问题matlab代码

1 算法介绍1.1 TSP介绍“旅行商问题”(Traveling Salesman Problem,TSP)可简单描述为一位销售商从n个城市中的某一城市出发不重复地走完其余n-1个城市并回到原出发点在所有可能路径中求出路径长度最短的一条。旅行商的路线可以看作是对n城市所设计的一个环形或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n-1)!个因此解决这个问题需要O(n!)的计算时间。而由美国密执根大学的Holland教授发展起来的遗传算法是一种求解问题的高效并行全局搜索方法能够解决复杂的全局优化问题解决TSP问题也成为遗传算法界的一个目标。1.2 遗传算法求解tsp模型巡回旅行商问题(TSP)是一个组合优化方面的问题已经成为测试组合优化新算法的标准问题。应用遗传算法解决 TSP 问题首先对访问城市序列进行排列组合的方法编码这保证了每个城市经过且只经过一次。接着生成初始种群并计算适应度函数即计算遍历所有城市的距离。然后用最优保存法确定选择算子以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。算法流程旅行商问题的遗传算法实现1.初始群体设定一般都是随机生成一个规模为 N 的初始群体。在这里我们定义一个s行t列的pop矩阵来表示群体t 为城市个数 1即 N 1s 为样本中个体数目。在本文探讨了 30 个城市的 TSP 问题此时 t 取值 31该矩阵中每一行的前 30 个元素表示经过的城市编号最后一个元素表示适应度函数的取值即每个个体所求的距离。2.适应度函数的设计是根据个体适应值对其优劣判定的评价函数。在该问题中用距离的总和作为适应度函数来衡量求解结果是否最优。3.选择指以一定的概率从群体中选择优胜个体的操作它是建立在群体中个体适应度评估基础上的。为了加快局部搜索的速度在算法中采用最优保存策略的方法即将群体中适应度最大的个体直接替换适应度最小的个体。它们不进行交叉和变异运算而是直接复制到下一代以免交叉和变异运算破坏种群中的优秀解答。4.交叉算子是产生新个体的主要手段。它是指将个体进行两两配对以交叉概率 Pc 将配对的父代个体的部分结构加以替换重组生成新个体的操作。本文中采用有序交叉法来实现。有序交叉法的步骤描述如下:5.变异操作是以较小的概率 Pm 对群体中个体编码串上的某位或者某些位作变动从而生成新的个体。本文中采用倒置变异法:假设当前个体 X为(1 3 7 4 8 0 5 9 6 2)如果当前随机概率值小于 Pm则随机选择来自同一个体的两个点mutatepoint(1) 和 mutatepoint(2)然后倒置两点的中间部分产生新的个体。例如假设随机选择个体 X 的两个点“7”和“9”则倒置该两个点的中间部分即将“4805”变为“5084”产生新的个体 X 为(1 3 7 5 0 8 4 9 6 2)。6.终止条件为循环一定的代数。2 部分代码global DISTANCE_Mglobal POPULATION_Nglobal POPULATIONglobal CITIES_POSITIONglobal STATSglobal BEST_PATHglobal PLOT_TITLEglobal PLOT_SIZEglobal PATH_PLOTglobal TABLECITIES 10;PLOT_SIZE 100;POPULATION_N 20;GENERATIONS 400;STATS cell(POPULATION_N 3, 5);% Generate map position of cities and distancesCITIES_POSITION PLOT_SIZE * rand(2, CITIES);DISTANCE_M zeros(CITIES);for i 1 : CITIES - 1position1 CITIES_POSITION(:, i);for j i 1 : CITIESposition2 CITIES_POSITION(:, j);dist position1 - position2;distSq sqrt(dist * dist);DISTANCE_M(i, j) distSq;DISTANCE_M(j, i) distSq;endend% Generate initial POPULATIONPOPULATION zeros(POPULATION_N, CITIES);for i 1 : POPULATION_NPOPULATION(i,:) randperm(CITIES, CITIES);end% Random initial bestPathBEST_PATH POPULATION(randi(CITIES), :);POPULATION;plots();stats();colTitles {Cromosoma, Distancia, f(x), P_Select, EC, AC};colFormat { char, numeric, numeric, numeric, numeric, numeric};TABLE uitable(...Units, normalized,...Position, [0, 0, 1.0, 0.5],...ColumnName, colTitles,...ColumnFormat, colFormat,...ColumnWidth, { 400 auto auto auto auto auto },...Data, STATS);for i 1 : GENERATIONSstats();parents reproduction();POPULATION mutation(crossover(reproduction()));% Find best and remove the worstBEST_PATH findBest();% Avoid update plots several timesif mod(i, 50) 0pause(0.05);set(PLOT_TITLE, string, {[ BEST PATH: num2str(BEST_PATH)];...[DISTANCE num2str(distanceForPath(BEST_PATH))];...[GENERATION num2str(i)]});set(TABLE, Data, STATS);set(PATH_PLOT,...XData, [CITIES_POSITION(1, BEST_PATH) CITIES_POSITION(1, BEST_PATH(1))],...YData, [CITIES_POSITION(2, BEST_PATH) CITIES_POSITION(2, BEST_PATH(1))])endend3 仿真结果4 参考文献[1]谢胜利, 唐敏, 董金祥. 求解TSP问题的一种改进的遗传算法[J]. 计算机工程与应用, 2002, 38(008):58-60.[2]文艺, and 潘大志. 用于求解TSP问题的改进遗传算法. 计算机科学 43.0z1(2016):90-92.**部分理论引用网络文献若有侵权联系博主删除。**​