极小极大问题的生物地理学优化邻近点算法

杨国平,刘三阳,张建科

(1.西安电子科技大学数学与统计学院,陕西西安 710071; 2.西安邮电大学理学院,陕西西安 710121)

极小极大问题的生物地理学优化邻近点算法

杨国平1,刘三阳1,张建科2

(1.西安电子科技大学数学与统计学院,陕西西安 710071; 2.西安邮电大学理学院,陕西西安 710121)

离散型非线性极小极大问题本质上为一个传统的梯度类算法难以求解的不可微优化问题.针对每个分量函数都是凸函数的此类问题,利用熵函数法将其转化为一个光滑的无约束凸优化问题,并将具有并行搜索机制的生物地理学优化算法和具有全局收敛性的邻近点算法相混合,设计了一种具有全局收敛性的混合算法.为了充分发挥生物地理学优化算法的并行搜索机制和无需使用初始点的优点,该混合算法采用生物地理学优化为内层算法邻近点算法为外层算法.数值仿真结果表明,所提算法是求解此类非线性极小极大问题的一种有效算法.

生物地理学优化;进化算法;极小极大问题;邻近点算法

极大极小问题来源于博弈论,是一类重要的不可微优化问题,具有广泛的应用,因此如何求解此类问题具有重要的理论意义和实际价值.求解此类问题的主要困难在于目标函数的不可微性,这就使得经典的梯度类算法难以直接使用.文献[1]基于熵函数法将极小极大问题转化为一个光滑优化问题进行求解.文献[2]针对约束极小极大问题提出一种解决此类问题的可行信赖域算法.文献[3]采用提升技术将极小极大问题转化为无约束优化问题并设计了一个光滑化信赖域拟牛顿算法.这些算法均取得了良好的计算效果,然而,提升技术和极大熵函数法的本质优势是将问题转化为可微的优化问题,进而采用基于传统的梯度类算法进行求解[1-3],这些算法依赖于初始点的选取、梯度和海森阵的计算,特别是在一些实际问题中计算量主要集中在梯度和海森阵上.

近年来,差分进化[4]、粒子群优化[5]、细菌觅食优化[6]及生物地理学优化[7]等智能优化算法因具有无需梯度信息和选取初始点的优点而得到了广泛应用.生物地理学优化算法(Biogeography-Based Optimization,BBO)是模拟生物物种在各栖息地之间迁入、迁出及消亡过程而提出来的一种智能优化算法[7].BBO算法由于进化机理的新颖性,近几年已经得到了极大的发展,其优化性能已被大量标准测试函数和实际应用问题所检验[7-9].目前,BBO算法已成功应用于图像处理、天线优化、混沌系统参数估计等领域[10-11].近年来,将各类智能优化算法与极大熵相结合来求解极大极小问题已受到一些研究者的关注.文献[12]提出了一种粒子群算法与极大熵函数法相结合的混合算法;在此基础上,一些研究者还将该方法推广到非线性l1模极小化问题和非线性互补问题上,并取得了一些成效[13].因为,这些算法属于随机搜索算法,本质上仅仅是依概率收敛的,熵函数仅起到将不可微优化问题转化为可微优化问题的作用;因此,算法不能保证100%收敛到问题的全局最优解.

笔者以每个分量函数均为凸函数的离散型非线性极小极大问题为研究对象.首先,采用熵函数法给出极小极大问题一个无约束的光滑逼近子问题;然后,将生物地理学优化算法作为内层算法,邻近点算法作为外层算法,构造出100%收敛的生物地理学优化-邻近点混合算法.文中选取几个典型的离散型非线性极小极大问题进行测试,测试结果表明,该算法是求解此类问题的一种有效算法.

1　离散型非线性极小极大问题的转化

一般的离散型非线性极小极大问题表示如下:

其中,fi(x),x∈D⊂Rn,(i=1,2,…,m,m≥2)为可微凸函数.因目标函数f(x)的不可微性使得该问题成为一个复杂的非光滑凸优化问题.采用熵函数作为光滑技术将该离散型非线性极小极大问题转化为一系列光滑的逼近子问题.

定理1 对任意x∈D⊂Rn,函数Fp(x)与f(x)在D上满足[12]:

即当p→+∞时,Fp(x)在D上一致收敛到f(x).

定理2 对任意x∈D⊂Rn,若fi(x)中存在一个严格凸函数,则Fp(x)满足如下性质:

(1)函数Fp(x)是严格凸的可微函数;

(2)函数Fp(x)随参数p的增大而减小,且Fp(x)从上方一致逼近f(x);

(3)Fp( x)与f(x)之间的误差不超过(ln m)p.

