一种多基元类的布局迁移自适应算法及在闸机设计中的应用*

陈华江，赵翠莲，范志坚，黄松恩，赵 盟

(上海大学机电工程与自动化学院，上海 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