多目标遗传算法在机器人路径规划中的应用
- 格式：pdf
- 大小：319.31 KB
- 文档页数：5
第３０卷第６期南京理工大学学报ｖ０１．３０Ｎｏ．６
』竺丝垦丝旦———塑些塑丝些塑堑型堕！竺堕鲤２￡墅ｉ竺些！璺鲤！呈堕塾坐Ｑ敛
望丝：呈堂
多目标遗传算法在机器人路径规划中的应用申晓宁，郭毓，陈庆伟，胡维礼
（南京理工大学自动化学院，江苏南京２１００９４）摘要：针对具有多个优化目标的机器人全局路径规划问题，提出一种改进的多目标优化遗传算法。在初始群体的生成中，采用把随机法和基于问题先验知识的启发式方法相结合的策略。以加快收敛速度；在遗传算子的设计中，引入删除、修复和平滑算子，以提高算法的搜索效率；在选择算子中，加入避免外部存储器中出现相同个体的机制，以防止早熟收敛。仿真结果表明：该文算法运行一次能够有效地产生一组近似Ｐａｒｅｔｏ最优路径解。关键词：多目标优化；遗传算法；机器人；路径规划中图分类号：ＴＰ１８文献标识码：Ａ文章编号：１００５—９８３０（２００６）０６—０６５９—０５
ＡｐｐＨｃａｔｉｏｎｏｆＭｕｌｔｉ－ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎＧｅｎｅｔｉｃ
ＡｌｇｏｒｉｔｌＩｍ
ｔｏＲｏｂｏｔＰａｔｈＰｌａｎＩｌｉｎｇ
ＳＨＥＮＸｉａｏ—ｎｉｎｇ，ＧＵＯＹｕ，ＣＨＥＮＱｉｎｇ—ｗｅｉ，ＨＵ
Ｗｅｉ—ｌｉ
（ＳｃｈｏｏｌｏｆＡｕｔｏｍａｔｉｏｎ，ＮＵＳＴ，Ｎａｎｊｉｎｇ２１００９４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｎｉｍｐｒ０Ｖｅｄｍｕｌｔｉ－ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎｇｅｎｅｔｉｃａ１９０ｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｔｏｏｐｔｉｍｉｚｅｔｈｅｐｍｂｌｅｍｏｆｍｂｏｔ９１０ｂａｌｐａｔｈｐｌａｎｎｉｎｇｗｉｔｈｍｕｌｔｉｐｌｅｏｂｊｅｃｔｉｖｅｓ．Ｔｈｅｒａｎｄｏｍａｐｐｒｏａｃｈ
ｃｏｍｂｉｎｅｄｗｉｔｈ
ｔｈｅｈｅｕｒｉｓｔｉｃｍｅｔｈｏｄｂａｓｅｄｏｎｄｏｍａｉｎｋｎｏｗｌｅｄｇｅａｒｅｅｍｐｌｏｙｅｄｉｎｔｈｅｉｎｉｔｉａ“ｚａｔｉｏｎｔｏｍｏｔｉｖａｔｅｔｈｅ
ｃｏｎＶｅ唱ｅｎｃｅｓｐｅｅｄ
ａｎｄｔｈｒｅｅｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓｎａｍｅｄｄｅｌｅｔｉｏｎ，ｒｅｐａｉｒａｎｄ
ｓｍｏｏｔｈａｒｅａｄｏｐｔｅｄｔｏｉｍ—
ｐｒｏＶｅｔｈｅｓｅａＩ℃ｈｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．ＩｎｔｈｅｓｅｌｅｃｔｉｏｎｏｐｅＬａｔｏｒ，ａｓｔｒａｔｅｇｙｔｈａｔａｖｏｉｄｓｔｈｅａｐｐｅ９ｒａｎｃｅｏｆｔｈｅｓａｍｅｉｎｄｉＶｉｄｕａｌｓｉｎｔｈｅａｒｃｈｉｖｅｉｓｉｎｃｏｒｐｏｍｔｅｄｔｏｐｒｅｖｅｎｔｐｒｅｍａｔｕｒｅ．Ｓｉｍｕｌａｔｉｏｎ
ｒｅｓｕｈｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃａｎｆｉｎｄａｓｅｔｏｆ印ｐｒｏｘｉｍａｔｅＰａｒｅｔｏ叩ｔｉｍａｌｓｏｌｕｔｉｏｎｓ
ｅｆ＿
６ｃｉｅｎｔｌｙｉｎｏｎｅｒｕｎ．
Ｋｅｙｗｏｒｄｓ：ｍｕｌｔｉ—ｏｂｊｅｃｔｉＶｅｏｐｔｉｍｉｚａｔｉｏｎ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ；ｒｏｂｏｔｓ；ｐａｔｈｐｌａｎｎｉｎｇ
机器人路径规划本质上是一个具有多个性能指标的ＮＰ完全问题，难以求得精确解。传统的图搜索法‘１｜、栅格法Ⅲ等搜索效率较低，路径优化结果也不尽理想。遗传算法是模拟生物在自然
收稿日期：２００５—０９—２６修回日期：２００６—０９—３０基金项目：国家自然科学基金（６０４７４０３４；６０１７４０１９）作者简介：申晓宁（１９８１一），女，江苏南京人，博士生，主要研究方向：进化算法、多目标优化，Ｅ．ｍａｉｌ：ｓｘｎｙｓｔｓ”＠ｓｉｎａ．ｃｏｍ．ｃｎ；通讯作者：胡维礼（１９４ｌ一），男，江苏东台人，教授，博士生导师，主要研究方向：智能控制、网路控制系统、机器人控制、数字交流伺服系统，Ｅ．ｍａｉｌ：ｈｗｌｌ００２＠ｈｏｔｍａｉｌ．ｃｏｍ。
万方数据南京理工大学学报第３０卷第６期环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它对复杂的非线性问题具有良好的适用性。近年来，国内外一些学者开始研究使用遗传算法求解路径规划问题旧。Ｊ，并取得了一定的成果。然而，多数文献为了简化问题，仅对机器人路径规划问题的单个目标进行优化【３Ｊ，或采用加权求和法把问题的多个性能指标组合成一个标量函数，使之转化为单目标优化问题进行求解Ｈ’５Ｊ。加权求和法简单直观，但它运行１次只能得到１个解，且解的值依赖于权重的选取。多目标遗传算法∞ｏ能够对多个目标同时优化，在它们之间进行协调，算法运行一次可以并行得到问题的一组Ｐａｒｅｔｏ最优解。决策者可以依据问题的当前需要，从中挑选出满意的解作为问题的最终解。因此，多目标遗传算法更适合于求解多目标优化问题。ＳＰＥＡ２【６１是一种高效的多目标优化遗传算法，它基于Ｐａｒｅｔｏ支配的概念进行适应值分配和选择操作，并采用了小生境法和精英保留的机制。本文针对机器人全局路径规划问题的特点，采用启发式方法对ｓＰＥＡ２算法的群体初始化过程和遗传算子进行了改进，并加入了防止算法早熟收敛的策略，使其能够对问题的３个性能指标（路径总长度、平滑性和安全性）同时优化。仿真实例表明了本文算法的有效性。１问题描述１．１数学模型为了便于描述，视机器人工作环境为二维空间，其中存在若干个障碍物。设机器人运动的起始点为ｓ，目标点为ｇ。机器人全局多目标路径规划问题的数学模型可表述为寻找可行路径Ｐ４＝［ｐ？ｐ；…ｐ：］，使得ＪＦＴ（Ｐ＋）＝ｍｉｎ［＾（Ｐ），厶（Ｐ），厶（Ｐ）］（１）且满足ｐ？＝ｓ，ｐ：＝ｇ（２）式中：ｐ？（Ｊ＝１，２，…，ｎ）为路径Ｐ＋的经过点，Ｚ（Ｐ）表示路径的总长度，五（Ｐ）表示路径的光滑性，六（Ｐ）表示机器人与障碍物发生碰撞的可能性（安全性能）。１．２Ｐａｍｔｏ最优解优化问题的多个目标之间往往是相互矛盾的，因而不存在一个解能够使得所有的目标同时达到最优。求解多目标优化问题一般使用Ｐａｒｅｔｏ最优解的概念。定义１（Ｐ盯ｅｔｏ最优解）：假设求解最小化问题，Ｆ＝［＾五…厶］为目标向量，ｘ为问题的决策空间。如果不存在任何ｚ∈ｘ，使得工（工）≤，（ｚ＋），Ｖｉ∈｛１，２，…，ｍ｝，并且Ｚ（工）＜．ｆ（ｚ＋），了，∈｛１，２，…，ｍ｝，则工＋是多目标优化问题的一个Ｐａｒｅｔｏ最优解。一个多目标优化问题通常存在多个Ｐａｒｅｔｏ最优解，这些解共同构成了问题的Ｐａｒｅｔｏ最优解集。机器人多目标路径规划问题即要求产生ｌ组有效的Ｐａｒｅｔｏ最优路径解。
２用于机器人全局路径规划的多目标遗传算法
２．１编码和初始群体的生成２．１．１编码每个染色体表示一条由一系列点连接而成的路径。其结构为（石１，ｙ１）＿（省２，ｙ２）＿…叶（石。，），。）染色体采用浮点数编码，长度ｎ可变。其中，（戈．，，，。）和（石。，ｙ。）分别表示起始点和终止点的坐标，（戈ｉ，ｙ从，＝２，…，ｎ一１）表示路径上除两端点以外某一中间点的坐标。这样的编码方式直观简洁，有助于算法遍历整个解空间，从而提高了搜索的精度和灵活性。２．１．２群体的初始化初始群体由两部分组成。一部分个体包含的中间点个数及其相应坐标均随机产生。由于路径的起始点和终止点已知，且当环境中不存在障碍物时，这两点的连线是长度最短、最平滑的一条路径，为了提高算法的搜索效率，借助这一信息启发式地产生另一部分初始个体。具体做法如图１所示。
图１启发式地产生部分初始群体示意图把起点ｓ到终点ｇ的连线随机平分成若干段（如图１中为３段），在第Ｊ（图１中，，＝１，２，３）段上随机取两点玛一，，勘，假设戈。＜茁，且儿＜％（戈，），
万方数据总第１５ｌ期申晓宁郭毓陈庆伟胡维礼多目标遗传算法在机器人路径规划中的应用６６１分别指相应点的坐标），在点ｐ：Ｈ与ｐ：ｉ之间随机产生一点矽（满足戈，：Ｈ＜埽＜石，：，，），。＜聊＜％），顺次连接ｐ：『＿１，ｐ，，％，添加到产生的路径中。图１中所示产生的初始路径为：Ｐ＝［ｓｐ。ｐ，ｐ：
ｐ３ｐ≥ｐ４ｐ５ｐ孑ｐ６ｇ］。２．２适应值评价与选择算子２．２．１目标函数设任意一条可行路径为Ｐ＝［ｐ。ｐ：…
ｐ。］，凡≥２，则问题的３个性能指标定义如下：（１）路径总长度一（Ｐ）ｎ—ｌ■（Ｐ）＝∑Ｉ册＋。Ｉ（３）
式中：Ｉｐ『ｐ…Ｉ表示路径段ｐ沪…的长度。（２）路径光滑性五（Ｐ）由于机器人的几何外形对其运动特性有一定的影响，因此整条行驶路径应平缓而光滑，即每一转折点处的拐角值应尽可能小。
当凡＞２时，ｎ一１∑哟＋后×们
以（Ｐ）＝丝—－－一（４）
五（Ｐ）为路径Ｐ的平均拐角值。式（４）中：仅，（Ｊ＝２，３，…，ｎ一１）表示两向量ｐ卜。ｐｆ和ｐ矽…间的夹角（０≤ａｉ＜订）；Ｉ｜｝为ａｉ中大于或等于订／２的个数，即当某一夹角大于或等于订／２时，对目标值进行惩罚。当ｎ＝２时，路径为起始点与终止点的连线。若其可行，则正（Ｐ）值为０。（３）路径安全性能六（Ｐ）为了防止机器人的某一部位与障碍物发生碰撞，应尽量使其与障碍物保持一定的安全距离。六（Ｐ）＝１／ｄ（５）式中：ｄ表示路径Ｐ距离所有障碍物的最短距离。当路径Ｐ与障碍物有交点，即Ｐ不可行时，应对它的目标函数值进行惩罚。记形（江１，２，３）为当前群体中的所有可行解在目标函数，上的最差值，则对不可行解Ｐ，令Ｚ（Ｐ）＝形＋ｎ１×Ｃｉ，ｉ＝１，２，３（６）式中，ｎ，为Ｐ中不可行段的个数；ｃｊ为惩罚因子。式（６）保证了不可行解的目标函数值差于可行解。２．２．２适应值分配与选择本文使用ｓＰＥＡ２的适应值分配策略，在为每个个体分配适应值时，综合考虑支配该个体和受该个体支配的其余个体的数目。对ｓＰＥＡ２的环境选择算子作了改进：在判断某个解是否应加入到外部存储器中时，需考察当前外部存储器中是否已存在与之相同的解，若存在，则阻止该解进入外部存储器。这样做的目的是防止某个适应值较好的个体在后代群体中迅速繁殖和扩张，以避免早熟收敛。２．３遗传算子２．３．１遗传算子的描述本文设计一类基于路径优化问题专门知识的启发式遗传算子，以提高算法的搜索效率。（１）交叉采用双点交叉。考虑到个体长度可变，在两个母体上分别随机选取两个交叉点（首点和尾点除外），交换两个体在各自交叉点之间的部分染色体。（２）变异ａ．当路径可行时，对路径上中间点的坐标依概率进行小范围调整，并保证变异后的路径仍为可行路径；ｂ．当路径不可行时，对路径上不可行段的端点坐标依概率进行较大范围调整。若有端点位于障碍物中，则使其变异到障碍物之外，否则，在两端点中随机选择一点进行变异，并保证变异后的端点不在障碍物中。（３）删除ａ．若某一路径中存在如图２（ａ）中的点ｐｉ，删除ｐｆ后，ｐｆ的前一个路径点ｐ卜。与后一个路径点ｐ…相连为可行的路径段，则删除点ｐｉ；ｂ．如果某一路径不可行，如图２（ｂ）所示，ｐｉ点所在的两条线段ｐ『－ｌｐｆ和ｐ沪…均不可行，则删除点ｐｉ，从而使不可行段个数减小。从图２（ａ）和图２（ｂ）中可以看出，删除算子使路径的长度减短。（４）修复修复算子是利用已知的机器人工作环境中的障碍物形状和位置信息而设计的智能遗传算子。如图２（ｃ）所示，路径段ｐ沪…与障碍物相交，则在障碍物周围产生点ｐ。，ｐ：，ｐ，，顺次连接点ｐｆ，ｐ。，ｐ：，ｐ，，ｐ…，则不可行段ｐ∥…被修补为环绕障碍物的可行路径段序列：ｐＪｐｌ—巾ｌｐ２—巾２ｐ３—垆３ｐｆ＋ｌ。（５）平滑平滑算子只对可行路径中最大的拐角进行操作。如图２（ｄ）所示，删除拐角仅。。的顶点ｐｉ，依次连接点ｐＨ，ｐ。，ｐ：，ｐ…，构成可行路径段序列：ｐ，一ｌｐｌ—巾ｌｐ２—巾２ｐ，＋ｌ。 万方数据
