陳華江，趙翠蓮，范志堅，黃松恩，趙 盟

(上海大學(xué)機(jī)電工程與自動化學(xué)院，上海 200072)

一種多基元類的布局遷移自適應(yīng)算法及在閘機(jī)設(shè)計中的應(yīng)用*

陳華江，趙翠蓮，范志堅，黃松恩，趙 盟

(上海大學(xué)機(jī)電工程與自動化學(xué)院，上海 200072)

布局問題研究物體的布局先后或布局定位以滿足設(shè)計要求，布局遷移設(shè)計是在已有布局基礎(chǔ)上高效設(shè)計新布局的方法。在軌道交通自動控制系統(tǒng)中，閘機(jī)表面?zhèn)鞲衅鞯牟季謱θ伺c物的識別有重要的影響。為了實現(xiàn)閘機(jī)在不同地域環(huán)境中的快速設(shè)計，首先以閘機(jī)布局中的傳感器作為研究對象，進(jìn)行基元劃分，提出了多種基元類型；并分析了基于拓?fù)浣Y(jié)構(gòu)的基元遷移變換方法，研究了人群特征因素、機(jī)械結(jié)構(gòu)約束的數(shù)學(xué)表達(dá)；然后提出基于包圍圓搜索的基元運動與干涉分析算法，其參數(shù)能夠根據(jù)求解精度進(jìn)行自適應(yīng)調(diào)整；并利用多目標(biāo)歸一化函數(shù)對各基元的解進(jìn)行擇優(yōu)，以獲取最終布局。最后以18對傳感器的閘機(jī)布局設(shè)計為例進(jìn)行實例分析，應(yīng)用此方法并借助于Visual Basic可視化編譯平臺，實現(xiàn)了閘機(jī)在不同地域環(huán)境中的傳感器布局快速設(shè)計。

布局遷移設(shè)計；傳感器；基元；包圍圓；自適應(yīng)算法

1 引言

布局問題是給定一個布局空間和若干待布物體，將待布物體按一定的規(guī)則擺放在空間中以滿足必要的約束，并達(dá)到某種最優(yōu)指標(biāo)[1]，其研究的是布局物體的布局先后或布局位置的定位以滿足在空間中放置的物體最多，或空間利用率最大等指標(biāo)?，F(xiàn)階段，一些基于遺傳算法、圖論、模擬退火算法的自適應(yīng)算法在布局問題中都有一些應(yīng)用[2～4]，這些算法能根據(jù)布局約束與布局目標(biāo)自動調(diào)整算法參數(shù)，以提高搜索效率和求解精度。布局求解時使用 Bottom-Up方式，首先產(chǎn)生初始解，再根據(jù)算法逐步尋優(yōu)，初始解的選擇對解的質(zhì)量和求解效率影響很大，因而有些學(xué)者專門研究布局初始方案的生成方法[5,6]。在電子設(shè)計自動化EDA(Electronic Design Automation)領(lǐng)域，布局遷移設(shè)計LMD(Layout Migration Design)是在布局壓縮(Layout Compaction)基礎(chǔ)上發(fā)展起來的在已有布局基礎(chǔ)上高效設(shè)計新布局的方法[7]。LMD通過在初始布局中建立拓?fù)潢P(guān)系，并為拓?fù)洳季痔砑蛹s束，在布局變換中保持物體的拓?fù)浣Y(jié)構(gòu)不變，從而形成新的布局[8]。

在地鐵自動售檢票系統(tǒng)中，利用閘機(jī)上布置的傳感器，識別在通道內(nèi)人攜帶物的位置和行為，從而控制閘門阻擋機(jī)構(gòu)的啟閉，實現(xiàn)軌道交通進(jìn)出口的自動控制。其中，傳感器的布局位置對系統(tǒng)的識別效果有著重要的影響[9]，其布局方案受到地域人群特征和閘機(jī)本身結(jié)構(gòu)特征的影響。為了實現(xiàn)閘機(jī)在不同地域環(huán)境中的快速設(shè)計，本文受EDA領(lǐng)域中LMD技術(shù)的啟發(fā)，提出了一種利用已有的布局作為原始布局，建立自適應(yīng)算法，將上述影響因素歸納為布局約束，建立目標(biāo)函數(shù)實現(xiàn)快速布局的布局遷移設(shè)計優(yōu)化方法，并以18對傳感器的布局為例進(jìn)行了實例分析，實現(xiàn)了閘機(jī)在不同地域環(huán)境中的快速設(shè)計。