定理1给出了极大熵函数逼近目标函数时产生的误差,当控制参数p充分大时,就可以用极大熵函数Fp(x)替代目标函数f(x);定理2表明极大熵函数与目标函数具有相同的凹凸性.这就为将离散型非线性极小极大问题转化为一个光滑优化问题提供了坚实的理论基础.控制参数p取值适当大时即可保证具有较高的求解精度.例如,若m=3,取p=103,此时计算误差就不会超过ln3×10-3.

2　生物地理学优化邻近点混合算法

2.1生物地理学优化算法

BBO算法主要由迁移算子(Migration operator)和变异算子(Mutation operator)两个算子组成,它们分别模拟了生物地理学中物种在栖息地之间的迁移、突变及其消亡过程.算法的基本原理是将种群中的每个个体模拟成一个栖息地(habitat),采用该栖息地的适宜度指数(Habitat Suitability Index,HSI)对个体进行评价,将刻画该栖息地的特征变量(如气候、植被、降雨量等因素)定义为适宜度索引变量(Suitable Index Variable,SIV)用来表示自变量,并以此设计了个体迁移算子(Habitat migration)和个体变异算子(Habitat mutation),使得不同个体间可以进行信息共享,从而获得问题的最优解.个体的适宜度指数HSI越高,候选解越好,反之亦然.适宜度指数高的个体以更大的概率共享自己的特征,而适宜度指数低的个体以更大的概率接受此特征.

BBO算法中,每个栖息地具有各自的迁入率λ和迁出率μ.栖息地迁入率越高,表明栖息地所含物种数越少,当该栖息地中的物种数目为0时,该栖息地λ=I,μ=0.每个栖息地的λ和其具有的物种数目成反比而μ和物种数目成正比,当该个体中的物种数目达到最大时,此时,λ=0,μ=E,I,E分别表示最大迁入率和迁出率.设BBO算法种群中第k个个体包含k个物种时,则常用的线性迁移公式为

其中,n表示该个体所能容纳的最大物种数,根据生物地理学的不同数学模型,可以得到不同的迁移公式,通常考虑最大迁入率和最大迁出率相等的情形.迁移算子就是基于迁移公式的个体特征交换方法,它使BBO算法具有很强的开发能力,详见文献[7].

BBO算法中,变异算子根据栖息地所含物种数量k的概率以随机方式对其特征变量进行变异运算,用以增加种群的多样性.生物物种数量的概率大,意味该栖息地的生态系统处于一个相对平衡的状态,发生突变的可能性小.反之,生物物种数量概率较少,栖息地的生态系统处于不稳定状态,栖息地容易受外突发事件的影响,发生突然变异,从而导致栖息地的生物物种数量急剧增多或减少.因此,种群中第k个个体的变异概率与该栖息地的数量概率成反比,其计算公式为

其中,mmax为用户指定的变异率,并且Pmax=arg max Pk,k=1,2,…,n,是指栖息地的种群概率的最大值.

变异算子可以增加种群的多样性,从而增强算法的全局搜索性能.

2.2邻近点算法

邻近点算法(Proximal Point Algorithm,PPA)是求解凸优化问题的一类基本方法.近年来,一些研究者从理论和算法设计两个方面对PPA算法进行了深入的研究[14-16].

考虑以下无约束凸优化问题:

其中,f(x)为闭正则凸函数.

采用邻近点算法求解式(5),其迭代序列{xk}由如下式子产生:

其中,x0∈Rn,为任意选取的初始点,{λk}为正值有界序列,D(x)为距离函数.早期的邻近点算法常采用欧氏距离函数,近年来,Bregman函数、类似熵函数等满足凸性的距离函数相继被提出来.根据不同的距离函数可以设计不同类型的邻近点算法,对凸优化问题,邻近点算法产生的迭代序列{xk}收敛于问题的全局最优点,详细内容见文献[14].

2.3生物地理学优化邻近点混合算法

针对离散型极小极大问题,采用生物地理学优化算法求解临近点子问题式(6),将其嵌入到临近点算法中设计出生物地理学优化-邻近点混合算法.

2.3.1混合算法的主要步骤

步骤1 给定初始点x0,控制参数p,正数λ0,置k:=1;

步骤2 执行BBO算法求解邻近点子问题,得到xk+1;

步骤3 检验是否满足算法终止条件,若是,算法停止;否则,置k:=k+1,转步骤2.

2.3.2生物地理学优化算法

步骤1 随机生成初始种群;

步骤2 计算每个个体的适宜度指数(HSI),对问题式(1),其适宜度指数为,此处的距离函数也可以使用其他距离;

