基于逆转算子的遗传算法在螺母紧固路径中的优化

2014-04-01陈震彭先涛

机械制造与自动化 2014年5期

陈震，彭先涛

(1.泰州职业技术学院信息工程学院，江苏泰州 225300;2.辽宁石油化工大学信息与控制工程学院，辽宁抚顺 113001)

0 前言

装配生产线上紧固螺母路径优化问题是在一条装配线上用一个机械手去紧固待装配部件上的螺母问题。机械手由其初始位置开始，依次移动到其余的每一个螺母，最后返回到起点。机械手的运行轨迹是以螺母为节点的一条周游路线。该问题的最优解是机械手对该配件上的所有螺母进行紧固后回到始点的工作时间最小，即寻找机械手在螺母间的最短运行路径，此时，该问题可以转换为TSP 问题。由此可见，该问题也是典型的多项式复杂程度的非确定性问题(Non－deterministic Polynomial problem)，即最坏情况下的寻优时间随着问题规模的增大按指数方式增长，该问题的答案是无法直接计算得到的，只能通过间接的“猜算”来得到结果，到目前为止还没有找到一个多项式时间的有效算法［1］。

遗传算法(genetic algorithm，GA)［2］的特点是先对问题参数进行编码，编成GA 可以处理的染色体，再对该染色体进行优化。基于此可知，GA 优化不是问题参数自身，故函数约束条件的限制可以不考虑;优化过程开始于问题解的某个集合(不是一个个体)，其具有的隐含并行搜索特性可减少算法陷入局部极小值的概率，隐含并行性和全局解控制键搜索是其两个最明显的特点;GA 的最大缺点是对结构复杂的组合优化问题进行优化时，需要进行搜索的空间大，进行优化搜索的时间长，出现早熟收敛和收敛性能差的可能性很大;初始种群的选择对算法影响很大［3］。针对GA 算法容易陷入局部极小值的缺点，本文提出了一种改进的GA(IGA):在选择、交叉、变异之后引入连续多次的进化逆转操作(这里的进化是指逆转算子的单方向性，即只有经过逆转后，适应度有提高的染色体才接受下来，否则逆转无效)［1］。仿真结果表明，该方法可以较快的找到机械手的最优运行路径，且运行稳定。

1 基于进化逆转算子改进的遗传算法

GA 算法的基本过程:以随机产生的待解决问题的一种排列为一条染色体，初始种群由随机构造的若干条染色体构成，计算每个个体的适应度值，根据适应度值的高低进行选择(遗传操作中的优胜劣汰机制)，两个双亲产生一个子代为一次繁殖;根据交叉算子进行交叉操作、变异算子进行变异操作，交叉算子和变异算子都是选择得到的，交叉概率(pc)一般的选取范围为［0.40，0.99］，变异概率(pm)的选取范围一般为［0.0001，0.1］。以设定的迭代次数或某个条件作为算法终止的条件。

本文中采用IGA 对螺母紧固路径优化，进行优化的步骤如下［1］:

1)螺母紧固路径优化参数集进行编码

编码方式采用整数编码(采用一个基因一个参数来编码，将原问题的解空间映射到整数串空间上，然后在整数串空间上进行遗传操作，结果再通过解码过程还原成其表现型以进行适应度评估)，以提高解的精度和运算速度［4］。如对8 个螺母的优化问题{1，2，3，4，5，6，7，8}，则|1|2|8|7|5|3|6|4 就是一个合法的染色体。

2)种群初始化

初始种群是起始解，本文产生的初始种群为100。

3)计算适应度函数

设k1|k2|…|ki|…|kn |为一个采用整数编码的染色体，Dkikj为螺母ki到螺母kj的距离，则该个体的适应度函数fitness 为:

其中，n 是螺母个数。

即适应度函数为机械手恰好走遍n 个螺母，在回到开始时待固定的螺母上方的距离的倒数。优化目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体品质越好，反之越次。

4)选择操作

从旧群体中以移动概率选择个体到新群体中，根据3)计算出来的适应度进行选择，个体适应度值越大，被选中的概率越大。

5)交叉操作

交叉概率pc=0.9。采用部分映射交叉，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程(假定有8 个螺母):

a)产生两个［1，8］区间内的随机整数r1和r2，确定两个位置，对两位置的中间数据进行交叉，如:r1=2，r2=5，

7 6 | 5 2 4 1 | 8 3 交叉为7 6 | 2 5 1 3 | 8 *

8 6 | 2 5 1 3 | 4 7 8 6 | 5 2 4 1 | * 7

b)交叉后，同一个个体中有重复的螺母编号，不重复的数字保留，有重复的数字(带* 位置)采用部分映射的方法消除冲突，即利用中间段的随影关系进行映射。结果为:

7 6 | 2 5 1 3 | 8 4 8 6 | 5 2 4 1 | 3 7 。

6)变异操作

变异概率pm=0.05。变异策略采取随机选择两个点，将其兑换位置。产生两个［1，8］范围内的随机整数r1和r2，确定两个位置，将其兑换位置，如:r1=2，r2=5，7 |6| 5 2 4 |1| 8 3 变异后为7 |1| 5 2 4 |6| 8 3。