2 基元與布局物體

2.1 布局問題

2.2 基元的分類與運動

鑒于傳感器在閘機(jī)表面的安裝孔位結(jié)構(gòu)，在此將基點抽象成圓，如圖1所示，在平面布局空間建立坐標(biāo)系X-O-Y，基點為si，其中心坐標(biāo)為si(xi,yi)，則常見的平面基元如圖1所示。

Figure 1 Common primitives in flat space圖1 平面空間常見基元示意圖

以基元為載體對各基元的中心點進(jìn)行坐標(biāo)變換，實現(xiàn)相應(yīng)基元中各基點的重新布局，可以用式(1)移動變換和式(2)、式(3)旋轉(zhuǎn)變換對其描述：

(1)

(2)

(3)

3 布局空間基元自適應(yīng)算法

3.1 基于平面拓?fù)浣Y(jié)構(gòu)的基元運動

基元中的基點在保持基元拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上可以進(jìn)行平面運動。在閘機(jī)傳感器的布局遷移設(shè)計問題中，受當(dāng)?shù)厝巳禾卣饕蛩赜绊?，分別體現(xiàn)為身高和體厚因素，前者會改變傳感器布局設(shè)計中某些基點的垂直遷移變動，后者則影響水平方向的遷移變動，需要將這些設(shè)計影響因素與基元拓?fù)浣Y(jié)構(gòu)加以關(guān)聯(lián)。

(4)

(5)

3.2 基于包圍圓搜索的基元運動與干涉分析

在布局空間中基元通過一定方式的運動來避開布局空間中存在的幾何約束，為此本文提出一種基于包圍圓搜索求解的自適應(yīng)算法，并以圖2為例進(jìn)行算法介紹。

Figure 2 Primitives and constraints圖2 基元與約束

在平面布局空間里有待布局的基元，并存在兩種典型的幾何約束：圓形約束和多邊形約束，后者可以簡化為多個三角形約束問題。要求基點在做遷移時與約束不能有位置干涉。為此，首先對基元中心O(x,y)沿著包圍圓的極坐標(biāo)方向進(jìn)行平移，再繞著基元中心進(jìn)行旋轉(zhuǎn)運動，并判斷約束干涉，得到布局的可行解。該算法分五個步驟：

步驟1參數(shù)初始化：包圍圓算法參數(shù)Δr、m、l影響到求解的精度與效率，Δr是包圍圓半徑擴(kuò)大的最小增量，m、l分別是移動和旋轉(zhuǎn)時圓周等分?jǐn)?shù)量，為簡化模型，參數(shù)l由m進(jìn)行傳遞。Δr與相鄰兩次基元的位移之差(圖3)共同影響精度ε，如下式：

(6)

當(dāng)m≥6時，2*Δr*sin(π/m)≤Δr≤ε，為提高搜索效率，取初始值l=m=6，Δr=ε。

Figure 3 Schematic diagram of minimun displacement圖3 最小位移示意圖

