编码目的和解析

• 旅行商问题：
  • 地图上有n个点，旅行商要求从一个点出发，经过每个城市一次且仅一次并最终回到出发城市，求最短路径
• 使用matlab作为编程工具，采用遗传算法对tsp（旅行商）问题进行基本编码实现和优化解答，最终控制误差在一定范围内，或者找到旅行商问题的最优解。

注：旅行商问题的已知最优解是通过遍历得到的，不可能通过智能算法得到更短的距离，除非计算公式出错或者数据出现问题。

数据获取

所需工具/软件/数据

软件：matlab

日志：csdn博客

搜索到的资料及其 址

1. 《TSP的已知最优解》：百度文库 址 该文档的上传日期为2014年，该文档最后一行显示的时间点为2007年。

2. oschina中的数据集下载 址：MP-TESTDATA – The TSPLIB Symmetric Traveling Salesman Problem Instances

数据集和代码已经上传到csdn中，欢迎学习和交流

3. 遇到的第一个问题是距离的计算问题，具体可以通过下载这个文件去查看具体数据集的距离计算公式：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf

   文件第九页有每种问题的对应距离计算方法，再通过该方法找到具体的措施即可

原理解析

种群确定与基本操作

• 首先要确定每个个体的元素和一个规模合适的种群
  • tsp问题每个个体其实可以看做n个城市的链条
  • 比如n = 5，<1,2,3,4,5>的排列顺序可以看成一个个体
  • 1 2 3 4 5就是一个一个基因片段，后续重组变异也是基于此实现
• 确定种群的规模
  • 和个体的基因数有关，一般规模不大时设置为100-1000即可
  • 注意：规模越大，可能导致运算时间过长
• 到这里，对应实现种群的初始化即可
  • 比如一千个个体，每个个体48个基因（n=48）随机排列

选择

• 主要有两种方法：轮盘赌和锦标赛（试验效果更好）
• 生成一个个体所需的父代一般是两个
  • 所以使用两次算法得出两个个体参与重组、变异即可

轮盘赌：

• 结合tsp算法进行解释：
• 适应度：粗略理解为该个体生存下去的可能性的大小
  • 在tsp问题中，可以理解为距离越小，适应度越高
  • 所以可以取距离的倒数
• 求出父代每个个体的适应度，并进行累加得到max
  • 这里需要生成一个数组，存放自第一个到第m个个体的累积适应度
    • 例如有三个个体，适应度为0.2,0.5,0.7
    • 生成的数组就是[0.2,0.7,1.4]
• 随后获得一个随机数 ran 在0-max之间
  • 看看这个ran小于哪个累计数（0.2,0.7,1.4）就选择哪个个体
  • 例如ran=0.6，则选择第二个个体，因为0.6>0.2且0.6<0.7

锦标赛

• 选择m个个体，选择适应度最高的个体作为父代
• 这个很简单，理解为在n个个体中选择m个个体，再比较这m个个体，选择距离最短的那个个体就行
  • 例如种群数量有10个，随机选择5个个体（n=10，m=5）
  • 这五个个体距离为：100,200,300,400,500
    • 选择第一个个体，因为距离最小

重组

• 通过筛选出来的两个个体，即可进行重组运算
• 生物学上：重组就是选择父代两个相同位置的片段，交换上面的基因，形成新的个体
• 在tsp问题中，也是一样的，但是要考虑到如果交换了，可能出现某些城市出现了两次的情况
  • 所以交换的时候采用以下的方法进行交换，看图解：

距离计算公式 –> 不同type不同

Read方法–> 读取tsp文件

种群初始化

randperm(int[]) 将一列序 随机打乱，序 必须是整数。

find(square,1, ‘first’); 找出square中第一个非零元素

find(条件, -, -) 返回满足某条件的值

find(sumDistance==parent1,1, ‘first’);

选择方式

随机选择四个，选择里面最好的适应度的元素

然后找到对应的路径进行取出

锦标赛算法

每一代的更新方法

保留上一代最好的值，然后使用锦标赛算法

看不懂没关系，后面有改进方案，学后面的

最终代码

优化点：

• 在开头计算好所有城市的距离矩阵（n*n），在之后的适应度计算中，直接读取矩阵中的数据即可，大大减轻计算压力

• 直接选择父代最好的一半元素作为下一代的父代，并从中随机选择两个进行交叉变异获得新个体

• 保留每一代最好的个体

• 初始化种群的时候不要随意初始化，使用贪婪算法进行初始化–> 对大数据集优化明显

  • 任选一个城市作为初始节点
  • 选择距离这个城市最短距离的城市作为下一个节点
  • 随后跳转到【下一个节点】,并重复执行上一步操作，知道找到一条”贪婪算法最短链”
  • 注意：找的时候已经找过的点不要再用了，可以使用一个zeros(n)数组保存是否已经被使用，使用过了就置为1，没有就还是0，读取对应位置的元素进行替换即可，非常快速

• 变异的时候变异多个基因

  • 效果不大

• 重组的时候重组多个部分

  • 效果好一点

• 设置超过200次，变异概率提高

  • 效果好点

• 设置超过1000次，跳出循环

  • 为了避免长时间无效运转

实验成果举例

迭代收敛图

运行结果

crossver——重组

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！