7)进化逆转操作［5－6］

在标准遗传算法中，交叉算子的地位和作用很大，通过交叉操作可以使GA 算法的搜索能力得到很大的提高。对顺序交叉算子进行考察研究时发现，即使两个父代一样，通过交叉以后任然会有不同于父代的子代产生，并且子代的码串排列顺序与父代的排列有很大的差异，交叉算子的这种变异效果可以起到两方面的作用:a)在一定程度上可以维持种群的多样性，使算法避免陷入局部最优解;b)子代不能够很好的继承父代较多的信息，尤其是当进化过程进行到后期的时候，种群空间中有很多的高适应度值的个体，这种操作会在很大程度上破坏父代的较优基因组合，父代的优良基因组难以被子代继承，从而导致算法的搜索能力降低。

由于这种交叉算子使子代难以继承父代优良基因组的缺点，本文采用一种进化逆转算子(利用遗传学中的“倒位”:在染色体中存在着两点，在这两点之间的基因位置是倒转的，从而使得那些在父代中离得很远的基因位在后代中紧靠在一起。基于此现象，Holland 提出一种“逆转算子”，并在烟花算法中得到很好的应用，使得染色体位串上的重要基因更加紧凑，交叉算子很难将其分裂)——使子代可以继承父代较多的信息，将进化逆转操作用于GA 算法的选择、交叉、变异之后，进而提高算法的局部搜索能力。逆转算子首先在染色体的个体串上随机选择两点，位串被这2 点分为3 段，然后将第2 段(中间段)的左右顺序倒转过来并与第1 段和第3 段连接起来，从而形成新的染色体个体位串。以(7 6 5* 2 4 1 8 * 3)为例介绍，其中* 为随机选择的倒位点，经过逆转算子作用后形成的新位串为(7 6 5 8 1 4 2 3)。

这里的“进化”是指逆转算子的单方向性，即只有经逆转后，适应度有提高的才接受下来(本文中适应度提高10%的才被接受下来)。和交叉算子对比可知，逆转算子可以使父代的基因信息被子代继承的更多，且文中的逆转操作是单方向的——只接受朝着好的方向的逆转，故它搜索最优解的能力比顺序交叉算子更强。

产生连个［1，8］区间累的随机整数r1和r2，确定两个位置，将其对换位置，如:r1=2，r2=5，7 |6 2 5| 1 3 8 4 进化逆转后为7 |5 2 6 |1 3 8 4。

对每个个体进行交叉变异，然后代入适应度函数进行评估，择出适应值大的个体进行下一代的交叉和变异以及进化逆转操作。循环操作:判断是否满足设定的终止条件(最大进化代数200)，满足则返回第3 步;则结束遗传操作，输出最优解。

2 仿真研究

本文以浙江宁波某汽车配件厂某条流水线上的某型号配件上的螺母固定为研究对象，数据见图1。

机械手在每个螺母上停留的时间为4 s(机械手移动到待固定的螺母上方、对螺母进行固定、离开螺母的总时间)，机械手在螺母间的运动速度为匀速(5 cm/s)。对该问题进行优化得到的目标是使机械手在对该配件上所有螺母进行固定后的总时间最小，也就是使机械手在该配件上所有螺母间的移动路径最短。

改进的遗传算法的流程图如图2 所示。

图1 螺母坐标数据

图2 IGA算法螺母紧固优化路径流程图

利用本文提出的改进遗传算法对螺母紧固路径优化问题进行Matlab 仿真研究得到仿真结果如图3、图4所示。

图3 IGA 算法寻找的机械手最优运行路径

机械手最优运行路径为:10－1－11－8－6－9－3－7－4－2－5－22－14－17－20－18－16－21－23－15－13－12－19－10

图4 IGA 算法的迭代过程

最短路径为:297.562 2(cm)

机械手运行的最短时间为:151.512 4(s)

基本GA 算法解决螺母紧固路径优化问题的流程图如图5。

图5 IGA算算法螺母紧固优化路径流程图

采用的基本参数与仿真数据同IGA 中的一样，仿真结果如图6 和图7 所示。

图6 基本GA 算法寻找的机械手最优运行路径

图7 基本GA 算法的迭代过程

机械手最优运行路径为:

23－15－19－10－1－11－8－6－3－7－4－2－5－14－17－20－22－9－12－13－16－18－21－23

最短路径为:335.616(cm)

机械手运行的最短时间为:175.904(s)

3 仿真结果比较和分析

由以上结果可知，IGA 算法寻找的机械手最优运行路径为297.562 2 cm，完成一块配件的装配时间为151.512 4 s;基本GA 算法寻找的机械手最优运行路径为335.616 cm，完成一块配件的装配时间为175.904 s。可知，IGA 的寻优精度较高，且IGA 能够很好的跳出局部极小值，快速、稳定的寻找到螺母紧固路径优化问题最优解，而基本GA 算法容易陷入局部极小值，寻优效果并不是很理想，IGA 算法的寻优结果、寻优能力远远高于基本GA算法的性能。由此验证了该改进算法的有效性。