admin管理员组文章数量:1596413
MATLAB–基于遗传算法的旅行商问题（TSP问题）实现
在干活的过程中整理下来的，希望对大家有帮助。
什么是旅行商问题：假设有一个旅行商人要拜访全国10个城市，他需要选择所要走的最近路径，路径的限制是每个城市只能访问一次，而且最后要回到原来出发的城市。对路径选择的要求是：所选路径的路程为所有路径之中的最小值。已知10个城市的坐标为[82,7;91,38;83,46;71,44;64,60;68,58;83,69;87,76;74,78;71,71]。在具体操作中一般都采用标号形式表示城市，在计算两城市之间距离时算法能够自动将标号转换成所对应的坐标，来计算两城市之间的距离。
-
1.求解的第一步是根据问题对解空间进行编码
根据TSP问题的具体要求，其解空间应该是遍历所有城市，并且每个城市只能经过一次的路径集合，为此采用序列编码表示法。具体编码规则是每个染色体表示一条可能的旅行路径，由按一定顺序排列的10个城市的序号组成，染色体中的每个基因表示一个城市，染色体的长度为需要遍历的城市数10。例如，3→2→5→4→10→7→1→6→9→8→3为一条路径，用序列编码表示法可简单表示为[3 2 5 4 10 7 1 6 9 8]，其含义为从城市3出发依次经过城市2、5、4、10、7、1、6、9、8然后返回城市3的一条路径。这种编码方式满足TSP问题的约束条件，保证了每个城市都经过且只经过一次，并且保证任何一个城市子集中不形成回路，同时在计算个体的适应度函数值时无需解码，变异算子也容易设计。坐标的位置与城市的标号是一一对应的，其中第一个坐标（82, 7）表示标号为1的城市坐标，第二个坐标（91, 38）表示标号为2的城市坐标，以此类推第10个坐标（71, 71）表示标号为10的城市坐标。 -
2.求解的第二步是生成初始种群
遗传算法一般都是随机生成初始种群。在MATLAB语言中可调用函数randperm()，对于10城市的TSP问题，randperm(10)能够随机生成一个由1～10数字组成的无重复序列，代表遍历所有城市的一条路径，存入矩阵Road中。矩阵Road是一个SizeScale×n的矩阵，其中SizeScale是种群规模的大小，表示初始种群有多少条路径；n是每个染色体中的基因数，为需要遍历的城市数10，Road(i,:)代表初始种群路径矩阵中的第i行，表示第i条路径。矩阵Road是一个动态矩阵，选择、交叉和变异操作后的结果都将反复存储在这个矩阵中。
种群规模的大小直接影响遗传优化的结果和效率，通常要根据问题的解空间来选取。种群的规模过小时将增加最大进化迭代次数，种群的规模过大时将增加每一次迭代的计算量，因此种群的规模应该进行多次实验后确定一个折中值。10城市的TSP问题的解空间为10!=3628800，根据以往经验，本例中取种群规模为150，那么Road是一个150×10的矩阵。这里我用的是MATLAB 2016b编写的程序。主程序设计的比较简单，算法的实现主要在tapga.m中。下边的第一段是主程序，tapga.m在文章的最后。tapga.m第17行生成了一个MaxIter×1的全1矩阵MinestRoad_fval，用来保存每一次迭代得到的最短里程。程序第18行生成了一个MaxIter×n的全1矩阵MinestRoad_opt，用来保存每一次迭代得到的最短里程对应的路径。
Map1=[82,7;91,38;83,46;71,44;64,60;68,58;
83,69;87,76;74,78;71,71];%具体城市坐标
MaxIter=200; %最大迭代次数
Pop_Size=150; %种群规模
pc=0.8; %选择概率
pm=0.1; %变异概率
[opt,fval]=tspga(Map1,MaxIter,Pop_Size,pm,pc);
版权声明：本文标题：MATLAB--基于遗传算法的旅行商问题（TSP问题）实现 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728256209a1151043.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论