一种基于免疫遗传混合算法的机构运动链同构识别方法

摘要

本发明公开了一种基于免疫遗传混合算法的机构运动链同构识别方法，包括如下步骤：1)根据机构运动链的结构形成其对应的拓扑图；2)根据拓扑图设定邻接矩阵的遗传编码；3)取待判定的两拓扑图邻接矩阵，确定目标函数；4）随机产生初始抗体种群；计算每个个体的适应度，并且利用适应度大小对其进行排序；5)对其进行最优保存策略；6）计算每个个体的浓度，个体浓度=相近个体总数/群体中总个体数；7）对步骤5）中得到的抗体群进行最优交叉策略；8）进行变异操作,采用倒位算子来实现；9)将局部搜索算子与遗传算法结合；10）形成免疫遗传混合算法，进行机构运动链的同构识别运算。本发明克服了遗传算法容易收敛到局部最优的缺点。

说明书

技术领域

本发明涉及机构运动链同构识别方法，特指一种用于机构创新设计及智能CAD中机构运动 链同构识别方法。

背景技术

由于在机构创新设计和智能CAD中，机构结构的研究是非常重要的，即：怎么在有多个构 件和运动副所组成的运动链中选出所需要的类型。而这一问题的根本就是机构运动链同构识 别，随着这一命题的提出，世界各国这方面的专家和学者提出了一系列的解决方法。如在2000 年，冯春等发表在《机械设计与研究》2000年增刊P40～41页的论文中提出将遗传算法应用于 机构运动链同构识别一种简单方法，但该方法由于过分简化使其在计算过程中存在的种群多样 性变差，难收敛到全局极值、算法运算后期收敛速度变慢甚至难以收敛；中国专利Z L 200910184138.0“一种基于伪杂交混合遗传算法的机构运动链同构识别方法”，虽然改进了遗 传算法在运算后期收敛速度变慢的问题，但也没有很好的解决运算过程中存在的种群多样性变 差的问题。

发明内容

本发明的目的是为克服已有设计方法存在的不足、更好地解决现有机构创新设计周期长、 成本高而且效率低的问题。促使机构创新设计向高效及低成本的方向发展而提供一种基于免疫 遗传混合算法的机构运动链同构识别方法。

本发明技术方案是依次采用如下步骤：

1)根据机构运动链的结构形成其对应的拓扑图；

2)根据拓扑图设定邻接矩阵的遗传编码；

3)取待判定的两拓扑图邻接矩阵，确定目标函数；

4）随机产生初始抗体种群，种群大小为M；计算每个个体的适应度，并且利用适应度大 小对其进行排序；若是初代群体则保存适用度最优的个体到特定的一个专用变量中，转到步骤 6），否则，继续；

5)对步骤4）的抗体种群进行最优保存策略,其方法如下：判断第t代群体P(t)中最优个 体的适用度是否大于专用变量中最优个体的适用度，若大于则把专用变量中最优个体复制一份 到群体P(t)中，同时删除其中的最差个体和保存群体P（t）中最优个体到上述专用变量中替 代原有数值；若小于则只把专用变量中最优个体复制一份到群体P(t)中，同时删除其中的最 差个体；

6）计算每个个体的浓度，个体浓度=相近个体总数/群体中总个体数，个体浓度大，则抑 制该抗体，就使得相近个体数变少，这样就保持了群体中个体的多样性；选出适应度高而浓度 较低的个体进行克隆复制，而对适应度低浓度较高的个体进行抑制；对抗体群执行选择和复制 操作；

7）对步骤5）中得到的抗体群进行最优交叉策略：选择出第t代群体P(t)中的适应度最 底的10％*M（M为种群数目）个抗体与保存在变量中的最优个体P^*(t)分别进行交叉，交叉的 方法是：把选出的个体P_i(t)和P^*(t)放到一个交配池中，i=1～0.1M，根据选定的交叉策略（即 伪杂交过程）对选出的两个个体进行交叉操作，得到一对子代个体P_iˊ(t)和P^*ˊ（t)，然 后用个体P_iˊ(t)替代群体中的个体P_i(t)而将个体P^*ˊ(t)舍弃掉；

