一种基于并行化混沌蜂群算法的机械臂逆运动学求解方法

摘要

本发明公开了一种基于并行化混沌蜂群算法的机械臂逆运动学求解方法，包括步骤：1)初始化阶段，利用混沌映射初始化食物源群体并将整个群体划分成多个相互独立的子群并行演化；2)雇佣蜂阶段，引入控制参数调整雇佣蜂搜索新食物源时的搜索步伐与参数更改频率；3)基于适应度值计算出每个食物源的被选概率；4)观察蜂阶段，观察蜂以轮盘赌法选择一个食物源进行跟踪；5)侦查蜂阶段，侦查蜂搜索新的食物源替换掉花蜜匮乏的食物源；6)信息交流阶段，一个子群的较差食物源替换成另外一个子群的较优食物源。本发明方法改善了基本人工蜂群算法在求解机械臂逆运动学问题时的性能，具有较快的收敛速度和较强的全局搜索能力。

说明书

技术领域

本发明涉及机器人逆运动学的技术领域，尤其是指一种基于并行化混沌蜂群算法的机械臂逆运动学求解方法。

背景技术

已知机械臂末端执行器的期望位姿，要求计算出满足期望要求的关节角，这类问题被称为机械臂的逆运动学问题。求解机械臂逆运动学的方法分成两大类：封闭解法和数值解法。封闭解法求解速度快，容易确定所有可能解，但适用范围小,只有结构参数很特殊的机械臂才存在封闭解(解析解)。数值解法适用范围广，但其迭代性质导致求解速度慢，无法满足实时控制的要求。所以寻找一种通用、高效的求解逆运动学问题的数值解法具有重要的实际意义。近年来，群智能算法被广泛应用于逆运动学问题中，例如粒子群算法、和声算法、人工蜂群算法等，这些算法能够在合理的时间内得出较好的数值解。

人工蜂群算法(Artificial Bee Colony Algorithm,ABC)是2005年由Karaboga等提出来的一种新颖的启发式搜索算法，是集群智能的一个具体应用。它模仿蜂群觅食的行为，通过人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，具有较快的收敛速度。该算法由于控制参数较少、易于实现和优良的求解性能受到关注并广泛应用于各种实际优化问题中。

在ABC算法中，搜索新食物源时参数改动的频率不变，即仅更改当前食物源的一个参数产生新食物源，导致算法收敛速度较慢。同时，搜索步伐也不变，即参数只在固定范围内被改动，算法无法根据运行情况灵活调整步伐，易陷入局部最优。为此，Karaboga等人提出了一种改进的人工蜂群算法，该算法引入更改率MR(modified Rate(Modified Rate)和缩放因子SF(scaling factor)对参数更改的频率和搜索步伐施加影响。初始食物源群体的分布对基于群体的搜索算法是至关重要的，在没有任何先验知识的情况下，随机地生成初始群体是最普遍的一种方法，然而该方法并不能帮助搜索算法高效地获取领域知识，致使全局搜索能力不佳。为此，Sharma等提出一种使用Halton点集生成初始食物源的新算法，称为H-ABC。受混沌系统的启发，Alatas等提出一种使用混沌映射优化初始食物源分布的人工蜂群算法，称为CABC(Chaotic ABC)。为了缩减人工蜂群算法求解复杂优化问题的时间，提升收敛速度，Luo等向ABC算法中融入并行化计算的思想并提出一种子群间的交流机制。

以上这些改进人工蜂群算法虽然改善了ABC算法的收敛速度和全局搜索能力，但相比其他群智能算法，例如粒子群算法，仍然在收敛速度或全局搜索能力上有差距，无法满足机械臂实时控制的要求。

发明内容

本发明的目的在于克服现有技术的不足，提供一种基于并行化混沌蜂群算法的机械臂逆运动学求解方法CPABC(Chaotic and Parallelized Artificial Bee Colony)，该方法考虑了在求解逆运动学问题时具有较快收敛速度和较强全局搜索能力的要求，克服了ABC算法及其改进算法并不能很好地满足机械臂实时控制并求得较优逆解的问题。

为实现上述目的，本发明所提供的技术方案为：一种基于并行化混沌蜂群算法的机械臂逆运动学求解方法，包括以下步骤：

1)初始化阶段：利用混沌映射初始化食物源群体并将整个群体划分成多个相互独立的子群并行演化；

