模拟寻优（精选3篇）
模拟寻优 篇1
0 引言
遗传算法(GA)与模拟退火法(SAA)是近年来优化领域的研究热点,与传统的优化方法相比,具有算法简单、使用灵活、寻优效高、算法“健壮”、适合并行计算、不需要梯度信息等优点,目前已在组合优化、管理决策、工程领域得到一些应用。鉴于这两种算法在寻优方面的优越性,特将其算法思想以及寻优特点作一归纳,使之在工程优化设计领域中能得到广泛应用。
1 两种算法的基本思想
1.1 遗传算法
遗传算法是根据达尔文的生物进化中的“优胜劣汰”原则建立的一种优化算法。20世纪60年代首先由美国Michigan大学的J. Holland教授提出。该算法模拟了自然界中生物自然选择、适者生存的进化过程,从而达到搜索最优解的目的,标准遗传算法主要由以下基本步骤组成:
a) 对设计向量编码:遗传算法不直接处理解空间数据,需通过编码将解空间中的设计向量转化为遗传空间中的基因串,通过遗传算法改变基因串的结构以达到搜索解空间最优解的目的,常用的编码形式为二进制编码、浮点编码等。
b) 生成初始母体群:遗传算法是群体操作算法,随机生成n个基因串(每个基因串对应解空间的一个设计向量),以此作为迭代搜索的初始点。
c) 适应度计算:适应度是反应基因串对环境的适应能力,遗传算法一般不需要其他信息,仅通过适应度来评价群体中的两个体的优劣,适应度越大,个体的遗传基因越优,反之遣传基因较劣。
d) 对群体基因串进行遗传算子操作,产生新一代群体基因串遗传算法,主要有选择、交叉、变异三种算子组成,选择的目的是从群体基因串中选择遗传基因优良的基因串作为遗传父代,交叉运算的目的是产生子代基因串,变异的目的是为产生新的基因串提供机会。
通过上述三种遗传运算操作形成新一代(子代)群体基因串,如此反复迭代遗传直到搜索到最优解。
1.2 模拟退火法
模拟退火法是模拟固体退火过程而设计的一种寻优算法。20世纪80年代首先由Kirkpatrilk等人提出,在模拟退火法中,解向量X和目标函数F(X)分别对应退火过程一个固体微观状态i和相应的能量E,随着算法进程递减其值的控制参数C对应于退火过程的温度T,在某一控制参数C值下,算法所进行的“产生新解→判断→接受或放弃”的迭代过程,相对应固体在某一恒温下趋于热平衡的过程。通过若干次迭代变换后算法求出的最优解x*和目标函数F(X*)分别对应固体的基态和最小能量。
模拟退火法的求解步骤如下:1) 设定初始解X=X0和初始控制参数C=Co;2) 随机产生新X′;3) 计算转移概率p;
P(X′=>X)=
undefined
4) 判断接受或放弃新解X′,当p(X′=>X)>r,接受X′为新解,否则,放弃为X′新解;5) 判断终止条件,满足条件则停止迭代,否则转向2)。
2 两种算法的寻优能力比较
2.1 测试函数算例
为了考察两种算法的寻优能力,曾经测试了几个具有典型“欺骗”性质的函数的优化,这种具有“欺骗”性的函数全局最优点往往是孤立的并被全局最优点包围,或是多峰值函数。
f1=100(x2-xundefined)2+(x2-1)2,Ω=(-200,200)2;
f2=undefined100(x1+1-xundefined)2+(x1-1)2,Ω=(-200,200)1;
f3=xundefined+2xundefined-0.3cos3πx1-0.4cos4πx2+0.7,Ω=(-100,200)2。
f1为二维Rosenbrock函数,最小值为0,全局最优点(1,1),是一个具有曲型“狭长深谷”的函数;f2为四维Rosenbrock函数,最小值为0,全局最优点为(1,1,1,1);f3为一个多峰值函数。上述函数用传统方法很难搜索到全局最优点,具体测试结果见表1:
遗传算法与模拟退火法均为随机搜索算法,与传统优化方法相比,两种算法在寻优方面各有特点。
2.2 遗传算法的寻优特点
a) 寻优过程不需梯梯信息,特别适用复杂目标函数的优化;
b) 不是从一个单点而是从多点(群体)开始搜索;
c) 利用概率转移规则,而非确定规则;
d) 由于引入了交叉与变异算子,使遗传算法搜索到全局最优解的能力增强,理论上遗传算法搜索到全局最优的概率为1;
e) 遗传算法对初始解没有苛刻要求是一种“健壮”的算法;
f) 由于遗传算法是在遗传空间中通过操作n个基因编码串进行寻优,而n个基因串能反映O(n3)阶个基因串模式,因而遗传算法隐含并行性,这一优点特别适用于并行计算机处理,除上述优点外,遗传算法也有其缺陷,其中最突出的是“早熟现象”特别是对多峰值目标函数的优化中表现的较明显,所谓“早熟现象”是过早收剑到某一局部最优解,目前国内外学者也提出了一些解决方法,如引入共享函数、学编码等。
2.3 遗传算法的寻优算例
例:已知20t/25m门座起重机变幅齿条最大切向力F1=344kN
常规计算过程如下:
a) 初选小齿轮模数m=25,Z=14,材料40Cr,变位系数ξ=0.177,根据齿变典强度条件,求得齿宽b=200mm。
选取齿轮轴材料45号钢,根据结构和齿宽b定轮轴支承情况和支承距离L,进行齿轮轴弯曲疲劳强度校核得到轴直径d=168mm。
b) 校核齿体强度:根据齿轮计算得齿根圆直径df=296.3mm,而齿体强度要求齿根圆直径不小于302.4mm。上述计算结果不满足要求,这时必须凭经验调整有关几何尺寸参数再进行齿轮、齿轮轴和齿体的强度校核直到满足为止。而通过遗传算法可得到下面一组解(见表2),其中第一组解为全局最优解,其他若干组次优解,设计人员可以根据实际情况从中任选一组解。必定优于常规计算所得的结果。
2.4 模拟退火算法的特点
a) 寻优过程不需要梯度信息,适合复杂目标函数优化;
b) 算法简单,易程序化;
c) 与局部搜索法相比,模拟退火法能以一定概率接受恶化解从而扩大了搜索空间,使迭代过程易跳出局部最优“陷井”,增大了搜索到全局最优解的机会;
d) 最终优化解的质量不依赖初始解,因而模拟退火法是一种“健壮”的算法;
e) 理论上模拟退火法搜索到全局最优解的概率为1;
f) 如冷却进度表选取合理,模拟退火法能在较短的CPU时间内获得者高质量的全局最优解。
由于模拟退火法是对固体退火过程的简单模拟,因而不可避免的存在一些不足,主要表现为合理选取初始温度T较为困难:1) 随着控制参数T的逐渐衰减,接受恶化解的概率逐渐减小,从而使算法停留在局部最优的“陷井”中无法跳出;2) 目前,已有学者提出了一些改进的模拟退火法来解决上述问题,如加温退火法、记忆退火法、回火退火法等,均取得了较好的效果。
2.5 模拟退火算法的寻优算例
算例:16t带载变幅直臂架起重机。有关技术性能参数如表3:起重质量16t,最大幅度Rmax=16m,最小幅度Rmin=7m,臂架端点至臂架铰点的垂直距离Hmin=14m。臂架自重Gb=5×104kN,臂架重心位置l1=8m。
计算结果列于表3:
根据计算结果绘制了落差曲线图(图1)和不平衡力矩曲线图(图2)。
3 总结
遗传算法与模拟退火法在优化领域有着非常广泛的应用前景,目前对这两种算法的数学理论、性能分析、并行性计算,在神经网络中的应用等方面均是国内外学者的研究热点,本文的目的就是希望通过对这两种算法的寻优特点进行一些归纳,使之能更好的用于工程优化设计领域,以提供有价值的帮助。
摘要：介绍了遗传算法与模拟退火算法的基本思想,综述归纳了两种算法的寻优特点,使之在工程优化设计领域得到更广泛的应用。
关键词：遗传算法,模拟退火法,优化设计
参考文献
[1]刘勇.非数值并行算法——遗传算法[M].北京:科学出版社,1994.
[2]康立山.非数值并行算法——模拟退火法[M].北京:科技出版社,1995.
[3]柳卫东,等.遗传算法优能力研究[J].武汉交通科技大学学报,1998.
[4]孙艳丰,王众托.遗传算法在优化问题中的应用进展[J].控制与决策,1996(4).
[5]vas Lasrhovon P J M,Asrts E H L.Simulated annealing[M].Theory and Applications.D Reidel,1997.
[6]胡琉达.实用多目标最优化[M].上海:上海科学技术出版社,1990.
[7]刘惟信.机械最优化设计[M].北京:清华大学出版社,1994.
[8]van laarhoven P J M,Aarts E H L:Simulated annealing[M].Theory Applitions D Reidel,1947.
[9]张氯,孙国正.模拟退火算法在抓斗优化设计中的应用[J].起重运输机构,1999(1).
一种SVM训练样本集寻优算法 篇2
关键词：SVM分类器,Bagging算法,自助网格搜索算法,训练样本数量
0 引 言
支持向量机 (SVM) 主要思想是针对两类分类问题而提出的, 在高维空间寻找一个超平面作为两类的分割, 以保证最小的分类错误率[1,2,6]。SVM的另一个重要的特点是能通过选择合适的核函数处理样本数据线性不可分的情况。一般来说, 在模式分类问题中, 训练样本数据的变化, 会引起分类器的不稳定, 并且不同的训练样本数量下的测试精度也是不相同的[5]。所以, 训练样本的选取对分类效果以及精度是至关重要的, 如何选取合适的训练样本的数量, SVM分类器才是最优的呢?文献[5]提出了能解决分类器的不稳定性的Bagging算法。通过产生多个分类器, 最后的分类结果由投票产生。但对于训练样本个数的选取, Bagging算法并没有提出。本文运用了Bagging算法的思想, 通过自助网格搜索算法寻得合适的训练样本集, 以寻求好的SVM分类器为目的进行了两个实验, 实验中发现, 自助网格搜索算法寻得的SVM分类器在学习性能上有较大的提高, 并且对大样本数据来说, 可以显著减少训练时间, 从而降低时间代价。
1 线性不可分的SVM问题[5]
在SVM中, 相似性和相似程度是用内积进行估价的, 这些内积强烈依赖于映射的选择。通过选取适当的到一个足够高维的非线性映射φ (g) , 数据总能被一个超平面分割。我们假设每个模式Xk变换到yk=φ (Xk) , 我们就把问题变为如何选择φ (g) 。对N个模式中的每一个, k=1, 2, …, n, 根据模式属于ω1或是ω2, 我们分别令z=±1, 增广空间y上的判别函数就是:
g (y) =aty (a是权向量) (1)
这里的权向量和变换后的模式向量都是增广的。这样, 一个分隔超平面保证:
zkg (yk) ≥1 (2)
训练一个SVM的目标是找到一个具有最大间隔的分隔平面, 如果间隔越大, 得到的分类器也越好。从超平面到变换后的模式y的距离是|g (y) |/‖a‖, 如果正的间隔b存在的话, 由式 (2) 可推出:
我们的目标就是找一个使b最大化的权向量a, 当然, 解向量可以任意伸缩, 同时保持超平面不变, 这样就保证了限制b‖a‖=1。支持向量就是使式 (2) 等号成立的模式向量。
对于训练SVM, 我们应该先选择将输入数据映射到更高维空间的非线性φ函数。映射后的空间的维数可以是任意高的。我们把有约束的权向量长度极小化问题转换为无约束的拉格朗日待定因子问题。这样通过式 (3) 及极小化‖a‖的目标, 我们构造泛函数:
找到使L (a, α) 极小的权向量a和使它极大的待定因子αk≥0。式 (4) 最后一项是正确分类的目标。我们将这个最优化的形式修改为极大化:
给出训练数据的约束条件:
这些方程可以用二次规划求解。
2 SVM训练样本集的寻优算法
本文所提出的SVM训练样本的寻优主要是指寻求合适的训练样本集, 来提高学习性能。在文献[5]中提出了从学习曲线预测SVM分类器最终性能的特殊学习曲线 (指数式的学习曲线) , 测试误差与训练误差随训练集尺寸的变化而变化, 但到达一定的训练集尺寸时, 测试误差与训练误差都趋于同一个值, 最终可以通过坐标空间确定出训练集的尺寸, 并保证了这个尺寸要远远小于原始训练集尺寸, 从而大大降低了时间的代价。但是, 现实中学习性能满足这样曲线的情况并不多, 往往是不规则的曲线, 鉴于这样的考虑, 提出了自助网格搜索算法来寻找合适的训练样本集。
2.1 Bagging算法[5]
Bagging算法的一般过程:从大小为N的原始数据集D中, 分别独立随机地抽取n′个数据 (n′<N) 形成自助数据集, 并且将这个过程独立地进行许多次, 直到产生很多个独立的自助集。然后, 每一个自助数据集都被独立地用于训练一个“分量分类器”。最终的分类结果由这些“分量分类器”各自的判别结果的投票来决定。
2.2 网格搜索算法
采用网格搜索法可以保证搜索到最优参数。在文献[3,4]中提出:网格搜索法就是首先确定每个参数的取值范围, 然后对每个参数取值范围按照一定规律插值, 得出若干组参数组合;对每组参数组合进行一次计算, 应用留一法计算其预测误差均方根;对应于预测误差均方根最小的参数组合, 就是最优的参数取值。网格搜索法的优点在于:可以安全地搜索到最优参数组合, 其方法主要用于寻找核参数的问题。
2.3 自助网格搜索算法
不同的训练样本集的尺寸以及数据的变化, 一般都会导致测试精度起伏不定, 而大训练样本训练时间代价大。考虑到这两个缺陷, 我们提出了自助网格搜索算法。
基于网格搜索法网格划分的思想, 执行算法时分别对小样本数据集与大样本数据集做不同的处理。就小样本数据集而言, 如实验1, 其训练样本数为45, 它的训练时间代价相对较小, 可以把全部训练样本进行网格划分成几个大小相同的区间, 结合Bagging算法, 区间边界上的样本的尺寸定义为ni, i=1, 2, …, l (l为区间边界上不同的样本尺寸的个数) , 分别独立随机地抽取ni个数据 (ni<N) 形成自助数据集, 并且将这个过程独立地进行许多次, 直到产生很多个独立的自助集。最终的分类结果由这些“分量分类器”投票来决定, 其共执行了l次Bagging算法。确定一个测试精度最高点所对应的训练样本的尺寸, 在这个值的一定范围内再进行一次更细致的同样的操作, 找到比第一次执行算法所得到的最好精度还好的测试精度所对应的样本尺寸, 将其作为SVM模型最终的训练集尺寸。SVM模型选定后, 对测试样本进行测试时, 训练样本集中的数据是随机多次抽取的, 同样执行Bagging算法来确定测试精度。我们把这样的过程叫作自助网格搜索算法。而对于大的样本集来说, 如实验2, 其训练样本数为4000, 它的训练时间代价是很大的, 基于时间上的考虑, 选取一个比训练样本尺寸小的训练集来进行训练, 对这样一个小的范围执行自助网格搜索算法, 寻找最优分类器, 从而可以节省大样本训练时间的代价。
设b是选取SVM分类器中参加训练的全部样本数量, N是全部训练样本集数量, n′是能使分类器最优的训练样本数量。step是第一次执行算法的步长, step′ (step′<step) 为第二次执行算法的步长。起初, n′=N, step=step′, a=step, b=n′。
其寻优步骤为:
(1) 对于小样本集而言, 选取一个步长step′, 把训练样本数量值n′下[a, b]区间划分成几个大小相等的区间, 区间边界上的多个值即为所要测试的多个训练集分别对应的样本数量。对于大样本来说, 选取n′ (n′<<N) 个训练样本, 区间划分规则与小样本集规则相同, 这时的n′对应的是小样本问题中的N。
(2) 根据步骤 (1) 求出的多个训练集样本尺寸, 构造相应的训练集, 在每种训练集下执行Bagging算法, 且每次都构造多个分类器, 每种训练集下的测试结果由投票产生。找到一个合适训练样本下的最优分类器。
(3) 由步骤 (2) 可以得到一个合适的训练样本数量下的最优分类器。b=step+n′, 递归执行步骤 (1) , 即:在这个值的一定范围内进行一次更细致的自助网格搜索。
(4) 把由算法得到的最优训练样本尺寸作为SVM模型的训练集样本尺寸, 即:作为对测试样本进行测试时所选用的训练集样本的尺寸。SVM模型选定后, 对测试样本进行测试时, 训练样本集中的数据是随机多次抽取的, 同样执行Bagging算法来确定测试精度。
对于大样本数据来说, 如果在选择的b (b<<N) 下执行此算法后得到的最好的精度不能使人满意, 可以增大b (b<<N) 的值, 对b到b增大后值b′ (b′<<N) 的区间上重新执行该算法即可
3 实验结果与分析
下面对IRIS与MAGIC04 (该数据下载地址:http://archive.ics.uci.edu/ml) 数据集进行实验, 两个实验都用QP算法来说明。对训练数据及测试数据进行归一化到区间[-1, +1]上。 文中所涉及的训练样本集都采用随机抽取的方式获取。SVM分类器核函数选RBF, 其参数gamma=0.5, 每次执行Bagging算法构造分类器个数为40个。
3.1 实验1
IRIS数据集共有150个样本, 共分为三类:s类, ve类, vi类, 每类分别有50个数据, 每类都为4维的向量。取每类前15个样本作为训练集, 然后对150个样本进行测试。采用一对多类方法测试。在执行自助网格搜索算法步骤 (2) 的时候, step=5, 即选择训练样本数分别为:10、15、20、25、30、35、40、45, 每次执行Bagging算法时SVM分类器个数都为40个。在执行算法中步骤 (3) 时, 我们取step=2。
从图1中可以看到执行到算法步骤 (2) 时这三类s、ve、vi 分别在训练样本数量是45、35、40的时候分类面是最优的, 精度分别为91.1333%、93.3333%、93.6333%, 其学习精度也比其他情况下的学习精度要高。详细的结果见表1。不同类下a的选取:s类, aϵ (40, 45) ;ve类, aϵ (30, 35) ∪ (35, 40) ;vi类, aϵ (35, 40) ∪ (40, 45) 。它们的步长step=2。执行算法步骤 (3) 后的结果见表2与图2所示。
从图2中我们可以看到s, ve, vi分别在训练样本数量是45、34、39的时候得到的精度是最高的, 分别为91.1333%、93.6842%、95.6333%。详细情况见表2。那我们就选定了训练样本数, 把它们作为训练集, 即训练样本数分别为:45、34、39, 测试其他的样本的时候只要对这几个量下的训练样本进行训练就可以了, 并且保证了分类器是较优的。
从表1和表2中还可以看出, 训练样本个数有很小的改变, 测试精度就有很大的改变, 但是, 当训练样本数量到达一定范围的时候, SVM分类器都保持较高的正确率。如ve 在训练样本数量为20的时候, 其分类正确率为92.0000%, 对于此实验来说, 这样的精度是很高的了 (由于训练集中包括了一些测试数据, 出现了用训练集进行测试的问题[4]) 。所以在进行ve类的分类时, 选取的训练样本个数不一定是所有训练集样本数45, 样本数量只要取20个, 我们就可以得到很好的测试效果。在小样本数据中, 我们可以选取训练集中所有样本进行寻优。对训练时间需要几小时或是几天的大样本数据来说, 如果像对小样本数据那样选取训练集中所有样本进行训练, 反而增加了时间代价, 那我们可以用自助网格搜索算法在训练集的小范围的样本集内选取一个最优的分类器。如果在这个小范围内寻得的SVM分类器的分类精度, 研究人员不是很满意, 我们可以适当再扩大选取的训练样本数量的范围, 这样的精度也许不是最好的, 如果是可以接受的精度就可以了, 而它却减少了很多很多的训练时间。
3.2 实验2
为了进一步说明自助网格搜索算法在寻求好的SVM分类器时所体现的良好的性能, 我们又用magic04 (MAGIC gamma telescope data 2004) 数据集进行了实验。该数据集有gamma (signal) 、hadron (background) 两类, 我们分别取其中的4000个样本作为训练集, 3000个样本作为测试集。样本都是随机抽取的。在用算法实验前, 对这4000个训练样本进行训练, 其需要的训练时间大约是2000秒, 时间代价是很大的。
用算法进行实验, 从4000个训练样本抽取500个样本作为执行算法所要的训练集。执行算法步骤 (2) 时, 选step=50, 即选择训练样本数分别为:50、100、150、200、250、300、350、400、450、500, 每次执行Bagging算法时SVM分类器个数都为40个。在执行算法步骤 (3) 时, 我们取step=20。表3为执行算法步骤 (2) 的分类结果。表4为执行算法步骤 (3) 的分类结果。
从表3中可以看到, 在执行了一次算法后, 选择400个样本进行训练时, SVM分类器体现的性能较其它的训练样本下的SVM分类器的性能要好。然后执行算法步骤 (3) , 选 step=10, 在400这个值旁再做一次自助网格搜索, 即划分的区间为 (350, 400) ∪ (400, 450) , 表4是执行算法步骤 (3) 而得到的分类结果。
从表4中可以看出, 在所选择的训练样本集的尺寸为500的范围内, 当训练集中训练样本的个数为410个的时候, SVM分类器的分类精度较其它区间边界处对应样本的尺寸下的分类精度要高, 且其训练时间只要2.020049秒, 较4000个训练时间花费约2000秒的时间要小得多, 从而降低了训练时间的代价。同时可以看到, 选择训练集中训练样本的个数为410的SVM分类器的分类精度是98.9467%, 在测试样本为3000个的时候它只错了35个样本, 这样的错误率是可以接受的。因此, 训练集应该选择410个样本, 其训练样本的尺寸远远小于4000个样本的原训练集样本的尺寸。综上分析, 自助网格搜索算法构造出来的SVM训练集是很优的。
4 总 结
本文是针对SVM最优分类器而提出的一种确定训练集的学习算法, 训练样本集中的数据以及样本尺寸的改变影响着测试精度, 选择合适的训练集能够提高SVM分类器的学习精度以及学习性能。自助网格算法是把Bagging算法与网格搜索算法的思想结合在一起来寻找合适的训练样本集, 实验发现, 该算法能够找到使泛化能力很好的训练集。对大样本数据来说, 主要的缺陷就是训练时间长的问题, 用自助网格算法可以用相对较少的样本进行训练后的性能来预测它对一个非常庞大的训练集的性能, 从而节省了时间。研究表明, 该算法对SVM分类器设计有一定的参考价值。
参考文献
[1]Vapnik VN.The Nature of Statistical Learning Theory[M].NewYork:Springer-Verlag, 1995.
[2]Cherkassky V, Mulier F.Learning from Data:Concept, Theory and Method.NY:JohnViley&sons, 1997.
[3]李琳, 张晓龙.基于RBF核的SVM学习算法的优化计算[J].计算机工程与应用, 2006, 29:190-192.
[4]Xie Z J, Wong H, Ip W C, et al.Artificial neural network and its appli-cation to financial forecasting[J].Acta Scientiarum NaturaliumUniver-sitatis Pekinensis, 2001, 37 (3) :421-425.
[5]Richard O Duda, Peter E Hart, David G Stork.Pattern Classification[M].Znd ed.2003.
模拟寻优 篇3
车道识别与跟踪是智能车辆基于机器视觉自动导航的关键技术。目前,车道检测方法主要包括基于特征和基于模型两大类。前者主要通过道路的边缘、颜色、纹理等特征来检测道路,容易受到光照条件、阴影遮挡、车道曲率、车道线污损的影响。后者先建立道路的参数模型,然后通过图像分析确定模型参数,得到完整的车道线[1]。
基于模型的方法是应用于车道识别和跟踪最合适有效的方法,国内外研究者已提出了多种车道模型。直线模型[2,3]简单,计算量小,对于有曲率的道路匹配不准确;三次曲线模型对于边界曲率半径较小,曲率变化较快的道路识别效果较好,但对边界附近噪声点干扰却比较敏感,且计算量大[4,5];样条曲线模型[6]通过一组控制点生成任意形状,可以描述更多的车道类型,计算损耗大。为弥补单一模型的缺陷,有研究者提出组合模型、切换模型等。对于近视场区域,组合模型利用直线匹配车道线,但是对于远视场模型的选择,组合模型依然面临困难。如果选择直线模型,有曲率道路吻合得不好,如果选择曲线模型,又不利于计算量的控制[7]。文献[8]对远视场区域在直线模型和二次曲线模型之间进行切换,确定车道模型参数时采用投票表决方法,二次曲线拟合曲率变化明显的道路效果不理想。
本文将道路图像分为近景和远景区域,近景区采用直线模型快速拟合车道线。远景区根据切换策略选取直线模型或三次曲线模型匹配车道线,三次曲线模型对于曲率变化明显的道路识别效果好,利用已知的近景区直线模型参数可以减少三次曲线模型的复杂度。结合道路图像的灰度和梯度信息,建立模型参数的概率判别函数,遗传算法操作改进标准粒子群算法,全局搜索车道模型的最优参数,实现车道标识线的拟合。试验表明该算法具有良好的鲁棒性,能有效地抵抗光照变化、阴影以及遮挡等干扰,在结构化和半结构化道路上,能够准确实时地检测车道。
1 车道模型
对于没有曲率的道路,车道线的形状在整个视场范围内都可以用直线去描述;对于有曲率的道路,在近景区域,车道线依然可以用直线近似,但是在远景区域,直线不能够很好的吻合车道线,采用曲线模型更为合适。应用于视觉导航的车道识别算法往往面临着多种使用工况,既会包含直线路段,也会遇到有曲率的路段。如果为了得到较好的车道线匹配效果而始终采用曲线模型,会增加系统的计算负担,影响算法的实时性。
1.1 分段直线模型
在图形坐标中,规定左上角为坐标原点,v代表横轴方向,u代表纵轴方向,图像下部分为近景区域,上部分为远景区域,如图1所示。用LL表示左车道线方程,LR表示右车道线方程。道路近景区域所用的车道模型如式(1)所示:
式中:kL1、bL1为左车道线的模型参数,kR1、bR1为右车道线的模型参数,uborder为图像远、近景区域的分界线,摄像机参数不同,其值也会不同,uborder可由摄像机标定结果确定。
道路远景区域所用的车道模型如式(2)所示:
式中:bL2=vLborder-kL2·uborder,bR2=vRborder-kR2·uborder。(uborder,vLborder)、(uborder,vRborder)分别是左、右车道线上的分界点。
1.2 直线-曲线模型
若道路图像中远近景区域的车道曲率变化明显,则自动切换车道模型,三次曲线模型对于曲率变化明显的道路识别效果好,利用已知的近景区直线模型参数可以使三次曲线模型的四个未知参数减少到三个。近景区域中的车道模型仍认为是直线,车道模型的建立与式(1)相同,如图2所示。
远景区域的车道模型切换成三次曲线模型,如式(3)所示
又因为左、右车道三次曲线模型分别经过分界点(uborder,vLborder)、(uborder,vRborder),故有
联立式(3)和式(4),左车道模型参数的对应关系:aL=aLX,bL=bLX-3·aLX·uborder,cL=cLX+3aLX·u2border-2bLX·uborder,dL=vLborder-aLX·u3border+bLX·u2border-cLX·uborder;右车道模型参数的对应关系:aR=aRX,bR=bRX-3·aRX·uborder,cR=cRX+3·aRX·uborder2-2bRX·uborder,dR=vRborder-aRX·uborder3+bRX·uborder2-cRX·uborder。
1.3 车道模型切换策略
图2中车道模型是近景直线和远景三次曲线的分段组合。初始检测时,左右车道均采用分段直线模型进行最优参数搜索,获得左车道参数kL1、kL2,右车道kR1、kR2。当φL=180abs[arctan(kL1)-arctan(kL2)]/π≥8o时,远景区域的左车道模型切换到三次曲线模型;当φR=180abs[arctan(kR1)-arctan(kR2)]/π≥8o时,远景区域的右车道模型切换到三次曲线模型。
车道检测中对左、右车道线分别采用了独立的模型切换策略和识别模块,仅在最终验证车道线识别结果时对两侧车道线的识别结果进行了关联,好处在于能够使得左、右车道线的识别结果更好地描述车道线的各自特性,不会使得两侧车道线的识别由于过早的关联而丧失应有的灵活性。车道类型如表1所示。
2 概率判别函数
概率判别函数建立在道路图像的梯度幅值、梯度方向和灰度值等信息的基础上,概率判别函数的优劣直接影响最优参数模型对车道拟合结果的好坏。综合考虑像素梯度值、梯度方向、像素灰度以及车道线模型等因素,引入权值,其判别函数表达式为
1)Ω表示一个由变形模板参数X所决定的区域,区域Ω中的像素由变形模板参数X所决定的车道线上的像素(ui,vi),左右邻域像素(ui,vi-1)和(ui,vi+1)共同构成。引入区域Ω保证了只有变形模板参数X所决定的车道线附近的像素才能参与计算,既减少了计算量,又避免了非模型上像素对判别函数的影响。
2)gm(u,v)为归一化后的梯度值,可表示为
式中:Em(u,v)为像素(u,v)的梯度幅值;gmax和gmin分别为归一化前像素梯度的最大值和最小值。可见,像素梯度越大,其属于车道线的概率越大,对判别函数的贡献也越大。
3)α(u,v)表示像素(u,v)的梯度方向与车道模板在点(u,v)的切线方向的夹角,计算公式为
4)I(u,v)是经过归一化后的像素(u,v)的灰度值。
道路图像近景区域的左、右车道线区域分别用45°角Sobel算子、-45°角Sobel算子做卷积,左车道线区域是近景区域图像左边2/3部分,右车道线区域是近景区域图像右边2/3部分。Hough变换是模式识别领域中对二值图像进行直线检测的有效方法,在检测数据点集的共线性时具有较强的抗噪声能力,在道路近景区域中存在阴影、车辆和道路标记等干扰因素,以及车道线污损的情况下,Hough变换也能快速准确地检测车道线,如图3所示。
按照车道模型切换策略,道路远景区域检测时初始模型参数X=k2,ρ(u,v)=k2,当满足模型切换要求时,变形模板参数X=(aLX,bLX,cLX),ρ(u,v)=3aLX(u-u2border)+2bLX(u-uborder)+cLX。右车道变形模板参数照此处理。
3 函数优化
本文中的优化问题就是利用优化算法寻找到一个参数X使得概率判别函数值F(X)最大。引入遗传算法中的复制、交叉、变异操作和粒子群优化相结合算法,将粒子群优化算法所具有的参数少、结构简单和熟练速度快特点,与遗传算法所具有的全局搜索特性、解的多样性和计算并行性的特点相融合,提高算法寻优的速度和精度。算法具体流程如下:
步骤1:初始化粒子群体。变形模板参数X的维数为D,种群规模n=4D,最大迭代次数S=100,当前迭代代数k=1。随机产生n个初始值xid和vid,i=1,2,…,n;d=1,2,…,D。第i个粒子表示为Xi=(xi1,xi2,…,xid),它经历过的最好位置(有最好的适应值)记为Pi=(pi1,pi2,…,pid),也称Pibest;在群体中所有粒子经历过的最好位置的索引号g用符号表示,即Pg=(pg1,pg2,…,pgd)也称为Pgbest。粒子的速度用表示Vi=(vi1,vi2,…,vid)。同时根据式(5)计算每个粒子的适应度。
步骤2:第k(2≤k≤S)次迭代时,第i(1≤i≤n)个粒子的第d(1≤d≤D)维参数根据如下方程更新速度和位置:
其中:惯性权重w=1-k/S,加速度常数c1=c2=1.5,rand1和rand2为两个在[0,1]范围内的随机函数。在式(8)、式(9)中,vkid为第k次迭代粒子i飞行速度矢量的第d维分量,xkid为第k次迭代粒子i位置矢量的第d维分量,pid为粒子i个体最好位置Pibest的第d维分量,pgd为群体最好位置Pgbest的第d维分量。
步骤3:计算粒子的适应度,并更新粒子的个体最好适应值Pibest和全局最好适应值Pgbest。
步骤4:粒子复制。在第k次迭代中,将所有粒子按照适应度值大小升序排列,从中选择适应度最大的m(取m=0.5n)个粒子进行复制。
步骤5:粒子交叉。选取适应度值最小的n-m个粒子作为交叉粒子群,对该粒子群中第i个粒子和第n-m+1-i个粒子配对,粒子对上的参数均匀交叉,形成新的粒子,直接进入下一次迭代。
步骤6:粒子变异。对步骤4中产生的复制粒子群中的粒子进行变异操作,当随机概率rand>Ti时选择第i(1≤i≤m)个粒子,然后对该粒子中的每维参数增加一个小的随机扰动,使其偏离原来的值,从而实现变异操作。
式中:Fmax表示复制粒子群中适应度最大值,Fmin表示复制粒子群中适应度最小值,Fi表示复制粒子群中粒子i的适应度值。
步骤7:算法达到最大迭代次数S时,搜索停止。未满足结束条件,则返回步骤2。
4 实验与分析
为说明本文算法的效果,实验中采用来自卡耐基梅隆大学的视觉与自动化系统实验中心(VASC)的道路序列图像(图像大小256×240),所有测试图像在实验室环境(2.10 GHz的CPU,1 G的内存)下用Matlab编程进行算法效果验证。权值w1设置为0.5,w2为1.5。
对光照条件下的280帧序列图像和阴暗条件下的175帧序列图像分别进行处理,限于篇幅,本文仅给出支持寻优算法的典型场景的处理结果图像。图4(a)中的道路图像分别存在车道线污损、车道线间断、车道遮挡、阴影干扰,拟合结果均能落在车道标志线上,图4(b)中的四帧图像从左至右依次属于车道类型4、1、2、3,参见表1。
为了验证算法的快速性,选取3幅车道曲率变化大的图像,分别采用模拟退火(SA,Simulated Annealing)算法[9,10]、标准PSO算法[11,12,13]、本文算法进行模板参数寻优,检测结果如图5所示。uborder设置为80,远景道路区域图像大小为256×80。上、中、下层三幅道路图像的左车道分界点横坐标分别为77、61、56,右车道分界点横坐标分别为194、178、181。图5(a)为SA算法检测结果,图5(b)为PSO算法检测结果,图5(c)展示本文算法检测结果,其车道模型参数详见表2。
针对每幅图像,每种算法执行5次寻优,最大概率判别函数值所对应的模板参数为最优参数,平均耗时取5次寻优时间的平均值,如表2所示。可以看出:处理车道标识线清晰、光照均匀正常的图像,优化算法耗时少;存在阴影遮挡、车道线污损的图像算法运行时间长;本文算法的效率明显高于标准粒子群算法和模拟退火。
5 结论及工作展望