发布时间 : 星期一 文章遗传算法求解TSP问题实验报告更新完毕开始阅读d7760e02844769eae009edb1
一、 实验目的
加深对逻辑程序运行机理的理解，掌握MATLAB语言的特点、熟悉其编程环境，同时为后面的人工智能程序设计做好准备。 1、熟悉MATLAB语言编程环境的使用；
2、了解MATLAB语言中常量、变量的表示方法；
3、了解利用MATLAB进行事实库、规则库的编写方法； 二、 实验环境
计算机 哈尔滨工程大学计算机学院实验室 三、 预习要求
实验前应阅读实验指导书，了解实验目的、预习MATLAB语言的相关知识。 四、 实验内容
1、学习使用MATLAB，包括进入MATLAB主程序、编辑源程序、修改环境目录、退出等基本操作。
2、在MATLAB集成环境下调试运行简单的MATLAB程序，如描述亲属关系的MATLAB程序或其他小型演绎数据库程序等。 五、 实验方法和步骤
步骤一 针对TSP问题，确定编码。
可采用十进制编码法，对城市进行编号，每个城市分别用1到n之间不同的整数表示，n个整数的一个排列就代表了旅行商问题。 步骤二 针对TSP问题，适应度函数可定义为：
其中d（ci，ci+1）表示相邻城市之间的距离。
步骤三 针对TSP问题，确定交叉规则。对于采用整数编码表示的染色体，可以有以下交叉规则： （1）常规交叉法
f(s)?1n?i?1d(ci,ci?1) 设有父代1和父代2，交配后产生子代1和子代2。随机选取一个交配位，子代1交配位之前的基因选自父代1交配位之前的基因，交配位之后的基因，从父代2中按顺序选取那些没有出现过的基因。子代2也进行类似的处理。 交叉位（黑色所示为交叉位）
父代1： 1 2 3 4 5 6 7 8 父代2： 5 2 1 7 3 8 6 4 子代1： 1 2 3 4 5 7 8 6 子代2： 5 2 1 7 3 4 6 8
步骤四 确定变异规则，以下三种变异规则可任选一种。 （1）基于位置的变异：
该方法随机地产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前。如假定变异位为2和5，对整数编码的TSP问题，变异前后的变化为： 变异前：1 2 3 4 5 编译后：1 5 2 3 4 （2）基于次序的变异：
该方法随机地产生两个变异位，然后交换这两个变异位上的基因。如假定变异位为2和5，对整数编码的TSP问题，变异前后的变化为： 变异前：1 2 3 4 5 编译后：1 5 3 4 2
步骤五 根据选定的编码、遗传操作实现基本遗传算法
（1） 根据在搜索空间U上定义一个适应度函数f(x)，确定种群规模N，交叉率Pc和变异率Pm，代数T。
（2） 随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1。 （3） 计算S中每个个体的适应度f()
（4） 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。
（5） 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1。
（6） 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2。
（7） 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3。
（8） 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。 六、 示例程序 function gaTSP clear; CityNum=30;
[dislist,Clist]=tsp(CityNum);
inn=100; %初始种群大小 gnmax=1000; %最大代数 pc=0.8; %交叉概率 pm=0.8; %变异概率
%产生初始种群 for i=1:inn
s(i,:)=randperm(CityNum); end
[f,p]=objf(s,dislist); gn=1;
while gn seln=sel(s,p); %选择操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:); scnew(j+1,:)=scro(2,:); smnew(j,:)=mut(scnew(j,:),pm); %变异操作 smnew(j+1,:)=mut(scnew(j+1,:),pm); end