多目标优化算法在冗余机械手逆解中的应用.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

第 38卷增刊 1
8月
中南大学学报(自然科学版)
J. Cent. South Univ. (Science and Technology)
Vol.38
Suppl.1
Aug.
多目标优化算法在冗余机械手逆解中的应用
李 胜, 申晓宁, 陈庆伟, 胡维礼
(南京理工大学自动化学院, 江苏南京, 210094)
摘 要: 针对带有 N个关节的冗余机械手运动学逆解问题, 提出了一种改进的多目标优化遗传算法。与传统的机
械手逆解方法相比, 所提算法不但考虑了使终端执行器精确地到达期望位置的目标, 而且同时优化了关节转动角、
机械手柔顺性、 与障碍物之间的距离 3个目标。在算法群体的初始化及子代群体的生成中, 采用了一种新型的个
体生成方式以满足约束条件的限制; 在选择算子中, 引入了防止算法早熟收敛的机制。仿真结果表明, 所提算法
能够有效地求解具有多个优化目标的机械手运动学逆解问题。
关键词: 多目标优化; 遗传算法; 冗余机械手; 运动学逆解
中图分类号: TP24
文献标识码: A
文章编号: 1672-7207( )S1−0598−05
Application of multi-objective optimal algorithm in
kinematical inverse of hyper redundant manipulator
LI Sheng, SHEN Xiao-ning, CHEN Qing-wei, HU Wei-li
(School of Automation, Nanjing University of Science and Technology, Nanjing 210094, China)
Abstract: An improved multi-objective optimization genetic algorithm was proposed for solving kinematical inverse
solutions of the redundant manipulator. Compared with the traditional methods, the proposed algorithm not only made the
end-effector reach the desired position precisely, but also optimized three objectives that were turning angles of joints,
flexibility of the manipulator and the distance to obstacles. A new method to create individuals satisfying the constraints
was proposed in the initialization of the algorithm and in generating child population, and a mechanism that prevented
premature of the algorithm was incorporated in the selection operator. Simulation results indicate that the proposed
algorithm can solve kinematical inverse solutions of the manipulator with multiple optimization objectives effectively.
Key words: multi-objective optimization; genetic algorithm; redundant manipulator; kinematic inverse solution
机械手运动学逆解问题是机械手控制中研究的基
本问题之一。当前求解机械手运动学逆解问题的方法
主要有以下 3类[1]: 代数法[2]、 几何法[3−4]、 数值迭代
法[5−6]。已有的这些方法虽然均能够较有效地解决冗余
机械手的逆解问题, 但大多数算法在求解时, 只考虑
了一个目标, 即如何使末端执行器较为精确地到达给
定位置, 而没有考虑机械手的柔顺性、 安全性等性能
指标。
为国内外学术界的一个研究热点[7]。MOEAs对问题的
多个目标同时优化, 算法运行一次便能够并行得到问
题的一组 Pareto
最优解。决策者能够依据问题的当前
需要, 从中挑选出一个或一些”足够满意”的解作为
多目标优化问题的最终解。
SPEA2[8]是瑞士学者 Zitzler在
年提出的一种
高效的多目标优化遗传算法, 它基于 Pareto支配的概
念进行适应值分配和选择操作, 并采用小生境法和精
英保留的机制。本文作者针对冗余机械手运动学逆解
多目标优化进化算法 (简称 MOEAs)近年来已成
收稿日期: −04−20
基金项目: 国家自然科学基金资助项目(60474034); 江苏省博士后科研基金资助项目(0502027B)
作者简介: 李 胜(1976−), 男, 江苏徐州人, 博士, 从事机器人系统的开发与研究
通讯作者: 李 胜, 男, 博士; 电话: ; E-mail:

