基于结构化编码的多粒子群协同进化算法

基于结构化编码的多粒子群协同进化算法

0单元布局的集成优化问题单元生产是一种先进的生产技术应用，是一种适用于现在多品种、少批生产的先进生产技术的先进生产方法。它结合了劳动监察的高效率和f自行车的高生产率，解决了传统生产方法下产量与生产灵活性之间的矛盾。构造单元生产系统需研究单元构建、单元内设备布局、单元间布局三个问题。单元构建阶段主要解决最佳设备及单元能力均衡、最小跨单元加工等问题,完成对生产单元的划分,并输出单元间的负荷平衡率、产品跨单元加工的次数以及产品的生产批量等;单元布局是在单元构建的基础上确定各单元和设施的摆放位置,并输出单元之间和设施之间的布局形式和位置。大量学者对单元构建技术进行了研究,而对单元设施布局方面的研究较少。传统方法是对单元设施布局问题中的单元内布局和单元间布局单独求解;王定益等同时求解单元内的设施摆放顺序和单元间的摆放顺序;Ho等提出一种单元布局的集成设计框架;Shahram等假定各设施面积相等,使用二次分配问题(QuadraticAssignmentProblem,QAP)模型求解单元间布局和单元内设施布局;WANG假定设施和单元的位置不受布局空间的约束,提出一种同时考虑单元内设施布局和单元间布局的集成设计方法。本文以单元布局为研究对象,考虑单元内设施布局和单元间布局,并利用并行工程的思想提出对单元布局的两个阶段进行集成优化的方法,建立了相应的多目标优化模型。针对模型求解,本文提出了基于结构化编码的改进协同粒子群算法。1单元配置问题的建模1.1生产单元内部设施布局优化设施布局指在一定的生产环境下,制造系统设计人员根据生产方式确定制造系统中各设施的布置形式和位置。本文假定单元内的设施采用U型布局;单元间采用多行布置,并采用自动换行策略。为提高设备利用率,本文在各生产单元内部留有一定面积的物料暂存区。假设布局空间和设施均为矩形块状结构,其长和宽已知,且设施有横向和纵向两种摆放方式。现对单元内的设施布局和单元间布局进行优化,最小化物料搬运成本和设施占地面积。为了描述方便,引入以下基本符号:p(p=1,2,…,P)为零件编号;i和j(i,j=1,2,…,M)为设施编号;(xi,yi)为设施i的中心点坐标;li和wi分别为设施i的长度和宽度;c(c=1,2,…,Nc)为单元编号。1.2设施间物料输送由于大多数离散型制造企业多采用托盘、容器等单元化物料装载工具,对于加工零件p而言,若相邻工序先后访问设施i和j,则设备i和j由p引起的物流量为式中:npij表示加工零件p时,从设施i到设施j的转移次数,若p的加工路径为4-3-2-1-4-3,则n4p,3=2,n3p,4=0;Vp为零件p的加工批量,Hp为零件p的搬运批量,Vp和Hp为已知常量。设施间总的物料搬运距离可描述为式中ceil()表示对数值进行向上取整。此处取折线距离作为设施间距。1.3确定空间矩形包络面积设施布置应考虑紧凑性原则,即应提高设施的面积利用率,设施面积利用率可描述为式中:Si表示设施i的矩形包络面积,S表示整体布局的矩形包络面积。由于各设施的矩形包络面积为定值,该优化目标可等价于minS。式中:(xib,yib)表示设施i包络矩形的左下角坐标,(xjt,yjt)表示设施j包络矩形的右上角坐标。1.4基于归一化因子的筛选本文要解决的单元布置问题有两个目标,属于多目标优化问题。求解多目标优化问题即为求问题的Pareto最优解集,然后再由决策者根据相关信息和要求确定一个折中解(compromise),也称妥协解。为了保证两个优化目标统一的量纲,本文采用归一化因子。定义归一化因子η,μ:式中:α和β分别为总搬运距离和总占地面积的权重,由决策者给出,α+β=1。1.5限制分析1.5.1降低设备布局面积考虑到实际情况,本文在每个制造单元内增设一个物料暂存区。传统的设施布局问题统一了设施的摆放方向,同为横向或纵向,但该假设缩小了问题的解空间,对于横纵比相差较大的设备,布局结果的占地面积得不到优化。为增大问题的解空间并降低设施布局面积,本文假设:(1)设施有横向和纵向两种摆放方式;(2)制造单元内统一采用U型布局;(3)设备的出入口视为同一位置,为设备包络矩形的中心位置;(4)同一侧设施的中心点在同一水平线上。如图1所示。若设施i和j在同一侧,则满足约束条件|xi-xj|≥(hi+hj)/2+dhij,yi=yj;(8)若设施i和j在不同侧,则满足约束条件|yi-yj|≥(vi+vj)/2+dvij,yi≠yj。(9)式中:hi和vi分别表示设备i的横向和纵向长度,当设备横向摆放时,hi=li,vi=wi,否则hi=wi,vi=li;dhij为单元内设备间的横向安全距离,dvij为单元内设备间的纵向安全距离。式(8)和式(9)使设备i和j保持一定的安全距离。1.5.2单元拓扑形状单元间采用多行布置,并假设:(1)同一行生产单元的中心位于同一水平线上;(2)同一行中各单元长度和相互间距之和如果大于最大布局空间长度,则采取自动换行策略。本文引入生产单元的拓扑模型,将生产单元看作规则的矩形形状,如图2所示。根据物流顺畅的要求,考虑到单元间距,包络矩形加入了这一距离,设d为单元间距,Lc和Wc分别为单元c拓扑矩形的长和宽,(xc,yc)和(xcb,ycb)分别表示单元c拓扑结构的中心点坐标和左下角坐标。定义决策变量生产单元应满足如下约束条件:式中:约束条件(10)表示每一生产单元所在行数是唯一的;式(11)和式(12)表示若单元c和单元c′在同一行,则单元拓扑矩形的中心点坐标处于同一水平线,且单元的拓扑结构在x方向上不重叠;式(13)表示若单元c和单元c′不同行,则单元的拓扑形状在y方向上不重叠;式(14)和式(15)表示单元c必须满足布局空间约束,不能超出所要求的布局空间。2解决问题的解决和算法的设计2.1极值点pbest粒子群优化算法(ParticleSwarmOptimization,PSO)是一个反复迭代的过程,每次迭代中,粒子通过跟踪两个极值点来更新自己:第一个极值点是粒子本身所找到的历史最优解,称为个体极值点(Pbest);另一个极值点是整个种群目前找到的最优解,称为全局极值点(Gbest)。找到这两个最优解后,粒子根据式(16)~式(18)更新自己的速度和位置。式中:a1和a2为加速系数,r1和r2为区间上的随机数,xik为第i个粒子在第k次迭代中的位置,Pbest为第i个粒子的历史最优位置,Gbest为所有粒子的历史最优位置,ω为设定的约束系数,定义式中:ωmax和ωmin为已知常量,T为迭代的总次数,k为已迭代次数。2.2子群协同进化和基因库构建PSO具有隐含并行性,搜索过程是从问题解的一个集合开始,而PSO搜索更新是跟随当前最优解的过程,信息的流动方向是单向的,故存在早熟现象,容易陷入局部最优解。为此,提出改进的多粒子群协同进化模型,将粒子群合理划分为m个子群,前m-1个子群根据本群搜索到的最优位置更新该群粒子的速度,第m个子群则根据所有粒子搜索到的最优位置更新该群粒子的速度。各子群基于信息的迁移和共享实现协同进化,以提高全局的性能;同时构建各子群的基因库,通过对基因粒子进行遗传操作,使产生的新粒子代替较劣的非基因粒子,从而促进粒子间信息的双向流动。迭代过程中,对于各子群,粒子按某种规则进化的同时,选择较优粒子构建基因库。假设p1和p2分别表示来自基因库的父代个体;q为介于0和1之间的常数。对于新粒子xi的第j维xij,其具体生成方式如下:新生成的粒子xi用于替代较劣的非基因粒子。2.3单元的编码/解码单元设施布局问题的求解有两个难点:(1)单元设施布置问题属于离散空间的非数值优化问题,而PSO算法属于连续空间域的优化算法;(2)一般的编码方法只用于解决一个方面的问题,而本文的单元设施布局问题要求设计的编码方式能同时描述单元间布局、单元内设施布置、设施摆放方向。文献利用实数编码及映射方法,解决了连续数值优化算法求解离散问题的矛盾,将PSO算法应用于求解单向环形布局问题。本文设计了一种新的多维实数编码方式,实现从粒子到设施布局形式的映射,使PSO算法成功应用到单元布局问题求解中。本文采用结构化编码方法,如图3所示,粒子编码被分成三部分。各部分编码/解码解释如下:(1)单元位置编码该部分是长度为Nc的正实数编码串,每一个编码位对应一个生产单元,解码时比较编码位上的实数大小,实数的排列顺序即为生产单元的排列顺序。为满足单元间的约束条件,各单元的间距不小于安全距离,且采用自动换行策略,若同一行中各单元的横向长度和单元间的距离之和超出设备布局范围,则该单元在下一行中进行布置。(2)设备位置编码该部分是长度为M的正实数编码串,解码时对属于同一单元的设备所对应的实数编码进行排序,实数的排列顺序即为该单元中设备的排列顺序。(3)设备摆放方向编码该部分是长度为M的正整数编码,若该整数为奇数,则设备横向摆放;若为偶数,则设备纵向摆放。本文采用的算例(如图3)有7台设备(i,j=1,2,…,7),已知单元划分结果为c1={1,4,5},c2={3,6},c3={2,7};单元位置编码为(10.5,3.2,11.6),解码后的单元排列次序为2-1-3;设备位置编码为(2.1,1.3,13.6,0.3,8.2,3.5,1.6),解码后的设备排列顺序为6-3|5-1-4|7-2;设备摆放方向编码为(2,7,3,4,15,19,10),解码后为“纵—横—横—纵—横—横—纵”。通过对粒子的各段实数串进行解码,确定单元间的摆放顺序、单元内各设施的摆放顺序和摆放方向。已知设施和单元间的安全距离、生产任务、各零件的生产路径,可以根据式(1)~式(4)计算物料搬运距离和设施布局结果的面积利用率。2.4基于全局最优位置的转化过程算法采用改进协同粒子群优化(CooperativeParticleSwarmOptimization,CPSO)求解单元设施布置问题,算法流程设计如下:步骤1确定粒子数量,将粒子划分为m个子群;初始化粒子位置和速度,将粒子的个体极值Pbest设置为当前位置,将前m-1个子群的Gbest设置为该群最优粒子位置,第m个子群的Gbest为所有粒子的最优位置;令全局最优位置未优化的次数n=0。步骤2判断算法是否达到最大迭代次数,若是,则停止迭代,输出结果,否则转步骤3。步骤3判断全局最优位置是否已连续N代没有优化,若是则停止迭代,输出结果,否则转步骤4。步骤4对每一种群,按式(16)~式(18)对粒子的速度和位置进行更新,其中前m-1个子群的Gbest为该群粒子最优位置,第m个子群的Gbest为全局粒子最优位置。步骤5计算所有粒子的适应值。对每一种群,更新其Pbest和Gbest的粒子位置。步骤6判断全局最优解是否被优化,若是则重置n=0,否则n=n+1。步骤7对粒子适应度进行排序,并按指定比率选择较优粒子构建基因库,根据基因库进行遗传操作。步骤8将通过遗传操作产生的新个体替代相同数量的非基因粒子,转步骤2。算法流程图如图4所示。3优化单元布局某公司由于现有的车间布局不能满足生产要求,决定对车间设备进行重新布局。通过考虑单元间生产能力的均衡等因素,完成生产单元的构建,现主要对单元内设施布局和单元间布局进行规划。单元划分结果和单元内各设备尺寸如表1所示,加工工件的生产批量、搬运批量、工艺路径如表2所示。设定算法最大迭代次数Gen=1000,种群规模Size=60,基因粒子比例为0.4,全局最优解连续没有进化的代数N=300,学习参数a1=a2=2,最大惯性系数权重ωmax=0.9,最小惯性系数ωmin=0.4;物流权重α=0.7,面积权重β=0.3。待布局的车间为25m×20m的矩形平面,同一单元内,相邻设施间距离为1.2m,相邻单元的间距为3.0m,每一单元内的物料暂存区大小为2m×2m。传统方法是对单元布局的两个阶段单独进行求解;文献同时求解单元内设施布置和单元间布置,但未考虑设施的摆放方向;文献采用模拟退火(SimulatedAnnealing,SA)算法对单元内布局和单元间布局进行集成求解,该方法不能同时优化设施的摆放方向。本文通过分别对单元间布局、单元内布局和单元内设施摆放方向进行结构化编码,同时考虑布局问题涉及的三个方面,并利用CPSO求解。为比较说明本文模型和算法的有效性,采用文献中的SA算法求解传统布局模型,并分别采用PSO算法和CPSO算法对传统布局模型、文献模型以及本文模型进行求解。CPSO求解模型时,种群数目n的大小会给结果带来影响:如果n过小,则种群间信息流动较少;如果n过大,则种群内部粒子数量较少,协同进化效果不显著,将会降低算法的寻优能力。本文分别取n=3,4,5,计算数值n对优化结果的影响。本文使用MATLAB7.0在Pentium2.1GHz平台上实现算法,利用SA,PSO和CPSO三种算法分别求解各模型30次,结果如表3所示。表3中:珚Z表示目标函数的平均值,D/S分别表示最小目标值下的物料总搬运距离和整体布局面积。图5所示为PSO和CPSO(n取4)分别采用传统模型、文献模型和本文模型求解仿真实例所得到的目标值的分布情况。对于表3,通过对图5所示实验结果的分析可知:(1)表3中SA和PSO的求解结果表明,与求解离散优化问题的SA算法相比,PSO算法可产生类似的布局结果,由此说明PSO算法能有效地解决设施布局等离散优化问题。(2)对于CPSO求解本文实例,当粒子种群数目为4(n=4)时,CPSO具有更好的算法性能。CPSO在子群数量分别取3,4,5时,对传统模型、文献模型以及本文模型求解,表3的CPSO部分表明:n=4时,CPSO求解所得到的布局结果最优。(3)CPSO较PSO具有更好的寻优能力。使用CPSO和PSO,在三种不同模型的基础上分别对本文实例进行求解,比较表3的PSO部分和CPSO部