实验题目的遗传算法解决TSP问题姓名
班级智能1001
学号
f一问题描述
旅行商问题即TSP问题Travelli
gSalesma
Problem又译为旅行商问题货郎担问题是数学领域中著名问题之一。假设有一个旅行商人要拜访
个城市他必须选择所要走的路径路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此任何能使该问题的求解得以简化的方法都将受到高度的评价和关注。
二遗传算法的基本原理
遗传算法是由美国JHolla
d教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象在每次迭代中都保留一组候选解并按某种指标从解群中选取较优的个体利用遗传算子选择、交叉和变异对这些个体进行组合产生新一代的候选解群重复此过程直到满足某种收敛指标为止。遗传算法在本质上是一种不依赖具体问题的直接搜索方法是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器
f学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智一样都是对今后十年的计算技术有重大影响的关键技术”。
基本步骤为
标准的遗传算法包括群体的初始化选择交叉变异操作。所示其主要步骤可描述如下
1随机产生一组初始个体构成的初始种群并评价每一个个体的适配值。
2判断算法的收敛准则是否满足。若满足输出搜索结果否则执行以下步骤。
3根据适配值大小以一定方式执行选择操作。
4按交叉概率Pc执行交叉操作。
5按变异概率Pm执行变异操作。
6返回步骤2
算法流程图为
f三TSP问题的遗传算法设计
初始种群对于
个城市的问题每个个体即每个解的长度为
用s行t列的pop矩阵表示初始群体s表示初始群体的个数t为
1矩阵的每一行的前
个元素表示城市编码最后一个元素表示这一路径的长度。这一算法通过startm程序实现。
适应度在TSP的求解中可以直接用距离总和作为适应度函数。个体的路径长度越小所得个体优越以pop矩阵的每一行最后一个元素作为个体适应值。
选择选择就是从群体中选择优胜个体、淘汰劣质个体的操作它是建立在群体中个体适r