基于伪杂交混合遗传算法的机构运动链同构识别方法

摘要

本发明公开了一种基于伪杂交混合遗传算法的机构运动链同构识别方法，先根据机构运动链的结构形成其对应的机构拓扑图；设定邻接矩阵的遗传编码；取待判定的两机构拓扑图邻接矩阵确定目标函数，计算每个个体的目标函数值和适应度；再采用伪杂交算子，在随机产生的群体中随机选取两个个体，随机产生两个杂交点进行空中扩展；从扩展生成的中间种群中选择两个个体进行初步局部寻优；最后结合局部搜索算子形成伪杂交混合遗传算法，进行机构运动链同构识别的运算和仿真，能对运动链进行高效、准确的同构判别。

主权项

1.一种基于伪杂交混合遗传算法的机构运动链同构识别方法，其特征是依次采用如下步骤：1)根据机构运动链的结构形成其对应的机构拓扑图；2)根据机构拓扑图设定邻接矩阵的遗传编码；3)取待判定的两机构拓扑图邻接矩阵确定目标函数，计算每个个体的目标函数值和适应度；目标函数为：C＝TAT^T，式中，d为个体长度，T＝P₁P₂……P_n，其中P_i为矩阵，A、B为两个机构拓扑图的邻接矩阵，C为邻接矩阵A经过变换矩阵T进行行变换和列变换后得到的矩阵；4)采用伪杂交算子，在随机产生的父代群体中随机选取两个个体x、y，随机产生两个杂交点k₁、k₂进行空中扩展；从扩展生成的中间种群中选择两个个体进行初步局部寻优；所述两个个体x、y表示为：$x=(x_1,···,x_{k_1},x_{k_1+1},···,x_{k_2-1},x_{k_2},···,x_d);$$y=(y_1,···,y_{k_1},y_{k_1+1},···,y_{k_2-1},y_{k_2},···,y_d),$(0≤k₁≤k₂≤d)，d为个体长度；令tx＝x，ty＝y，对x进行如下操作：步骤1：令i＝k₁+1；步骤2：令j＝0；步骤3：如果tx_j≠ty_i，则j＝j+1，重复步骤3；步骤4；如果(i≠j)∩(k₁+1≤j≤k₂-1)，则转步骤5；否则转步骤6；步骤5：交换x_i和x_j；步骤6：i＝i+1，如果i＝k₂，结束，否则转步骤2；对y进行如下操作：步骤1：令i＝k₁+1；步骤2：令j＝0；步骤3：如果ty_j≠tx_i，则j＝j+1，重复步骤3；步骤4：如果(i≠j)∩(k₁+1≤j≤k₂-1)，则转步骤5；否则转步骤6；步骤5：交换y_i和y_j；步骤6：i＝i+1；如果i＝k₂，结束；否则转步骤2；所述初步局部寻优的步骤为：步骤1：令i＝1；步骤2：如果y_i≠i，则交换x_i和得到$x^{\prime }=(x_1,···,x_{i-1},x_{y_i},x_{i+1},···,x_{y_i-1},x_i,x_{y_i+1},···,x_d);$否则转步骤4；步骤3：若F(x′)＞F(x)，则x＝x′；步骤4：i＝i+1，如果i＞d，则结束；否则转步骤2；5)结合局部搜索算子形成伪杂交混合遗传算法，进行机构运动链同构识别的运算和仿真；局部搜索算子步骤如下：步骤1：令i＝1；步骤2：令j＝1；步骤3：如果j≠i，则交换x_i和x_j的位置，得到x′；否则转步骤5；步骤4：比较x和x′的适应度，如果F(x′)＞F(x)，则x＝x′；步骤5：j＝j+1；如果j≤d，则转步骤3；步骤6：i＝i+1；如果i≤d，转步骤2；否则结束。