实验题目：的遗传算法解决TSP问题姓名：***
班级：智能1001
学号：***********
一:问题描述
二:遗传算法的基本原理
遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器
学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智一样，都是对今后十年的计算技术有重大影响的关键技术”。
基本步骤为:
标准的遗传算法包括群体的初始化，选择，交叉，变异操作。所示，其主要步骤可描述如下：
（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。
（2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。
（3）根据适配值大小以一定方式执行选择操作。
（4）按交叉概率Pc执行交叉操作。
（5）按变异概率Pm执行变异操作。
（6）返回步骤（2）
算法流程图为:
三:TSP问题的遗传算法设计
初始种群：对于n个城市的问题，每个个体即每个解的长度为n，用s行,t列的pop矩阵表示初始群体，s表示初始群体的个数，t为n+1，矩阵的每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长度。这一算法通过start.m程序实现。
适应度：在TSP的求解中，可以直接用距离总和作为适应度函数。个体的路径长度越小，所得个体优越，以pop矩阵的每一行最后一个元素作为个体适应值。
选择：选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个体。
交叉：受贪婪算法的启发,本文设计一种有目的使适应值上升的交叉算子。已知两a1(m11,m12,m13,...,m1n),a2(m21,m22,m23,...,m2n)，算法产生后代a1’和a2’的过程如下：
(1)随机产生一个城市d作为交叉起点,把d作为a1’和a2’的起始点
(2)分别从a1和a2中找出d的右城市dr1和dr2,并计算(d,dr1)和(d,dr2)的距离j1和j2。
(3)如果j1
(4)如果j1>j2,则把dr2作为a1'的第二个点，从a1和a2中删除d，并且把当前点改为dr2。
(5)若此时p1和p2的个数为1，结束，否则回到第二步继续执行。
同理，把第二步中的右城市改成左城市dle1和dle2，通过计算(d,d1e1)和(d,d1e2)的距离并比较大小来确定子代a2'。
变异：变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。这里采用的方法是倒置变异法。假设当前个体X为（1374805962）。如果Pm>rand，那么随机选择
来自同一个体的两个点mutatepoint(1)和mutatepoint(2)，比如说3和7，倒置P1和P之间的部分，产生下面的子体X'为(1375084962)。
四：实验代码
1主函数部分
clc;
clearall;
closeall;
globalxy
cityfile=fopen('city30.txt','rt');%取30个城市的样本
cities=fscanf(cityfile,'%f%f',[2,inf]);
fclose(cityfile);
t=30+1;%城市的数目是30个
s=1500;%样本的数目是1400个
G=300;%运算的代数
c=25;%选择算子中每次替代的样本的数量
x=cities(1,:);
y=cities(2,:);
pc=0.10;%交叉的概率
pm=0.8;%变异的概率
pop=zeros(s,t);%得初始的pop矩阵，矩阵的最后一列表示所在行的样本的路径距离
fori=1:s
pop(i,1:t-1)=randperm(t-1);%随机产生1—（t-1）的t-1个数