增刊 1
李 胜, 等: 多目标优化算法在冗余机械手逆解中的应用
599
问题具有较强的约束条件的特点, 采用了一种新型的
个体生成方式; 并在 SPEA2的选择算子中加入了防止
算法早熟收敛的策略。与已有冗余机械手逆解算法相
比, 本文作者提出的算法在求解时, 不但考虑了使其
终端执行器精确地到达给定位置, 而且同时优化了冗
余机械手的关节转动角度、 柔顺性、 安全性等目标。
置为 Pgoal = [xgoal, ygoal ]T, 求取一组满意的θ*, 使得:
θ* = arg min[ f1(θ), f 2 (θ),..., f m (θ)]
θ
(2)
且θ*对目标位置 Pgoal = [xgoal , ygoal ]T满足冗余机械手
的运动学正解方程式(1), θ*对应的机械手位置与障碍
物无交点。
式(2)中, θ = [θ0,θ1,",θ N−1]; fi(θ)表示目标函
1 问题描述
数, j=1, 2, …, m。
考虑冗余机械手自身的一些特点和真实环境中可
能出现的一些情况, 选取如下几个性能指标作为上述
多目标优化问题的目标函数:
1.1 数学模型
本文主要研究一类平面型冗余机械手的运动学
逆解问题。此类机械手在电子制造、 生物制药和食品
加工等场合得到大量应用, 较常见的主要有三关节和
四关节平面型冗余机械手 2类。
1) 各关节转动角度 f1(θ):
N−1
∑
f1(θ) =
(θ0 −
θ
ini 2 +
[(θ
θ ) (θi−1 −θ )]
i − ini − ini 2
i i−1
(3)
)
0
i=1
为使本文提出的算法更具有通用性, 在研究时,
以图 1 所示的带有 N 个转动关节的平面型机械手为
例。
为了减少能量的消耗, 当机械手从初始位置运动
到目标位置时, 各关节连杆转动的角度应尽可能小。
2) 机械手柔顺性 f 2 (θ):
N−1
以机械手基底位置作为坐标原点, 其运动学正解
方程如下:
∑
f 2 (θ) =
ξi (θi −θ i−1) 2
(4)
i=1
其中, ξ1 =1;
⎧
N−1
∑
x =
y =
li+1 cosθi
⎪
⎪
⎨
⎧C(t) , if (θi −θ i−1)(θi−1 −θ i−2
) < 0, i=2, …, N−1
i=0
(1)
ξi = ⎨
1,
N−1
otherwise
⎪
⎩
∑
li+1 sinθi
⎪
⎩
i=0
为了便于机械手更好地工作, 应尽可能保持各相
邻关节转角的偏转方向一致, 如图 2所示, 偏转角度
q1和 q2的方向应尽量一致, 且 q1和 q2的绝对值越小
越好( qi =θi −θ i−1, i =1,2, qi ∈[−π, π] ), 以保证机
式中: [x,y]T 表示终端执行器的位置; li+1 表示各连杆
的长度, θi表示各关节的转角, θi∈[−π, π], i=0, 1, …,
N−1。
械手具有较好的柔顺性。当第i ( i = 2,", N −1)个关节
转角的偏转方向与它前一个关节转角的偏转方向不一
致时, 即 (θi −θ i−1)(θi−1 −θ i−2) < 0。
对 f2(θ)的第 i项施加惩罚因子 C(t)=t1/2, 其中 t为
算法的进化代数, 随着 t的增加, 惩罚项增大。
3) 机械手整体安全性 f3(θ):
f3(θ) =1 ds
(5)
式中: ds表示整个机械手距离所有障碍物的最短距离。
当关节转角 θ '对应的机械手位置与障碍物有交
点, 即θ '不可行时, 应对它的目标函数值进行惩罚。
记 fi,worst (i =1,2,3)为当前群体中所有可行解在目标
函数 fi上的最差值, 则对不可行解 θ ', 令
图 1带有 N个转动关节的平面型冗余机械手
Fig.1 Redundant planar manipulator with n joints
fi (θ ') = fi,worst + n× Di, i =1, 2, 3
(6)
本文冗余机械手运动学逆解问题的数学模型可
表述为: 设机械手的工作环境为二维平面, 其中存在
若干个障碍物。已知机械手各关节的初始转角为
θiini (i=0, 1, …, N-1), 要求终端执行器到达的目标位
其中: n 为θ '对应的机械手位置与障碍物交点的
个数; Di为一个适当的正数。式(6)保证了不可行解的
所有目标函数值均差于可行解。

600
中南大学学报(自然科学版)
第 38卷
的θ N−2、 θ N−1, 组成完整的个体 θ。若对某个向量
[θ0,θ1,",θ N−3], 式(1)无解, 则重新随机生成一个
N − 2维的向量, 直到式(1)有解为止。
2.2 适应值评价和选择算子
依据其相应的 3个目标函数值, 为当前群体中的
每个个体分配一个适当地反映其优劣程度的适应值,
然后从中选择出若干个适应值较优的个体, 进行遗传
算子的操作。
图 2
关节转角的偏转方向示意图
本文使用 SPEA2的适应值分配策略。设置一个外
部存储器保存算法在进化过程中搜索到的 Pareto支配
解。在为每个个体分配适应值时, 综合考虑群体和外
部存储器中支配该个体及受该个体支配的其余个体的
数目, 该方法体现了基于 Pareto支配概念的小生境机
制[9], 避免了以往基于距离的小生境法中小生境范围
(距离参数)难以确定的问题。当两个个体的适应值相
同时, 引入密度信息(第 k个最近邻居估计法[9])对它们
的优劣进行区分。
Fig.2
Schema of joint rotator’s direction
1.2
Pareto最优解
多目标优化问题的多个目标之间往往是相互矛盾
的, 因而不存在一个最优解能够使得所有的目标同时
达到最优。求解多目标优化问题一般使用 Pareto最优
解的概念。
定义 (Pareto 最优解): 假设求解最小化问题,
F = ( f1, f 2,", f m )为目标向量, X 为问题的决策空
间。如果不存在任何 x∈ X , 使得 fi (x) ≤ fi (x*),
SPEA2 的选择算子分为交配选择和环境选择两
种。交配选择采用二进制联赛法。环境选择用来确定
新一代外部存储器中保存的个体。本文对 SPEA2的环
境选择算子做了改进: 在判断某个解是否应加入外部
存储器中时, 需考察当前外部存储器中是否已存在与
之相同的解, 若存在, 则阻止该解进入外部存储器。
这样做的目的是防止某个适应值较好的个体在后代群
体中迅速繁殖和扩张, 从而避免了早熟收敛。
2.3 遗传算子
∀i∈(1,", m), 而且 f j (x) < f j (x*), ∃j ∈(1,", m),
则 x*是多目标优化问题的一个 Pareto最优解。
一个多目标优化问题一般存在多个 Pareto 最优
解, 这些解共同构成了问题的 Pareto最优解集。
2 算法描述
本文采用模拟二进制交叉算子 (SBX)和多项式变
异算子[10]。文献[10]的结果表明上述两种算子能够有
效地对实数编码的个体进行操作。
针对上述多目标优化问题, 对经典的多目标优化
遗传算法 SPEA2进行了改进。在群体的初始化及子代
群体的生成中, 采用一种新型的个体生成方式以满足
约束条件的限制; 在选择算子中 , 加入了避免外部存
储器中出现相似个体的机制, 以防止早熟收敛。
2.1 个体的编码和群体的初始化
2.4 算法的步骤
本文算法的步骤如下:
1) 初始化:生成规模为 np的初始群体 O(0), 设置
一个初始为空的外部存储器 A(0), 设进化过程中外部
存储器的大小固定为 M, 最大进化代数为 T, 计数器
t=0;
冗余机械手的运动学正解方程式 (1)是一个很强
的约束条件, 如果直接对个体 θ = [θ0,θ1,",θ N−1]进
2) 适应值评价: 对 O(t)和 A(t)中的所有个体计算
行编码并实施遗传算子的操作, 算法难以求得满足式
(1) 的 可 行 解 。 本 文 取 θ 的 前 N − 2 个 元 素
θ0,θ1,",θ N−3作为自由参数进行实数编码, 参与进化
操作; 而θ的后两个元素θ N−2、 θ N−1由θ0,θ1,",θ N−3
适应值;
3) 环境选择: 把 O(t)和 A(t)中所有的非支配解加
入 A(t+1)。如果 A(t+1)的规模超过 M, 则采用基于密
度信息的”裁减”法 [6]移除多余的非支配解; 反之,
则再选取若干个适应值最优的支配解添入 A(t+1), 直
到它保存的解的个数达到 M为止;
根据式(1)采用解析法求得。这种方法能够保证每个个
体均满足式(1)的约束。
群体的初始化采用随机生成法。设算法的群体规
模为 np, 则在[−π, π]内随机生成 np个 N − 2维的向量
[θ0,θ1,",θ N−3], 把每个向量分别代入式(1)求得相应
4) 交配选择: 采用二进制联赛法从 A(t+1)中选择
出部分较优解组成交配池;

增刊 1
李 胜, 等: 多目标优化算法在冗余机械手逆解中的应用
601
[1.8,2.6]T。机械手的工作环境中存在3个障碍物。本文
算法的运行参数为: 群体规模np与外部存储器的大小
M均取30, 交配选择中的联赛规模取为2, 最大进化代
数T取50, 交叉概率为0.9, 变异概率为1/3。
5) 遗传操作: 在交配池中, 对所有个体的前 N−2
个元素构成的参数群体进行遗传算子的操作, 把生成
的每个参数向量依次代入式 (1)求取相应的另两个元
素, 以构成完整的子代个体。若对生成的某个参数向
量, 式(1)无解, 则从交配池中随机选取两个个体重新
进行交叉和变异操作, 直到产生的参数向量代入式(1)
有解为止。把生成的子代群体作为新一代的群体
O(t+1);
本文算法只需运行一次, 便能够得到上述问题的
一组非支配解(近似 Pareto最优解)。从这组解中挑选 4
个具有代表性的解作为示例, 如图 3所示(图中实线表
示机械手的初始位置, 虚线表示终端执行器到达目标
位置时机械手所处的位置)。
6) 终止准则: 如果 t≥T, 则把 A(t)中所有非支配
解组成的集合作为问题最终的 Pareto最优解集输出,
算法终止; 否则, t=t+1, 转到第 2)步。
从图 3能够看出, 图(a)对应的解其转动角度 f1性
能很好, 柔顺性 f2 也较好, 但安全性 f3 却很差; (b)
对应的解柔顺性 f2很好, 转动角度 f1和安全性 f3一般;
(c)对应的解安全性 f3很好, 但转动角度 f1和柔顺性 f2
较差; (d)表示的解在 3个目标上的性能比较平均, 都
不是最好也不是最差。表 1分别给出了图 3各子图所
对应的解在 3个优化目标上的值。
3 示例分析
为了验证本文算法的有效性, 以带有 5个转动关
节的平面型机械手运动学逆解问题作为示例。机械手
的连杆长度分别为: l1=1.2, l2=1, l3=0.8, l4=0.6, l5=0.4,
总 长 度 为 4 ; 机 械 手 各 关 节 的 初 始 转 角 为
θ = [π 6, π 3,11π 18,5π 6,−17π 18]; 终端执行器的初
由此可见, 利用本文给出的冗余机械手多目标优
化逆解算法, 决策者能够较容易地搜索到一组多样性
较好的非支配解。这组解在给定的目标函数上各有侧
重, 决策者能够根据当前的需求, 从这组非支配解中
挑选出一个足够满意的解作为最终解, 即机械手终端
始位置为 Pini=[0.325 ,2.44 8]T, 目标位置为 Pgoal=
(a) 转动角指标 f1很好, 柔顺性指标 f2较好, 安全性指标 f3一般; (b)柔顺性指标 f2很好, 转动角指标 f1和安全性指标 f3一般;
(c) 安全性指标 f3很好, 转动角指标 f1和柔顺性指标 f2较差; (d)转动角指标 f1、 柔顺性指标 f2, 安全性指标 f3较为平均
图 3
冗余机械手逆解问题非支配解的示例
Fig.3
Example of non-dominated resolutions of redundant manipulator’s kinematical inverse

