应用于立体车库车位调度的DSP控制系统的工作方法

摘要

一种应用于立体车库车位调度的DSP控制系统的工作方法，其特征在于：它包括以下工作步骤：①确认车库工作状态就绪；②存取车信号；③DSP控制系统开始信息处理；④参数编码；⑤初始群体的设定；⑥适应度函数的设计；⑦控制参数的设定；⑧GAAA算法与存取车最优路线的求取；⑨转换控制语言与输出控制信号；本发明的优越性在于：①GAAA算法优于传统的只是利用传感和光电元件把车辆自动随机地存入和取出车库的车位，克服了遗传算法和蚁群算法各自的缺点，在时间效率和求解效率上都是比较好的启发式算法；②采用DSP控制系统，其硬件电路简单、输出触发脉冲安全可靠、实时控制精度高，可较大提高装置的稳定性和可靠性；③具有广阔的市场应用前景。

说明书

(一)技术领域：

本发明涉及一种DSP控制系统的工作方法，特别是一种应用于立体车库车位调度的DSP控制系统的工作方法。

(二)背景技术：

目前，传统立体车库车位调度控制系统大多存在以下几个问题：

一是，传统立体车库只是利用传感和光电元件对车位进行自动随机地存取的调度，存取顺序和车位的管理还没有达到科学化、智能化、合理化；

二是，遗传算法虽然具有快速全局搜索能力，但对于系统中的反馈信息却没有利用，往往导致无为的冗余迭代，求解效率低；

三是，蚁群算法是通过信息素的累积和更新而收敛于最优路径，具有分布、并行、全局收敛能力，但初期信息素匮乏，导致算法速度慢；

四是，立体车库动作复杂，要求控制系统实现顺序动作控制、速度控制、定位控制及安全互锁控制，由于可编程序控制器(PLC)的优点都能够适应和满足立体车库高性能的使用要求，因此目前几乎所有的自动停车系统中都采用PLC作为立体车库控制系统的核心，但由于PLC控制系统I/O点数和运算速度的限制，PLC在应用于立体车库车位调度时却存在着运行速度和生产成本等方面的问题，影响到车库的整体效率和利用率，造成车辆在存取时间和存取车能耗上的浪费。

(三)发明内容：

本发明的目的在于提供一种应用于立体车库车位调度的DSP控制系统的工作方法，该方法基于GAAA算法(Genetic And Ant Algorithm)，它是将遗传算法(Genetic Algorithm)和蚁群算法(Ant Algorithm)相融合应用于立体车库车位调度的DSP控制系统，它充分利用计算机的高级决策功能，并利用已成为当今新热点技术的数字信号处理器件(DSP)来做实时处理，实现对立体车库车位调度的优化控制，将自动化立体车库推向智能化发展方向。

本发明的技术方案：一种应用于立体车库车位调度的DSP控制系统的工作方法，其工作环境是在一个由交流横移电机和升降电机、变频器、传感器、各种机械开关、钢丝绳、停车位框架、载车板和横移导轨等常规设备构成的立体车库中，其特征在于：它是利用计算机的高级决策功能，将遗传算法(Genetic Algorithm)和蚁群算法(Ant Algorithm)相结合构成基于GAAA的算法，通过DSP控制系统用于立体车库车位调度的方法，它包括以下工作步骤：

(1)确认车库工作状态就绪：先确认车库是否准备就绪，车库内各个设备是否均可安全可靠工作，能否以正常工作状态完成存取车任务；

(2)存取车信号：车库内收到存取车信号，检测车库内存取车状态，当控制系统接收到用户存车或取车的信号时，DSP控制系统通过对数据库的扫描，确认该信号是存车还是取车；

(3)DSP控制系统开始信息处理：DSP控制系统根据遗传算法与蚁群算法融合的GAAA算法，开始进行信息处理；