步骤3 计算每个个体的种群数k,迁入率λ和迁出率μ;

步骤4 基于迁入率λ和迁出率μ对种群中进行个体的迁移运算;

步骤5 用变异算子对种群中的个体进行变异;

步骤6 采用精英选择策略保留最好个体;

步骤7 如果终止条件满足,则停止;否则,返回到步骤2执行下一次的迭代.

2.3.3两点说明

(2)由于邻近点算法的全局收敛性,内层生物地理学优化算法只需求得邻近点子问题的近似最优解,因此,其种群规模和迭代次数不必选取得太大.

3　数值实验

为了检验所提生物地理学优化-邻近点算法(记为PPBBO)的有效性,采用4类典型的测试函数进行测试并与标准的生物地理学优化算法和经典的梯度类算法进行比较.在MatlabR2008a编程环境下,采用Intel (R)Core(TM)i3-3110M,2.40 GHz CPU内存2 GB的微机进行实验.PPBBO和标准BBO算法的参数设置如下:种群规模:PN=5D;最大迁入概率I=1;最大迁出概率E=1;变异率mmax=0.05;求解精度ε=10-6;光滑参数p=106;最大迭代次数(MaxIter)为100.算例1和算例2的每个变量搜索范围分别为[-2,2]和[-3,3];初始点x0分别为(0.3,0.5)和(0.5,0.5,1,-0.5).算例3和算例4的每个变量搜索范围均为[-5,5].经典梯度类算法选取文献[5]中的信赖域牛顿共轭梯度算法(记为TRNCG).为公平比较起见,采用与文献[3]中相同的光滑函数,对算例3和算例4中不同维数和函数个数进行仿真.各算法独立运行30次,统计它们的运行时间和目标值,仿真结果见表1.

表1　算法PPBBO和其它算法的统计结果

问题2 考虑如下非线性极小极大问题:

已知最优解和最优值分别为x*=(0,1,2,-1)T,f(x*)=-44.

从表1可以看出,随着极小极大问题规模的增大,PPBBO、TRNCG及标准BBO在相同的精度要求下,算法耗费时间越来越长,BBO算法对同样问题规模耗费时间大概是PPBBO两倍以上;而对例3和例4问题维数不超过80时,PPBBO和TRNCG算法耗时相差无几,但当维数超过100时,PPBBO耗时接近TRNCG的两倍.从这几个典型的数值算例说明,PPBBO算法在一定程度上综合了经典算法在迭代过程每一步都取最优的优点,改善了随机搜索的盲目性;同时将随机算法多点搜索优点引入经典算法,使得经典算法在一定程度上放宽对初始点的苛刻要求.

4　结束语

采用熵函数法将一类每个分量函数都是凸函数的离散型非线性极小极大问题转化为一个可微的优化问题,并将生物地理学优化算法与邻近点算法相混合提出了求解此类问题的一种新的混合算法.新算法具有智能算法的并行性和邻近点算法的全局收敛性的两个优点.数值算例仿真结果表明,在计算的精度方面与文献[3]所得结果相当,并且当控制参数p足够大时,所得结果与理论值趋于一致.为了与传统的优化算法作比较研究混合算法的性能,采用分段多项式光滑函数为光滑化函数进行试验,新算法在求解时间上比标准BBO算法有及大的降低,在精度上和TRNCG算法相差无几,在计算成功率上达到100%.以上指标表明了新算法求解此类非线性极小极大问题的有效性.

[1]黄震宇,沈祖和.解一类非线性极大极小问题的熵函数方法[J].科学通报,1996,41(17):1550-1554. HUANG Zhenyu,SHEN Zuhe.Entropy Function Method for Solving a Class of Nonlinear Minimax Problem[J]. Chinese Science Bulletin,1996,41(17):1550-1554.

[2]欧宜贵,邓谋杰,洪世煌.一类极大极小优化问题的信赖域算法[J].工程数学学报,2004,21(8):41-57. OU Yigui,DENG moujie,HONG Shihuang.Trust Region Algorithm for a Class of Minimax Optimization Problems [J].Journal of Engineering Mathematics,2004,21(8):41-57.

[3]YE F,LIU H W,ZHOU S S,et al.A Smoothing Trust-region Newton-CG Method for Minimax Problem[J].Applied Mathematics and Computation,2008,199(2):581-589.

[4]李蕊,史小卫,徐乐,等.竞争差分进化算法及其在共形阵综合中的应用[J].西安电子科技大学学报,2012,39(3): 114-119. LI Rui,SHI Xiaowei,XU Le,et al.Synthesis of a Conformal Antenna Array Using the Competition Differential Evolution Strategy[J].Journal of Xidian University,2012,39(3):114-119.

