资源描述：
《遗传混合算法路径规划研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、遗传混合算法路径规划研究摘要：遗传算法和蚁群算法被广泛应用于路径规划，但遗传算法收敛速度慢，蚁群算法易陷入局部最优，在求解旅行商问题上都有一定的缺陷。本文采用遗传与蚁群混合算法，充分利用遗传算法的快速全局搜索能力和蚁群算法的智能性，用蚁群算法迭代每只蚂蚁走过的路径序列作为遗传算法的初始种群,克服随机选择的盲目性,从而提高算法的性能。仿真计算结果表明，该算法可以找到最优解或近似最优解，并提高了求解效率。关键词：遗传算法；蚁群算法；路径规划；旅行商问题引言物流与国民经济及生活的诸多领域密切相关，得到越来越多的重视，甚至被看作是企业“第三利润的
2、源泉”。因此，作为物流领域中的典型问题，旅行商问题(TravelingSalesmanProblem，TSP)的研究具有巨大的经济意义。TSP(TravelingSalesmanProblem)问题,是VRP[2]的特例，也称为巡回旅行商问题,货担郎问题。简称为TSP问题，已证明TSP问题是NP难题。。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X
3、中的元素表示对n个城市的编号)的一个排列π(X)={v1,v2,…,vn},使取最小值.式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。它是一个典型的、容易描述但却难以处理的NP完全问题。同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。所以,有效解决TSP问题在计算理论上和实际应用上都有很高的价值。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法(如遗传算法、神经X络优化法、列表寻优法、模拟退火法等)的间接比较标准。1遗传算法与蚁群算法1.1遗传算法原理遗传算法(GeicAlgorithms，G
4、A)是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息.该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题.。选择算子、交叉算子和变异算子是遗传算法的3个主要操作算子.遗传算法中包含了如下5个基本要素:①对参数进行编码;②设定初始种群大小;③设计适应度函数;④设计遗传操作;⑤设定控制参数(包括种群大小、最大进化代数、交叉率、变异率等)1.2蚁群算法原理研究表明：蚂蚁在觅食途中会留下一种外激素．蚂蚁利用外激素
5、与其他蚂蚁交流、合作，找到较短路径．经过某地的蚂蚁越多，外激素的强度越大．蚂蚁择路偏向选择外激素强度大的方向．这种跟随外激素强度前进的行为会随着经过蚂蚁的增多而加强，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强．这样就会有更多的蚂蚁选择此路径，这条路径上的外激素就会越来越强，选择此路径的蚂蚁也越来越多．直到最后，几乎所有的蚂蚁都选择这条最短的路径．这是一种正反馈现象．2.算法改进在传统解决方法中，遗传算法以其快速全局搜索能力在物流领域获得了广泛的应用。但遗传
6、算法在求解到一定程度时，往往作大量的冗余迭代，对于系统中的反馈信息利用不够，效率较低；蚁群算法也以其较强的鲁棒性和智能选择能力被广泛应用于旅行商问题。蚁群算法是通过信息素的累积和更新而收敛于最优路径,具有分布、并行、全局收敛能力，但由于蚁群算法的全局搜索能力较差，易陷入局部最优，很难得到最优解。为了克服两种算法各自的缺陷,形成优势互补。为此首先利用遗传算法的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后,充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。算法流程如图1图1遗传混合算法流程2.1遗传混合算法的具体描述如下
7、：Step1给出，放置m个蚂蚁在n个城市上。Step2把所有蚂蚁的初始城市号码放置到tabuk中，列表tabuk纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到tabuk中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径便是问题的一个解。Step3蚂蚁K从起点开始，按概率的大小选择下一个城市j,k∈{1，2，…,m},j∈allo只蚂蚁对所有城市进行遍历，将得到的结果进行优化，做为蚁群算法的初始种群。每只蚂蚁走过的路径的就代表了一条基因（a0、a1、…、am-1、am），对于这条基因表示这只蚂蚁首先从a0出发，次之访问a1、…然后依
8、次访问am-1、am最后再回到a0。（2）状态转移规则设置转移概率，为t时刻蚂蚁由i城到j城的概率。（1）式中，allo(R)M1.66GH内存512M操作系统Microsoft].西安交通大
