路径规划几种算法的比较与分析.doc-资料库

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第1页.png

第1页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第2页.png

第2页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第3页.png

第3页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第4页.png

第4页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第5页.png

第5页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第6页.png

第6页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第7页.png

第7页 / 共10页

ggggkmhny408-7152167-4744300845239994569.doc.pdf-第8页.png

第8页 / 共10页

单位代码 01 学号 100101112 分类号 TP312 密级文献综述路径规划算法的比较与分析院（系）名称信息工程学院专业名称计算机科学与技术（嵌入式方向）学生姓名指导教师冯治波王学春 2014 年 2 月 22 日

黄河科技学院毕业设计 (文献综述 ) 第 I页路径规划算法的比较与分析摘要现代的物流涉及到一个对路径合理分配的问题，而路径规划需要一种恰当的算法，分别对蚁群算法、模拟退火算法，贪婪算法的背景、原理、实现及存在优缺点做了分析与比较，其中蚁群算法是一种自组织的算法，是一种本质上并行的正反馈的算法，而且具有较强的鲁棒性；退火算法采用复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，由随机函数求得最优解；贪婪算法既可得到最优解，也可得到次优解，较依赖于具体问题的特点和贪婪策略的选取。关键词：路径规划，蚁群算法，模拟退火算法，贪婪算法

黄河科技学院毕业设计 (文献综述 ) 第 II页目录 1 绪论........................................................................................................................................1 2 蚁群算法................................................................................................................................2 2.1 蚁群算法描述.................................................................................................................2 2.2 蚁群算法的应用.............................................................................................................2 3 贪婪算法................................................................................................................................3 3.1 贪婪算法简介.................................................................................................................3 3.2 贪婪算法法组成结构.....................................................................................................3 3.3 贪婪算法存在的问题.....................................................................................................3 4 混合型模拟退火算法............................................................................................................3 4.1 混合型模拟退火算法简介.............................................................................................4 4.2 模拟退火的思想.............................................................................................................4 4.3 混合型模拟退火算法的前景..........................................................................................5 结论....................................................................................................................................6 参考文献....................................................................................................................................7

黄河科技学院毕业设计 (文献综述 ) 第 1页 1 绪论随着物流用户的不断上升和社会的进步，物流的应用也向深度和广度发展，而庞大的数据量和复杂的分配也为物流的运行相应增加了困难。然而随着科学技术的日益进步，计算机的应用越来越广泛。而且计算机具有运算快，处理能力强等特点，很自然地会应用到这一领域。而且用计算机进行分配和筛选能够快速地得到满足约束条件的可行性结果，具有效率高、质量高和节约人力的优点，这能使物流人员从繁杂盲目的规划任务中解脱出来，并对推动物流的发展起到非常重要的作用[3,4]。所以如何用计算机实现高效的、快速的路径规划工作，成为许多人研究的目标，而在这其中算法的分析与选择是相当重要的，是实现高效功能的关键。所以要对许多相关算法进行比较与分析，以此找到一种高效、快速的路径规划算法[5,]。而让计算机从多种复杂的路径规划中选择出一条最优路径来进行合理分配，达到人力，车辆以及路程安排的高效工作，这就是路径规划算法的应用与实现[6]。