(4)参数编码：首先，对每个车位动作的方向进行参数编码，并利用rand函数随机生成一定数量的十进制实数编码种群；

(5)初始群体的设定：由遗传算法对群体进行进化操作，设定一些表示起始搜索点的初始群体数据，为下一阶段最优路径代码的输出生成最初的原始群体；

(6)适应度函数的设计：即对遗传个体适应度的评价，是指在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率；通过对遗传个体适应环境的能力的评价，作为选择操作的依据，它是由目标函数变换而成；通过设计的适应度值函数将各个染色体的适应度值计算出来之后，按照“优胜劣汰”原则把好的个体遗传到下一代，而把不好的个体淘汰掉；然后，按照遗传算法中改良型的OX交叉算子、变换变异算子对其进行交叉计算和变换变异；

(7)控制参数的设定：确定对遗传算法性能影响很大的参数取值；

(8)GAAA算法与存取车最优路线的求取：对最大-最小蚂蚁MMAS算法系统进行设计及改进，在GAAA算法中，蚂蚁算法采用最大—最小蚂蚁系统MMAS算法，并对步骤(5)中经过设定代数的递归迭代后产生出的若干组优化解，采用最大-最小蚂蚁系统MMAS对这几组优化解递归迭代最终输出最好解，即求出车辆存取的最短路径；

(9)转换控制语言与输出控制信号：将步骤(8)中求出的存取车辆的最短路径转换成控制语言，由DSP控制系统输出信号，控制车库电机、变频器、载车板等设施完成存取车。

上述所说的步骤(4)中车位动作的方向共有：静止、不动、向上、向下、向左和向右五种状态；采用的编码方法为：每个个体(染色体)的奇数位表示车位号，偶数位表示方向，分别用0、1、2、3、4来表示车位的静止不动、向上、向下、向左和向右这五种状态；形式如下：

9      1    20     2     5      2   ……

车位号 动作 车位号 动作 车位号 动作…

上述所说的步骤(5)初始群体的设定中一般有两种方法：①根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，设定初始群体；②先随机生成一定数目的个体，从中挑出最好个体加到初始群体中；这种过程不断迭代，直到达到预定的规模；并经过设定代数的递归迭代后产生出若干组优化解。

上述所说的步骤(6)中适应度函数的设计的个体的适应度与该个体被遗传到下一代的概率成正比；适应度函数唯一的要求是其结果为非负值；适应度的尺度变换是对目标函数值域的某种映射变换，可克服未成熟收敛和随机漫游现象。

上述所说的步骤(6)中按照“优胜劣汰”原则把好的个体遗传到下一代分为直接遗传或者通过交叉产生新的个体再遗传。

上述所说的步骤(6)中对遗传算法的操作的设计包括选择算子、交叉算子、变异算子的设计：①选择算子：选择算子亦称为复制算子，是从当代群体中选择出一些比较优良的个体，并将其复制到下一代群体中，个体的复制概率正比于其适应值；②交叉算子：交叉算子是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，组合出新的个体，在串空间进行有效搜索，同时降低对有效模式的破坏概率，各种交叉算子均包含两个基本内容：确定交叉点的位置和进行部分基因的交换；③变异算子：变异算子是指将个体编码串中的一些基因值用其它基因值来替换，形成一个新的个体，变异算法包括确定变异点的位置和进行基因值替换。

上述所说的步骤(7)中控制参数的设定主要包括串长1，群体大小n，交叉概率p_c、变异概率p_m等，其中，一般确定的参数范围是：n＝20～200，p_c＝0.5～1.0，p_m＝0～0.05；