步驟2構(gòu)造包圍圓：以每個基元的中心O(x,y)為圓心，構(gòu)造同心包圍圓，半徑分別為i×Δr，i=1,2,…,n-1，i=0為點O。對半徑為i×Δr的圓的圓弧進(jìn)行m等分，圓弧上得到m個點，其相對O(x,y)的坐標(biāo)為(i×Δr×cos(2πj/m)，i×Δr×sin(2πj/m)，j=0,1,2,…,m-1，如圖4所示。

Figure 4 Bounding circle圖4 包圍圓

步驟3平移和旋轉(zhuǎn)：按式(7)進(jìn)行移動，其中ψ為相關(guān)的一個約束中心C與基元中心O的向量與x軸正方向的夾角弧度(0≤ψ<2π)，如圖5所示。當(dāng)基元移到中心為O′(x′,y′)的位置時，按式(3)進(jìn)行繞基元中心的旋轉(zhuǎn)運動，以調(diào)整基元上基點的位置，將圓周l等分，由公式(8)得旋轉(zhuǎn)弧度θ，如圖6所示，式(9)為平移和旋轉(zhuǎn)總公式，即可解出P′；

(7)

(8)

(9)

Figure 5 Vector angle in radians ψ圖5 向量角弧度ψ

Figure 6 Primitive rotation in radians θ圖6 基元旋轉(zhuǎn)弧度θ

步驟4干涉判斷：經(jīng)過步驟3，得到了基元中各基點新的中心坐標(biāo)，根據(jù)基點形狀特征，反求出邊界坐標(biāo)方程，并判斷與約束的關(guān)系，如果還在約束內(nèi)，則重復(fù)執(zhí)行步驟2和步驟3，若在約束外，則輸出一組可行解。

圓類約束的干涉判斷如圖7所示，如果:

(10)

則基點在約束外，反之，則基點在約束內(nèi)。

Figure 7 Schematic diagram of circle class constraint judgement圖7 圓類約束判斷示意圖

以三角形為基礎(chǔ)的多邊形類約束判斷如圖8所示，D(x,y)是邊界點，

(11)

Figure 8 Schematic diagram of polygon class constraint judgement圖8 多邊形類約束判斷示意圖

如果θ∈[0,2π)時，

(12)

則基點在約束外，否則基點在約束內(nèi)。

步驟5步驟1中的參數(shù)進(jìn)行自適應(yīng)調(diào)整：精度要求為ε時，如果參數(shù)在初始值狀態(tài)下得不到可行解，則m、l自增，Δr自減，重復(fù)執(zhí)行步驟2～步驟5，直至得到可行解。

3.3 基于包圍圓自適應(yīng)算法的遷移布局目標(biāo)函數(shù)

通過上述計算，分別可以得到圖2中直線基元和三角形基元的多組可行解，為此考慮與初始布局最吻合的最小距離算法以及布局空間面積最小算法，提出歸一化的目標(biāo)函數(shù)。

(1)與初始布局最吻合。

(13)

(2)各基元組成的面積最小[10]。

(14)

設(shè)點p1(x1,y1)、p2(x2,y2)、…、pn(xn,yn)依次構(gòu)成首尾相接的凸多邊形，則：

(15)

歸一化處理之后目標(biāo)函數(shù)為：

(16)

其中,λ1、λ2為加權(quán)因子，需要根據(jù)工程實際中的側(cè)重程度來確定，其關(guān)系式為：

(17)

Z1j、Z2j為取第j組解時各自的取值。

4 算法應(yīng)用

閘機(jī)傳感器利用光電傳感器作為測量信號的元器件，探測乘客進(jìn)入通道、識別出行李與乘客以及判斷乘客離安全區(qū)的距離、保護(hù)乘客在安全區(qū)的安全通行、檢測乘客離開通道，以及檢測乘客是否有反向闖入通道內(nèi)部等，布局區(qū)域依次可分為進(jìn)入?yún)^(qū)、檢測區(qū)、安全區(qū)、監(jiān)測區(qū)、出行區(qū)。常用的傳感器對數(shù)有16對、18對、19對等，其中18對傳感器式的分布特點為沿閘門阻擋機(jī)構(gòu)中心軸對稱，容易實現(xiàn)雙向通行的判斷，被某廠商在國外得到成熟的應(yīng)用，即原有布局及其通行控制算法充分考慮了人群特征及行為的復(fù)雜性，但是在引進(jìn)到國內(nèi)時需要根據(jù)當(dāng)?shù)厍闆r重新進(jìn)行布局設(shè)計。

4.1 傳感器布局基元劃分

閘機(jī)傳感器布局是基于人體的關(guān)鍵特征位置如膝蓋、腰部、腳踝等而布局的。將18對傳感器根據(jù)人群特征映射劃分成10對基元，如圖9所示，s1與s2構(gòu)成橫線基元j1，s3、s4、s5構(gòu)成三角形基元j2，s7、s8構(gòu)成豎線基元j3，s6、s9為點基元j4、j5，s10,s11,…,s18分別是s1,s2,…,s9關(guān)于閘機(jī)中心y軸對稱的傳感器，則相應(yīng)的對稱基元有j6、j7、j8、j9、j10。