2)雇佣蜂阶段：引入控制参数调整雇佣蜂搜索新食物源时的搜索步伐与参数更改频率；

3)基于适应度值计算出每个食物源的被选概率；

4)观察蜂阶段：观察蜂以轮盘赌法选择一个食物源进行跟踪；

5)侦查蜂阶段：侦查蜂搜索新的食物源替换掉花蜜匮乏的食物源；

6)信息交流阶段：一个子群的较差食物源替换成另外一个子群的较优食物源。

在步骤1)中，所述的初始化阶段，具体如下：

混沌是非线性系统中特有并普遍存在的一种现象，看似混乱却有精致的内在结构。随机性、遍历性和规律性是混沌最典型的特点，使其能按照自身的某一规律不重复地遍历给定范围内的所有状态。将混沌思想引入到人工蜂群算法中，可在一定程度上防止算法陷入局部最优并加快收敛速度。其中，采用如下的一维Logistic映射初始化食物源：

X_n+1＝μX_n(1-X_n)n＝0,1,...,K

式中，X_n∈(0,1)，μ为Logistic参数，K是混沌序列的迭代次数。生成第i个初始食物源m_i的过程如下：

a)设置混沌序列的迭代次数K。

b)随机生成混沌序列的初始向量ch₀＝(ch₀₁,ch₀₂,...,ch_0D)，其中D为食物源的参数数量(解空间的维数)。

c)根据混沌方程循环迭代K次，产生混沌向量ch_K＝(ch_K1,ch_K2,...,ch_KD)。

d)产生初始食物源m_i＝(m_i1,m_i2,...,m_iD)，其中：

m_ij＝m_j^min+ch_Kj(m_j^max-m_j^min),i＝1,2,...,SN>

其中，m_ij表示第i个食物源的第j个参数，m_j^max和m_j^min分别代表第j个参数的最大与最小值，SN代表食物源数量，D代表解空间的维数。同时，每一个食物源都有一个被初始化为0的计数器trial表示尝试搜索的次数。初始食物源会在随后的阶段被雇佣蜂、观察蜂、侦查蜂循环迭代地探索，直至达到最大迭代次数MCN并得到最佳食物源。每一个食物源只能由一个雇佣蜂或观察蜂负责采集，即雇佣蜂、观察蜂和食物源三者的数量相等。

将初始食物源群体划分成P个子群，每个子群单独地演化。各子群每迭代R次就相互交流信息。当所有子群都演化完毕后，对比各子群中最佳食物源并得到整个群体的最佳食物源。

在步骤2)中，所述的雇佣蜂阶段，具体如下：

新算法引入控制参数更改率MR(modified rate)，雇佣蜂围绕食物源m_i搜索新食物源v_i时，针对m_i的第j个参数生成随机数R_ij∈(0,1)，R_ij与MR比较后按下式生成v_ij：

式中，m_k是随机选择的第k(k不等于i)个食物源，Ф_ij表示参数的更改频率，在ABC中是区间[-1,1]之间的随机数，而在新算法中是区间[-SF,SF]之间的随机数。缩放因子SF(scaling>

式中，Ф_m表示m次迭代搜索后的较优食物源与总食物源的数量比值，如果Ф_m小于1/5，SF减小使算法的开发能力提高。如果Ф_m大于1/5，SF增大使算法的搜索能力提高。

雇佣蜂依据代价函数对新食物源v_i的质量进行评价，如果v_i的质量高于m_i，则v_i取代m_i，trial被重置为0。如果v_i的质量小于等于m_i，trial累加1。如果v_ij超过了第j个参数的取值范围，则重新设定v_ij为合理范围内的有效值。然后，按照如下公式得出新食物源v_i的适应度值fitness_i：

式中，cost_i表示第i个食物源的质量。

在步骤3)中，所述的基于适应度值计算出每个食物源的被选概率，具体如下：

雇佣蜂将食物源的适应度值带回蜂巢与观察蜂共享。算法基于适应度值计算出第i个食物源的被选概率p_i，公式如下：

在步骤4)中，所述的观察蜂阶段，具体如下：

观察蜂根据被选概率p_i以轮盘赌选择法对较优食物源进行跟踪，跟踪过程中观察蜂执行和雇佣蜂阶段相同的任务。所有观察蜂执行完毕后，记录下当前迭代次数下适应度值最高的食物源。

在步骤5)中，所述的侦查蜂阶段，具体如下：

