遗传混合算法路径规划研究

摘　要：遗传算法和蚁群算法被广泛应用于路径规划，但遗传算法收敛速度慢，蚁群算法易陷入局部最优，在求解旅行商问题上都有一定的缺陷。本文采用遗传与蚁群混合算法，充分利用遗传算法的快速全局搜索能力和蚁群算法的智能性，用蚁群算法迭代每只蚂蚁走过的路径序列作为遗传算法的初始种群,克服随机选择的盲目性,从而提高算法的性能。仿真计算结果表明，该算法可以找到最优解或近似最优解，并提高了求解效率。

关键词：遗传算法；蚁群算法；路径规划；旅行商问题

引言
　　物流与国民经济及生活的诸多领域密切相关，得到越来越多的重视，甚至被看作是企业“第三利润的源泉”。因此，作为物流领域中的典型问题，旅行商问题(Traveling Salesman Problem，TSP)的研究具有巨大的经济意义。
　　TSP(Traveling Salesman Problem)问题, 是VRP^[2]的特例，也称为巡回旅行商问题,货担郎问题。简称为TSP问题，已证明TSP问题是NP难题。。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v₁, v₂,…, v_n},使取最小值.式中的d(v_i,v_i+1)表示城市vi到城市vi+1的距离。它是一个典型的、容易描述但却难以处理的NP完全问题。同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。所以,有效解决TSP问题在计算理论上和实际应用上都有很高的价值。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法 (如遗传算法、神经网络优化法、列表寻优法、模拟退火法等)的间接比较标准。
1 遗传算法与蚁群算法
1.1 遗传算法原理
　　遗传算法(Genetic Algorithms，GA) 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息.该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题.。选择算子、交叉算子和变异算子是遗传算法的3个主要操作算子.遗传算法中包含了如下5个基本要素:①对参数进行编码;②设定初始种群大小;③设计适应度函数;④设计遗传操作;⑤设定控制参数(包括种群大小、最大进化代数、交叉率、变异率等)
1.2 蚁群算法原理
　　研究表明：蚂蚁在觅食途中会留下一种外激素．蚂蚁利用外激素与其他蚂蚁交流、合作，找到较短路径．经过某地的蚂蚁越多，外激素的强度越大．蚂蚁择路偏向选择外激素强度大的方向．这种跟随外激素强度前进的行为会随着经过蚂蚁的增多而加强，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强．这样就会有更多的蚂蚁选择此路径，这条路径上的外激素就会越来越强，选择此路径的蚂蚁也越来越多．直到最后，几乎所有的蚂蚁都选择这条最短的路径．这是一种正反馈现象．
2.算法改进
　　在传统解决方法中，遗传算法以其快速全局搜索能力在物流领域获得了广泛的应用。但遗传算法在求解到一定程度时，往往作大量的冗余迭代，对于系统中的反馈信息利用不够，效率较低；蚁群算法也以其较强的鲁棒性和智能选择能力被广泛应用于旅行商问题 。蚁群算法是通过信息素的累积和更新而收敛于最优路径,具有分布、并行、全局收敛能力，但由于蚁群算法的全局搜索能力较差，易陷入局部最优，很难得到最优解。
　　为了克服两种算法各自的缺陷,形成优势互补。为此首先利用遗传算法的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后,充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。算法流程如图1

　　图1 遗传混合算法流程
　　2.1遗传混合算法的具体描述如下：
Step1 给出，放置m个蚂蚁在n个城市上。
Step 2 把所有蚂蚁的初始城市号码放置到tabu_k中，列表tabu_k纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到tabu_k中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径便是问题的一个解。
Step 3 蚂蚁K从起点开始，按概率的大小选择下一个城市j,k∈{1，2，…,m},j∈allowedk如果蚂蚁k转移到j ,从allowed_k中删除,并将j加入到tabuk直至allowed_k= 时重新回到起点。
Step 4 是否走完所有的城市，否，则转入Step 3。
Step 5 计算,记录，更新信息素浓度，所有路径信息更新，如果,清空tabu_k则转入Step 2。
Step 6 当时，得到相对较优蚂蚁的序列。初始化种群。
Step 7 计算适应度值。
Step 8 进行遗传交叉与变异操作。
Step 9 输出得到的最短回路及其长度。
　　2.2 算法过程实现
　　（1）种群初始化
　　用蚁群算法进行初始化种群，放m只蚂蚁对所有城市进行遍历，将得到的结果进行优化，做为蚁群算法的初始种群。每只蚂蚁走过的路径的就代表了一条基因（a₀、a₁、…、a_m-1、a_m），对于这条基因表示这只蚂蚁首先从a₀出发，次之访问a₁、…然后依次访问a_m-1、a_m最后再回到a₀。
　　（2）状态转移规则设置
    转移概率，为t时刻蚂蚁由i城到j城的概率。

