·332· 智能系统学报 第16卷 利用轮盘算法计算当前节点到下一到达节点的 3.16m,节点2至节点3路径长度为2m,因此，方 概率： 案1路径总长度为5.16m,方案2为节点1变步 [t(t0]P.[(t)P 长跳跃至节点4再到节点5，最后由节点5单步移 j∈aw p0= [t.(t)]严·[s(t)9 (1) 动至终点3，方案2路径总长度为4.65m,方案 3为传统蚁群算法的单步长移动方式，从当前节 0. 其他 点1到节点6，再移动到节点7，再移动到节点8， 1 no=du (2) 最后再到终点3，该方案路径总长度为4.83m,方 式中：为路径（位，）上的信息素；为位置i到 案4为节点1跳跃至节点9，从节点9单步长移动 位置j的启发因子；a为蚂蚁k下一步可到达节 到节点8，最后移动到终点3，该方案路径总长度 点的集合；α表征信息素重要程度；B表征启发因 为5.16m,显然，方案2作为变步长移动方式优于 子重要程度；d是蚂蚁从位置i到位置j构建的 其他方案，变步长蚁群算法在寻路过程中，对每 路径长度。 种方案的路径长度进行评估，最终挑选出路径最 为了避免蚂蚁选择已经达到过的节点，采用 短的方案。 禁忌表记录蚂蚁k当前所达到过的位置，经过1 时刻，所有蚂蚁都已完成了一次路径规划，计算 所有蚂蚁完成的有效路径长度，筛选出最短路径 长度，同时更新各路径上的信息素，经过时间的 增长，信息素将挥发一部分： Ty =(1-p)Tij (3) 式中：P是信息素挥发系数，同时，蚂蚁也将在路 径中释放信息素： T=t+∑△ (4) k=1 式中：△是第k只蚂蚁在所经过的路径上释放的 图3步长选择 Fig.3 Step size selection 信息素，定义如下： 在图3中，节点1为起始点，节点3为终点， 1/d,边i,)在路径T上 △=0，其他 (5) 移动机器人进行路径规划时，将节点1作为父节 点，通过变步长选择策略，将下一步移动机器人 由式（⑤）可知，蚂蚁所构建的路径长度d,越 要到达的节点4作为子节点，再将节点4作为父 小，那么各路径将得到更多的信息素，在以后的 节点确定下一子节点，以此方法进行迭代，最终 迭代中该路径被其他蚂蚁选择的概率也将更大。 确定了本轮迭代后的最优路径{1,4,5,3}，结合变 2 变步长蚁群算法 步长蚁群算法的优点，移动机器人对于下一步所 选择的节点越接近于终点，则可以减少节点转折 传统蚁群算法步长选择为单步长，蚁群仅能 的次数，同时，转折点越接近于障碍物，则可以减 向相邻栅格位置移动，不能满足移动机器人实际 少无效路径，因此，为了缩短移动机器人路径长 需求，且搜索效率低及路径长度无法满足最优， 度，引入终点诱导因子中及障碍物诱导因子山，其 因此，本文提出变步长选择策略，在避开障碍物 选择概率为 的条件下，移动机器人可以从当前位置向全局地 [t)]P·[0]B 图的任何位置移动，大幅提高移动机器人搜索 k中μ· Jeat p(0= ∑PTnOF (6) 效率。 0. 其他 2.1步长选择策略 跳点的选择即步长的选择，所谓跳点就是移 ∑ty. sEd 动机器人在搜索过程中从当前节点可以到达下一 = (7) 步的节点。如图3所示。移动机器人从起点到终 点有4条路径可供选择，方案1为当前节点1跳 跃至节点2再到终点3，节点1到节点2步长为 (8)利用轮盘算法计算当前节点到下一到达节点的 概率： p k i j(t) =    [τi j(t)]α ·[ηi j(t)]β ∑ s∈ak [τis(t)]α ·[ηis(t)]β , j ∈ ak 0, 其他 (1) ηi j = 1 di j (2) τi j (i, j) ηi j i j ak k α di j 式中： 为路径 上的信息素； 为位置 到 位置 的启发因子； 为蚂蚁 下一步可到达节 点的集合； 表征信息素重要程度；β 表征启发因 子重要程度； 是蚂蚁从位置 i 到位置 j 构建的 路径长度。 k t 为了避免蚂蚁选择已经达到过的节点，采用 禁忌表记录蚂蚁 当前所达到过的位置，经过 时刻，所有蚂蚁都已完成了一次路径规划，计算 所有蚂蚁完成的有效路径长度，筛选出最短路径 长度，同时更新各路径上的信息素，经过时间的 增长，信息素将挥发一部分： τi j = (1−ρ)τi j (3) 式中： ρ 是信息素挥发系数，同时，蚂蚁也将在路 径中释放信息素： τi j = τi j + ∑m k=1 ∆τ k i j (4) ∆τ k i j 式中： 是第 k 只蚂蚁在所经过的路径上释放的 信息素，定义如下： ∆τ k i j =    1/di j, 边(i, j)在路径T k上 0, 其他 (5) 由式 (5) 可知，蚂蚁所构建的路径长度 di j 越 小，那么各路径将得到更多的信息素，在以后的 迭代中该路径被其他蚂蚁选择的概率也将更大。 2 变步长蚁群算法 传统蚁群算法步长选择为单步长，蚁群仅能 向相邻栅格位置移动，不能满足移动机器人实际 需求，且搜索效率低及路径长度无法满足最优， 因此，本文提出变步长选择策略，在避开障碍物 的条件下，移动机器人可以从当前位置向全局地 图的任何位置移动，大幅提高移动机器人搜索 效率。 2.1 步长选择策略 跳点的选择即步长的选择，所谓跳点就是移 动机器人在搜索过程中从当前节点可以到达下一 步的节点。如图 3 所示。移动机器人从起点到终 点有 4 条路径可供选择，方案 1 为当前节点 1 跳 跃至节点 2 再到终点 3，节点 1 到节点 2 步长为 3.16 m，节点 2 至节点 3 路径长度为 2 m，因此，方 案 1 路径总长度为 5.16 m，方案 2 为节点 1 变步 长跳跃至节点 4 再到节点 5，最后由节点 5 单步移 动至终点 3，方案 2 路径总长度为 4.65 m，方案 3 为传统蚁群算法的单步长移动方式，从当前节 点 1 到节点 6，再移动到节点 7，再移动到节点 8， 最后再到终点 3，该方案路径总长度为 4.83 m，方 案 4 为节点 1 跳跃至节点 9，从节点 9 单步长移动 到节点 8，最后移动到终点 3，该方案路径总长度 为 5.16 m，显然，方案 2 作为变步长移动方式优于 其他方案，变步长蚁群算法在寻路过程中，对每 种方案的路径长度进行评估，最终挑选出路径最 短的方案。 1 2 3 4 5 6 7 8 9 图 3 步长选择 Fig. 3 Step size selection ϕ µ 在图 3 中，节点 1 为起始点，节点 3 为终点， 移动机器人进行路径规划时，将节点 1 作为父节 点，通过变步长选择策略，将下一步移动机器人 要到达的节点 4 作为子节点，再将节点 4 作为父 节点确定下一子节点，以此方法进行迭代，最终 确定了本轮迭代后的最优路径{1,4,5,3}，结合变 步长蚁群算法的优点，移动机器人对于下一步所 选择的节点越接近于终点，则可以减少节点转折 的次数，同时，转折点越接近于障碍物，则可以减 少无效路径，因此，为了缩短移动机器人路径长 度，引入终点诱导因子 及障碍物诱导因子 ，其 选择概率为 p k i j(t) =    k · ϕ · µ · [τi j(t)]α ·[ηi j(t)]β ∑ s∈ak [τis(t)]α [ηis(t)]β , j ∈ ak 0, 其他 (6) ϕ= ∑ s∈ak [γis(t)]ε σε (7) µ = ∑ s∈ak [γis(t)]ω λ ω (8) ·332· 智 能 系 统 学 报 第 16 卷