侦查蜂检查每一个食物源的计数器值trial，如果trial大于阈值limit，表明食物源及其周边花蜜匮乏并将其丢弃，由侦查蜂按照初始化阶段的方式搜索新的食物源。如果有多个食物源的trial大于limit，就将其中trial最大的食物源丢弃。

在步骤6)中，所述的信息交流阶段，具体如下：

所有子群每迭代R次就相互交流信息，让子群group_i中花蜜最丰富(适应度值最高)的k个食物源替换掉子群group_{(i+1)mod>中花蜜最匮乏的k个食物源，其中i表示子群编号，p表示子群数量。信息交流完成后，各子群从步骤2)开始继续并行独立地演化。}

本发明与现有技术相比，具有如下优点与有益效果：

1、本发明利用混沌映射初始化食物源群体，混沌映射对初始条件具有极端敏感的依赖性，即使混沌序列初始向量ch₀中的D个参数之间非常相近，在一维Logistic混沌映射的迭代作用下，最终向量ch_k中的各参数都可能分开，这无疑提高了初始食物源群体的多样性，在一定程度上避免了算法陷入局部最优，并加快算法的收敛速度。

2、本发明引入控制参数调整搜索步伐与参数更改频率，因为ABC、CABC和PABC-RC算法在搜索新食物源时参数的改动频率与搜索步伐都固定不变，即只在固定范围内更改当前食物源的一个参数产生新食物源，在雇佣蜂与观察蜂阶段影响了新食物源的分布，导致全局探索能力不佳，容易陷入局部最优。而CPABC使得当前食物源的每一个参数都有机会被更改，同时更改幅度会根据当前算法的求解性能进行适当调整，这样全局探索能力与局部开发能力达到一个动态平衡的状态，算法可以很好地发挥这两类能力，在解空间内能找到更优的解。

3、本发明将搜索食物源的蜂群划分成多个独立的子群并行演化，CPABC实质上是在多处理机上并行执行多个ABC算法，使算法的求解速度得到提高。同时子群间的交流机制让差解被抛弃，只围绕本子群和其他子群的优解继续搜索，提升了算法的全局收敛速度。

附图说明

图1a为本实施例中PUMA560的运动学模型之一。

图1b为本实施例中PUMA560的运动学模型之二。

图2为本实施例中单个子群演化的简易流程图。

图3为本实施例中5种算法分别求解逆运动学问题30次时平均最优代价函数值迭代过程的比较曲线。

具体实施方式

下面结合具体实施例对本发明作进一步说明。

以典型的六自由度机械臂PUMA560为例。PUMA560机械臂具有六个自由度并且所有关节均为转动关节。前三个关节主要影响末端执行器的位置，后三个关节决定末端执行器的姿态。采用D-H方法对PUMA560机械臂进行表示和建模，并推导出正运动学方程。图1a、1b显示了所有关节角为零位时连杆坐标系的分布情况，其中图1b表示机械臂前臂的分布情况。下表1则给出了PUMA560的D-H参数：

表1 PUMA560的D-H参数

关节角α_i-1(度)a_i-1(米)d_i(米)θ_i(度)范围(度)1000θ₁-160～1602-9000θ₂-245～45300.43180.1491θ₃-45～2254-90-0.02030.4331θ₄-110～17059000θ₅-100～1006-9000θ₆-266～266

坐标系i相对于坐标系i-1的变换矩阵如下：

根据PUMA560机械臂的D-H参数求出所有相邻连杆坐标系间的变换矩阵⁰₁T(θ₁)、¹₂T(θ₂)、²₃T(θ₃)、³₄T(θ₄)、⁴₅T(θ₅)以及⁵₆T(θ₆)，最后得到6个变换矩阵的乘积：

式中，⁰₆T(θ₆)构成了PUMA560的正运动学方程，它描述了末端执行器(连杆坐标系6)相对于基坐标系(连杆坐标系0)的位姿。

给定机械臂所有关节角的值(θ₁,θ₂,θ₃,θ₄,θ₅,θ₆)，通过正运动学可以将末端执行器在工具坐标系中的笛卡尔坐标(x_T,y_T,z_T)转换为基坐标系中的笛卡尔坐标(x_B,y_B,z_B)。本发明方法求解六自由度机械臂逆运动学问题就是利用该方法找出一组最优的关节角值，使得(x_B,y_B,z_B)与末端执行器在基坐标系中的期望坐标(x,y,z)尽可能接近，其中最优关节角值(θ₁,θ₂,θ₃,θ₄,θ₅,θ₆)就是本发明方法的最优食物源。为此，需要定义一个代价函数去衡量(x_B,y_B,z_B)与(x,y,z)之间的近似程度，此处使用这两点间欧氏距离的平方作为本发明中的代价函数，公式如下：

