基于遗传蚁群算法的路径规划方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN105527965A(43)申请公布日2016.04.27(21)申请号201610005195.8(22)申请日2016.01.04(71)申请人江苏理工学院地址213000江苏省常州市中吴大道1801号(72)发明人贺乃宝陆毅高倩沈琳罗印升潘瑜刘波俞烨(74)专利代理机构南京同泽专利事务所(特殊普通合伙)32245代理人蒋全强(51)Int.Cl.G05D1/02(2006.01)G06N3/12(2006.01)权利要求书3页说明书8页附图2页(54)发明名称基于遗传蚁群算法的路径规划方法及系统(57)摘要本发明涉及一种基于遗传蚁群算法的路径规划方法及系统，本路径规划方法包括：步骤S1，将遗传算法得到的一部分优化解转化为蚁群算法的信息素初始值；步骤S2，通过蚁群算法再进行路径寻优，寻优结束后对符合条件的路径进行交叉操作，最终得到最优路径；本发明的路径规划方法及系统克服了单个蚁群算法存在的不可避免的弊端，即蚁群算法在搜索初始阶段盲目性太大，实现了蚁群和遗传算法的优势互补，缩小了路径搜索的查找范围，提高了最优路径的搜索效率。CN105527965ACN105527965A权利要求书1/3页1.一种路径规划方法，其特征在于,包括如下步骤：步骤S1，将遗传算法得到的一部分优化解转化为蚁群算法的信息素初始值；步骤S2，通过蚁群算法再进行路径寻优，寻优结束后对符合条件的路径进行交叉操作，最终得到最优路径。2.根据权利要求1所述的路径规划方法，其特征在于,所述步骤S1中将遗传算法得到的一部分优化解转化为蚁群算法的信息素初始值的方法包括：步骤S11，对环境进行建模；步骤S12，初始化遗传参数，以产生初始种群；步骤S13，设置适应度函数，计算每个种群的适应度；步骤S14，将适应度较高的前50％组解转换为蚁群算法的信息素初始值3.根据权利要求2所述的路径规划方法，其特征在于,所述步骤S2中通过蚁群算法再进行路径寻优，寻优结束后对符合条件的路径进行交叉操作，最终得到最优路径的方法包括如下步骤：步骤S21，设置蚁群规模m2，最大迭代次数Nc以及迭代次数初值u为0，并按下式初始化剩余信息素：式中：dij表示节点i和节点j之间的距离；步骤S22，每只蚂蚁按照状态转移公式选择下一节点，直到到达目标点则输出路径，若比当前迭代最优路径短，则对其更新，状态转移公式如下：式中：allowk(k＝1,2...m2)为蚂蚁k待访问节点的集合，开始时，allowk中有(m2-1)个元素，即包括除了蚂蚁k出发节点的其他所有节点，随着时间的推进，allowk中的元素逐渐减少，直至为空，即表示所有的节点均访问完毕；τij(t)表示在t时刻节点i、节点j间路径上的信息素浓度；α为信息素重要程度因子；β为启发函数重要程度因子；ηij(t)为启发函数，表示t时刻蚂蚁从节点i转移到节点j的期望程度，计算公式如下：dij表示节点i和节点j之间的距离；步骤S23，对寻优过的路径按如下公式进行全局信息素更新，同时输出本次迭代的最优路径，同时判断本次迭代最优路径与当前全局最优路径是否有除起始点和目标点以外的相同点；若有，则以该节点为交叉点，对两条路径进行交叉操作，产生新路径与全局最优路径比2CN105527965A权利要求书2/3页较，若新路径短，则更新全局最优路径；对寻优过的路径进行全局信息素更新的公式如下：τij(t+1)＝(1-ρ)τij(t)+ρΔτij(t)+Δ1τij-Δ2τij；式中，ρ表示全局信息素挥发系数，表示第k只蚂蚁在节点i与节点j连接路径上释放的信息素浓度，Δ1τij表示经过本轮最优路径的信息素增量，Δ2τij表示经过本轮最差路径的信息素增量；L1、L2分别表示本次循环中的局部最优长度、局部最差长度；k1、k2分别表示本次循环局部最优、局部最差蚂蚁个数；步骤S24，循环次数u＝u+1；步骤S25，把蚂蚁重新放回起始点，进行下一轮迭代；步骤S26，若迭代次数u>Nc，则寻优结束，输出最优路径；否则转入步骤S25。4.一种路径规划系统，其特征在于，包括：用于获得蚁群算法的信息素初始值的信息素获得模块，以及与信息素获得模块相连的最优路径获得模块。5.根据权利要求4所述的路径规划系统，其特征在于，所述信息素获得模块适于将遗传算法得到的一部分优化解转化为蚁群算法的信息素初始值；即对环境进行建模，初始化遗传参数，以产生初始种群；设置适应度函数，计算每个种群的适应度；以及将适应度较高的前50％组解转换为蚁群算法的信息素初始值6.根据权利要求5所述的路径规划系统，其特征在于，所述最优路径获得模块适于通过蚁群算法再进行路径寻优，寻优结束后对符合条件的路径进行交叉操作，最终得到最优路径；即设置蚁群规模m2