计算机联锁控制系统的进路生成算法研究

1、计算机联锁控制系统的进路生成算法研究徐洪泽燕永田(北方交通大学电子信息工程学院,北京100044徐立新(北京理工大学自控系,北京100081关键词计算机联锁进路生成算法遗传算法分类号TP273Study on the G enerating R oute Algorithm ofComputer 2based Interlocking SystemXu Hongze Yan Y ongtianCollege of Electronics and Information Engineering ,Northern Jiaotong University ,Beijing 100044Xu Lix

2、in(Department of Automatic Control ,Beijing Institute of Technology ,Beijing 100044Abstract A method resolving the railway station graph effectively is proposed.The subset chain composed of sections is constructed.Based on the above treatment ,the generating route problem is converted into optimizat

3、ion problem with variant con 2strained condition ,and by dealing with the subset ,the variant constrained condition is eliminated.Then the genetic algorithm suitable for generating route is proposed.Theo 2retical analysis and simulation results show the effectiveness and practicality of the gen 2era

4、ting route algorithm proposed in this paper.K ey w ords computer 2based interlocking generating route algorithm genetic algo 2rithm1问题描述随着电子计算机技术的飞速发展及容错控制技术的不断进步,基于计算机的铁路车站信号联锁控制系统逐步被接受并受到普遍重视,并在国内外获得了广泛的应用1,取得了丰富的经验.然而,在工程实践及教学过程中我们发现,计算机联锁控制系统在许多方面仍需作进一步的研究与探索.生成进路是计算机联锁控制系统的关系环节之一,是进行联锁关系运算的前提条件

5、,对计算机联锁控制系统的性能具有重要的影响.计算机联锁控制系统的进路生成过程:在操作人员按压了进路的终、始端按钮以后,由计算机根据不同的规则及计算方法完成进路的选取.基于不同的规则及计算方法可产生多种进路生成算法,现有的进路生成算法主要有3种2: 2车站站场分解及处理方法211站场的分解方法为能够有效地利用遗传算法生成进路,必须变换车站站场的描述形式,才能把生成进路问题转化为优化问题.根据车站站场图形及遗传算法的特点,以图1所示的车站信号平面站场图(下行咽喉部分为例,采取如下方法分解站场:粗实线为轨道;长细实线为分割线;短细实线为绝缘节图1车站信号平面图站场(下行咽喉部分(1如图1长细实线所示

6、,先以列的形式分割站场,从右到左站场被不等分成H 块(列,辅以站场原有水平方向轨道(行,股道及渡线被分成由特定行列定义的区段.(2由于股道的长短不同,渡线的起始位置无规律,见图1,在分解站场的过程中,一条渡线常被分割在相邻的两个列区间内,一条股道往往连续占有多个相邻的列区间,为了确切定义每一股道及渡线,作如下规定:以渡线主体部分所在的列为基准定义该渡线的列坐标.从左到右定义列区间的排列顺序,从上到下的顺序定义股道.允许同一段股道对应若干相邻的小段股道区段.规定从左到右定义渡线的方向,以区别分割在同一列的交叉渡线.59第5期徐洪泽等:计算机联锁控制系统的进路生成算法研究212分解及处理结果按上述

7、的站场分解方法及相关规定,得到如下结果:(1被分割出的每一列都对应一个由该列所含的小区段及渡线构成的集合C i=P1,P2,P k,P mi=1,2,n,其中i为小区段所在的列;m为该列所含股道及渡线的个数;P k为该列所属的第k个小股道或渡线,定义为(P k,h,P k,e,P k,h及P k,e分别为该小区段或渡线从左到右首尾所在的行,k 为列区段内股道及渡线的自然排列顺序.(2由进路的终始端构成了一个子集链C i,j=C j,C i+1,C j(1其中i为进路始端所在的列,j为进路终端所在的列.按上述站场分解规则及相应的子集与子集链的构造方法,选排进路就是从式(1中找出可行的(最优的单链

8、,这样,进路生成问题就是在某一最优指标下的有限状态空间优化问题.采用这种方法可很自然地屏蔽掉超出进路范围的线路,提高了算法的效率.(3变约束条件的处理在选排进路的始、终端所包含的列区间时,某些小区段往往已经被其它进路占用,而且已有进路的数量及位置是变化的,这样,进路的生成问题就变成了具有变化约束条件的优化问题.尽管遗传算法能够处理具有约束条件的优化问题,但是,如果能够利用已知条件把具有变化约束条件的优化问题转化为无约束条件的优化问题,可降低算法的难度,减小计算量,提高算法的工作效率,为此,采用下面的方法消除约束条件:通过查询站场的数据结构了解股道及渡线的占用情况,在组成子集的过程中,隐含掉被占

9、用的股道及渡线,这样,变化约束条件的优化问题就转化为无约束条件的优化问题.3生成进路的遗传算法311性能指标的建立求解优化问题,首先要建立待优化问题的性能指标,性能指标是解决优化问题的关键因素之一,它的不同选取对遗传算法的性能具有重要影响.针对进路生成问题,建立性能指标为J i,j=1jk=i |p k,e-p k,h|×M+2jk=i|pk,e-pk,h|-imnj(pm,e-pm,h(pn,e-pn,h面仍一(2其中式(2右边的第一项保证所选出的进路是连续的;式(2右边的第二项消除迂回进路; M为权值,取50.312编码方法及遗传策略的研究(1编码方法根据站场分解结果,我们选用自

10、然数编码方法,交叉操作作用在自然数(即子串之间,而突变操作的对象是代表每一个子集中元素的自然数.(2解空间的组成方法解空间的维数由进路始终端之间所含有的列数决定;每一列对应一个由当前列中可见股道区段及渡线组成的子集;在子集中,每一区段和渡线分别对应一个自然数,子集链首尾两子集分别只含有一个元素;根据从平行进路中优先选出基本进路的原则,在构造子集时,使规定基本进路的股道或渡线对应多个自然数,以减弱变更进路对基本进路的影响,提高基本进路被选出的概率.(3再生策略首先,采用常规的比例再生方法,根据父代码串性能指标的优劣按照式(3产生剩余的部分子代,然后,加入一定数量的随机码串来产生剩余的部分子代,使

11、码串的群体69北方交通大学学报第22卷规模N保持不变.采取这种再生策略可以保证遗传算法在不断优化的同时增加群体的多样性,消除运行过程中适应值相对极大的“超级个体”对算法收敛概率及收敛效率的不良影响,增强算法跳出及避免落入局部极小的能力.比例再生数量为q=N×(J mean/J max(3其中J mean,J max分别为当前码串群的平均适应值及最大适应值.(4交叉及突变策略采用多点交叉的方法,以提高产生码串的多样性4和算法的计算效率;采用常规等概率的突变方法.(5采用最优保留策略5.313算法的终止及结果的判定根据适应函数的定义及遗传算法的特点,在遗传算法迭代次数达到规定的上限后,终

12、止优化搜索过程,利用式(4判定进路是否生成.若式(4满足,则表明进路成功生成,当前码串群中最优码串对应的进路就是希望的进路;否则,表明不能生成指定进路.J i,j mean>1/2|p i,e-p i,h|p i,e-p i,h|<2 1/2(|p i,e-p i,h|-C2|p i,e-p i,h|p i,e-p i,h|2根据本文给出的自然数编码遗传算法的操作原则和二进制编码方法分析的结果不难得出引理1基于自然数编码再生操作的转移概率矩阵R 是随机的;交叉操作的转移概率矩阵C 的随机的;突变操作的转移概率矩阵M 是严格正的.定理3基于自然数编码的进路生成遗传算法是全局收敛的.证

13、明具有再生、交叉及突变操作的基于自然数编码简单遗传算法的转移概率矩阵P =RCM 是严格正的,那么,由定理2及定义1可知Markov 链是遍历的,最优保留特性不影响Markov 链是遍历的,则由文献8的定理313可证基于自然数编码的进路生成遗传算法是全局收敛的.512收敛速度估计定理49定义在状态空间E 上的Markov 链,对所有的状态x E 及所有的可测子集AE 及E 上的某些概率分布(满足P (x ,A (A ,则,给定任意初始分布0及稳定分布有k -(1-k ,其中=y E min x E P (x ,y 1推论19在有限状态空间E 上,如果转移概率矩阵P 的所有元素均为正值,即P &

14、gt;0,则Markov 链几何收敛.定理5基于遗传算法的进路生成算法是几何收敛的.证明:由定理1可知基于自然数编码的遗传算法是有限状态空间上的Markov 链.其中遗传算法的群体空间就是Markov 链的状态空间.遗传算法构成的Markov 链的转移概率矩阵为P =RCM.由引理1可知矩阵R 及矩阵C 是随机矩阵,矩阵M 为严格正随机矩阵(R ,C 0,M >0.具有突变操作的遗传算法的转移矩阵P >0为严格自随机矩阵.则由推论1显然可以得出:基于遗传算法的进路生成算法是几何收敛的.6结论在有效分解站场的基础上,基于遗传算法研究了进路的生成方法,提出了便于应用遗传算法的站场分解方

15、法及有益于进行进路搜索的遗传算法.理论分析及仿真结果表明了本文提出的基于遗传算法的进路生成方法的有效性.参考文献1燕永田1微机连锁控制系统1铁道通信信号,1996,32(12:34362燕永田1微机连锁控制系统1铁道通信信号,1997,33(3:32353Holland J H.G enetic Algorthms.Scientific American.J uly ,1992,44455Rudolph G.Convergence Analysis of Canonical G enetic Algorithm.IEEE Trans on NN ,1994,5(1:911016Losifescu M.Finite Markov Provess