摘  要： 将遗传算法与蚁群算法进行有机结合，并将其应用到智能机器人全局路径规划中，其目的是探索一种基于栅格划分的环境中新的路径寻优算法，研究机器人路径规划问题。首先利用遗传算法全局搜索能力强的特点，生成初始信息素分布，再利用蚁群算法正反馈机制的特点求精确解，通过两种算法的优势互补，提高系统的路径寻优能力。
关键词： 遗传算法；蚁群算法；路径寻优算法；路径规划

    移动机器人的全局路径规划可归为有约束条件下的多目标优化问题，在已知环境信息的情况下，利用有限条件规划出一条由起始点到目标点、且能避开障碍物的最优或次最优路径[1]。目前，国内外学者针对机器人全局路径规划问题做了大量研究，提出了许多算法，主要有可视图法、栅格法、人工势场法、A*搜索方法以及随机搜索法等，这些算法都存在搜索速度慢、易陷入局部最小等缺点。
    随着蚁群算法(ACO)[2]、微粒群算法(PSO)[3]、遗传算法(GA)[4]等智能算法的提出，机器人路径规划算法得到了很大的发展。通过这些方法在路径规划中的应用使得机器人更加智能，其运行路径也更加逼近理想的优化要求，但在搜索效率以及最优能力等方面仍然存在各自的缺陷。本文主要针对遗传算法进行路径规划时运算速度慢、占据存储空间大、容易陷入早熟等缺点，结合蚁群算法和遗传算法两种算法的优点提出一种新的复合型路径规划算法。
1 遗传算法的应用
    遗传算法是一种概率搜索算法，它利用某种编码技术作用于称为染色体的数串。其基本思想是模拟由这些串组成的个体的进化过程[5]。遗传算法实现主要涉及编码、初始群体的设定、适应度函数的设计以及遗传算子操作。
1.1 编码
    遗传编码对于算法的性能如搜索能力和计算效率等影响很大，本文采用路径编码方法，从起点到目标点的路径节点序列作为染色体，该染色体是不定长的。编码如下所示：



    综上所述，改进的组合优化算法主要步骤如下：
    (1)进行编码，产生初始种群；对个体适应度进行检测评估；
    (2)根据适配值大小进行选择、交叉和变异操作；
    (3)根据结果判断子代群体的进化率是否都小于设置的子代群体最小进化率，若满足则根据结果生成若干组优化解，否则重新进行个体适应度的检测评估，执行步骤(3)、步骤(4)；
    (4)根据遗传算法生成的若干组优化解，初始化蚁群算法参数，生成信息素初始分布，并将蚂蚁置于初始节点；
    (5)根据蚁群算法的状态转移概率进行下一个节点的选择；
    (6)更新蚁群算法禁忌表，并对信息素进行更新；
    (7)判断是否满足结束条件，若满足则输出结果，否则转到步骤(3)，继续执行步骤(3)~步骤(7)。
3 仿真验证
    为了验证本文所提出的静态环境下改进组合算法在机器人路径规划中的正确性和有效性，在Matlab环境下进行了仿真验证。运用概率地图方法在规划环境中得到路线图，分别采用基本蚁群算法和改进后的组合优化算法进行路线图搜索，假设机器人的规划区域为400 m×400 m的空间，其遗传操作取值为：交叉率为0.7，变异概率为0.06，种群规模为35，进化代数为5%，n为3；蚁群算法取值为：ι0=0.01，ρ=0.3，β=4，NC_max=10Q=100，m=60。仿真曲线结果如图1～图4所示，其中，图4为收敛曲线。

    仿真结果表明，蚁群算法路径长度为490.077 663 m；搜索用时9.941 37 s；路径上节点数为15；混合算法路径长度为448.825 552 m；搜索用时4.614 29 s；路径上节点数为14。经计算，混合算法路径长度比蚁群算法路径长度缩短了8.4%，用时缩短了53.5%。
    本文对复杂环境下全局路径规划搜索速度较慢的问题进行了改进。首先利用遗传算法的全局寻优特性进行大范围寻优，构成蚁群算法的初始信息素分布，再利用蚁群算法正反馈机制寻找精确解，通过信息素的不断更新最终收敛于最优路径。该组合优化算法根据遗传算法与蚁群算法各自的特点，将两者进行有机结合构成GA-ACO(Genetic Algorithm- Ant Colony Optimization)算法，并将其应用在规划路径寻优中。通过仿真验证，组合后的优化算法在路径的搜索过程中更具有方向性，显著地减少了冗余迭代的次数，在收敛速度和求解精度上均优于基本蚁群算法。
参考文献
[1] TSAI C C，HUANG H C，CHAN C K.Parallel elite genetic  algorithm and its application to global path planning for autonomous robot navigation[C].In Proceedings of IEEE international Conference on Computer Applications，Shipbuilding，2011：4813-4821.
[2] LIM K K，Yew-Soon Ong，LIM M H，et al.Hybrid ant colony algorithms for path planning in sparse graphs[J].Soft Computing，2008，12(10)：981-994.
[3] 孙波，陈卫东，席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策，2005，20(9)：1052-1060.
[4] CASTILLO O，TRUJILLO L，MELIN P.Multiple objective genetic algorithms for path-planning optimization in  autonomous mobile robots[J].Soft Computer，2007，11(3)：69-279.
[5] 李剑锋，段文军，方斌，等.基于改进遗传算法立体车库存取调度优化[J].控制工程，2010，17(5)：658-661.
[6] 邓见光，袁华强，赵跃龙.一种基于遗传—蚁群算法的网格任务调度策略[J].计算机应用研究，2011，28(12)：4485-4488.
[7] Tan Guanzheng，He Huan，SLOMAN A.Global optimal path  planning for mobile robot based on improved Dijkstra  algorithm and ant system algorithm[J].Journal of Central   South University of Technology，2006，13(1)：80-86.
[8] BRANKE J，GUNTSCH M.Solving the probabilistic TSP with ant colony optimization[J].Journal of Mathematical  Modelling and Algorithms，2004，3(4)：403-425.