　　            （1）
　　式中，allowed_k表示蚂蚁k下一步允许选则的城市，表示信息启发因子，其值越大，该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性超强；β为期望启发因子，β的大小表明启发式信息受重视的程度，其值越大，蚂蚁选择离它近的城市的可能性也越大，越接近于贪心规则^［6］。为启发因子，其表达式为: ，每条路上的信息量为：　　 （2）其中
其中ρ表示路径上信息的蒸发系数，1-ρ表示信息的保留系数；表示本次循环路径(i,j)上信息的增量。表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量，如果蚂蚁k没有经过路径(i,j)，则的值为零，表示为：
　　（3）

其中，Q为常数， 表示第k只蚂蚁在本次循环中所走过的路径的长度。
　　（3）交叉算子的设计
　　首先随机地在父体中选择两杂交点,再交换杂交段,其它位置根据保持父体中城市的相对次序来确定。例如,设两父体及杂交点的A₁和A₂, A₁=(2 6 4 7 3 5 8 9 1), A₂=(4 5 2 8 1 6 7 9 3)。交换杂交段于是仍有B₁=(2 6 4 1 8 7 6 9 1),B₂=(4 5 2 7 3 5 8 9 3)。在新的城市序列中有重复的数，将杂交段中对应次序排列,即: 7-8、3-1、5-6，依此对应关系替换杂交段中重复的城市数。将B₁中(2 6 4)重复的6换为5，B₂(9 3)中重复的3换为1.。杂交后的两个体为B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交杂交。
3.仿真实验
对TSP问题仿真所用的数据库是TSPLIB典型51城市的数据。仿真平台如表1所示。
表1  仿真试验平台

3.1 遗传算法仿真
　　基本遗传算法仿真。对51城市路径优化路径优化。参数设置如下:种群:50,最大迭代数:5000,交叉概率:0.8,变异概率:0.2
　　遗传算法找到最优解的时间是95 s, ,路径长度497。
3.2 蚁群算法仿真
　　基本蚁群算法对51城市路径优化。其参数设置如下：ρ=1α=1，β=8，τ₀=0.001Q_u=100., m=51
　　基本蚁群算法找到最优解的时间是68 s, 路径长度465。
3.3遗传混合算法
　　遗传混合算法对51城市路径优化。其参数设置如下：种群:51,最大迭代数:5 000,交叉概率:0.8,变异概率:0.001;ρ=1α=1，β=8，τ₀=0.001Q_u=100，m=51；
遗传混合算法找到最优解的时间是50 s, 路径长度459。

遗传算法、基本蚁群算法、遗传混合算法对TSPLIB典型51城市的数据进行仿真,仿真结
果对比如表2所

4.结论
　　本文为了更好地解决物流领域中的旅行商问题，充分发挥遗传算法的全局搜索能力和蚁群算法的正反馈能力和协同能力，采用了遗传算法与蚁群算法混合算法进行求解，并且进行了模拟仿真。仿真结果表明，利用遗传与蚁群混合算法可以找到较好解的能力，大大提高计算效率，结果质量也较好。   
参考文献：
［1］小平,曹立明.遗传算法———理论、应用与软件实现[M].西安交通大学出版社,2002.
［2］[日]玄光男,程润伟.遗传算法与工程设计[M].科学出版社, 2000.
［3］胡小兵，黄席樾。蚁群优化算法及其应用[J]. 计算机仿真 2004，24（5）
［4］王凌。智能优化算法及其应用[M]. 北京：清华大学出版社 2001.
［5］陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社, 1996
［6］李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004，