一種多基元類的布局遷移自適應算法及在閘機設計中的應用*

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

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

一種多基元類的布局遷移自適應算法及在閘機設計中的應用*

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

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

布局問題研究物體的布局先后或布局定位以滿足設計要求，布局遷移設計是在已有布局基礎上高效設計新布局的方法。在軌道交通自動控制系統中，閘機表面傳感器的布局對人與物的識別有重要的影響。為了實現閘機在不同地域環境中的快速設計，首先以閘機布局中的傳感器作為研究對象，進行基元劃分，提出了多種基元類型；并分析了基于拓撲結構的基元遷移變換方法，研究了人群特征因素、機械結構約束的數學表達；然后提出基于包圍圓搜索的基元運動與干涉分析算法，其參數能夠根據求解精度進行自適應調整；并利用多目標歸一化函數對各基元的解進行擇優，以獲取最終布局。最后以18對傳感器的閘機布局設計為例進行實例分析，應用此方法并借助于Visual Basic可視化編譯平臺，實現了閘機在不同地域環境中的傳感器布局快速設計。

布局遷移設計；傳感器；基元；包圍圓；自適應算法

1 引言

布局問題是給定一個布局空間和若干待布物體，將待布物體按一定的規則擺放在空間中以滿足必要的約束，并達到某種最優指標[1]，其研究的是布局物體的布局先后或布局位置的定位以滿足在空間中放置的物體最多，或空間利用率最大等指標。現階段，一些基于遺傳算法、圖論、模擬退火算法的自適應算法在布局問題中都有一些應用[2～4]，這些算法能根據布局約束與布局目標自動調整算法參數，以提高搜索效率和求解精度。布局求解時使用 Bottom-Up方式，首先產生初始解，再根據算法逐步尋優，初始解的選擇對解的質量和求解效率影響很大，因而有些學者專門研究布局初始方案的生成方法[5,6]。在電子設計自動化EDA(Electronic Design Automation)領域，布局遷移設計LMD(Layout Migration Design)是在布局壓縮(Layout Compaction)基礎上發展起來的在已有布局基礎上高效設計新布局的方法[7]。LMD通過在初始布局中建立拓撲關系，并為拓撲布局添加約束，在布局變換中保持物體的拓撲結構不變，從而形成新的布局[8]。

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

2 基元與布局物體

2.1 布局問題

2.2 基元的分類與運動

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

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

以基元為載體對各基元的中心點進行坐標變換，實現相應基元中各基點的重新布局，可以用式(1)移動變換和式(2)、式(3)旋轉變換對其描述：

(1)

(2)

(3)

3 布局空間基元自適應算法

3.1 基于平面拓撲結構的基元運動

基元中的基點在保持基元拓撲結構的基礎上可以進行平面運動。在閘機傳感器的布局遷移設計問題中，受當地人群特征因素影響，分別體現為身高和體厚因素，前者會改變傳感器布局設計中某些基點的垂直遷移變動，后者則影響水平方向的遷移變動，需要將這些設計影響因素與基元拓撲結構加以關聯。

(4)

(5)

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

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

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

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

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

(6)

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

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

步驟2構造包圍圓：以每個基元的中心O(x,y)為圓心，構造同心包圍圓，半徑分別為i×Δr，i=1,2,…,n-1，i=0為點O。對半徑為i×Δr的圓的圓弧進行m等分，圓弧上得到m個點，其相對O(x,y)的坐標為(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平移和旋轉：按式(7)進行移動，其中ψ為相關的一個約束中心C與基元中心O的向量與x軸正方向的夾角弧度(0≤ψ<2π)，如圖5所示。當基元移到中心為O′(x′,y′)的位置時，按式(3)進行繞基元中心的旋轉運動，以調整基元上基點的位置，將圓周l等分，由公式(8)得旋轉弧度θ，如圖6所示，式(9)為平移和旋轉總公式，即可解出P′；

(7)

(8)

(9)

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

Figure 6 Primitive rotation in radians θ圖6 基元旋轉弧度θ

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

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

(10)

則基點在約束外，反之，則基點在約束內。

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

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

(11)

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

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

(12)

則基點在約束外，否則基點在約束內。

步驟5步驟1中的參數進行自適應調整：精度要求為ε時，如果參數在初始值狀態下得不到可行解，則m、l自增，Δr自減，重復執行步驟2～步驟5，直至得到可行解。

3.3 基于包圍圓自適應算法的遷移布局目標函數

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

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

(13)

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

(14)

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

(15)

歸一化處理之后目標函數為：

(16)

其中,λ1、λ2為加權因子，需要根據工程實際中的側重程度來確定，其關系式為：

(17)

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

4 算法應用

閘機傳感器利用光電傳感器作為測量信號的元器件，探測乘客進入通道、識別出行李與乘客以及判斷乘客離安全區的距離、保護乘客在安全區的安全通行、檢測乘客離開通道，以及檢測乘客是否有反向闖入通道內部等，布局區域依次可分為進入區、檢測區、安全區、監測區、出行區。常用的傳感器對數有16對、18對、19對等，其中18對傳感器式的分布特點為沿閘門阻擋機構中心軸對稱，容易實現雙向通行的判斷，被某廠商在國外得到成熟的應用，即原有布局及其通行控制算法充分考慮了人群特征及行為的復雜性，但是在引進到國內時需要根據當地情況重新進行布局設計。

4.1 傳感器布局基元劃分

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

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

4.2 基于VB的基元及設計約束表達

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

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

此外，對稱基元：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 閘機機械結構約束

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

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

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

4.3 基于VB的遷移布局求解

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

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

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

Figure 12 Object function value圖12 目標函數值

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

5 結束語

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

[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)

附中文參考文獻:

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

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

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

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

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

[9] 柴益龍.地鐵車站門式檢票機的通行邏輯設計及其實現[D].上海：上海大學,2012.

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

[12]GB10000-88.中國成年人人體尺寸[S].北京：國家技術監督局，1988.

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

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

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

范志堅(1982-),男,山西臨汾人，碩士，工程師，研究方向為機電一體化。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 浙江省紹興市上虞區人民西路1801號

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