[Chrom,ObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代，得到新种群 X=bs2rv(Chrom,FieldD); gen=gen+1; %代计数器增加
%获取每代的最优解及其序号，Y为最优解,I为个体的序号 [Y,I]=min(ObjV);
trace(1:N,gen)=X(I,:); %记下每代的最优值 trace(end,gen)=Y; %记下每代的最优值 end
%% 画进化图 figure(1);
plot(1:MAXGEN,trace(end,:)); grid on
xlabel('遗传代数') ylabel('误差的变化') title('进化过程')
bestX=trace(1:end-1,end); bestErr=trace(end,end);
fprintf(['最优初始权值和阈值:\\nX=',num2str(bestX'),'\\n最小误差err=',num2str(bestErr),'\\n'])
第 4 章 基于遗传算法的TSP算法
1、案例背景
TSP (旅行商问题—Traveling Salesman Problem)，是典型的NP完全问题，即其最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能。
2、案例目录：
第4章 基于遗传算法的TSP算法 4.1 理论基础 4.1.1 遗传算法概述 4.1.2 TSP问题介绍 4.2 案例背景 4.2.1 问题描述 4.2.2解决思路及步骤 4.2.2.1 算法流程 4.2.2.2 遗传算法实现 1. 编码 2. 种群初始化 3. 适应度函数 4. 选择操作 5. 交叉操作 6. 变异操作 7. 进化逆转操作 4.3 MATLAB程序实现 4.3.1 种群初始化 4.3.2 适应度函数 4.3.3 选择操作 4.3.4 交叉操作 4.3.5 变异操作 4.3.6 进化逆转操作 4.3.7 画路线轨迹图 4.3.8 遗传算法主函数 4.3.9 结果分析 4.4 延伸阅读 4.4.1 应用扩展 4.4.2 遗传算法的改进 4.4.3 算法的局限性 4.5 参考文献
3、案例实例及结果：
本案例以14个城市为例，假定14个城市的位置坐标为：
表4.1 14个城市的位置坐标
城市编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14
X坐标 16.47 16.47 20.09 22.39 25.23 22 20.47 17.2 16.3 14.05 16.53 21.52 19.41 20.09
Y坐标 96.1 94.44 92.54 93.37 97.24 96.05 97.02 96.29 97.38 98.12 97.38 95.59 97.13 92.55
从某个城市出发访问每个城市一次且仅一次， 最后回到出发城市，如何安排才使其所走路线最短。
结果：
优化前的一个随机路线轨迹图
图4.1 随机路线图
随机路线为：
11—>7—>10—>4—>12—>9—>14—>8—>13—>5—>2—>3—>6—>1—>11 总距离：71.1144 优化后的路线图：
图4.2 最优解路线图
最优解路线:
5—>4—>3—>14—>2—>1—>10—>9—>11—>8—>13—>7—>12—>6—>5 总距离：29.3405 优化迭代过程：
图4.3 遗传算法进化过程图
4、主程序：
clear clc
close all
load CityPosition1;%个城市坐标位置 NIND=100; %种群大小 MAXGEN=200;
Pc=0.9; %交叉概率 Pm=0.05; %变异概率
GGAP=0.9; %代沟(Generation gap) D=Distanse(X); %生成距离矩阵 N=size(D,1); %(34*34) %% 初始化种群
Chrom=InitPop(NIND,N);
%% 在二维图上画出所有坐标点 % figure
% plot(X(:,1),X(:,2),'o'); %% 画出随机解的路线图 DrawPath(Chrom(1,:),X) pause(0.0001)
%% 输出随机解的路线和总距离 disp('初始种群中的一个随机值:') OutputPath(Chrom(1,:));
Rlength=PathLength(D,Chrom(1,:));