上述所说的步骤(8)中的蚂蚁算法基于仿生学，即计算蚂蚁凭借路径寻优的能力能够找到蚁巢与食物之间的最短路径，包括蚂蚁在所经过的路径上留下一种称为信息素的挥发性分泌物(pheromone)与信息素随着时间的推移会强度逐渐挥发消失；蚂蚁在觅食过程中能够感知这种物质的存在及其强度，并以此来指导自己的运动方向，倾向于朝着这种物质强度高的方向移动，即选择该路径的概率与当时这条路径上该物质的强度成正比；信息素强度越高的路径，选择它的蚂蚁就越多，则在该路径上留下的信息素的强度就更大，而强度大的信息素又吸引更多的蚂蚁，从而形成一种正反馈，通过这种正反馈，使得大部分的蚂蚁都会走此最佳路径。

上述所说的步骤(8)中最大—最小蚂蚁系统MMAS算法与标准蚁群算法有三个方面不同：

①信息素更新方式不同，每次循环后只对本次循环最优解或到目前为止找出最优解的一只蚂蚁进行信息素更新，而在标准蚁群算法中，对所有蚂蚁走过路径都进行信息素更新，MMAS信息素更新方式如下：

τ_ij(t+n)＝ρτ_ij(t)+Δτ_ij^best，Δτ_ij^best＝1/f(s^best)  (i)

其中f(s^best)表示迭代最优解(s^ib)或全局最优解(s^gb)的值；

②为避免搜索的停滞，在每个解的元素上的信息素轨迹量的值域范围被限制在[τ_min，τ_max]区间内。即：若有τ_ij(t)>τ_max，则置τ_ij(t)＝τ_max；若有τ_ij(t)<T_min，则置τ_ij(t)＝τ_min。而在标准蚂蚁系统中信息素轨迹量不被限制，使得一些路径上的轨迹量远高于其他边，从而蚂蚁都沿着同条路径移动，阻止了进一步搜索更优解的行为；

③为使蚂蚁在算法的初始阶段能够更多地搜索新的解决方案，将信息素轨迹初始化为τ_max，MMAS由于把各路径上的信息素轨迹量的值域限制在[τ_min，τ_max]区间内。

上述所说的步骤(8)中对最大-最小蚂蚁MMAS算法系统进行设计及改进，其中对MMAS的信息素更新方式为：第一，因MMAS中各路径上信息素初始化为τ_max，应迅速减少较差路径上的信息素，加快搜索速度，所以在每次循环后，先计算各条路径长度的平均值L_ave，然后，小于平均值长度的路径信息素增加，大于平均值长度的路径信息素减小，第二，各条路径上各边信息素的增加或减少的量不应一样，应体现出各条路径的各边的长度对路径总长度的贡献程度，所以(i)式修改成如下形式：

τ_ij(t+n)＝ρτ_ij(t)+Δτ_ij，Δτ_ij＝ΣΔτ_ij^k  (ii)

其中Δτ_ij^k表示第k只蚂蚁在本次循环中留在路径ij上的信息量，Δτ_ij表示本次循环中留在路径ij上的信息总量，其中Δτ_ij^k如下：

其中L_k为第k只蚂蚁在本次循环中所走过的路径长度；L_ave为m只蚂蚁所走路径的平均长度；d_ij为城市i到城市j的距离。

本发明的工作原理为：DSP控制系统是相对于传统的PLC控制系统而提出的更具有优势和发展前景的控制系统；对于传统PLC控制系统在立体车库的应用中所出现的运行速度和生产成本等方面的问题，DSP控制系统具有比PLC控制系统更多的优势：首先在运行速度方面，PLC控制系统的运算速度只能达到us级，而DSP控制系统的运算速度可以到ns级，因此能更好地满足电子高智能化立体车库对于控制芯片的要求；在生产成本方面，由于立体车库需要的I/O点数比较多，如果用PLC控制系统，生产成本将会很高，但是用DSP+CPLD实现的话会在生产成本上大大降低，目前DSP控制系统外扩CPLD的方法已经在军事、工业高精度控制、数码产品中都得到了广泛的应用；在功能扩展方面，DSP控制系统在片内集成了各种工业上常用的各种模块，为立体车库功能的升级提供了强大的硬件保障；上述可以看出，DSP控制系统外扩CPLD会逐渐取代PLC控制系统成为现代电子智能化立体车库控制部分的主流。