cost＝(x-x_B)²+(y-y_B)²+(z-z_B)²

本实施例所提供的基于并行化混沌蜂群算法的机械臂逆运动学求解方法，具体包括以下步骤：

1)初始化阶段

采用如下的一维Logistic映射初始化食物源：

X_n+1＝μX_n(1-X_n)n＝0,1,...,K

式中，X_n∈(0,1)，Logistic参数μ设定为4。生成第i个初始食物源m_i的过程如下：

a)设置混沌序列的迭代次数K＝1000。

b)随机生成混沌序列的初始向量ch₀＝(ch₀₁,ch₀₂,...,ch_0D)，其中D＝6。

c)根据混沌方程循环迭代K次，产生混沌向量ch_K＝(ch_K1,ch_K2,...,ch_KD)。

d)产生初始食物源m_i＝(m_i1,m_i2,...,m_iD)，其中：

m_ij＝m_j^min+ch_Kj(m_j^max-m_j^min),i＝1,2,...,SN>

其中，m_ij表示第i个食物源的第j个参数，m_j^max和m_j^min分别代表第j个参数的最大与最小值，在本实施例中对应表1中第j个关节角的最大与最小值。食物源数量SN＝40，解空间的维数D＝6，本实施例中对应D个关节角。同时，每一个食物源都有一个被初始化为0的计数器trial表示尝试搜索的次数。初始食物源会在随后的阶段被雇佣蜂、观察蜂、侦查蜂循环迭代地探索，直至达到最大迭代次数MCN得到最佳食物源，MCN设定为500。每一个食物源只能由一个雇佣蜂或观察蜂负责采集，即雇佣蜂、观察蜂和食物源三者的数量相等。

将初始食物源群体划分成P个子群，其中P为4，每个子群单独地演化。各子群每迭代R次就相互交流信息，本实施例中R＝50。当所有子群都演化完毕后，对比各子群中最佳食物源并得到整个群体的最佳食物源。

2)雇佣蜂阶段

设置参数更改率MR为0.3，雇佣蜂围绕食物源m_i搜索新食物源v_i时，针对m_i的第j个参数生成随机数R_ij∈(0,1)，R_ij与MR比较后按下式生成v_ij：

式中，m_k是随机选择的第k(k不等于i)个食物源，Ф_ij表示参数的更改频率，在ABC中是区间[-1,1]之间的随机数，而在新算法中是区间[-SF,SF]之间的随机数。缩放因子SF是新算法引入的另外一个控制参数，在算法运行前设定为0.6并在搜索过程中按照Rechenberg1/5突变规则自动调整，调整公式如下：

式中，Ф_m表示m次搜索后的较优食物源与总食物源的数量比值，如果Ф_m小于1/5，SF减小使算法的开发能力提高。如果Ф_m大于1/5，SF增大使算法的搜索能力提高。

雇佣蜂依据代价函数cost对新食物源v_i的质量进行评价，如果v_i的质量高于m_i，则v_i取代m_i，trial被重置为0。如果v_i的质量小于等于m_i，trial累加1。如果v_ij超过了第j个参数的取值范围，则重新设定v_ij为合理范围内的有效值。然后，按照如下公式得出新食物源v_i的适应度值fitness_i：

式中，cost_i表示第i个食物源的质量。

3)基于适应度值计算出每个食物源的被选概率

雇佣蜂将食物源的适应度值带回蜂巢与观察蜂共享。算法基于适应度值计算出第i个食物源的被选概率p_i，公式如下：

4)观察蜂阶段

观察蜂根据被选概率p_i以轮盘赌的方式对较优食物源进行跟踪，跟踪过程中观察蜂执行和雇佣蜂阶段相同的任务。所有观察蜂执行完毕后，记录下当前迭代次数下适应度值最高的食物源。

5)侦查蜂阶段

侦查蜂将每一个食物源的计数器值trial与阈值limit对比，本实施例中limit＝150，如果trial大于limit，表明食物源及其周边花蜜匮乏并将其丢弃，由侦查蜂按照初始化阶段的方式搜索新的食物源。如果有多个食物源的trial大于limit，就将其中trial最大的食物源丢弃。