Figure 9 Primitive of gate sensor partition圖9 閘機(jī)傳感器基元劃分圖

4.2 基于VB的基元及設(shè)計約束表達(dá)

Visual Basic[11]具有可視化的用戶界面設(shè)計功能，利用VB作為求解平臺，可以將布局物體和約束在VB的界面中直觀地表達(dá)出來。

根據(jù)文獻(xiàn)[9]，在通行算法的約束下，新布局與原始布局在水平方向上的傳感器依次順序保持一致，由此可以推斷出應(yīng)用算法搜索解時對各基元只做移動，不涉及旋轉(zhuǎn)。圖10是原始布局在VB中的示意圖，對左側(cè)布局物體矩陣進(jìn)行直線基元和三角形基元表達(dá)：

此外，對稱基元：xi+9=-xi、yi+9=yi(i=1,2,…,9)；點基元：x2

Figure 10 Schematic diagram of original layout圖10 原始布局示意圖

Figure 11 Constraints of gate mechanical structure圖11 閘機(jī)機(jī)械結(jié)構(gòu)約束

將布局物體即傳感器抽象成半徑為r1=5mm的圓，構(gòu)成動態(tài)幾何約束；阻擋機(jī)構(gòu)的位置、閘機(jī)四周邊緣、立柱等位置不能放置傳感器，構(gòu)成靜態(tài)幾何約束，如圖11中約束1～約束9所示，傳感器在這些約束處需要讓位。以添加約束1和約束5為例的方法分別添加這些約束，并利用VB圖片框的繪圖方法在VB編譯界面中直觀地表達(dá)這些約束：

(1)圓類約束：VB的圓類表達(dá)為Picture1.Circle(X,Y),r,blue,a,b,ξ。其中，(x,y)為圓類中心坐標(biāo)，r為半徑，a與b為弧的起止點(缺省時為圓/橢圓)，ξ為縱橫比(缺省值為1，即圓)，約束1為橢圓弧，其約束形式為傳感器在此約束的下方，當(dāng)X-r

(2)三角形類約束：任何一個n邊形都可以看成是由n-2個彼此相鄰的三角形組成，而三角形是由三條邊首尾相接而成，VB直線表達(dá)為：Picture1.Line(x1,y1)-(x2,y2)。(x1,y1)與(x2,y2)分別為直線的起點和終點。約束5為矩形，其約束形式為傳感器在此約束的外面，則：xi+r1X2或yi+r1Y2，在本文所應(yīng)用的閘機(jī)中，X1=-28,X2=28,Y1=300,Y2=800。

4.3 基于VB的遷移布局求解

首先將人群特征作為一種布局遷移設(shè)計的驅(qū)動作用于原始布局，使得與人群特征相關(guān)的傳感器按3.1節(jié)進(jìn)行基元運動。與身高相關(guān)的基元有j1、j2、j4及與之左右對稱的基元j6、j7、j9。中國成年男女平均身高[12]分別為169.7cm、160.1cm，某國的為180.2cm、170.1cm，則式(4)中的a取0.94。兩地域的人體體厚有差異，但由于考慮氣候原因衣服厚度的修正量不同，其存在很多不確定性，本文不考慮體厚因素對遷移變換的影響，故b=0，只考慮身高因素。根據(jù)式(4)對這些基元的基點做運動變換。結(jié)果如下：

然后，將閘機(jī)機(jī)械結(jié)構(gòu)包括閘機(jī)的外型、支撐部件，閘門阻擋機(jī)構(gòu)等因素作為空間幾何約束，其表達(dá)為4.2節(jié)中的約束1～約束9，在對各基元進(jìn)行包圍圓搜索運動時進(jìn)行干涉檢查。

