资源描述：
《基于matlab的遗传算法程序设计及tsp问题求解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6卷第1期集美大学学报(自然科学版)Vol.6No.12000年3月JournalofJimeiUniversity(NaturalScience)Mar.2001[文章编号]1007-7405(2001)01-0014-06基于MATLAB的遗传算法程序设计及TSP问题求解储理才(集美大学基础教学部,福建厦门361021)[摘要]首先分析了用Matlab语言设计遗传算法程序的优越性,接着以遗传算法求解TSP问题为例,深入讨论了各个遗传算子的程序实现,并通过分析实验数据,得到各个遗传算子在搜索寻优过程中所起的作用,最后指出了用Matlab语言编程
2、同用其它高级程序语言编程的差异所在.[关键词]Matlab语言;遗传算法;程序设计;TSP[中图分类号]O224[文献标识码]A0引言当前,有关遗传算法的研究方兴未艾,由于其基础理论尚未有突破性进展,因此要想知道一个新的方案效果到底如何,一个有效途径就是利用计算机进行模拟.目前,人们大多采[1]用C语言编写这类程序.C语言作为一种高效的编程语言有它的许多优点,但对于编写遗传算法程序来说,笔者认为,Matlab语言比它更为合适.遗传算法诸多算子(如选择、交叉、变异等),都是针对所谓染色体进行的,而染色体实质上是一个向量,可将其看成一个1×n的矩阵,因
3、此这些算子实质上是一些矩阵运算,而Matlab的基本数据单元就是一个维数不加限制的矩阵,在这种编程环境下,无需用户考虑大量的有关矩阵的运算该采用何种算法等低层问题,更不必深入了解相应算法的具体细节,因而对用户算法语言方面的要求十分宽松,用它编写遗传算法程序,比用C等其它高级语言要简单、灵活、快捷,程序篇幅也将缩小许多.1TSP问题的遗传算法程序设计TSP(TravelingSalesmanProblem)问题是一个NP完全问题,近几年来,基于遗传算法求解[1～3]TSP问题的研究相当活跃,在遗传算法研究中,TSP问题已被广泛地用于评价不同的遗传操作
4、及选择机制的性能,因此,将求解TSP问题的遗传算法编制成程序进行计算机模拟有[收稿日期]2000-05-06[基金项目]福建省自然科学基金项目(F9810013).[作者简介]储理才(1969-),男,讲师,硕士,从事遗传算法与模糊系统的研究.©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net第1期储理才:基于MATLAB的遗传算法程序设计及TSP问题求解·15·重要意义.TSP问题的描述十分简单,简言之,就是寻找
5、一条最短的遍历n个城市的最短路径,或者说搜索自然数子集X={1,2,⋯,n}(X的元素表示对n个城市的编号)的一个排列π(X)={V1,V2,⋯,Vn},使n-1Td=∑d(Vi,Vi+1)+d(V1,Vn)i=1取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.笔者对遗传算法方法求解TSP问题,用Matlab语言作过实验研究.现就笔者所用的遗传算法框架,介绍其算法的程序实现过程.1.1编码与适应值函数以城市的遍历次序作为遗传算法的编码,适应度函数取为哈密顿圈的长度的倒数.在群体初始化,交叉操作和变异操作中均考虑TSP问题的合法
6、性约束条件(即对所有城市要作到不重不漏).1.2控制参数、城市位置及距离矩阵为见其名知其义,分别用lchrom、popsize、maxgen、pcross、pmutation表示染色体长度(城市数)、群体规模、遗传代数、交叉概率、变异概率.在平面上随机生成lchrom个点(数对)表示城市位置,再计算出两城市之间的距离,构成距离矩阵distmatrix,其Matlab程序为%xy是一个lchrom行,2列的矩阵,每一行表示一个城市的位置.X=[];Y=[];n=1;whilen<=1chrom,a=rand31.4+rand;X=[X;real(a)
7、];Y=[Y;imag(a)];n=n+1;end;xy=[xy];%计算任意两城市间的距离,构造距离矩阵.distmatrix=zeros(lchrom);forcountl=1∶lchrom,forcount2=1∶countl,x1=xy(count1,1);y1=xy(count1,2);x2=xy(count2,1);y2=xy(count2,2);distmatrix(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);distmatrix(count2,count1)=distmatrix(count1,
8、count2);end;end;1.3生成初始群体系统内建函数randperm(n)随机产生一个由自然数1到n组成的全排列
