作者简介:宁剑平(1966—),男(汉族),湖南省衡阳市人,广州军区76127部队高级工程师.E-mail:1002624905@qq.com
中文责编:英 子; 英文责编:雨 辰
1)广州军区76127部队,湖南 郴州 424202; 2)军械工程学院,石家庄 050003
Ning Jianping1, Wang Bing1, 2, Li Hongru2, and Xu Baohua21)76127 Unit, Guangzhou Military Area, Chenzhou 424202, Hunan Province, P.R.China2)Ordnance Engineering College, Shijiazhuang 050003, P.R.China
artificial intelligence; optimization algorithm; fruit fly algorithm; global optimiation; diminishing step; support vector machine(SVM); regression model
DOI: 10.3724/SP.J.1249.2014.04367
提出一种递减步长果蝇优化算法(diminishing step fruit fly optimization algorithm,DS-FOA).该算法的搜索步长随果蝇觅食进程逐步减小,从而使果蝇群体在觅食初期具有较强的全局搜索能力,在觅食后期具有较强的局部寻优能力,从而实现全局搜索能力和局部寻优能力的平衡.将该算法用于支持向量机(support vector machine,SVM)回归模型的惩罚因子和核函数参数优化中,结果表明,DS-FOA收敛速度快,全局搜索与局部寻优能力强.与其他算法相比,由DS-FOA优化参数的SVM回归模型均方误差最低,回归效果好.
A diminishing step fruit fly optimization algorithm(DS-FOA)is proposed.The step length is decreased progressively along with the process of foraging.DS-FOA demostrates preferable global optimization capability in early stage and local optimization capability in later period.Dynamic balance is achieved between global and local optimizing capability.Also DS-FOA is applied in the field of support vector machine(SVM)regression model parameter optimization.Experimental results show that the DS-FOA has fast convergence speed and powerful global and local optimization capability.The SVM model using DS-FOA has the lowest error of mean square and the best optimization result.
支持向量机(support vector machine,SVM)[1-2]是一种基于统计学理论的机器学习算法,该算法利用VC维(Vapnik-Chervonenkis dimension,VC维)理论和结构风险最小化原则,研究小样本下模型的泛化能力,具有理论完备性好、适应性强、全局优化及泛化性能好等优点.SVM的性能主要取决于核函数和参数的选取,如何根据实际问题选择合适的核函数和参数是关键.但该问题目前还缺乏理论指导[3].当前常见的参数寻优方法包括梯度下降算法、遗传算法和粒子群优化算法[4]都存在缺陷. 梯度下降法效率低,稳定性不高[5]; 遗传算法收敛速度慢,容易陷入局部最优值[6]; 粒子群优化算法较遗传算法收敛速度快也更易于实现,但容易陷入局部最优,局部搜索能力较差.
果蝇优化算法(fruit fly optimization algorithm,FOA)是2011年潘文超提出的一种根据果蝇觅食行为推演出的寻求全局优化的群智能方法.该算法通过嗅觉搜索提高果蝇个体的多样性,增大果蝇个体的搜索空间,通过视觉搜索使果蝇个体快速收敛.该算法具有参数少、计算速度快、全局寻优能力强和易于实现等特点,现已在许多领域得到了有效的研究与应用[7-10].
本研究针对果蝇优化算法中固定步长对于搜索效率敏感,且不易选取的问题,提出一种递减步长果蝇算法(diminishing step fruit fly optimization algorithm,DS-FOA),将固定步长改为依觅食进程递减.运用该算法优化SVM回归模型的惩罚因子c与核函数参数g, 选取样本数据进行预测分析,并将该算法与FOA、粒子群优化(particle swarm optimization,PSO)算法和遗传算法(genetic algorithm,GA)进行性能对比.
FOA首先随机初始化果蝇群体的位置坐标,根据群体的位置随机初始化群体中的果蝇利用嗅觉搜索食物的随机方向和距离.由于无法得知食物的位置,因此先估计果蝇与原点的距离,以距离的倒数做为当前的味道浓度判定值,以此判定值得到每个果蝇个体的味道浓度.保留最佳味道浓度值和果蝇最佳个体位置,果蝇群体即利用视觉往该位置飞去.在新的最佳位置重新初始化群体果蝇位置,并重复上述过程,直到找到最优的食物位置为止.FOA步骤如下:
1)在设定区间随机初始化果蝇群体位置坐标(x,y).
2)根据果蝇群体位置坐标,采用式(1)初始化群体中果蝇个体的位置坐标,使该个体果蝇利用嗅觉搜寻食物.
{Zxi=x+Lr
yi=y+Lr(1)
其中, Lr为在固定步长区间[-L,L]内随机生成的步长值,可由Lr=L×rands(1,1)求得, L为果蝇个体利用嗅觉搜索的固定步长值.
3)由于果蝇群体无法得知食物位置,因此需先采用式(2)估计第i个果蝇个体与坐标原点的距离di, 再按照式(3)计算味道浓度判定值Si.
di=(x2i+y2i)1/2(2)
Si=1/di(3)
4)将Si代入味道浓度判定函数(fitness function)中,得到该果蝇个体利用嗅觉得到的味道浓度为
smelli=fitness function(Si)(4)
5)找出果蝇群体中味道浓度最高的个体,即
[bestsmell bestindex]=max(smell)(5)
其中,bestsmell为最高的味道浓度; bestindex为果蝇群体中具有最高味道浓度的果蝇个体序号; smell为果蝇群体的味道浓度集合.
6)判断味道浓度是否优于前一代的浓度,若是,则执行7); 否则,重复执行2)至6).
7)利用式(6)和式(7)保留最佳味道浓度值与最佳果蝇个体的位置坐标,使果蝇群体利用视觉向该位置飞去.
smellbest=bestsmell(6)
{Zxbest=x(bestindex)
ybest=y(bestindex)(7)
8)判断是否达到结束条件(通常根据实际问题设至固定适应度值或最大迭代代数),若是,则找到最优食物位置; 否则,执行2).
在FOA步骤2)中,步长L设为固定值,即在每次觅食迭代中,果蝇个体利用嗅觉在果蝇群体位置周围以步长值为单位,随机搜索.显然,在果蝇群体个数一定的情况下,步长越大,果蝇个体的搜索空间越大,全局搜索能力越强,但其局部寻优能力会降低; 反之,若步长过小,则果蝇个体的局部寻优能力较强,搜索空间较小,全局搜索能力较弱,果蝇个体容易陷入局部最优.可见,在FOA中,步长参数的选取直接影响算法的执行效率.因此,运用果蝇算法解决实际问题时,必须选择合适的步长值,使之既有较强的全局搜索能力以免陷入局部最优,又具有较好的局部寻优能力,以提高搜索的精度.
本研究通过分析模拟实验结果,基于果蝇算法,变固定补偿为递减补偿,提出DS-FOA算法,并设步长值为
L=L0-(L0(G-1))/(Gmax)(8)
其中,L0为初始步长值; Gmax为最大觅食迭代数; G为当前觅食代数.
当第1代果蝇觅食时,L=L0, 果蝇个体步长为最大值L0. 果蝇觅食迭代每增加1代,步长减小L0/Gmax, 直至最后一代减至L0/Gmax.
显然,DS-FOA在迭代初期具有最大的搜索步长,此时,搜索空间大,全局寻优能力最强.随着觅食迭代次数的增加,算法的局部搜索能力逐渐增强,保证了觅食初期有较大概率找到全局最优解,却不致于陷入局部最优,觅食末期能达到最大的搜索精度,从而实现全局搜索能力和局部寻优能力的平衡.
为验证DS-FOA的寻优效果,以正弦变化率函数为例进行模拟分析,如式(9).
Y=sin(10πt)/t, t∈[0,2](9)
该函数的特点是在定义域内具有一个最小值和多个局部极小值,对应的函数曲线如图1.
分别选用固定步长为3和30的FOA以及初步长为30的DS-FOA进行最小值寻优,参数设置见表1.按照果蝇算法规则,将自变量定义为
t=1/((x2+y2)1/2)(10)
经觅食迭代后,3种模拟实验的最优值觅食曲线及果蝇飞行轨迹分别见图2、图3和图4.
由模拟分析可见,DS-FOA算法在觅食初期,由于搜索范围的最大化,全局寻优能力强,第1代即达到较优值-6.748; 随着觅食迭代次数的增加,算法结果逐渐接近最优值,觅食末期,随着局部搜索能力的增强,还有轻微的最优值调整; 最后在第48 代处达到最优值-6.825,由该果蝇个体的觅食
路线也可观察到果蝇群体由稀疏到稠密的进化过程; L=30时,FOA的全局搜索能力强,在第7代即达到最优值-6.824,但之后一直不变. 可见,固定的搜索尺度导致大步长FOA在迭代后期局部搜索能力不强,果蝇个体在([-20,20], [-20,20])的直角坐标系范围内呈近似均匀分布状态,全局搜索能力强,而局部搜索能力不足; 当L=3时,果蝇在第17代达到最优值-2.869. 可见,由于小步长导致算法局部搜索能力强,全局搜索能力弱,使算法过早地陷入局部最优值.果蝇个体在([-4,0], [-2,4])的直角坐标范围内呈均匀搜索状态,搜索空间过小,无法跳出局部最优解.
综上研究认为,DS-FOA保持了搜索过程中的搜索尺度变化,平衡了算法的全局与局部搜索能力,对于寻优问题取得较好效果.
为考察DS-FOA优化算法的应用效果,运用该
算法优化SVM模型惩罚因子参数c和核函数参数g. 采集大智慧证券软件1997-10-22到2009- 08-19记录的上证指数作为实验测试数据.该样本数据是一个2 079×6的矩阵,记录了此时间段内的2 079个交易日每日上证综合指数的6种指标.假设当日开盘指数为因变量,前一日6种指标值为自变量.选取前2 069组数据为SVM训练样本,后10组数据作为检测SVM回归模型性能的验证样本.
由于样本向量中各指标的数量级差别较大,为便于计算并减小误差,采用式(12)对输入样本进行归一化处理,而对SVM模型的输出则进行反归一化处理,即式(12)的逆运算,如此便可得到实际预测数据.
X ^=(X-Xmin)/(Xmax-Xmin)(12)
其中,Xmax和Xmin分别为辅助变量X的上下限值.本研究取Xmax=2,Xmin=1.
基于训练样本数据,分别运用DS-FOA、FOA、PSO[12-13]和GA[14]对SVM回归模型参数c和g进行优化.每种算法进行10组实验.SVM的参数训练采用K-CV方法,本研究取K=3.这4种优化算法均以训练样本最低均方误差作为个体适应度值,主要参数设置如表2.
图5为典型的第5组算法寻优进化曲线对比图,表3为4种算法10组实验优化结果的定量对比. 由分析可见, DS-FOA的寻优精度最高,且运行时间最短,因此,搜索效率最高; FOA运行时间与DS-FOA相近,但由于局部寻优能力较低,导致寻优精度略低; PSO与GA优化算法的运行速率远低于DS-FOA与FOA,而前两者相比,PSO的寻优精度较高,GA则由于过早收敛而陷入局部最优,寻优精度最低.可见,DS-FOA在保持FOA的优势前提下,进一步提高了算法的寻优精度和搜索效率.
针对实际问题中果蝇优化算法(FOA)步长参数对寻优效率影响权重大、不易选取的不足,提出递减步长果蝇优化算法(DS-FOA).该算法实现了全局搜索能力和局部寻优能力的平衡,使果蝇群体伴随觅食行为进程,实现全局搜索能力和局部寻优能力的此消彼长.将DS-FOA应用到SVM模型的参数优化中,仿真结果表明,其搜索效率、预测精度和运算速度均取得较好效果.与FOA、PSO和GA算法相比,DS-FOA优化参数的SVM回归模型的均方误差最低,回归效果好.
深圳大学学报理工版
JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING
(1984年创刊 双月刊)
主 管 深圳大学
主 办 深圳大学
编辑出版 深圳大学学报理工版编辑部
主 编 阮双琛
国内发行 深圳市邮电局
国外发行 中国国际图书贸易集团有限公司(北京399信箱)
地 址 北京东黄城根北街16号
邮 编 100717
电 话 0755-26732266
0755-26538306
Email journal@szu.edu.cn
标准刊号 ISSN 1000-2618
CN 44-1401/N