由于人群特征的復(fù)雜性，使得傳感器在定位時在保證算法精度前提下在一定范圍內(nèi)是可以浮動的。當(dāng)精度ε=1時，初始值Δr=1，m=6，由于基元不做旋轉(zhuǎn)運動，l取值無意義，求各布局物體圍成的面積優(yōu)化指標(biāo)可以用以j1、j2、j3、j5四個基元的中心點圍成的凸四邊形面積來等價，則式(16)中，根據(jù)工程實踐經(jīng)驗，取λ1=0.4，λ2=0.6。得到14組可行解，其中第四組為最優(yōu)解，式(16)中，目標(biāo)值Z=0.32，如圖12所示；此時基元j1、j2、j3、j4、j5中心坐標(biāo)分別為(-727,827)、(-362,735)、(-80,429)、(-352,390)、(-571,200)，得到的最優(yōu)布局如圖13所示，其左側(cè)布局物體矩陣為：

Figure 12 Object function value圖12 目標(biāo)函數(shù)值

Figure 13 New layout chematic diagram圖13 新布局示意圖

5 結(jié)束語

本文提出了一種多基元類的布局遷移自適應(yīng)算法，并在地鐵閘機(jī)傳感器布局方案設(shè)計中得到了應(yīng)用。以基元為基本獨立單位做布局的調(diào)整，既保持了拓?fù)潢P(guān)系，又降低了布局復(fù)雜度。參數(shù)Δr、m、l與求解精度或求解效率相關(guān)，會隨著求解過程進(jìn)行自適應(yīng)性調(diào)整，ψ確保包圍圓算法的搜索是從約束中心與基元中心的矢量方向開始，能提高搜索的有效性。但是，本文未考慮存在某些基點同時屬于多個基元的拓?fù)浼s束現(xiàn)象，這會對基元的運動以及多個基元的尋優(yōu)形成新的問題。另外，利用本文提出的算法雖然求得了最優(yōu)布局解，但如果要將閘機(jī)傳感器布局應(yīng)用于實際工程中，進(jìn)一步的三維仿真與樣機(jī)測試是必要的。

[1]ZhaJian-zhong,TangXiao-jun,LuYi-ping.Surveyonpackingproblems[J].JournalofComputer-AidedDesign&ComputerGraphics, 2002,14(8):705-712.(inChinese)

[2]YuShi-gen,LuJian-xia.Studyonfacilitylayoutproblemofmulti-objective,fixedconstraintbasedonGA[J].JournalofZhejiangUniversityofTechnology, 2010,38(4):401-405.(inChinese)

[3]FrickA,LudwigA,MehldauH.Afastadaptivelayoutalgorithmforundirectedgraphs[C]∥ProcoftheDIMACSInternationalWorkshoponGraphDrawing, 1994:388-403.

[4]FanXiao-ning,LinYan,JiZhuo-shang.Approachofshippipepathsroutingoptimizationbasedonadaptiveannealinggeneticalgorithm[J].JournalofDalianUniversityofTechnology, 2007,47(2):215-221.(inChinese)

[5]LuYi-ping,ZhaJian-zhong,LiJian-yong,etal.Patterngenerationandsolutionoflayoutproblembasedonneighboringminimumsearching[J].JournalofNorthernJiaotongUniversity, 2000,24(4):52-56.(inChinese)

[6]TengHong-fei,SunShou-lin.Turntheroundtablebalanceplateontherotatingtable-packingproblemofdrivingthebalancedperformanceconstraints[J].ScienceinChina(ASeries), 1994,24(7):755-760.(inChinese)

[7]ChinHsiungHsu,YaoWenChang,NassifSR.Simultaneouslayoutmigrationanddecompositionfordoublepatterningtechnology[J].Journals&Magazines, 2011,30(2):284-294.

[8]FuDS,ChaungYZ,LinYH,etal.Topology-drivencelllayoutmigrationwithcollinearconstraints[C]∥ProcofIEEEInternationalConferenceonComputerDesign(ICCD2009),2009:439-444.

[9]CaiYi-long.Logicaldesignandimplementationofsubwaystationaccessdoorticketmachine[D].Shanghai:ShanghaiUniversity,2012.(inChinese)

[10]HengFL,ChenZhan,TellezGE.AVLSIartworklegalizationtechniquebasedonanewcriterionofminimumlayoutperturbation[C]∥ProcofInternationalSymposiumonPhysicalDesign, 1997:116-121.

[11]ZhangShu-bing,DaiHong,ChenZhe.VisualBasic6.0entryandimprove[M].Beijing:TsinghuaUniversityPress, 1999.(inChinese)

