1 简介
TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止"早熟"收敛的问题.针对上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法.为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群.仿真实验结果证明,该算法相对于基本遗传算法的收敛速度,搜索质量和最优解输出概率方面有了明显的提高.
2 部分代码
% % %输入input： 文本文件[序号,x坐标,y坐标] %输出bestRoute： 全局最优路线 %输出bestL： 全局最优路线对应的路径长度 function [bestRoute,bestL]=SAGA_TSP(filename) %% 输入数据 input=importdata(filename); n=size(input,1); %n-城市数目 vertexs=input(:,2:3); %城市xy坐标 x=vertexs(:,1); %x坐标 y=vertexs(:,2); %y坐标 h=pdist(vertexs); dist=squareform(h); %距离矩阵 %% 遗传算法参数设置 NIND=50; %种群大小 MAXGEN=10; %迭代次数 GGAP=0.9; %代沟 Pc=0.8; %交叉概率 Pm=0.2; %变异概率 pSwap=0.2; %选择交换结构的概率 pReversion=0.5; %选择逆转结构的概率 pInsertion=1-pSwap-pReversion; %选择插入结构的概率 N=n; %染色体长度=城市数目 %% 模拟退火算法参数 MaxOutIter=300; %外层循环最大迭代次数 MaxInIter=15; %里层循环最大迭代次数 T0=0.025; %初始温度 alpha=0.99; %冷却因子 %% 种群初始化 Chrom=InitPop(NIND,N); %% 优化 while gen<=MAXGEN if minObj<=bestL bestChrom=Chrom(minIndex,:); bestL=minObj; end %% 记录每一代全局最优个体，及其总距离 BestChrom(gen,:)=bestChrom; BestL(gen,:)=bestL; %% 显示外层循环每次迭代的信全局最优路线的总距离 disp(['第' num2str(gen) '次迭代：全局最优路线总距离 = ' num2str(bestL)]); %% 画出每次迭代的全局最优路线图 figure(1); PlotRoute(bestChrom,x,y) pause(0.01); %% 计数器加1 gen=gen+1; end bestRoute=bestChrom; %全局最优路线 %% 打印每次迭代的全局最优个体的总距离变化趋势图 figure; plot(BestL,'LineWidth',1); title('优化过程') xlabel('迭代次数'); ylabel('总距离'); end3 仿真结果
4 参考文献
[1]乔彦平, 张骏. 基于一种改进遗传模拟退火算法的TSP求解[J]. 计算机仿真, 2009(5):4.
部分理论引用网络文献，若有侵权联系博主删除。