论文部分内容阅读
摘 要：装配线上的螺母问题属于NP完全问题，对其进行优化具有很重要的工程意义和现实意义。智能算法的出现为解决此类问题提供了很有效的方法。由于智能算法在解决全局最优解的问题上有着独到的优点，本文先采用GA、SA两种传统智能优化算法解决螺母问题，并对两种算法得到的结果进行比较、分析。
关键词：装配线；螺母问题；遗传算法；模拟退火算法
生产装配线的螺母紧固是指用装配机器人在一条生产装配线上去拧紧需要装配的部件上的螺母。机械机器人从初始位置（在第一个要紧固的螺母的上方）开始，依照一定的路径，依次拧紧每一个螺母，最终返回到刚开始的出发位置。一条最小成本周游路线将使机械手完成工作所用的时间取最小值（只有机械手移动的时间总量是可变化的）。
上世纪五十年代中期仿生学出现以后，人们仿照自然界中生物的某些行为，发明了很多智能算法，用智能算法解决该问题的意义是可以使机械手的运行轨迹最小，从而使机械手完成对该配件的装配总时间最小，可以极大提高装配生产效率和使企业的效益最大化。
1遗传算法（GA）在螺母装配线路径规划中的应用研究
GA从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。算法的主要步骤如下：首先，随机产生一定数据的初始种群，种群中染色体的数目称为种群的大小并计算各自染色体的适应度，然后用适值度函数来评价每一个染色体的优劣， 一次繁殖由两个双亲产生一个子代；通过选择过程，产生一个新的种群。对这个新的种群进行交叉和变异操作，目的是挖掘种群中个体的多样性，避免有可能陷入局部解。最后以设定的迭代次数或某个条件作为终止条件，得到最优解。
由于GA很容易陷入局部极小值，为避免遗传算法陷入局部极小值的循环，本文采用一种改进措施对传统GA算法进行优化，即在新的种群进行交叉和变异操作之后引入进化逆转操作，经过逆转后，适应函数值较高的染色体才能遗传下来，否则该染色体被抛弃。本文中的编码方式采用整数编码，选择算子采用轮盘赌，交叉算子采用部分映射杂交，变异策略采用随机选取两个点，将其对换位置。
本文以某汽车配件厂流水生产线上的螺母固定过程为研究对象，各个螺母所在位置信息经过采集，输入仿真数据库中，数据来源可以参考文献2中的相关章节。
装配机器人在每个螺母上停留的时间为4s，机器人的运动为匀速运动，运动速度为5cm/s。优化目标是是装配机器人在紧固一个配件上的所有螺母所用时间最短，也就是装配机器人在该配件上所有需紧固的螺母间的移动路径最短。
本文GA中的参数设置如下：进化代数设为200代，交叉概率为0.9，变异概率为0.05，适应度函数为机械手固定完23个螺母后回到起点的倒数，优化目标就是选择适应度值尽可能大的染色体，终止条件为GA寻优200代。
利用改进的GA算法，经过编程计算，得到的装配机器人最优路径为：11-1-10-8-6-7-3-9-4-2-5-18-14-17-20-22-16-21-19-15-13-12-25-10。最短路径为：296.56cm，运行的最短时间为：150.51s。
2模拟退火算法（SA）在螺母生产装配线路径规划中的应用
模拟退火算法（Simulated Annealing，SA）是一种通用概率算法，其最早是由Metropolis等人于1953年提出的。SA的出发点是模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小 。模拟退火算法详细原理及数学模型可参考文献4和文献5。
SA可以分解为解空间、目标函数和初始解三部分，與物理退火过程结合，其可分为三部分：加温过程相当于算法设定温度初始值，等温过程相当于算法的蒙特卡洛（Metropolis）抽样过程，冷却过程则相当于控制参数的下调过程。优化目标是使退火过程的能量的下调变化最大，直到找到温度能量的最低态也就得到了所求问题的最优解。SA算法收敛于全局最优解的关键在于所设定的Metropolis准则，Metropolis准则以一定的概率按受恶化解，从而使算法跳出局部最优的缺陷。
根据文献中对SA中参数的研究可将本文中SA的参数设置如下：初始温度T0=1000，终止温度Tend=0.001，降温速率q=0.85，链长=600；采用随机排列的方法产生S1；用二邻域变换法产生S2；Metropolis准则为 ，df<0时以概率1接受新的路径，其它情况下以概率exp（-df/T）接受新的路径；停止条件为T小于Tend。进行优化的数据如上。
用SA优化机械手最优运行路径如下：22-14-17-20-18-16-21-23-15-10-19-13-12-8-11-1-6-9-3-7-4-2-5-22，最短路径为：297.6495cm，机械手运行的最短时间为：151.5299s。
3两种优化方法所得结果的比较与分析
遗传算法（GA）和模拟退火算法（SA）都能在比较短的时间内寻找到需优化的目标函数的最小值，都能有效减少原装配生产线配件的螺母紧固所需时间，验证了两种算法的有效性。遗传算法需迭代85代左右才能寻找到最优目标，需用时间为约7.8s；SA需迭代40代左右能找到最优目标，需用时间约为3.2s。主要原因是GA中需要编码和解码。
参考文献：
[1]Kenneth A Dejong. Genetic Algorithms： A 25 Year Perspective [A ]. Computational Intelligence： Imitating Life，WCCI 94[C]. 1994： 124-125.
[2]史峰，王辉，郁磊，胡斐.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社.2011.7：第一版。
[3]苏劲松，周昌乐，蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].2007.7，17（7）：94-97.
[4]高海昌，冯博琴，朱利.智能优化算法求解TSP问题[J].控制与决策.2006.3，21（03）：241-247，252.
[5]刘洪普，侯向丹.模拟退火中关键参数的研究[J].计算机工程与科学.2008，30（10）：55-57
关键词：装配线；螺母问题；遗传算法；模拟退火算法
生产装配线的螺母紧固是指用装配机器人在一条生产装配线上去拧紧需要装配的部件上的螺母。机械机器人从初始位置（在第一个要紧固的螺母的上方）开始，依照一定的路径，依次拧紧每一个螺母，最终返回到刚开始的出发位置。一条最小成本周游路线将使机械手完成工作所用的时间取最小值（只有机械手移动的时间总量是可变化的）。
上世纪五十年代中期仿生学出现以后，人们仿照自然界中生物的某些行为，发明了很多智能算法，用智能算法解决该问题的意义是可以使机械手的运行轨迹最小，从而使机械手完成对该配件的装配总时间最小，可以极大提高装配生产效率和使企业的效益最大化。
1遗传算法（GA）在螺母装配线路径规划中的应用研究
GA从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。算法的主要步骤如下：首先，随机产生一定数据的初始种群，种群中染色体的数目称为种群的大小并计算各自染色体的适应度，然后用适值度函数来评价每一个染色体的优劣， 一次繁殖由两个双亲产生一个子代；通过选择过程，产生一个新的种群。对这个新的种群进行交叉和变异操作，目的是挖掘种群中个体的多样性，避免有可能陷入局部解。最后以设定的迭代次数或某个条件作为终止条件，得到最优解。
由于GA很容易陷入局部极小值，为避免遗传算法陷入局部极小值的循环，本文采用一种改进措施对传统GA算法进行优化，即在新的种群进行交叉和变异操作之后引入进化逆转操作，经过逆转后，适应函数值较高的染色体才能遗传下来，否则该染色体被抛弃。本文中的编码方式采用整数编码，选择算子采用轮盘赌，交叉算子采用部分映射杂交，变异策略采用随机选取两个点，将其对换位置。
本文以某汽车配件厂流水生产线上的螺母固定过程为研究对象，各个螺母所在位置信息经过采集，输入仿真数据库中，数据来源可以参考文献2中的相关章节。
装配机器人在每个螺母上停留的时间为4s，机器人的运动为匀速运动，运动速度为5cm/s。优化目标是是装配机器人在紧固一个配件上的所有螺母所用时间最短，也就是装配机器人在该配件上所有需紧固的螺母间的移动路径最短。
本文GA中的参数设置如下：进化代数设为200代，交叉概率为0.9，变异概率为0.05，适应度函数为机械手固定完23个螺母后回到起点的倒数，优化目标就是选择适应度值尽可能大的染色体，终止条件为GA寻优200代。
利用改进的GA算法，经过编程计算，得到的装配机器人最优路径为：11-1-10-8-6-7-3-9-4-2-5-18-14-17-20-22-16-21-19-15-13-12-25-10。最短路径为：296.56cm，运行的最短时间为：150.51s。
2模拟退火算法（SA）在螺母生产装配线路径规划中的应用
模拟退火算法（Simulated Annealing，SA）是一种通用概率算法，其最早是由Metropolis等人于1953年提出的。SA的出发点是模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小 。模拟退火算法详细原理及数学模型可参考文献4和文献5。
SA可以分解为解空间、目标函数和初始解三部分，與物理退火过程结合，其可分为三部分：加温过程相当于算法设定温度初始值，等温过程相当于算法的蒙特卡洛（Metropolis）抽样过程，冷却过程则相当于控制参数的下调过程。优化目标是使退火过程的能量的下调变化最大，直到找到温度能量的最低态也就得到了所求问题的最优解。SA算法收敛于全局最优解的关键在于所设定的Metropolis准则，Metropolis准则以一定的概率按受恶化解，从而使算法跳出局部最优的缺陷。
根据文献中对SA中参数的研究可将本文中SA的参数设置如下：初始温度T0=1000，终止温度Tend=0.001，降温速率q=0.85，链长=600；采用随机排列的方法产生S1；用二邻域变换法产生S2；Metropolis准则为 ，df<0时以概率1接受新的路径，其它情况下以概率exp（-df/T）接受新的路径；停止条件为T小于Tend。进行优化的数据如上。
用SA优化机械手最优运行路径如下：22-14-17-20-18-16-21-23-15-10-19-13-12-8-11-1-6-9-3-7-4-2-5-22，最短路径为：297.6495cm，机械手运行的最短时间为：151.5299s。
3两种优化方法所得结果的比较与分析
遗传算法（GA）和模拟退火算法（SA）都能在比较短的时间内寻找到需优化的目标函数的最小值，都能有效减少原装配生产线配件的螺母紧固所需时间，验证了两种算法的有效性。遗传算法需迭代85代左右才能寻找到最优目标，需用时间为约7.8s；SA需迭代40代左右能找到最优目标，需用时间约为3.2s。主要原因是GA中需要编码和解码。
参考文献：
[1]Kenneth A Dejong. Genetic Algorithms： A 25 Year Perspective [A ]. Computational Intelligence： Imitating Life，WCCI 94[C]. 1994： 124-125.
[2]史峰，王辉，郁磊，胡斐.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社.2011.7：第一版。
[3]苏劲松，周昌乐，蒋旻隽.一种基于逆转算子的求解TSP问题的改进演化算法[J].2007.7，17（7）：94-97.
[4]高海昌，冯博琴，朱利.智能优化算法求解TSP问题[J].控制与决策.2006.3，21（03）：241-247，252.
[5]刘洪普，侯向丹.模拟退火中关键参数的研究[J].计算机工程与科学.2008，30（10）：55-57