遗传算法毕业论文
更新时间:2024-05-14 21:48:01 阅读量: 综合文库 文档下载
目录
1 引言 ............................................................................................................................................ 1 2 问题描述 .................................................................................................................................... 2 3 基于遗传算法TSP算法 ........................................................................................................... 2
3.1 基于遗传算法的TSP算法总体框架 ............................................................................ 2 3.2 算法的详细设计 ............................................................................................................. 3
3.2.1 解空间的表示方式 ................................................................................................ 3 3.2.2 种群初始化 ............................................................................................................ 4 3.2.3 适应度函数 .......................................................................................................... 4 3.2.4 选择操作 .............................................................................................................. 4 3.2.5 交叉操作 .............................................................................................................. 5 3.2.6 变异操作 .............................................................................................................. 6 3.2.7进化逆转操作 ......................................................................................................... 6 3.3 实验结果分析 ................................................................................................................... 7 4 基于模拟退火算法的TSP算法 ............................................................................................... 10
4.1 SA算法的实现过程 ........................................................................................................ 10 4.2 算法流程图 ................................................................................................................... 10 4.3模拟退火算法的实现过程 .............................................................................................. 10 4.4实验结果 .......................................................................................................................... 11 5 对两种算法的评价 .................................................................................................................... 14
5.1遗传算法优缺点 .............................................................................................................. 14 5.2 模拟退火算法的优缺点 ................................................................................................. 15 6结语 ............................................................................................................................................. 15 参考文献......................................................................................................................................... 17 附录: ............................................................................................................ 错误!未定义书签。
廊坊师范学院本科生毕业论文
论文题目:基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途
论文摘要:TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中
关键词:国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例,分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题. 本论文给出了遗传算法与模拟退火算法中各算子的实现方法,并展示出求解系统的结构和求解系统基于MATLAB的实现机制. 利用MATLAB软件编程,运行出结果,并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较,描述其优缺点,并选择最为恰当的TSP算法,实现最短旅途的最优解.
遗传算法;模拟退火算法;TSP;最短路径;
Title: TSP Algorithm Based on Genetic Algorithm or Simulated Annealing
Algorithm for Solving the Shortest Journey of 10 Cities
Abstract:TSP problem is a classic NP problem about combinatorial
optimization. This article takes a travel agency looking for the shortest trip of ten tourist cities in China-Zhuhai, Xi'an, Hangzhou, Lhasa, Beijing, Lijiang, Kunming, Chengdu, Luoyang and Weihai for instance,and solves this problem by TSP algorithm based on genetic algorithm and simulated annealing algorithm. The article gives the implementations of every operator of genetic algorithm and simulated annealing algorithm and demonstrates the architecture and the implementation mechanism of the solving system based on MATLAB. I program and operate the results by MATLAB software,and compare the results based on genetic algorithm and simulated annealing algorithm.And describe their advantages and disadvantages so that choose the most appropriate TSP algorithm to achieve the optimal solution for the shortest path.
Keywords:genetic algorithm;simulated annealing algorithm;TSP;the shortest path
1 引言
TSP问题为组合优化中的经典问题,已经证明为一NP完全问题[1],即其最坏情况下的时间复杂性随着问题规模的扩大,按指数方式增长[2],到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题,其他许多的NP完全问题可以归结为TSP问题,如邮路问题、装配线上的螺帽问题和产品的生产安排问题等,使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法.
遗传算法是一种进化算法,其基本原理是仿效生物界中的“物竞天择,适者生存”的演化法则[3].遗传算法把问题参数编码为染色体,再按照所选择的适应度函数,利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化,使适应值大的个体被保留,适应值小的个体被淘汰[4],新的群体继承了上一代的信息,又优于上一代,这样反复循环,直至满足条件,最后留下来的个体集中分布在最优解的周围,筛选出最优个体作为问题的解.
模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性[5],该算法是一种优化算法,其物理退火过程由三部分组成,分别为:加温过程、等温过程、冷却过程.其中,加温过程对应算法设定初温,等温过程对应算法的Metropolis[6]抽样过程,冷却过程对应控制参数的下降.这里能量的变化就是目标函数,要得到的最优解就是能量最低态[7].Metropolis准则是SA算法收敛于全局最优解的关键所在,Metropolis准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱.
1
2 问题描述
本案例为某旅行社为中国十大旅游城市,分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海,根据全程路径最短为目的,制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决,寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标,下表为这十个城市的位置坐标如表2-1所示.
表2-1 10个城市的位置坐标
城市编号 1 2 3 4 5 X坐标 22.31 34.37 30.29 29.66 39.95 Y坐标 113.58 108.95 120.16 91.14 116.41 城市编号 6 7 8 9 10 X坐标 26.86 24.89 30.59 34.65 37.53 Y坐标 100.23 102.83 104.07 112.46 122.13 3 基于遗传算法TSP算法
3.1 基于遗传算法的TSP算法总体框架
TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解,假设每个城市和其它任意一个城市之间都以欧氏距离[8]直接相连.遗传算法TSP问题的流程图如图2-1所示.
2
Evolutionary Computation, 2011,6 ( 12) :557~565
[17]Tsai Cheng-Fa , Tsai Chun-Wei , Yang Tzer . A Modified Mul-
tiple-Searching Method to Genetic Algorithms for Solving Travel-ing Salesman Problem[J].IEEE Transactions on Systems ,Man and Cybernetics ,2011 ,3 (10) :6~12
[18] Write A H. Genetic Algorithms for Real Parameter Optimization.
FoundationofGeneticAlgorithms.Sanmateo,GA.2010:205-218
18
附录:
遗传算法的TSP方法代码:
1 种群初始化函数InitPop的代码:
%% 初始化种群 %输入:
% NIND:种群大小
% N: 个体染色体长度(这里为城市的个数) %输出:
%初始种群
function Chrom=InitPop(NIND,N) Chrom=zeros(NIND,N);%用于存储种群 for i=1:NIND
Chrom(i,:)=randperm(N);%随机生成初始种群 end
2 种群个体的适应度函数Fitness的代码:
%% 适配值函数 %输入:
%个体的长度(TSP的距离) %输出:
%个体的适应度值
function FitnV=Fitness(len) FitnV=1./len;
3选择操作函数的Select的代码:
%% 选择操作 %输入 %Chrom 种群 %FitnV 适应度值 %GGAP:代沟 %输出
%SelCh 被选择的个体
function SelCh=Select(Chrom,FitnV,GGAP) NIND=size(Chrom,1);
NSel=max(floor(NIND*GGAP+.5),2); ChrIx=Sus(FitnV,NSel); SelCh=Chrom(ChrIx,:);
其中,函数Sus的代码为:
% 输入:
%FitnV 个体的适应度值
19
%Nsel 被选择个体的数目 % 输出:
%NewChrIx 被选择个体的索引号
function NewChrIx = Sus(FitnV,Nsel) [Nind,ans] = size(FitnV); cumfit = cumsum(FitnV);
trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)'); Mf = cumfit(:, ones(1, Nsel)); Mt = trials(:, ones(1, Nind))';
[NewChrIx, ans] = find(Mt < Mf & [ zeros(1, Nsel); Mf(1:Nind-1, :) ] <= Mt);
[ans, shuf] = sort(rand(Nsel, 1)); NewChrIx = NewChrIx(shuf);
4 交叉操作函数Recombin的代码:
%% 交叉操作 % 输入
%SelCh 被选择的个体 %Pc 交叉概率 %输出:
% SelCh 交叉后的个体
function SelCh=Recombin(SelCh,Pc) NSel=size(SelCh,1);
for i=1:2:NSel-mod(NSel,2)
if Pc>=rand %交叉概率Pc
[SelCh(i,:),SelCh(i+1,:)]=intercross(SelCh(i,:),SelCh(i+1,:)); end end %输入:
%a和b为两个待交叉的个体 %输出:
%a和b为交叉后得到的两个个体
其中intercross函数代码:
function [a,b]=intercross(a,b) L=length(a);
r1=randsrc(1,1,[1:L]); r2=randsrc(1,1,[1:L]); if r1~=r2 a0=a;b0=b; s=min([r1,r2]); e=max([r1,r2]); for i=s:e a1=a;b1=b;
20
a(i)=b0(i); b(i)=a0(i); x=find(a==a(i)); y=find(b==b(i)); i1=x(x~=i); i2=y(y~=i); if ~isempty(i1) a(i1)=a1(i); end
if ~isempty(i2) b(i2)=b1(i); end end end
5变异操作函数Mutate的代码:
%% 变异操作 %输入:
%SelCh 被选择的个体 %Pm 变异概率 %输出:
% SelCh 变异后的个体
function SelCh=Mutate(SelCh,Pm) [NSel,L]=size(SelCh); for i=1:NSel if Pm>=rand R=randperm(L);
SelCh(i,R(1:2))=SelCh(i,R(2:-1:1)); end end
6进化逆转操作函数Reverse代码:
%% 进化逆转函数 %输入
%SelCh 被选择的个体 %D 个城市的距离矩阵 %输出
%SelCh 进化逆转后的个体
function SelCh=Reverse(SelCh,D) [row,col]=size(SelCh);
ObjV=PathLength(D,SelCh); %计算路径长度 SelCh1=SelCh; for i=1:row
r1=randsrc(1,1,[1:col]);
21
r2=randsrc(1,1,[1:col]); mininverse=min([r1 r2]); maxinverse=max([r1 r2]);
SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:-1:mininverse); end
ObjV1=PathLength(D,SelCh1); %计算路径长度 index=ObjV1 SelCh(index,:)=SelCh1(index,:); 7画出所给路线的轨迹图函数DrawPath的代码: %% 画路径函数 %输入 % Chrom 待画路径 % X 各城市坐标位置 function DrawPath(Chrom,X) R=[Chrom(1,:) Chrom(1,1)]; %一个随机解(个体) figure; hold on plot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5]) plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20) for i=1:size(X,1) text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]); end A=X(R,:); row=size(A,1); for i=2:row [arrowx,arrowy] = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));%坐标转换 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]); end hold off xlabel('横坐标') ylabel('纵坐标') title('轨迹图') box on 8遗传算法的主函数代码: %遗传算法求解TSP问题(为选择操作从新设计后程序) %输入: %D 距离矩阵 %NIND 为种群个数 %X 参数是中国10个城市的坐标(初始给定) %MAXGEN 为停止代数,遗传到第MAXGEN代时程序停止,MAXGEN的具体取值视问题的规模和 22 耗费的时间而定 %m 为适值淘汰加速指数,最好取为1,2,3,4,不宜太大 %Pc 交叉概率 %Pm 变异概率 %输出: %R 为最短路径 %Rlength 为路径长度 clear clc close all X=[22.31 113.58 34.37 30.29 29.66 39.95 26.86 24.89 30.59 34.65 37.53 108.95 120.16 91.14 116.41 100.23 102.83 104.07 112.46 122.13]; D=Distanse(X); %生成距离矩阵 N=size(D,1); %城市个数 %% 遗传参数 NIND=100; %种群大小 MAXGEN=200; %最大遗传代数 Pc=0.9; %交叉概率 Pm=0.05; %变异概率 GGAP=0.9; %代沟 %% 初始化种群 Chrom=InitPop(NIND,N); %% 画出随机解的路径图 DrawPath(Chrom(1,:),X) title pause(0.0001) %% 输出随机解的路径和总距离 disp('初始种群中的一个随机值:') OutputPath(Chrom(1,:)); Rlength=PathLength(D,Chrom(1,:)); disp(['总距离:',num2str(Rlength)]); disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') %% 优化 gen=0; figure; 23 hold on;box on xlim([0,MAXGEN]) title('优化过程') xlabel('代数') ylabel('最优值') ObjV=PathLength(D,Chrom); %计算路径长度 preObjV=min(ObjV); while gen ObjV=PathLength(D,Chrom); %计算路径长度 % fprintf('%d %1.10f\\n',gen,min(ObjV)) line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001) preObjV=min(ObjV); FitnV=Fitness(ObjV); %% 选择 SelCh=Select(Chrom,FitnV,GGAP); %% 交叉操作 SelCh=Recombin(SelCh,Pc); %% 变异 SelCh=Mutate(SelCh,Pm); %% 逆转操作 SelCh=Reverse(SelCh,D); %% 重插入子代的新种群 Chrom=Reins(Chrom,SelCh,ObjV); %% 更新迭代次数 gen=gen+1 ; end %% 画出最优解的路径图 ObjV=PathLength(D,Chrom); %计算路径长度 [minObjV,minInd]=min(ObjV); DrawPath(Chrom(minInd(1),:),X) %% 输出最优解的路径和总距离 disp('最优解:') p=OutputPath(Chrom(minInd(1),:)); disp(['总距离:',num2str(ObjV(minInd(1)))]); disp('-------------------------------------------------------------') 其中用到的函数如下: 计算距离函数Distence代码: %% 计算两两城市之间的距离 %输入 a 各城市的位置坐标 %输出 D 两两城市之间的距离 function D=Distanse(a) row=size(a,1); 24 D=zeros(row,row); for i=1:row for j=i+1:row D(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5; D(j,i)=D(i,j); end end 输出路线函数OutputPath代码: %% 输出路径函数 %输入:R 路径 function p=OutputPath(R) R=[R,R(1)]; N=length(R); p=num2str(R(1)); for i=2:N p=[p,'—>',num2str(R(i))]; end disp(p) 计算个体路线长度函数PathLength代码: %% 计算各个体的路径长度 % 输入: % D 两两城市之间的距离 % Chrom 个体的轨迹 function len=PathLength(D,Chrom) [row,col]=size(D); NIND=size(Chrom,1); len=zeros(NIND,1); for i=1:NIND p=[Chrom(i,:) Chrom(i,1)]; i1=p(1:end-1); i2=p(2:end); len(i,1)=sum(D((i1-1)*col+i2)); end 重插入子代得到新种群的函数Reins代码: %% 重插入子代的新种群 %输入: %Chrom 父代的种群 %SelCh 子代种群 %ObjV 父代适应度 25 %输出 % Chrom 组合父代与子代后得到的新种群 function Chrom=Reins(Chrom,SelCh,ObjV) NIND=size(Chrom,1); NSel=size(SelCh,1); [TobjV,index]=sort(ObjV); Chrom=[Chrom(index(1:NIND-NSel),:);SelCh]; 模拟退火算法的TSP方法代码: 生成新解: function S2=NewAnswer(S1) %% 输入 % S1:当前解 %% 输出 % S2:新解 N=length(S1); S2=S1; a=round(rand(1,2)*(N-1)+1); W=S2(a(1)); S2(a(1))=S2(a(2)); S2(a(2))=W; Metropolis准则函数 function [S,R]=Metropolis(S1,S2,D,T) %% 输入 % S1: 当前解 % S2: 新解 % D: 距离矩阵(两两城市的之间的距离) % T: 当前温度 %% 输出 % S: 下一个当前解 % R: 下一个当前解的路线距离 %% R1=PathLength(D,S1); %计算路线长度 N=length(S1); %得到城市的个数 R2=PathLength(D,S2); %计算路线长度 dC=R2-R1; %计算能力之差 if dC<0 %如果能力降低 接受新路线 S=S2; R=R2; elseif exp(-dC/T)>=rand %以exp(-dC/T)概率接受新路线 S=S2; 26 R=R2; else %不接受新路线 S=S1; R=R1; End function varargout = dsxy2figxy(varargin) if length(varargin{1}) == 1 && ishandle(varargin{1}) ... && strcmp(get(varargin{1},'type'),'axes') hAx = varargin{1}; varargin = varargin(2:end); else hAx = gca; end; if length(varargin) == 1 pos = varargin{1}; else [x,y] = deal(varargin{:}); end axun = get(hAx,'Units'); set(hAx,'Units','normalized'); axpos = get(hAx,'Position'); axlim = axis(hAx); axwidth = diff(axlim(1:2)); axheight = diff(axlim(3:4)); if exist('x','var') varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1); varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2); else pos(1) = (pos(1) - axlim(1)) / axwidth * axpos(3) + axpos(1); pos(2) = (pos(2) - axlim(3)) / axheight * axpos(4) + axpos(2); pos(3) = pos(3) * axpos(3) / axwidth; pos(4) = pos(4) * axpos(4 )/ axheight; varargout{1} = pos; end set(hAx,'Units',axun) 模拟退火算法主函数: clc; clear; close all; %% tic T0=1000; % 初始温度 27
正在阅读:
遗传算法毕业论文05-14
医学遗传学知识总结03-17
雪乡02-13
二级减速器课程设计说明书05-05
华侨大学自动控制原理复习09-29
可爱的小狗小学作文06-15
第六章作业内容(答案)11-11
四年级口算题100道8587403-08
计算机二级题库03-08
- 计算机试题
- 【2012天津卷高考满分作文】鱼心人不知
- 教育心理学历年真题及答案--浙江教师资格考试
- 20180327-第六届“中金所杯”全国大学生金融知识大赛参考题库
- 洪林兴达煤矿2018年度水情水害预测预报
- 基本要道讲义
- 机电设备安装试运行异常现象分析与对策
- 《有机化学》复习资料-李月明
- 非常可乐非常MC2--非常可乐广告策划提案 - 图文
- 2011中考数学真题解析4 - 科学记数法(含答案)
- 企业人力资源管理师三级07- 09年真题及答案
- 基于单片机的光控自动窗帘控制系统设计说明书1 - 图文
- 20160802神华九江输煤皮带机安装方案001
- (共53套)新人教版一生物必修2(全册)教案汇总 word打印版
- 2014行政管理学总复习
- 中国银监会关于加强地方政府融资平台贷款风险监管的指导意见
- 民宿酒店核心竞争与研究
- 游园活动谜语大全2012
- 河南省天一大联考2016届高三英语5月阶段性测试试题(六)(A卷)
- 小型超市管理系统毕业论文详细设计4
- 毕业论文
- 遗传
- 算法
- 《电工电子》习题及答案
- 冀教版小学四年级英语上册教案新版
- 静海临时变压器电力工程施工方案.6
- 2013年航空运输地理考试题
- 管窥教育法规在教育教学过程中对教师合法权益的维护
- 最新北师大版小学一年级上册数学整理与复习教学设计及反思
- 2017-2022年中国四乙氧基硅烷行业深度调研报告(目录) - 图文
- 鲁迅小说中的女性反抗悲剧
- 电机学第11章同步发电机的基本工作原理和结构思考题与习题参考答
- 药品市场营销学练习题及答案
- 2017-2022年中国电子外包行业市场运行态势研究报告(目录) - 图
- 2015第一批六西格玛绿带结业考试试卷
- 《管理会计》试题一
- 八上U1T3重点短语
- 数码真空干燥箱
- 整体声源预测模式
- (模板)新建年产3万立方米大理石板材项目可行性研究报告
- 2013年度邯郸市科技计划项目申报指南
- 档案学概论习题
- 教师个人师德师风自查报告的范文