收藏 分销(赏)

西北工业大学算法设计实验三.doc

上传人:天**** 文档编号:10820174 上传时间:2025-06-18 格式:DOC 页数:7 大小:21.05KB 下载积分:6 金币
下载 相关
西北工业大学算法设计实验三.doc_第1页
第1页 / 共7页
西北工业大学算法设计实验三.doc_第2页
第2页 / 共7页


点击查看更多>>
资源描述
实验三:遗传算法VS回溯法 一、问题分析 回溯法可以处理货郎担问题,遗传算法也可以处理货郎担问题,回溯法和遗传算法哪个算法处理货郎担问题效率更高呢?在相同计算时间内,哪个算法得到的解更好呢? 实现遗传算法,通过随机产生10个不同规模的算例(城市数量分别为10,20,40,80,100,120,160,180,200,500,或者其它规模),比较上次实验实现的回溯法和遗传算法。 二、算法基本思想 1、回溯法 从初始状态出发,搜索其所能到达的所有“状态”, 当一条路走到尽头 ,再后退一步或若干步,从另外一种状态出发,继续搜索,直到所有的路径都搜索过。这种不断前进 、不断回溯寻找解的方法叫回溯法。 回溯法通常将问题解空间组织成“树”结构,采用系统的方法搜索解空间树,从而得到问题解。 搜索策略: 深度优先为主,也可以采用广度优先、函数优先、广度深度结合等。 避免无效搜索策略: 约束函数:在扩展结点处剪去不满足约束条件的子树 界限函数:在扩展结点处剪去得不到最优解的子树 2、遗传算法 首先针对遗传算法要有种群,个体,适应度函数,选择,交叉,变异。对于种群是由若干个个体组成,其中个体的编码可以用走过的每一个城市的路径表示。适应度函数用一个路径的代价的倒数表示。使用轮盘赌的方式进行选择下一代个体。其中轮盘赌的方式可以转换为每一个个体的适应度与种群的适应度的比例进行比较。先随机选择两个个体,根据交叉的概率进行单点交叉,将较优的交叉结果保留下来。接着在种群中选择一个个体,根据变异概率来判断是否变异,将该个体保留,根据生成的子代的个数重复上述的运算。根据指定的代数,重复上述的运算。 三、算法设计 1、回溯法 TSP问题的目的是得到一条路径,即一个解向量(X1,X2...Xn),为排列树问题。 对所有城市进行编号后,按大小顺序存储于数组path中,构造一个交换函数swap();对数组path进行遍历,判断当前城市与目标城市是否连通,若连通,通过swap函数对当前节点和目标城市进行交换,即树的节点拓展。若不连通则恢复,并进入下一次的循环,循环到叶子节点时,判断叶是否与初始节点相连,并计算代价cost是否小于当前最小代价bestc,若小于,则更新bestc,再返回上一节点,知道遍历完树中的所有节点。 核心代码: public void backtrack(int depth){//depth深度 if(depth==size){ if(map[path[depth-1]][path[depth]] != -1 && map[path[depth]][path[1]]!= -1 && cost +map[path[depth]][path[1]]<bestc){ bestp=path.clone(); bestc = cost + map[path[depth]][path[1]]; //bestc = cost +a[path[i-1]][path[i]]+a[path[i]][path[1]]; //重复计算了上一边 } }else{ for(int j =depth;j<=size;j++){ if(map[path[depth]][path[j]]!=-1){ swap(path,depth+1,j); cost +=map[path[depth]][path[depth+1]]; //System.out.println(Arrays.toString(x)+":"+cost); backtrack(depth+1); cost -=map[path[depth]][path[depth+1]]; swap(path,depth+1,j); } } } } 2、 遗传算法 先设计个体,个体里面用城市的邻接矩阵map[][]表示,当前路径path[],当前路径的代价cost,适应度值。主要方法有随机初始化当前路径,计算路径代价,适应度值的求解。 针对旅行商的问题,设计初始化种群,生成下一代种群,生成下一代种群包含选择,交叉,变异的方法。在交叉的结果会产生同一个城市重复两次,所以需要一个修复方法。 核心代码: public void solve() { int i; int k; // 初始化种群 initGroup(); // 计算初始化种群适应度,Fitness[max] for (k = 0; k < scale; k++) { fitness[k] = evaluate(oldPopulation[k]); // System.out.println(fitness[k]); } // 计算初始化种群中各个个体的累积概率,Pi[max] countRate(); System.out.println("初始种群..."); for (k = 0; k < scale; k++) { for (i = 0; i < size; i++) { System.out.print(oldPopulation[k][i] + ","); } System.out.println(); System.out.println("----" + fitness[k] + " " + Pi[k]); } for (t = 0; t < MAX_GEN; t++) { //evolution1(); evolution(); // 将新种群newGroup复制到旧种群oldGroup中,准备下一代进化 for (k = 0; k < scale; k++) { for (i = 0; i < size; i++) { oldPopulation[k][i] = newPopulation[k][i]; } } // 计算种群适应度 for (k = 0; k < scale; k++) { fitness[k] = evaluate(oldPopulation[k]); } // 计算种群中各个个体的累积概率 countRate(); } System.out.println("最后种群..."); for (k = 0; k < scale; k++) { for (i = 0; i < size; i++) { System.out.print(oldPopulation[k][i] + ","); } System.out.println(); System.out.println("---" + fitness[k] + " " + Pi[k]); } System.out.println("最佳长度出现代数:"); System.out.println(bestT); System.out.println("最佳长度"); System.out.println(bestc); System.out.println("最佳路径:"); for (i = 0; i < size; i++) { System.out.print(bestp[i] + ","); } } public static void main(String[] args) throws IOException { long startTime = System.currentTimeMillis(); //获取开始时间 System.out.println("Start...."); ycTSP yc = new ycTSP(30, 40, 1000, 0.8f, 0.9f); yc.init("C://data.txt"); yc.solve(); System.out.println(""); long endTime = System.currentTimeMillis(); //获取程序运行时间 System.out.println("程序运行时间:" + (endTime - startTime) + "ms"); } } 五、算法复杂性理论分析 1、回溯法 TSP问题是排列树问题,因而该算法的时间复杂度为O(n!)。 2、遗传算法 六、算法代码(单独文件提交) 见项目文件 七、算法复杂性实验分析 遗传算法中种群规模为30,运行代数为1000,交叉率为0.8,变异率为0,9 问题规模 回溯法 遗传算法 5 3ms 44ms 10 10ms 87ms 20 272510ms 110ms 25 -- 124ms 30 -- 141ms 40 -- 188ms 八、实验中的问题总结 回溯法: 优点:采用深度优先,可以快速的找到一组解,并依此为参照(bestc)。当搜索完解空间时便可以得最优解。 缺点:需要搜索大量的结点,工程浩大,速度慢,而且随着结点的个数不断地增加之后,解空间按照阶乘的增长速度增加,算法效率较低。 遗传算法: 遗传算法在问题规模较小的时候,不一定会比回溯法快,但在问题规模大的时候,就会有较明显的优势,虽然不一定会给出最优解,但会有一个较好的解。
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服