602
中南大学学报(自然科学版)
第 38卷
执行器到达目标位置时各关节的转角。与文献[9]中所
给出的同类型冗余机械手逆解算法相比, 本文给出的
算法不但考虑机械手终端执行器如何到达给定位置,
而且同时考虑了机械手自身的柔顺性与安全性等指
标, 较大程度上提高了计算结果的多样性。
[2]
Manocha D, Canny J F. Real time inverse kinematics for general
6R manipulators[C]// Proc 1992 IEEE Int'l Conf Robotics &
Automation. Los Alamitos: IEEE, 383−389.
[3] 祖 迪, 吴镇炜, 谈大龙. 一种冗余机器人逆运动学求解的
有效方法[J]. 机械工程学报, , 41(6): 71−75.
ZU Di, WU Zhen-wei, TAN Da-long. Efficent inverse kinematic
solution for redundant manipulators[J]. Chinese Journal of
Mechanical Engineering, , 41(6): 71−75.
表 1图 3中各运动学逆解的目标函数值
Table 1 Objective function’s values of every kinematical
inverse in Fig.3
[4]
Chung W J, Youm Y, Chung W K. Inverse kinematics of planar
redundant manipulators via virtual links with configuration
index[J]. Journal of Robotic Systems, 1994, 11(2): 117−128.
图形编号
转动角 f1
0.8875
4.5110
8.0061
2.8953
柔顺性 f2 安全性 f3
(a)
(b)
(c)
(d)
1.1194
0.9596
3.8958
1.3124
25.5561
6.3202
3.0388
4.7437
[5] 周友行, 何清华, 邓伯禄. 一种改进的爬山法优化求解冗余
机械手运动学逆解[J]. 机器人, , 25(1): 35−38.
Zhou You-xing, HE Qing-hua, ZHENG Bo-lu. An ameliorative
”Mountain Climbing” arithmetic to solve inverse kinematics of
redundant manipulator[J]. Robot, , 25(1): 35−38.
4 结 论
[6]
LU Bao-liang, Ito K. Regularization of inverse kinematics for
redundant manipulators using neural network inversions[C]//
Proc of IEEE International Conference on Neural Networks,
New York: IEEE, 1995, 5: 2726−2731.
针对多关节冗余机械手的逆解问题, 在 SPEA2
算法的基础上, 提出了一种适用于冗余机械手运动学
逆解问题的多目标优化遗传算法。该算法采用的新型
的个体生成方式有效地处理了冗余机械手运动学正解
方程这一较强的约束条件; 在选择算子中引入基于密
度信息的”裁减”策略, 剔除外部存储器中出现的相
同个体, 有效地防止了算法早熟收敛。仿真结果表明,
本文算法经过较少的迭代次数, 便可产生一组多样性
较好的非支配解, 供决策者根据不同的工作目标与实
际情况进行选择。由此可见, 本文算法适用于求解具
有多个(≥2)目标的冗余机械手运动学逆解问题。
[7]
[8]
Abraham A, Jain L, Goldberg R. Evolutionary multiobjective
optimization[C]// Theoretical Advances and Applications. USA:
Springer, .
Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the
strength
pareto evolutionary algorithm[C]// Evolutionary
Methods for Design, Optimization and Control with Applications
to Industrial Problems. Athens, Greece, : 95−100.
Zitzler E, Laumanns M, Bleuler S. A tutorial on evolutionary
multiobjective optimization[J]. Metaheuristics for Multiobjective
Optimisation, , 2(1): 3−37.
[9]
参考文献:
[10]
Deb K, Agrawal R B. Simulated binary crossover for continuous
search space[J]. Complex Systems, 1995, 9(2): 115−148.
[1]
Krieger C, Hosticka B J. Inverse kinematics computations with
modified CORDIC iterations[J]. IEE Proc Computer Digital
Techniques, 1996, 143(1): 87−92.
(编辑 彭超群)