黄河科技学院毕业设计 (文献综述 ) 第 2页 2 蚁群算法 2.1 蚁群算法算法描述蚁群算法，是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法，又称人工蚁群。这种算法在于优先选择信息素尝浓度大的路径，但是选择路径时又不是盲目的，而是按一定规律有意识的寻找最短路径[11]。例如，可以预先知道当前城市到下一个目的地的距离。蚁群算法能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。 2.2 蚁群算法的应用受蚁群觅食过程启发，意大利学者 MDorigo，VManiezzo 和 A Colomi 提出了一种新型的模拟进化算法即蚁群算法(antsystem，简称 AS)。AS 算法是一种正反馈和启发式算法相结合的算法，首先用来求解 TSP 问题，并获得了极大的成功，实验结果显示 AS 算法具有极强的发现较好解的能力。 (1)蚂蚁根据某一概率函数选择下一个城市，其中概率函数是城市间距离及连接边上信息素量的函数为某时刻连接边上的信息素量。 (2)除非一次周游结束，否则每只蚂蚁不允许转到已经访问过的城市。该过程由蚂蚁的禁忌表来控制，设 tabu 为蚂蚁 k 的禁忌表，则蚂蚁 k 在经过城市 f 后，就将城市 f 加入到自己的禁忌表 tabu 中，表示下一次不能再选择城市 f，用 tabu(s)表示禁忌表中第 s 个元素，也即蚂蚁所走过的第 s 个城市。 (3)完成一次周游后，蚂蚁在其访问过的每一条边上留下相应的信息素。根据以上规则，AS 算法在初始时刻将 m 只蚂蚁随机地放入到 n 个城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此时各路径上的信息素量相等。然后，每只蚂蚁根据路径上残留的信息素量和启发式信息(两城市间的距离)独立地选择下一个城市。

黄河科技学院毕业设计 (文献综述 ) 第 3页 3 贪婪算法 3.1 贪婪算法简介贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。 3.2 贪婪算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程：从问题的某一初始解出发； while 能朝给定总目标前进一步 do；求出可行解的一个解元素；由所有解元素组合成问题的一个可行解。 3.3 贪婪算法存在的问题对于贪婪算法而言，局部最优非常重要，它需要囊括所有的局部最优解然后给出一个整体解。然而对于解决类似路径规划问题的系统来说，贪婪算法的快速解答是一个较为可取的地方，但是它给出的是局部最优路径，这在所有的复杂分配中势必会造成许多不可避免的损失，所以这也是影响贪婪算法的原因。

黄河科技学院毕业设计 (文献综述 ) 第 4页 4 混合型模拟退火算法 4.1 混合型模拟退火算法简介基于概率型启发式算法(HA)的混合型模拟退火算法采用了复杂度高者优先、循环首次适应算法、贪婪法、回溯法和松弛法等多种方法，该算法所给出的路径可作为模拟退火算法的初始解[9，10]。模拟退火可对概率型启发式算法的路径规划结果做进一步优化，克服了启发式算法不具有全局收敛性的缺点。所以，混合型模拟退火算法具有启发式算法充分利用领域知识、计算量小、优化快速和模拟退火的全局收敛性，数值实验也证明了它的有效性和可行性。 4.2 模拟退火的思想模拟退火算法是基于 Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与一般组合优化问题之间的相似性[11]。模拟退火算法是在某一初温下，伴随着温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的最优解，即在局部最优解能概率性地跳出，并最终趋于全局最优。标准模拟退火算法如下： (1) 给定初始温度 t=t0，随机产生初始状态 S=S0，令 k=0； (2) repeat； (3) repeat； (4) 产生新状态 s’=Genete(s)； (5) Δf=f(s΄ )－f(s)； (6) if min{1，exp[－Δf／tk]}≥random[0，1]； (7) s=s’； (8) 直到抽样稳定准则成立； (9) 退温 tk+1=update(tk)，并令 k=k+1； (10) 直到算法终止准则成立； (11) 输出算法搜索结果。

黄河科技学院毕业设计 (文献综述 ) 第 5页 4.3 混合型模拟退火算法的前景基于知识的概率型启发式算法(HA)和模拟退火(SA)相结合的混合型算法，该算法能充分利用领域知识，计算小、优化快速，并具有模拟退火的全局收敛性。数值实验进一步表明该算法的有效性和可行性。今后可继续研究模拟退火的不同退温策略，如增加升温或重升温过程，以及采用两种退温速率策略对算法效率和性能的影响。

资料库

路径规划几种算法的比较与分析.doc

相关推荐

开发技术

热门标签

最新资料