[5]常磊,顾华玺,张之义,等.一种粒子群优化的用户优先级虚拟网络映射算法[J].西安电子科技大学学报,2015,42(1):16-22. CHANG Lei,GU huaxi,ZHANG Zhiyi,et al.Particle Swarm Optimization User-priority Virtual Network Embedding Algorithm[J].Journal of Xidian University,2015,42(1):16-22.

[6]姜建国,周佳薇,郑迎春,等.一种自适应细菌觅食优化算法[J].西安电子科技大学学报,2015,42(1):75-81. JIANG Jianguo,ZHOU Jiawei,ZHENG Yingchun,et al.Adaptive Bacterial Foraging Optimization Algorithm[J]. Journal of Xidian University,2015,42(1):75-81.

[7]SIMON D.Biogeography-based Optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(6):702-713.

[8]MA H P,DAN S,FEI M R,et al.Hybrid Biogeography-based Evolutionary Algorithms[J].Engineering Applications of Artificial Intelligence,2014,30:213-224.

[9]GONG W Y,CAI Z H,LING C X.DE/BBO:A Hybrid Differential Evolution with Biogeography-based Optimization for Global Numerical Optimization[J].Soft Computing,2011,15(4):645-665.

[10]郑肇葆.生物地理学优化(BBO)在图像分割中的应用[J].武汉大学学报:信息科学版,2011,36(8):932-935. ZHENG Zhaobao.Application of Biogeography-based Optimigation to Image Segmentation[J].Geomatics and Information Science of Wuhan University,2011,36(8):932-935.

[11]WANG L,XU Y.An Effective Hybrid Biogeography-based Optimization Algorithm for Parameter Estimation of Chaotic Systems[J].Expert Systems with Applications,2011,38(12):15103-15109.

[12]周畅,张建科.一类非线性极小极大问题的粒子群-邻近点算法[J].计算机工程与应用,2012,48(36):19-22. ZHOU Chang,ZHANG Jianke.Particle Swarm Optimization-proximal Point Algorithm for a Class of Nonlinear Minimax Problems[J].Computer Engineering and Applications,2012,48(36):19-22.

[13]雍龙泉,刘三阳,张建科,等.基于差分算子的和声搜索算法求解非线性l1极小化问题[J].兰州大学学报:自然科学版,2013,49(4):541-546. YONG Longquan,LIU Sanyang,ZHANG Jianke,et al.Improved Harmony Search Algorithm with Differential Operator for Nonlinear l1Norm Minimization Problems[J].Journal of Lanzhou University(Natural Sciences),2013,49(4):541-546.

[14]DONG Y D.The Proximal Point Algorithm Revisited[J].Journal of Optimization Theory and Applications,2014,161(2):478-489.

[15]YAO Y H,SHAHZAD N.Strong Convergence of a Proximal Point Algorithm with General Errors[J].Optimization Letters,2012,6(4):621-628.

[16]HARE W L,LUCET Y.Derivative-free Optimization via Proximal Point Methods[J].Journal of Optimization Theory and Applications,2014,160(1):204-220.

(编辑:王 瑞)

Biogeography based optimization-proximal point algorithm for nonlinear minimax problems

YANG Guoping1,LIU Sanyang1,ZHANG Jianke2
(1.School of Mathematics and Statistics,Xidian Univ.,Xi’an 710071,China; 2.School of Sciences,Xi’an Univ.of Posts and Telecommunications,Xi’an 710121,China)

Concerning the discrete nonlinear minimax problems with the convex function as each of its components,a new method,called the biogeography based optimization-proximal point algorithm,is presented.By using maximum-entropy methods,the minimax problem is transformed into the unconstrained optimization problem of the smooth function.The algorithm employs the proximal point algorithm as the outer algorithm,and the biogeography based optimization as the internal algorithm.The proposed algorithm which resolves several minimax problems is global convergent.Preliminary numerical experiments show that the proposed algorithm is an effective algorithm for nonlinear minimax problems.

biogeography based optimization;evolutionary computation;minimax problems;proximal point algorithm

O224

A

1001-2400(2016)05-0088-05

10.3969/j.issn.1001-2400.2016.05.016

2015-07-28 网络出版时间:2015-12-10

国家自然科学基金资助项目(61373174,71271165);陕西省教育厅自然科学专项基金资助项目(2013JK1130,11JK1051);中央高校基本科研业务费专项资金资助项目(JB140705,2014GXNSFBA118023)

杨国平(1975-),男,副教授,硕士,E-mail:guoping02@126.com.

网络出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.032.html