基于結(jié)構(gòu)化編碼的多粒子群協(xié)同進(jìn)化算法

基于結(jié)構(gòu)化編碼的多粒子群協(xié)同進(jìn)化算法

0單元布局的集成優(yōu)化問(wèn)題單元生產(chǎn)是一種先進(jìn)的生產(chǎn)技術(shù)應(yīng)用，是一種適用于現(xiàn)在多品種、少批生產(chǎn)的先進(jìn)生產(chǎn)技術(shù)的先進(jìn)生產(chǎn)方法。它結(jié)合了勞動(dòng)監(jiān)察的高效率和f自行車(chē)的高生產(chǎn)率，解決了傳統(tǒng)生產(chǎn)方法下產(chǎn)量與生產(chǎn)靈活性之間的矛盾。構(gòu)造單元生產(chǎn)系統(tǒng)需研究單元構(gòu)建、單元內(nèi)設(shè)備布局、單元間布局三個(gè)問(wèn)題。單元構(gòu)建階段主要解決最佳設(shè)備及單元能力均衡、最小跨單元加工等問(wèn)題,完成對(duì)生產(chǎn)單元的劃分,并輸出單元間的負(fù)荷平衡率、產(chǎn)品跨單元加工的次數(shù)以及產(chǎn)品的生產(chǎn)批量等;單元布局是在單元構(gòu)建的基礎(chǔ)上確定各單元和設(shè)施的擺放位置,并輸出單元之間和設(shè)施之間的布局形式和位置。大量學(xué)者對(duì)單元構(gòu)建技術(shù)進(jìn)行了研究,而對(duì)單元設(shè)施布局方面的研究較少。傳統(tǒng)方法是對(duì)單元設(shè)施布局問(wèn)題中的單元內(nèi)布局和單元間布局單獨(dú)求解;王定益等同時(shí)求解單元內(nèi)的設(shè)施擺放順序和單元間的擺放順序;Ho等提出一種單元布局的集成設(shè)計(jì)框架;Shahram等假定各設(shè)施面積相等,使用二次分配問(wèn)題(QuadraticAssignmentProblem,QAP)模型求解單元間布局和單元內(nèi)設(shè)施布局;WANG假定設(shè)施和單元的位置不受布局空間的約束,提出一種同時(shí)考慮單元內(nèi)設(shè)施布局和單元間布局的集成設(shè)計(jì)方法。本文以單元布局為研究對(duì)象,考慮單元內(nèi)設(shè)施布局和單元間布局,并利用并行工程的思想提出對(duì)單元布局的兩個(gè)階段進(jìn)行集成優(yōu)化的方法,建立了相應(yīng)的多目標(biāo)優(yōu)化模型。針對(duì)模型求解,本文提出了基于結(jié)構(gòu)化編碼的改進(jìn)協(xié)同粒子群算法。1單元配置問(wèn)題的建模1.1生產(chǎn)單元內(nèi)部設(shè)施布局優(yōu)化設(shè)施布局指在一定的生產(chǎn)環(huán)境下,制造系統(tǒng)設(shè)計(jì)人員根據(jù)生產(chǎn)方式確定制造系統(tǒng)中各設(shè)施的布置形式和位置。本文假定單元內(nèi)的設(shè)施采用U型布局;單元間采用多行布置,并采用自動(dòng)換行策略。為提高設(shè)備利用率,本文在各生產(chǎn)單元內(nèi)部留有一定面積的物料暫存區(qū)。假設(shè)布局空間和設(shè)施均為矩形塊狀結(jié)構(gòu),其長(zhǎng)和寬已知,且設(shè)施有橫向和縱向兩種擺放方式?，F(xiàn)對(duì)單元內(nèi)的設(shè)施布局和單元間布局進(jìn)行優(yōu)化,最小化物料搬運(yùn)成本和設(shè)施占地面積。為了描述方便,引入以下基本符號(hào):p(p=1,2,…,P)為零件編號(hào);i和j(i,j=1,2,…,M)為設(shè)施編號(hào);(xi,yi)為設(shè)施i的中心點(diǎn)坐標(biāo);li和wi分別為設(shè)施i的長(zhǎng)度和寬度;c(c=1,2,…,Nc)為單元編號(hào)。1.2設(shè)施間物料輸送由于大多數(shù)離散型制造企業(yè)多采用托盤(pán)、容器等單元化物料裝載工具,對(duì)于加工零件p而言,若相鄰工序先后訪(fǎng)問(wèn)設(shè)施i和j,則設(shè)備i和j由p引起的物流量為式中:npij表示加工零件p時(shí),從設(shè)施i到設(shè)施j的轉(zhuǎn)移次數(shù),若p的加工路徑為4-3-2-1-4-3,則n4p,3=2,n3p,4=0;Vp為零件p的加工批量,Hp為零件p的搬運(yùn)批量,Vp和Hp為已知常量。設(shè)施間總的物料搬運(yùn)距離可描述為式中ceil()表示對(duì)數(shù)值進(jìn)行向上取整。此處取折線(xiàn)距離作為設(shè)施間距。1.3確定空間矩形包絡(luò)面積設(shè)施布置應(yīng)考慮緊湊性原則,即應(yīng)提高設(shè)施的面積利用率,設(shè)施面積利用率可描述為式中:Si表示設(shè)施i的矩形包絡(luò)面積,S表示整體布局的矩形包絡(luò)面積。由于各設(shè)施的矩形包絡(luò)面積為定值,該優(yōu)化目標(biāo)可等價(jià)于minS。式中:(xib,yib)表示設(shè)施i包絡(luò)矩形的左下角坐標(biāo),(xjt,yjt)表示設(shè)施j包絡(luò)矩形的右上角坐標(biāo)。1.4基于歸一化因子的篩選本文要解決的單元布置問(wèn)題有兩個(gè)目標(biāo),屬于多目標(biāo)優(yōu)化問(wèn)題。求解多目標(biāo)優(yōu)化問(wèn)題即為求問(wèn)題的Pareto最優(yōu)解集,然后再由決策者根據(jù)相關(guān)信息和要求確定一個(gè)折中解(compromise),也稱(chēng)妥協(xié)解。為了保證兩個(gè)優(yōu)化目標(biāo)統(tǒng)一的量綱,本文采用歸一化因子。定義歸一化因子η,μ:式中:α和β分別為總搬運(yùn)距離和總占地面積的權(quán)重,由決策者給出,α+β=1。1.5限制分析1.5.1降低設(shè)備布局面積考慮到實(shí)際情況,本文在每個(gè)制造單元內(nèi)增設(shè)一個(gè)物料暫存區(qū)。傳統(tǒng)的設(shè)施布局問(wèn)題統(tǒng)一了設(shè)施的擺放方向,同為橫向或縱向,但該假設(shè)縮小了問(wèn)題的解空間,對(duì)于橫縱比相差較大的設(shè)備,布局結(jié)果的占地面積得不到優(yōu)化。為增大問(wèn)題的解空間并降低設(shè)施布局面積,本文假設(shè):(1)設(shè)施有橫向和縱向兩種擺放方式;(2)制造單元內(nèi)統(tǒng)一采用U型布局;(3)設(shè)備的出入口視為同一位置,為設(shè)備包絡(luò)矩形的中心位置;(4)同一側(cè)設(shè)施的中心點(diǎn)在同一水平線(xiàn)上。如圖1所示。若設(shè)施i和j在同一側(cè),則滿(mǎn)足約束條件|xi-xj|≥(hi+hj)/2+dhij,yi=yj;(8)若設(shè)施i和j在不同側(cè),則滿(mǎn)足約束條件|yi-yj|≥(vi+vj)/2+dvij,yi≠yj。(9)式中:hi和vi分別表示設(shè)備i的橫向和縱向長(zhǎng)度,當(dāng)設(shè)備橫向擺放時(shí),hi=li,vi=wi,否則hi=wi,vi=li;dhij為單元內(nèi)設(shè)備間的橫向安全距離,dvij為單元內(nèi)設(shè)備間的縱向安全距離。式(8)和式(9)使設(shè)備i和j保持一定的安全距離。1.5.2單元拓?fù)湫螤顔卧g采用多行布置,并假設(shè):(1)同一行生產(chǎn)單元的中心位于同一水平線(xiàn)上;(2)同一行中各單元長(zhǎng)度和相互間距之和如果大于最大布局空間長(zhǎng)度,則采取自動(dòng)換行策略。本文引入生產(chǎn)單元的拓?fù)淠Ｐ?將生產(chǎn)單元看作規(guī)則的矩形形狀,如圖2所示。根據(jù)物流順暢的要求,考慮到單元間距,包絡(luò)矩形加入了這一距離,設(shè)d為單元間距,Lc和Wc分別為單元c拓?fù)渚匦蔚拈L(zhǎng)和寬,(xc,yc)和(xcb,ycb)分別表示單元c拓?fù)浣Y(jié)構(gòu)的中心點(diǎn)坐標(biāo)和左下角坐標(biāo)。定義決策變量生產(chǎn)單元應(yīng)滿(mǎn)足如下約束條件:式中:約束條件(10)表示每一生產(chǎn)單元所在行數(shù)是唯一的;式(11)和式(12)表示若單元c和單元c′在同一行,則單元拓?fù)渚匦蔚闹行狞c(diǎn)坐標(biāo)處于同一水平線(xiàn),且單元的拓?fù)浣Y(jié)構(gòu)在x方向上不重疊;式(13)表示若單元c和單元c′不同行,則單元的拓?fù)湫螤钤趛方向上不重疊;式(14)和式(15)表示單元c必須滿(mǎn)足布局空間約束,不能超出所要求的布局空間。2解決問(wèn)題的解決和算法的設(shè)計(jì)2.1極值點(diǎn)pbest粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)是一個(gè)反復(fù)迭代的過(guò)程,每次迭代中,粒子通過(guò)跟蹤兩個(gè)極值點(diǎn)來(lái)更新自己:第一個(gè)極值點(diǎn)是粒子本身所找到的歷史最優(yōu)解,稱(chēng)為個(gè)體極值點(diǎn)(Pbest);另一個(gè)極值點(diǎn)是整個(gè)種群目前找到的最優(yōu)解,稱(chēng)為全局極值點(diǎn)(Gbest)。找到這兩個(gè)最優(yōu)解后,粒子根據(jù)式(16)~式(18)更新自己的速度和位置。式中:a1和a2為加速系數(shù),r1和r2為區(qū)間上的隨機(jī)數(shù),xik為第i個(gè)粒子在第k次迭代中的位置,Pbest為第i個(gè)粒子的歷史最優(yōu)位置,Gbest為所有粒子的歷史最優(yōu)位置,ω為設(shè)定的約束系數(shù),定義式中:ωmax和ωmin為已知常量,T為迭代的總次數(shù),k為已迭代次數(shù)。2.2子群協(xié)同進(jìn)化和基因庫(kù)構(gòu)建PSO具有隱含并行性,搜索過(guò)程是從問(wèn)題解的一個(gè)集合開(kāi)始,而PSO搜索更新是跟隨當(dāng)前最優(yōu)解的過(guò)程,信息的流動(dòng)方向是單向的,故存在早熟現(xiàn)象,容易陷入局部最優(yōu)解。為此,提出改進(jìn)的多粒子群協(xié)同進(jìn)化模型,將粒子群合理劃分為m個(gè)子群,前m-1個(gè)子群根據(jù)本群搜索到的最優(yōu)位置更新該群粒子的速度,第m個(gè)子群則根據(jù)所有粒子搜索到的最優(yōu)位置更新該群粒子的速度。各子群基于信息的遷移和共享實(shí)現(xiàn)協(xié)同進(jìn)化,以提高全局的性能;同時(shí)構(gòu)建各子群的基因庫(kù),通過(guò)對(duì)基因粒子進(jìn)行遺傳操作,使產(chǎn)生的新粒子代替較劣的非基因粒子,從而促進(jìn)粒子間信息的雙向流動(dòng)。迭代過(guò)程中,對(duì)于各子群,粒子按某種規(guī)則進(jìn)化的同時(shí),選擇較優(yōu)粒子構(gòu)建基因庫(kù)。假設(shè)p1和p2分別表示來(lái)自基因庫(kù)的父代個(gè)體;q為介于0和1之間的常數(shù)。對(duì)于新粒子xi的第j維xij,其具體生成方式如下:新生成的粒子xi用于替代較劣的非基因粒子。2.3單元的編碼/解碼單元設(shè)施布局問(wèn)題的求解有兩個(gè)難點(diǎn):(1)單元設(shè)施布置問(wèn)題屬于離散空間的非數(shù)值優(yōu)化問(wèn)題,而PSO算法屬于連續(xù)空間域的優(yōu)化算法;(2)一般的編碼方法只用于解決一個(gè)方面的問(wèn)題,而本文的單元設(shè)施布局問(wèn)題要求設(shè)計(jì)的編碼方式能同時(shí)描述單元間布局、單元內(nèi)設(shè)施布置、設(shè)施擺放方向。文獻(xiàn)利用實(shí)數(shù)編碼及映射方法,解決了連續(xù)數(shù)值優(yōu)化算法求解離散問(wèn)題的矛盾,將PSO算法應(yīng)用于求解單向環(huán)形布局問(wèn)題。本文設(shè)計(jì)了一種新的多維實(shí)數(shù)編碼方式,實(shí)現(xiàn)從粒子到設(shè)施布局形式的映射,使PSO算法成功應(yīng)用到單元布局問(wèn)題求解中。本文采用結(jié)構(gòu)化編碼方法,如圖3所示,粒子編碼被分成三部分。各部分編碼/解碼解釋如下:(1)單元位置編碼該部分是長(zhǎng)度為Nc的正實(shí)數(shù)編碼串,每一個(gè)編碼位對(duì)應(yīng)一個(gè)生產(chǎn)單元,解碼時(shí)比較編碼位上的實(shí)數(shù)大小,實(shí)數(shù)的排列順序即為生產(chǎn)單元的排列順序。為滿(mǎn)足單元間的約束條件,各單元的間距不小于安全距離,且采用自動(dòng)換行策略,若同一行中各單元的橫向長(zhǎng)度和單元間的距離之和超出設(shè)備布局范圍,則該單元在下一行中進(jìn)行布置。(2)設(shè)備位置編碼該部分是長(zhǎng)度為M的正實(shí)數(shù)編碼串,解碼時(shí)對(duì)屬于同一單元的設(shè)備所對(duì)應(yīng)的實(shí)數(shù)編碼進(jìn)行排序,實(shí)數(shù)的排列順序即為該單元中設(shè)備的排列順序。(3)設(shè)備擺放方向編碼該部分是長(zhǎng)度為M的正整數(shù)編碼,若該整數(shù)為奇數(shù),則設(shè)備橫向擺放;若為偶數(shù),則設(shè)備縱向擺放。本文采用的算例(如圖3)有7臺(tái)設(shè)備(i,j=1,2,…,7),已知單元?jiǎng)澐纸Y(jié)果為c1={1,4,5},c2={3,6},c3={2,7};單元位置編碼為(10.5,3.2,11.6),解碼后的單元排列次序?yàn)?-1-3;設(shè)備位置編碼為(2.1,1.3,13.6,0.3,8.2,3.5,1.6),解碼后的設(shè)備排列順序?yàn)?-3|5-1-4|7-2;設(shè)備擺放方向編碼為(2,7,3,4,15,19,10),解碼后為“縱—橫—橫—縱—橫—橫—縱”。通過(guò)對(duì)粒子的各段實(shí)數(shù)串進(jìn)行解碼,確定單元間的擺放順序、單元內(nèi)各設(shè)施的擺放順序和擺放方向。已知設(shè)施和單元間的安全距離、生產(chǎn)任務(wù)、各零件的生產(chǎn)路徑,可以根據(jù)式(1)~式(4)計(jì)算物料搬運(yùn)距離和設(shè)施布局結(jié)果的面積利用率。2.4基于全局最優(yōu)位置的轉(zhuǎn)化過(guò)程算法采用改進(jìn)協(xié)同粒子群優(yōu)化(CooperativeParticleSwarmOptimization,CPSO)求解單元設(shè)施布置問(wèn)題,算法流程設(shè)計(jì)如下:步驟1確定粒子數(shù)量,將粒子劃分為m個(gè)子群;初始化粒子位置和速度,將粒子的個(gè)體極值Pbest設(shè)置為當(dāng)前位置,將前m-1個(gè)子群的Gbest設(shè)置為該群最優(yōu)粒子位置,第m個(gè)子群的Gbest為所有粒子的最優(yōu)位置;令全局最優(yōu)位置未優(yōu)化的次數(shù)n=0。步驟2判斷算法是否達(dá)到最大迭代次數(shù),若是,則停止迭代,輸出結(jié)果,否則轉(zhuǎn)步驟3。步驟3判斷全局最優(yōu)位置是否已連續(xù)N代沒(méi)有優(yōu)化,若是則停止迭代,輸出結(jié)果,否則轉(zhuǎn)步驟4。步驟4對(duì)每一種群,按式(16)~式(18)對(duì)粒子的速度和位置進(jìn)行更新,其中前m-1個(gè)子群的Gbest為該群粒子最優(yōu)位置,第m個(gè)子群的Gbest為全局粒子最優(yōu)位置。步驟5計(jì)算所有粒子的適應(yīng)值。對(duì)每一種群,更新其Pbest和Gbest的粒子位置。步驟6判斷全局最優(yōu)解是否被優(yōu)化,若是則重置n=0,否則n=n+1。步驟7對(duì)粒子適應(yīng)度進(jìn)行排序,并按指定比率選擇較優(yōu)粒子構(gòu)建基因庫(kù),根據(jù)基因庫(kù)進(jìn)行遺傳操作。步驟8將通過(guò)遺傳操作產(chǎn)生的新個(gè)體替代相同數(shù)量的非基因粒子,轉(zhuǎn)步驟2。算法流程圖如圖4所示。3優(yōu)化單元布局某公司由于現(xiàn)有的車(chē)間布局不能滿(mǎn)足生產(chǎn)要求,決定對(duì)車(chē)間設(shè)備進(jìn)行重新布局。通過(guò)考慮單元間生產(chǎn)能力的均衡等因素,完成生產(chǎn)單元的構(gòu)建,現(xiàn)主要對(duì)單元內(nèi)設(shè)施布局和單元間布局進(jìn)行規(guī)劃。單元?jiǎng)澐纸Y(jié)果和單元內(nèi)各設(shè)備尺寸如表1所示,加工工件的生產(chǎn)批量、搬運(yùn)批量、工藝路徑如表2所示。設(shè)定算法最大迭代次數(shù)Gen=1000,種群規(guī)模Size=60,基因粒子比例為0.4,全局最優(yōu)解連續(xù)沒(méi)有進(jìn)化的代數(shù)N=300,學(xué)習(xí)參數(shù)a1=a2=2,最大慣性系數(shù)權(quán)重ωmax=0.9,最小慣性系數(shù)ωmin=0.4;物流權(quán)重α=0.7,面積權(quán)重β=0.3。待布局的車(chē)間為25m×20m的矩形平面,同一單元內(nèi),相鄰設(shè)施間距離為1.2m,相鄰單元的間距為3.0m,每一單元內(nèi)的物料暫存區(qū)大小為2m×2m。傳統(tǒng)方法是對(duì)單元布局的兩個(gè)階段單獨(dú)進(jìn)行求解;文獻(xiàn)同時(shí)求解單元內(nèi)設(shè)施布置和單元間布置,但未考慮設(shè)施的擺放方向;文獻(xiàn)采用模擬退火(SimulatedAnnealing,SA)算法對(duì)單元內(nèi)布局和單元間布局進(jìn)行集成求解,該方法不能同時(shí)優(yōu)化設(shè)施的擺放方向。本文通過(guò)分別對(duì)單元間布局、單元內(nèi)布局和單元內(nèi)設(shè)施擺放方向進(jìn)行結(jié)構(gòu)化編碼,同時(shí)考慮布局問(wèn)題涉及的三個(gè)方面,并利用CPSO求解。為比較說(shuō)明本文模型和算法的有效性,采用文獻(xiàn)中的SA算法求解傳統(tǒng)布局模型,并分別采用PSO算法和CPSO算法對(duì)傳統(tǒng)布局模型、文獻(xiàn)模型以及本文模型進(jìn)行求解。CPSO求解模型時(shí),種群數(shù)目n的大小會(huì)給結(jié)果帶來(lái)影響:如果n過(guò)小,則種群間信息流動(dòng)較少;如果n過(guò)大,則種群內(nèi)部粒子數(shù)量較少,協(xié)同進(jìn)化效果不顯著,將會(huì)降低算法的尋優(yōu)能力。本文分別取n=3,4,5,計(jì)算數(shù)值n對(duì)優(yōu)化結(jié)果的影響。本文使用MATLAB7.0在Pentium2.1GHz平臺(tái)上實(shí)現(xiàn)算法,利用SA,PSO和CPSO三種算法分別求解各模型30次,結(jié)果如表3所示。表3中:珚Z表示目標(biāo)函數(shù)的平均值,D/S分別表示最小目標(biāo)值下的物料總搬運(yùn)距離和整體布局面積。圖5所示為PSO和CPSO(n取4)分別采用傳統(tǒng)模型、文獻(xiàn)模型和本文模型求解仿真實(shí)例所得到的目標(biāo)值的分布情況。對(duì)于表3,通過(guò)對(duì)圖5所示實(shí)驗(yàn)結(jié)果的分析可知:(1)表3中SA和PSO的求解結(jié)果表明,與求解離散優(yōu)化問(wèn)題的SA算法相比,PSO算法可產(chǎn)生類(lèi)似的布局結(jié)果,由此說(shuō)明PSO算法能有效地解決設(shè)施布局等離散優(yōu)化問(wèn)題。(2)對(duì)于CPSO求解本文實(shí)例,當(dāng)粒子種群數(shù)目為4(n=4)時(shí),CPSO具有更好的算法性能。CPSO在子群數(shù)量分別取3,4,5時(shí),對(duì)傳統(tǒng)模型、文獻(xiàn)模型以及本文模型求解,表3的CPSO部分表明:n=4時(shí),CPSO求解所得到的布局結(jié)果最優(yōu)。(3)CPSO較PSO具有更好的尋優(yōu)能力。使用CPSO和PSO,在三種不同模型的基礎(chǔ)上分別對(duì)本文實(shí)例進(jìn)行求解,比較表3的PSO部分和CPSO部