遗传算法.zip常用算法模型学习资料MATLAB源程序文档教程下载

----------------------- Page 1----------------------- 基于Matlab的遗传算法解决TSP问题 基于Matlab的遗传算法解决TSP问题 报告题目：基基于于MMaattllaabb的的遗遗传传算算法法解解决决TTSSPP问问题题 说明： 说明： 说说明明：：该文包括了基于Matlab的遗传算法解决TSP问题的 基本说明，并在文后附录了实现该算法的所有源代码。此代 码经过本人的运行，没有发现错误，结果比较接近理论最优 值，虽然最优路径图有点交叉。 因为本人才疏学浅，本报告及源代码的编译耗费了本人 较多的时间与精力，特收取下载积分，还请见谅。若有什么 问题，可以私信，我们共同探讨这一问题。 希望能对需要这方面的知识的人有所帮助！ ----------------------- Page 2----------------------- 1. 1.问题介绍 11.. 旅行商问题(Traveling Salesman Problem，简称TSP)是一个经典的组合优 化问题。它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城市 出发，需要经过所有城市后，回到出发地，应如何选择行进路线，以使总行程最 短。从图论的角度看，该问题实质是在一个带权完全无向图中。找一个权值最小 的Hemilton回路。其数学描述为：设有一个城市集合其中每对城市之间的距离 d c,c ∈R+ ，求一对经过C中每个城市一次的路线 c ,c ,⋯c 使 ( i j) ( Π1 Π2 Πn) n−1 min d c ,c +d c ,c ∑ ( Πi Π i+1 ) ( Πn Π ) ( ) 1 i=1 其中Π ,Π ,⋯Π 是1，2⋯n 的一个置换。 1 2 n ( ) 2. 2.遗传算法 22.. 2.1遗传算法基本原理 2.1遗传算法基本原理 22..11遗遗传传算算法法基基本本原原理理 遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系 统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随 机化搜索算法。 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现 象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体， 利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群， 重复此过程，直到满足某种收敛指标为止。 遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问 题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器 学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会 科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适 应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计算技术 有重大影响的关键技术”。 2.2遗传算法的流程 2.2遗传算法的流程 22..22遗遗传传算算法法的的流流程程 标准的遗传算法包括群体的初始化，选择，交叉，变异操作。流程图如图1 所示，其主要步骤可描述如下： （1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。 （2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下 步骤。 ----------------------- Page 3----------------------- （3）根据适配值大小以一定方式执行选择操作。 （4）按交叉概率Pc执行交叉操作。 （5）按变异概率Pm执行变异操作。 6 2 （ ）返回步骤（ ）。 图 1 遗传算法流程图 3.TSP 3.TSP 33..TTSSPP问题的遗传算法设计与实现 3.1TSP 问题的图论描述 3.1TSP 问题的图论描述 33..11TTSSPP问问题题的的图图论论描描述述 求最短路径问题，用图论术语描述如下：在图G(V,A)中，V表示顶点集合， V=(v1,v2,…,vn)对G中的某一边(v,v )，相应的有一个数d(v,v )，如果G中不 i j i j 存在边(v,v )，则令d(v,v )无穷大，如果把d(v,v )认为是边(v,v )的长度， i j i j i j i j 则通路的长度定义为组成路的各条边的长度总和。顶点v,v 之间是否有边相连， i j 由邻接矩阵来决定。 ----------------------- Page 4----------------------- A v e G A=[ ] 邻接矩阵 ：对一个具有 个顶点， 条边的图 的邻接矩阵 a 是一 ij v×v =1 =0 vi vj 个 阶方阵，其中a ，表示v和v 邻接，a 表示 和 不相邻接（或 ij i j ij i=j）。 3.2读取txt 文件 3.2读取txt 文件 33..22读读取取ttxxtt文文件件 标准的测试文件一般都是存储 n*2 的 txt 文件，为此本人编译了一个 readfile.m的程序，方便了不同文件的使用。此程序返回的是城市的坐标矩阵pop 和城市的距离矩阵dista。 3.3初始种群 3.3初始种群 33..33初初始始种种群群 对于n个城市的问题，每个个体即每个解的长度为n ，用s行, t列的pop矩阵 表示初始群体，s表示初始群体的个数，t为n+1，矩阵的每一行的前n个元素表示 城市编码，最后一个元素表示这一路径的长度。这一算法通过start.m程序实现。 3.3适应度 3.3适应度 33..33适适应应度度 TSP 在 的求解中，可以直接用距离总和作为适应度函数。个体的路径长度越 pop 小，所得个体优越，以 矩阵的每一行最后一个元素作为个体适应值。求适应 值的qiujuli.m 程序，见附录。 3.4选择 3.4选择 33..44选选择择 选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中 个体适应度评估基础上。这里采用方法是最优保存方法。 算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个个 体。程序为select.m，见附录。 3.5交 3.5交 33..55交交叉 受贪婪算法的启发, 本文设计一种有目的使适应值上升的交叉算子。已知两 个父代a1(m11,m12,m13,...,m1n),a2(m21,m22,m23,...,m2n)，算法产生后代a1’ 和a2’的过程如下： (1) 随机产生一个城市d作为交叉起点, 把d作为a1’和a2’的起始点 (2) 分别从a1和a2中找出d的右城市dr1和dr2,并计算(d,dr1)和(d,dr2)的 距离j1和j2。 (3) 如果j1<j2,则把dr1作为a1'的第二个点，从a1和a2中删除d，并且把当 前点改为dr1.转步骤(5)。 ----------------------- Page 5----------------------- (4) 如果j1>j2,则把dr2作为a1'的第二个点，从a1和a2中删除d，并且把当 前点改为dr2。 (5) 若此时p1和p2的个数为1，结束