参数编码是应用遗传算法解决个体的染色体排列形式或个体从搜索空间到基因型变化到解空间的表现型时的解码方法。

车库运行的主要问题是要在车位移动方向受限制的约束条件下，求得车库运行的最短路径；首先对其动作的方向进行参数编码，车位的动作总共有：静止、不动、向上、向下、向左和向右5种状态；由此，可以采用这样的编码方法：每个个体(染色体)的奇数位表示车位号，偶数位表示方向，分别用0、1、2、3、4来表示车位的静止不动、向上、向下、向左和向右这五种状态，并利用rand函数随机生成一定数量的十进制实数编码种群，为了方便适应度函数比较排序并在此基础上计算选择概率，适应度函数的值要取正值；通常，我们采取最小值转化为最大值的方法，即用一个较大的与群体无关的常数减去目标函数的方法；对于本发明来说，每行的偶数元素表示载车板的动作，将非零的个数相加，就得到整个车库载车板动作的次数了；将各个染色体的适应度值计算出来之后，下一步的工作就是要按照“优胜劣汰”思想，把好的个体直接遗传到下一代或者通过交叉产生新的个体再遗传到下一代，而把不好的个体淘汰掉，这一步操作叫做选择；本发明采用了赌轮选择的方法，它能够较好的反映个体适应度在整个群体的个体适应度总和中所占的比例。也就是说，个体每次被选中的概率与其在群体环境中的相对适应度成正比；传统的遗传交叉算子并没有充分考虑到立体车库车位调度的特点，不能将巡回路线上的优良性能很好地遗传到下一代群体中，且寻优速度较差；本发明采用了一种改良型的OX交叉算子，较好地解决了该问题。为了维护群体的多样性，防止遗传算法的过早收敛，本文引入了变换变异算子，也叫反转变异算子，保留了优良的基因片断，使之能够遗传给下一代，同时又产生了包含更加复杂的新个体，有效地扩大了搜索范围；该算子操作时，在路径中随机选择切入点，然后将这两点之间的子路反转；按照本发明的遗传算子设计，种群规模为20，迭代次数为20代，交叉概率p_c＝0.8，变异概率p_m＝0.2，通过遗传算法GA所产生出的若干组优化解，采用上述所说的最大-最小蚂蚁系统MMAS对这几组优化解递归迭代最终输出最好解也即求出车辆存取的最短路径，然后再由DSP控制系统控制车库电机、变频器、载车板等设施完成存取车。

本发明的优越性在于：①GAAA算法首先利用遗传算法的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后，充分利用蚁群的并行性、正反馈机制以及求解效率高等特征，不仅优于传统的只是利用传感和光电元件把车辆自动随机地存入和取出车库的车位，而且克服了遗传算法和蚁群算法各自的缺点，这样融合后的算法，在时间效率和求解效率上都是比较好的启发式算法；②采用DSP控制系统代替原有的PLC控制系统，硬件电路简单、输出触发脉冲安全可靠、实时控制精度高，可较大提高装置的稳定性和可靠性；③具有广阔的市场应用前景。

(四)附图说明

附图1为本发明所涉一种基于遗传算法与蚁群算法融合的GAAA算法应用于立体车库车位调度的DSP控制系统的工作方法整体流程示意图。

附图2为本发明所涉一种应用于立体车库车位调度的DSP控制系统的工作方法中的遗传算法与蚁群算法融合的GAAA算法流程图。

(五)具体实施方式：

实施例：一种应用于立体车库车位调度的DSP控制系统(见附图1、2)的工作方法，其工作环境是在一个由交流横移电机和升降电机、变频器、传感器、各种机械开关、钢丝绳、停车位框架、载车板和横移导轨等常规设备构成的立体车库中，其特征在于：它是利用计算机的高级决策功能，将遗传算法(Genetic Algorithm)和蚁群算法(Ant Algorithm)相结合构成基于GAAA的算法，通过DSP控制系统用于立体车库车位调度的方法，它包括以下工作步骤：

