文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于时变适应度函数的改进粒子群算法及其在移动机器人路径规划中的应用
侵权投诉

基于时变适应度函数的改进粒子群算法及其在移动机器人路径规划中的应用

针对粒子群算法在解空间盲目搜索的缺点,提出一种基于时变适应度函数的改进粒子群路径规划算法。该算法有效地将人类搜索经验与粒子群算法相结合,利用神经网络描述环境约束和距离信息,并构造粒子的适应度函数,从而该算法在迭代过程中可以利用权值的改变合理地调整适应度函数。这样,新算法在寻优过程中能够先确定路径方向,然后逐步提高路径安全性。将该算法应用于机器人路径规划,与

第1 2期

蒲兴成,:于时变适应度函数的改进粒子群算法及其在移动机器人路径规划中的应用等基

‘ 4 5 45

定义为所有线段长度的平方之和,即对于所有路径点定义

1能量函数的构造 通常机器人活动空间假定为有限二维平面,间中的障碍空

E: L=[一 ) := (… f+( jl- + y ) 1一 ) y+(+ )] ( ) 4 1

其中表示第 i个线段的长度。整条路径的总能量定义为 E= E+ f∞E () 5

物视为位置已知的凸多边形障碍物。将工作空间中障碍物按 照机器人半径尺寸膨胀,可将机器人等效为一个点,这样可将

其中:、分别表示对每一部分的加权。 。

路径规划问题等价为约束优化问题: mn,,) i ( Y∈ Y∈R R

2改进粒子群算法在移动机器人路径规划中的应用 利用粒子群算法进行路径规划的传统思想是将 E作为粒 子的适应度函数,用粒子群算法在解空间进行寻优,利即对 E () 1

St g ( Y>0…, ( Y>0 . .: ), ,) , 1 1 g ( Y>0,,?,)>0 , ) i… g ( Y -

求极小值,最终得到的最优粒子即期望的最优路径。

算法在寻优过程中的盲目性严重降低了算法的寻优能力。 g ( Y>0…, ( y>0 ,), , ) t 1 1≤Ⅳ≤

为了克服盲目性的影响,以考虑将人类的寻优经验引入到算可

法的寻优过程中。在外部环境已知的情形下,人类的寻优经验

其中

,)目标函数, Y为即一般为路径的长度; 2,) g ( Y为第

m个障碍物对机器人的第 n个约束。能量函数便是通过 f, (

是:首先确定路径方向,在确定正确路径方向的基础上再考虑 路径安全。如果路径规划算法能利用人类经验,将很大程度地提高算法的寻优能力。 为了使算法能够利用人类经验进行寻优,算

法应具备两个 性质:

Y,n Y ( 12…,构造函数 Ff xY,: Y, )g (,) m=— Ⅳ) ((,)g( )…,, ( Y,,, )…,, )…,,)…,,) ,)… g ( Y, g ( Y, g ( Y, g ( Y ) 1

使原来的约束问题转换为无约束问题。笔者按照文献[] 4中的方法,采用神经网络法构造碰撞罚函数。为了对路径与障碍物之间的碰撞性质加以量化,一条路径的碰撞罚函数定义为各

a算法能够尽快找到正确路径方向。 )

b算法不能降低路径安全性的影响。 ) 采用固定适应度函数粒子群算法,不能同时满足以上两个性质。如果算法要满足性质 a, )则应减小路径安全对总能量

路径点的碰撞罚函数之和,而一个点的碰撞罚函数是通过它对各个障碍物的连接网络表示得到的。 假设障碍物为多边形,可以用一组线性不等式来表示,它 则在障碍物中的点必须满足所有不等式的限制, 1表示了一图个这样的神经网络。该网络的运算关系为 C= ( 1厂 l T) M

的影响力,同时增大路径长度信息的影响力。更侧重利用路径 长度评价粒子的优劣,有利于算法更快地确定正确的路径方将 向。如果要满足性质 b,不能减小路径安全性对总能量的 )则

影响力。因此,以上两性质对于固定适应度函数粒子群算法是矛盾的,采用时变适应度函数则可以解决这个矛盾,从而可以有效利用人类经验进行寻优操作。 由式 ( )知,过调整和∞可以改变 E和 E在 E 5可通

=∑ 0+0 r

oM j| m: M I m=∞ m+ ̄y Y M O m i+山肌 z i+

其中: C为顶层节点输出;为顶层节点输入;,为顶层节点 0

中所占的比重,比传统 P O算法采用固定的和。笔者相 S, 引入以下公式对和。出调整:作 0。 I 0W 9 1 一

阈值;为中间层第 m个节点的输出;为中间层第 m个节 0 点的输入;为中间层第 m个节点的阈值; m一 为第 、 m个不等式限制条件的系数。通常取激发函数为常用的型 函数,即 1

O J

一

ed+( s r一∞— n )× n∞—t t e d a

ep x (一5×(t/ x e) ) irmai r e t f n ow —∞f —

(

) 6 () 7

ed+( fs r一 ̄1ed n —t t 0一 n )× a

, )÷ (=

( 2 )

ep x (一5×(t/ x e)2 irmai r^ ) e t

其中:e为当前迭代步数; ai r ir t m x e为最大迭代步数;—nw和 t c o o∞一 o nw为当前迭代步数时碰撞罚函数的权值和路径长度函数的权值; s r和。e d为碰撞罚函数权值的初始值和终止 t一 t t o a _n 值; s r和 _ n t一 tt o a ed为长度函数权值的初始值和终止值。 假设在固定适应度函数 P O算法中, S∞取为定值,为 定值 Y。在改进 P O算法中,—tr>。s r<, S fs t,一tt Y因此改进 a a

图1计算到一个障碍物的罚函数的神经网络

无碰路径规划问题可以等效为具有两个约束条件的优化问题:一个是不与障碍物相碰,另一个是路径尽量短。基于上述关于障碍物的网络表示,两个约束条件可以加以量化,这这样,路径规划问题可变为一个极值问题。其优化的能量函数由

P O算法中路径长度对路径总能量的影响更大。利用此时刻 S的适应度函数有利于改进 P O算法挑选出路径长度更短的粒 S子作为更优秀的粒子,进而引导其他粒子向路径长度更短的方 向调整自身位置,因此改进 P O算法可以更快地确定正确的 S路径方向。在迭代过程中,采用式( ) 7更新权重的大小, 6和( ) f

路径长度和障碍物罚函数两部分组成。路径的罚函数定义为所有路径点的罚函数之和,每个点的罚函数可通过相应的网络来计算。相应于罚函数的这部分能量可以表示为 K

不断减小,不断增大,终∞=一 n, e d 最 f ed∞=∞一 n。其

中 6— n, ed>, 0 ed< 6一 n Y由于后期 C不断增大, z 0 . O 使得 E对 E 的影响力逐渐增大,用此时刻的适应度函数有利于挑选出路利

E I善 r J=I c

()径更安全的粒子作为更优秀的粒子, 3 进而引导其他粒子向路径 安全性更好的方向调整自身位置,前期忽略的安全性在后期逐 步得到弥补,最终得到最优路径。以上操作引导着粒子按照先

其中: k是障碍物的个数;Ⅳ是路径点的个数; C表示第 i路个径点对第 k障碍物的罚函数。相应于路径长

度这部分能量个

基于时变适应度函数的改进粒子群算法及其在移动机器人路径规划中的应用

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email