6)信息交流阶段

所有子群每迭代R次就相互交流信息，让子群group_i中花蜜最丰富(适应度值最高)的k个食物源替换掉子群group_{(i+1)mod>中花蜜最匮乏的k个食物源，其中i表示子群编号，p表示子群数量，k设定为5。信息交流完成后，各子群从步骤2)开始继续并行独立地演化。}

单个子群演化的过程请参见图2。

除了使用本发明方法求解PUMA560的逆运动学问题，本实施例中还在相同的参数设定下使用ABC算法及其3种改进算法求解。下表2为5种算法分别求解逆运动学问题30次后最优代价函数值的统计结果。

表2—5种算法分别求解逆运动学问题30次后最优代价函数值的统计结果

最好最差平均方差ABC1.072511e-033.150317e-021.316312e-026.638365e-05CABC2.970008e-051.440834e-033.158536e-047.998854e-08PABC-RC3.585916e-051.363282e-025.690389e-031.036634e-05MABC1.278826e-171.074712e-165.859731e-177.762848e-34CPABC1.498140e-185.243530e-171.983738e-171.555608e-34

从表中可以看出：a)由于ABC算法在求解过程中容易陷入局部最优，所得到的优化结果与另外四种算法相比有较大偏差。b)在30次运行结果中，CPABC得出的最优和最差优化解均好于另外四种算法的对应值，说明更改率MR和缩放因子SF两个控制参数的引入使得算法的全局搜索能力得到提高。c)CPABC运行30次得到的优化解方差要低于另外四种算法的对应值，说明该算法的求解质量相对稳定。

图3为5种算法分别求解逆运动学问题30次时平均最优代价函数值迭代过程的比较曲线。从中可以看出：a)因为ABC、CABC和PABC-RC算法在搜索新食物源时参数的改动频率与搜索步伐都固定不变，即只在固定范围内更改当前食物源的一个参数产生新食物源，在雇佣蜂与观察蜂阶段影响了新食物源的分布，导致全局探索能力不佳，容易陷入局部最优。而MABC和CPABC使得当前食物源的每一个参数都有机会被更改，同时更改幅度会根据当前算法的求解性能进行适当调整，这样全局探索能力与局部开发能力达到一个动态平衡的状态，算法可以很好地发挥这两类能力，在解空间内能找到更优的解。所以从图3观察到MABC与CPABC的迭代曲线快速趋近于横轴，全局探索能力相比另外3种算法有显著提高。b)CABC相比ABC和PABC-RC，CPABC相比MABC，前者算法得到的最终优化解都要优于后者，这是因为CABC和CPABC使用了Logistic混沌映射产生初始食物源群体。混沌映射对初始条件具有极端敏感的依赖性，即使混沌序列初始向量ch₀中的D个参数之间非常相近，在Logistic映射的迭代作用下，最终向量ch_k中的各参数都可能分开，这无疑提高了初始食物源群体的多样性，在一定程度上避免了算法陷入局部最优，并加快算法的收敛速度。c)由于CPABC中存在多个子群并行演化，子群间的交流机制让各子群围绕自身其他子群的优解继续搜索，而MABC只会丢弃最差解。因此从图3中可观察到CPABC的最优代价函数值在大多数迭代次数中都要优于MABC，PABC-RC与ABC也是这种情况。

表3给出了在相同计算机及参数设定的前提下，5种算法求解逆运动学问题得出最终优化解的平均耗时，从表中可以看出CPABC的平均CPU耗时较其他算法要多,仅低于CABC。但由于CPU耗时与计算机硬件配置、操作系统、编程语言及代码编写技巧等多种因素有关,算法更关注的是在相同参数设下求解的质量.从这个角度看本文提出的CPABC算法有更好的求解性能。

表3—5种算法得出最终优化解的平均CPU耗时

算法平均耗时ABC0.043267CABC0.087467MABC0.049133PABC-RC0.060500CPABC0.075567

综上所述，采用本发明方法求解机械臂运动学逆解相比ABC算法及其衍生算法具有较快的收敛速度和较强的全局搜索能力，值得推广。

以上所述实施例只为本发明之较佳实施例，并非以此限制本发明的实施范围，故凡依本发明之形状、原理所作的变化，均应涵盖在本发明的保护范围内。