(1)确认车库工作状态就绪：先确认车库是否准备就绪，车库内各个设备是否均可安全可靠工作，能否以正常工作状态完成存取车任务；

(2)存取车信号：车库内收到存取车信号，检测车库内存取车状态，当控制系统接收到用户存车或取车的信号时，DSP控制系统通过对数据库的扫描，确认该信号是存车还是取车；

(3)DSP控制系统开始信息处理：DSP控制系统根据遗传算法与蚁群算法融合的GAAA算法，开始进行信息处理；

(4)参数编码：首先，对每个车位动作的方向进行参数编码，并利用rand函数随机生成一定数量的十进制实数编码种群；

(5)初始群体的设定：由遗传算法对群体进行进化操作，设定一些表示起始搜索点的初始群体数据，为下一阶段最优路径代码的输出生成最初的原始群体；

(6)适应度函数的设计：即对遗传个体适应度的评价，是指在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率；通过对遗传个体适应环境的能力的评价，作为选择操作的依据，它是由目标函数变换而成；通过设计的适应度值函数将各个染色体的适应度值计算出来之后，按照“优胜劣汰”原则把好的个体遗传到下一代，而把不好的个体淘汰掉；然后，按照遗传算法中改良型的OX交叉算子、变换变异算子对其进行交叉计算和变换变异；

(7)控制参数的设定：确定对遗传算法性能影响很大的参数取值；

(8)GAAA算法与存取车最优路线的求取：对最大-最小蚂蚁MMAS算法系统进行设计及改进，在GAAA算法中，蚂蚁算法采用最大—最小蚂蚁系统MMAS算法，并对步骤(5)中经过设定代数的递归迭代后产生出的若干组优化解，采用最大-最小蚂蚁系统MMAS对这几组优化解递归迭代最终输出最好解，即求出车辆存取的最短路径；

(9)转换控制语言与输出控制信号：将步骤(8)中求出的存取车辆的最短路径转换成控制语言，由DSP控制系统输出信号，控制车库电机、变频器、载车板等设施完成存取车。

上述所说的步骤(4)中车位动作的方向共有：静止、不动、向上、向下、向左和向右五种状态；采用的编码方法(见附图2)为：每个个体(染色体)的奇数位表示车位号，偶数位表示方向，分别用0、1、2、3、4来表示车位的静止不动、向上、向下、向左和向右这五种状态；形式如下：

9      1    20     2    5      2   ……

车位号 动作 车位号 动作 车位号 动作…

上述所说的步骤(5)初始群体的设定(见附图2)中一般有两种方法：①根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，设定初始群体；②先随机生成一定数目的个体，从中挑出最好个体加到初始群体中；这种过程不断迭代，直到达到预定的规模；并经过设定代数的递归迭代后产生出若干组优化解。

上述所说的步骤(6)中适应度函数的设计(见附图2)的个体的适应度与该个体被遗传到下一代的概率成正比；适应度函数唯一的要求是其结果为非负值；适应度的尺度变换是对目标函数值域的某种映射变换，可克服未成熟收敛和随机漫游现象。

上述所说的步骤(6)中按照“优胜劣汰”原则把好的个体遗传到下一代分为直接遗传或者通过交叉产生新的个体再遗传。

上述所说的步骤(6)中对遗传算法的操作(见附图2)的设计包括选择算子、交叉算子、变异算子的设计：①选择算子：选择算子亦称为复制算子，是从当代群体中选择出一些比较优良的个体，并将其复制到下一代群体中，个体的复制概率正比于其适应值；②交叉算子：交叉算子是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，组合出新的个体，在串空间进行有效搜索，同时降低对有效模式的破坏概率，各种交叉算子均包含两个基本内容：确定交叉点的位置和进行部分基因的交换；③变异算子：变异算子是指将个体编码串中的一些基因值用其它基因值来替换，形成一个新的个体，变异算法包括确定变异点的位置和进行基因值替换。