8）为了避免陷入局部最优，采用倒位算子对上述抗体种群中各抗体进行变异操作；

9）将局部搜索算子与遗传算法结合；

10）形成最优选择交叉遗传混合算法，进行机构运动链的同构识别运算。

本发明的有益效果是：

1、本发明中，利用免疫算子和遗传算法相结合，保证了算法在运行过程群体的多样性。 克服了遗传算法容易收敛到局部最优的缺点；

2、本发明中，利用最优保存策略的特点不仅不会使得迄今出现的最优个体不会被选择、 交叉和变异操作所丢失和破坏，保证了算法收敛到全局最优解的可能性。克服了遗传算法在算 法后期难以收敛的缺点；

3、本发明中，利用最优交叉策略的特点是使得适用度较低的个体快速向适应度较高的方 向进化，加快了算法向全局最优的收敛速度。克服了遗传算法收敛速度慢的缺点。

附图说明

图1为本发明的流程示意图。

具体实施方式

本发明算法的具体流程描述如下：

步骤1:由式C=TAT^T，变换T来随机产生一个规模为M的初始种群P（0）；

步骤2:计算每个个体的目标函数值和适应度，将适应度最大的个体储存局部最优解到一 个专用变量中；

步骤3：若是初代种群，则转到步骤5）；否则，继续；

步骤4：确定每个个体的适用度，并按适应度大小排序；进行最优保存策略,其方法如下： 判断P（t）中最优个体的适用度是否大于专用变量中最优个体的适用度，若大于则把专用变 量中最优个体复制一份到P(t)中，同时删除其中的最差个体和保存P（t）中最优个体到上述 专用变量中替代原有数值；若小于则只把专用变量中最优个体复制一份到P(t)中，同时删除 其中的最差个体；

步骤5：根据抗体的相似度和浓度定义，计算每个抗体的浓度；

步骤6：选出适应度高而浓度较低的个体进行克隆复制，而对适应度低浓度较高的个体进 行抑制；对抗体群执行选择和复制操作；

步骤7：对抗体群进行最优交叉策略：选择出第t代群体P(t)中的适应度最底的10％*M （M为种群数目）个抗体与保存在变量中的最优个体P^*(t)分别进行交叉，交叉的方法是：把 选出的个体P_i(t)和P^*(t)放到一个交配池中，i=1～0.1M，根据选定的交叉策略（，即伪杂交 过程），对选出的两个个体进行交叉操作，得到一对子代个体P_iˊ(t)和P^*ˊ（t)，然后用个 体P_iˊ(t)替代群体中的个体P_i(t)而将个体P^*ˊ(t)舍弃掉；

步骤8：为了避免陷入局部最优，采用倒位算子对上述抗体种群中各抗体进行变异操作；

步骤9：对抗体群执行局部搜索；

步骤10：找到最优解，两运动链同构；否则，不同构。

其中步骤2中目标函数和适应度函数计算方法如下：

取A、B为待判定的两拓扑图G1、G2的邻接矩阵，目标函数取：

$\min f\left(x\right)=\underset{i,j=0}{\overset{d-1}{\Sigma }}|C_{(i,j)}-B_{(i,j)}|,$

C=TAT^T，

式中，d为顶点数，也是个体长度，T=P₁P₂……P_n，其中P_i为矩阵

A——为机构拓扑图G1的邻接矩阵，

B——为机构拓扑图G2的邻接矩阵，

C——邻接矩阵A经过变换矩阵T进行行变换和列变换后得到的矩阵。

亲和度评价公式如下：

F(x)=1/f(x)

可推算出F(x)的取值在(0,1]之间，可见f(x)越小，F(x)就越大

其中步骤9中的局部搜索，对于个体x=(x₁,x₂,…,x_d)算法如下:

步骤1：随机选取下标为i，j的两个元素；

步骤2：交换这两个元素得到新的个体就是原来个体的一个邻居x'；

步骤3：比较x和x'的适应度F，如果F(x')＞F(x)，则x=x'；否则舍弃x'。