有关多目标遗传算法在优化市民出行路径中的应用毕业论文写作资料-论文写作网

简介:适合不知如何写算法路径方面的相关专业大学硕士和本科毕业论文以及关于算法路径论文开题报告范文和相关职称论文写作参考文献资料下载。

算法路径论文范文

摘要:市民出行时的路径选择可归结为多目标路径规划问题.遗传算法在解决这类问题上具有很大优势.在传统遗传算法的框架上,采用新的生成初始种群的方法,同时在适应度标定中使用压缩映像,并且改进传统的世代更新策略,从而提高了算法的性能.最后应用改进后的遗传算法进行实例计算,取得了比较满意的结果.

关键词:多目标路径规划贪心算法压缩映像早熟收敛

中图分类号:TP301 文献标识码:A 文章编号:1672-3791(2014)01(c)-0238-03

随着需求的增长,市民出行时除路程外还将其他要素纳入考虑,比如驾驶过程中的舒适度体验,行程的安全性,路段的拥挤程度等等.所以把市民出行时的路径规划问题抽象成多目标优化模型更加符合实际[1].在实际应用中,用户需要在可忍受的时间内获得一组高质量的解.因为用户最满意的不一定是算法定义的最优解,而是最符合现实情境要求的解,所以合理的做法是提供多个选择,让用户根据实际情况进行决策.上述背景对算法提出了两个基本要求,即高效性和解的多样性.在一个城市内进行最优路径搜索时,所涉及到的节点数高达几千多个,而路径规划问题是典型的NP难问题,一些精确算法,如动态规划,分枝定界,其计算量呈指数增长[2].而经典Dijkstra算法在节点数比较多时,消耗的时间和存储空间都十分巨大,所以应用也十分有限.近几年来,遗传算法在解决复杂的多目标优化问题中有成功应用,将其应用于大规模的多目标路径规划问题开始成为学者们研究的热点.相较于前面提到的几种算法,遗产算法在处理大规模路径规划问题时更具优势,更加容易实现解的多样性[3].本文在遗传算法的传统框架上进行优化,用贪心算法设计初始种群,将压缩映像引入适应度标定中并且改进了更新策略,从而将算法更好地植入模型中,提高了计算效率.

1. 模型建立

本文设定三个目标,,,分别代表最小路径长度,最小事故发生率和最小路径拥挤度,建立多目标路径规划问题的数学模型:

2. 算法设计

在60年代中期,Holland提出遗传算法,模仿达尔文的生物进化论,将适者生存的概念引入算法设计中,其主要组成部分包括初始种群的产生,个体适应度标定,选择算子,交叉算子和变异算子[4].本文对传统遗传算法进行了三处改动:(1)用贪心算法设计初始种群,(2)将压缩映像法引入适应度标定中,(3)改进更新策略.

2.1 初始种群的生成

初始种群最常用的是逐次递进法,节点从起始点开始深入,逐层递进,不满足条件时,逐步退回上一个节点,再次逐层深入直至到达终点.还有随机节点生成法,由计算机随机生成一列节点,检验是否构成有效路径.与上述两种方法的盲目式搜索相反,利用贪心算法能够在起点和终点唯一确定一条路径.

算法步骤是这样的:决定起点的下一个节点时,考察其邻节点到终点的距离,两点间的距离由坐标计算可得,选择离终点最近的节点,依此类推直至到达终点.所以建立每个节点的二维坐标信息是算法实现的重要前提,节点的坐标能简化算法设计,提高搜索效率,并且通过现有的科技手段很容易获得,既不占用过大的存储空间,也不增加数据结构的设计的难度.所以路径搜索时引入节点的坐标有很大的价值.

2.3 更新策略

设为第代父代种群,为经交叉生成的子代种群,种群规模均为.传统的遗传算法通过选择算子从选出一组染色体进入交配池,交叉生成子代,经变异后直接作为新种群继续进化[7].这种做法会流失父代中的优秀基因,从而降低收敛效率.结合精英保留策略和NSGA-Ⅱ算法中的更新策略[8～9],本文采用如下方法:合并父代和子代组成规模为的,剔除中重复的染色体,根据适应度从大到小排列,选取前条染色体进入新种群,若不足,剩余个体从中随机产生.在更新过程中,子代个体并不比父代更具被选入的先天优势,两者根据适应度大小公平竞争,获得继续进化的机会.相较经典的“精英保留”策略,它扩大了父代染色体参与竞争的数量,使更多优良个体被保留,相较NSGA-Ⅱ,它的计算量要小得多.其中删除重复个体的操作维持了种群在进化过程中的多样性,避免算法陷入早熟收敛.

2.4 几个关键算子

选择算子使用普通的论文范文赌方式,在文献[10]中有详细介绍.交叉算子采用常用的一点交叉,但如果随机选出的染色体,没有共同节点时,则搜索二者中距离最近的节点,(距离由坐标计算可得),使用前文提到的贪心算法构造连通路径,接着仿照一点交叉法完成染色体交叉,得到两条新的染色体.

设计变异算子时,首先由计算机随机生成两个节点,通过贪心算法构造这两个节点间的连通路径替代原染色体中的路段.