上述所说的步骤(7)中控制参数的设定(见附图2)主要包括串长1，群体大小n，交叉概率p_c、变异概率p_m等，其中，一般确定的参数范围是：n＝20～200，p_c＝0.5～1.0，p_m＝0～0.05；

上述所说的步骤(8)中的蚂蚁算法基于仿生学，即计算蚂蚁凭借路径寻优的能力能够找到蚁巢与食物之间的最短路径，包括蚂蚁在所经过的路径上留下一种称为信息素的挥发性分泌物(pheromone)与信息素随着时间的推移会强度逐渐挥发消失；蚂蚁在觅食过程中能够感知这种物质的存在及其强度，并以此来指导自己的运动方向，倾向于朝着这种物质强度高的方向移动，即选择该路径的概率与当时这条路径上该物质的强度成正比；信息素强度越高的路径，选择它的蚂蚁就越多，则在该路径上留下的信息素的强度就更大，而强度大的信息素又吸引更多的蚂蚁，从而形成一种正反馈，通过这种正反馈，使得大部分的蚂蚁都会走此最佳路径。

上述所说的步骤(8)中最大—最小蚂蚁系统MMAS算法(见附图2)与标准蚁群算法有三个方面不同：

①信息素更新方式不同，每次循环后只对本次循环最优解或到目前为止找出最优解的一只蚂蚁进行信息素更新，而在标准蚁群算法中，对所有蚂蚁走过路径都进行信息素更新，MMAS信息素更新方式如下：

τ_ij(t+n)＝ρτ_ij(t)+Δτ_ij^best，Δτ_ij^best＝1/f(s^best)  (i)

其中f(s^best)表示迭代最优解(s^ib)或全局最优解(s^gb)的值；

④为避免搜索的停滞，在每个解的元素上的信息素轨迹量的值域范围被限制在[τ_min，τ_max]区间内。即：若有τ_ij(t)>τ_max，则置τ_ij(t)＝τ_max；若有τ_ij(t)<τ_min，则置τ_ij(t)＝τ_min。而在标准蚂蚁系统中信息素轨迹量不被限制，使得一些路径上的轨迹量远高于其他边，从而蚂蚁都沿着同条路径移动，阻止了进一步搜索更优解的行为；

⑤为使蚂蚁在算法的初始阶段能够更多地搜索新的解决方案，将信息素轨迹初始化为τ_max，MMAS由于把各路径上的信息素轨迹量的值域限制在[τ_min，τ_max]区间内。

上述所说的步骤(8)中对最大-最小蚂蚁MMAS算法系统进行设计及改进(见附图2)，其中对MMAS的信息素更新方式为：第一，因MMAS中各路径上信息素初始化为τ_max，应迅速减少较差路径上的信息素，加快搜索速度，所以在每次循环后，先计算各条路径长度的平均值L_ave，然后，小于平均值长度的路径信息素增加，大于平均值长度的路径信息素减小，第二，各条路径上各边信息素的增加或减少的量不应一样，应体现出各条路径的各边的长度对路径总长度的贡献程度，所以(i)式修改成如下形式：

τ_ij(t+n)＝ρτ_ij(t)+Δτ_ij，Δτ_ij＝ΣΔτ_ij^k  (ii)

其中Δτ_ij^k表示第k只蚂蚁在本次循环中留在路径ij上的信息量，Δτ_ij表示本次循环中留在路径ij上的信息总量，其中Δτ_ij^k如下：

其中L_k为第k只蚂蚁在本次循环中所走过的路径长度；L_ave为m只蚂蚁所走路径的平均长度；d_ij为城市i到城市j的距离。