您好, 访客   登录/注册

粒子群优化算法在皮革排样中的应用

来源:用户上传      作者:

  摘 要:该文针对皮革排样优化中保持种群个体多样性和全局寻优存在的问题,研究了粒子群算法、基于小生境的粒子群算法及基于免疫原理的粒子群算法这3种方法,分别对其算法的原理和操作步骤进行阐述,增强了研究者对粒子群算法的理解,提供了研究粒子群的比较系统的算法研究现状,最后对粒子群的应用方向进行列举,使学者对粒子群算法的应用及发展有进一步了解。
  关键词:皮革排样 粒子群算法 改进
  中图分类号:TP391 文献标识码:A 文章编号:1672-3791(2015)12(a)-0270-02
  排样是指在一个平面(母版)内排布多个面积小于母版的平面(子版),排样优化是指让子版尽可能多地排进母版内,使母版利用率最高。母版利用率的提升对提高生产效率、经济效益和节省资源具有重要的现实意义和价值。排样优化问题是组合优化领域中计算复杂性最高的一类NPC(Nondeterministic Polynomial Complete)问题,解决排样优化问题的主要途径多趋向于现代优化技术中的各种仿生学理论和智能算法。
  粒子群优化算法PSO(Particle Swarm Optimization)是源于鸟群觅食运动行为的启发,是动物个体之间集体合作与竞争的自组织体现。这种基于生物群体间的生物信息交流的共享机制进行搜索更新的算法,可以得到当前目标函数的最优解。同时这种算法也能够在连续的定义域内搜索函数极值[1]。对于比较简单的粒子群可以较容易收敛到最优解。而对于比较复杂的多重最优解问题,这种方法也提供了较优的解决办法。该文介绍了粒子群优化算法的应用[2]、基于小生境的粒子群排样优化算法以及基于免疫原理的粒子群排样优化算法并且对粒子群新的应用做了展望。
  1 粒子群算法的应用
  1.1 粒子群算法在不规则件排样中的应用
  首先以零件的入排交换序列和角度变异序列作为粒子运动速度,以零件入排编码值来表示粒子的位置,从而构造粒子群算法,然后利用剩余矩形动态匹配算法完成解码和局部寻优任务,并结合不规则件的正交靠接算法完成自动排样任务。
  粒子群算法的基本程序如下。
  (1)初始化粒子群,即随机产生各个粒子的初始解和交换序列。
  (2)依据粒子当前位置得出其个体极值及群体最佳极值,并且计算新解:①推算当前粒子和、的交换序列及旋转角度变异序列;②根据式(1)计算粒子的速度,得到粒子新的解,如果有更好的解,更新。
  (3)如果在整体粒子群中可以找到更优的解,那么就更新。
  (4)如果满足跳出循环条件(足够优的位置或最大迭代次数),那么就终止计算并输出结果;否则跳转到步骤(2),继续循环计算。
  最后得到运用粒子群算法的最终排样结果。
  1.2 基于小生境的粒子群排样优化算法
  小生境技术源于遗传算法,这种方法能够让基于群体的随机优化算法形成物种,然后使对应的优化算法可以解出多个最优解 [3]。针对排样优化问题,基于小生境的粒子群优化算法关键是在物种进化过程中小生境技术具有保持物种多样性的优势,可以达到避免陷入局部最优的目的。在一定程度上使排版结果更优。
  基于小生境的粒子群算法(NPSO)步骤如下。
  (1)初始化整个粒子群,随机产生各个粒子的初始位置和速度。
  (2)依据粒子间的欧式几何距离把种群分成多个子群。
  (3)利用式(2)更新每一个粒子的速度和位置参量。
  (4)依据粒子位置使用BL算法(最下最左算法)进行排样,计算适应度值F=1/排样高度。
  (5)依据F的值更新粒子、子群和整个种群的当前最优解。
  (6)判断在连续代内子群是否有新的最优解,若存在新的最优解则跳到步骤(8);否则进行步骤(7)。
  (7)重置该子群的速度和位置参量。
  (8)迭代次数为,判断是否为最大迭代值,如果是,则终止迭代过程,执行结束;否则跳转到步骤(3)继续执行。
  1.3 基于免疫原理的粒子群排样优化算法
  基于免疫原理的粒子群排样优化算法运用生物免疫系统的自适应能力,得到粒子群优化的免疫机制策略,进而用这种方法来解决排样优化问题,利用浓度机制实现多样性度量来控制种群特征,进而扩大搜索空间,并且将个体的优势基因免疫储备在免疫中增强。为了制定种群多样性度量指标和浓度计算,以基本的粒子群优化算法为基础。则该算法随机生成 M+N个新粒子进行免疫调节,扩大搜索空间。
  为了达到粒子群搜索的多样性得到有效增强的目的,通过浓度概率的大小来降低浓度高的个体被选择的概率,从而提高浓度低的个体被选择的概率。从中选择 N 个粒子形成新一代的粒子群。针对排样优化中保持种群个体多样性及全域寻优存在的问题,此方法提高了算法的全域搜索速度并且保持了种群个体多样性,从而更好地对不规则的零件进行排样。
  2 结论
  该文论述了粒子群优化算法在二维不规则排样问题中的应用。粒子群优化算法对现有的应用实例进行探讨,并在构造粒子飞行速度更新运算上进行研究;基于小生境的粒子群算法能够在不改变时间复杂度的前提下,增加全局搜索能力,从而弥补粒子群算法的容易陷入局部最优缺陷;基于免疫原理的粒子群排样优化算法是依据免疫信息处理机制的全域寻优策略,为了平衡粒子群算法中由于信息流动的单向性导致的种群多样性弱化,该方法制定粒子浓度的多样性度量标准。同时在粒子克隆变异过程中,使优势基因的记忆存储得到加强;在保证粒子群信息共享机制的基础上,增强了算法的全局寻优能力并且提高了收敛精度。这3种方法都是在求解排样优化问题的基础上,提出基于粒子群算法的解决方案,从而有效提高材料利用率。
  3 粒子群算法研究的展望
  (1)理论研究:自诞生以来其数学基础一直不完备,特别是收敛性一直没有得到彻底解决。因此,仍需要对PSO的收敛性等方面进行进一步理论研究。
  (2)信息共享机制:基于邻域拓扑的粒子群优化算法局部模型有效地提高了PSO的全局搜索能力,充分运用和改进现有拓扑结构并提出新的拓扑,从而改善算法性能,是一个值得研究的问题。同时,PSO算法具有较快的收敛速度,而局部模型具有较优的全局搜索能力,对两者结合得到的算法作进一步研究,保证新的算法不仅具有较优的全局搜索能力,而且具有较快的收敛速度,也是一个很有意义的研究方向。
  (3)应用研究:算法的有效性和价值必须在实际应用中才能得到充分体现。
  参考文献
  [1] 杨建锋,孟利民.视频监控系统中实时流媒体传输控制方法的设计[J].浙江工业大学学报,2012,40(4):454-457.
  [2] 梁利东,钟相强.粒子群算法在不规则件排样优化中的应用[J].中国机械工程,2010(17):2050-2052,2069.
  [3] 章军.小生境粒子群优化算法及其在分类器集成中的应用研究[D].合肥:中国科学技术大学,2007.
转载注明来源:https://www.xzbu.com/8/view-11276338.htm