无论是交叉算子还是变异算子,生成的新染色体都有可能产生回路,和初始种群的产生一样,也需要消除路径中的回路.强调一点,在本文的交叉算子和变异算子中,节点的坐标信息发挥了很大的作用,笔者认为在解决多目标路径规划问题时,有必要将节点的坐标进行充分利用.

2.5 算法流程

step1:产生初始种群.

step2:计算个体适应度并判断是否满足终止条件,若满足,输出一组最优解,否则转入step3.

step3:用选择算子从中选出条染色体进入交配池.

step4:对交配池中的染色体通过交叉算子进行随机交配,产生种群.

最短路径算法:[第17集] 最短路径算法：Dijkstra算法，广度优先搜索

step5:合并,组成,用本文设计的更新策略获得条染色体.

step6:对更新后的种群应用变异算子,结果作为新种群,返回第二步.

3. 试验结果及分析

3.1 前5条最优解

利用几何画板5.0绘制出33个节点75条边的无向图,节点坐标和路段长度由几何画板获得,事故发生率和拥挤度由计算机随机产生,构造出验证遗传算法效果的算例,如图1所示.

算法在MATLAB7.0环境下编译.种群规模取40,迭代次数取200,交叉率取0.8,变异率取0.08,路程,事故发生率,拥挤程度的权重系数分别为0.4,0.3,0.3,求得从节点1到节点33的在多目标规划下的前5条最优解,结果见表1.从表1中可以看出目标之间的相互制约关系.由于本文选取的算例规模比较小,所以可以用Dijkstra算法获得算例在仅考虑一个目标下的精确的最优值,见表1中最后一行.从表中可以发现没有一条路径能同时取得单目标下最小值,这证明求解多目标优化模型的关键在于协调和平衡几个目标.值得一提的是,为考察本文使用的更新策略的作用,将传统方法即把交叉变异后的种群直接作为进化的新种群的方式和改进后的方法对比,经试验发现,用传统方法得到的最后一代几乎全是路径1,而后者却得到了超过30条互不相同的路径.实验结果表明,该遗传算法在解决解的多样性问题上效果很好,扩大了用户决策的空间.(如表1)

3.2 解的收敛性

图2是迭代200次中种群的路程平均值变化曲线.从图中可以看出,最初种群的路程平均值比较大,经过50代后开始逐渐趋向平稳,在100代时因变异算子产生小的波动,最后稳定在18.7左右.曲线表明算法是快速收敛的.

3.3 解的有效性

我们知道在多目标路径规划问题中,绝大多数情况下无法找到一条路径同时取得三个目标的最优值.现在假定这条路径存在,那么非劣性解越接近它,表明解的质量越好[11].基于这种思想,定义任意一条有效路径到虚拟的最优路径的距离,记这条虚拟路径的三个目标函数值为,,,任意有效路径函数值为,,.计算两者距离的公式如下:

公式(7)给出了比较两条路径优劣的指标.那么用产生初始种群的算法随机生成一条有效路径,挑战表中的5条最优解,如果最优路径到虚拟路径的距离小于随机路径到虚拟路径的距离,则称这个最优解是成功的,否则失败.试验200次,5条最优路径的成功率分别为100％,98％,99.5％,99％,91％.为避免算法的偶然性,对算例求解10次,其最优解的成功率均在90％以上,说明这5条最优解的性质都不错,证明遗传算法是有效的.

4. 结语

本文采用遗传算法解决大规模的多目标路径规划,并对传统的遗传算法进行改进,使之具备更好的计算性能.在具体试验中,该算法体现了良好的收敛性和解的多样性,同时保证了最优解的有效性.为缓解种群陷入早熟收敛的压力,本文改进了传统的更新策略,但尚不明确它是否会带来意想不到的副作用.遗传算法的研究仍将集中在两方面:一是改进交叉和变异算子,防止种群早熟或陷入局部最优解[12],二是提高算法的搜索能力,减少求解时间.

参考文献

[1]潘斌斌.多目标路径规划问题的算法综述[J].重庆工商大学学报:自然科学版,2012,29(5):78-84.

[2]郎茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报,2002,15(7):77-79.

[3]梁晓辉,吴威,赵沁平.大规模真实地形数据中的全局路径规划方法—— 基于遗传算法的研究[J].计算机研究与发展,2002,39(3):301-306.

[4]阮宏博.基于遗传算法的工程多目标优化研究[D].山东:大连理工大学土木工程系,2007.

[5]刘旭红,张国英,刘玉树,等.基于多目标遗传算法的路径规划[J].北京理工大学学报,2005,25(7):613-616.

[6]宋晓秋.模糊数学原理与方法[M].徐州:中国矿业大学出版社,2004.

[7]肖晓伟,肖迪,林锦国.多目标优化问题的研究概述[J].计算机应用研究,2011,28(3):805-808,827.

[8]刘旭红,刘玉树,张国英,等.多目标优化算法NSGA-II的改进[J].计算机工程与应用,2005(15):76-78.

[9]关志华.非支配排序遗传算法(NSGA)算子分析[J].管理工程学报,2004(1):56-60.

[10]井祥鹤,魏冬峰,周献中.运输方式选择多目标优化问题的混合遗传算法[J].计算机工程与应用,2008,44(6):210-212,224.

[11]毕娜.基于多目标遗传算法的配送路径问题研究[D].浙江:浙江工业大学机械自动化系,2007.