[12]GB/T10000-1998.HumandimensionsofChineseadults[S].Beijing:GeneralAdministrationofQualitySupervision,InspectionandQuarantineofthePeople’sRepublicofChina,1988.(inChinese)

附中文參考文獻(xiàn):

[1] 查建中,唐曉君,陸一平.布局及布置設(shè)計問題求解自動化的理論與方法綜述[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2002,14(8):705-712.

[2] 余世根,魯建廈.基于GA的固定約束條件下多目標(biāo)車間設(shè)備布局問題研究[J].浙江工業(yè)大學(xué)學(xué)報, 2010,38(4):401-405.

[4] 范小寧,林焰,紀(jì)卓尚.基于自適應(yīng)退火遺傳算法的船舶管路布局優(yōu)化方法[J].大連理工大學(xué)學(xué)報,2007,47(2):215-221.

[5] 陸一平,查建中,李建勇,等.一種基于鄰接極小搜索的布局模式生成方法[J].北方交通大學(xué)學(xué)報,2000,24(4):52-56.

[6] 滕弘飛,孫守林,葛文海.轉(zhuǎn)動圓桌平衡擺盤—帶動平衡性能約束的Packing問題[J].中國科學(xué)(A輯),1994,24(7):755-760.

[9] 柴益龍.地鐵車站門式檢票機(jī)的通行邏輯設(shè)計及其實現(xiàn)[D].上海：上海大學(xué),2012.

[11] 張樹兵,戴紅,陳哲.VisualBasic6.0入門與提高[M].北京:清華大學(xué)出版社,1999.

[12]GB10000-88.中國成年人人體尺寸[S].北京：國家技術(shù)監(jiān)督局，1988.

CHENHua-jiang,born in 1987,MS,his research interests include CIMS & process layout.

趙翠蓮(1963-),女,上海人，博士，教授，研究方向為數(shù)字化測量和生機(jī)電工程。E-mail:clzhao@shu.edu.cn

ZHAOCui-lian,born in 1963,PhD,professor,her research interests include digital measurement，and bio-mechatronics engineering.

范志堅(1982-),男,山西臨汾人，碩士，工程師，研究方向為機(jī)電一體化。E-mail:chris2813@shu.edu.cn

FANZhi-jian,born in 1982,MS,engineer,his research interest includes mechatronics.

Anadaptivealgorithmformulti-primitiveslayoutmigrationanditsapplicationingatedesign

CHEN Hua-jiang,ZHAO Cui-lian,FAN Zhi-jian,HUANG Song-en,ZHAO Meng

(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072,China)

Layout problem is regarding the study on the arrangement of the order and position of the objects according to the design requirements, while layout migration design is a new and efficient layout method based on the existing layout. In the automatic control system of rail transportation, the sensor layout of the auto gate plays an important role in the identification of human body and objects. In order to achieve the rapid design of auto gate for different geographical environments, firstly, sensors in auto gate layout are taken as the research object and broken down into various kinds of primitives, multiple primitive types are proposed, the topological-structure-based primitive migration transformation method is analyzed, and the crowd characteristics factors and the mathematical expression of the mechanical structure constraints are studied. Secondly, the primitive motions and interference analysis algorithm based on the bounding circle search is proposed, whose parameters can be adjusted according to the solution precision, and multi-objective normalization function is utilized to search for the optimum solution out of all the feasible solutions for each primitive. Finally, with the help of the visualization compile platform Visual Basic, the method is applied to the sensor layout design for the auto gate with eighteen-pair sensors and fast sensor layout design of auto gate for different geographical environment is achieved.

layout migration design;sensor;primitive;bounding circle;adaptive algorithm

1007-130X(2014)05-0929-07

2012-12-05;

：2013-04-13

TP399

：A

10.3969/j.issn.1007-130X.2014.05.024

陳華江(1987-),男,浙江上虞人，碩士，研究方向為CIMS與工藝布局。E-mail:chjchj120@163.com

通信地址：312300 浙江省紹興市上虞區(qū)人民西路1801號

Address:1801 Renmin Rd West,Shangyu District,Shaoxing 312300,Zhejiang,P.R.China