整数规划的量子行为蝙蝠算法

李枝勇,马 良,张惠珍

(上海理工大学管理学院,上海 200093)

1 引言

整数规划问题是运筹学中的一门重要内容,在工业、商业、运输、经济管理和军事等诸多领域中都有广泛的应用,如决策变量为人数、机器台数、商店个数等,要求其取值为整数[1]。对于规模较小的整数规划问题,常用的精确求解方法有分支界定法和割平面法,但随着问题规模的增大,精确算法变得不可取。为此,多年来人们设计了各种启发式算法来应对实际工作的需求。如蜂群算法[2]、粒子群算法[3]、量子行为粒子群算法[4]和蚁群算法[5]等。

蝙蝠算法BA(Bat Algorithm)是Yang Xin-she[6]受启发于微型蝙蝠的回声定位行为方式与优化目标功能的相关联性,于2010年提出的一种新型启发式算法。自该算法提出以来,已有学者将该算法应用于优化问题[7～9],他们的研究成果表明:相比于粒子群算法、遗传算法和和声算法,蝙蝠算法具有发挥更大作用的潜能。但是,通过大量的实验测试,发现传统的蝙蝠算法的聚集性限制了蝙蝠的搜索范围,因此它不允许蝙蝠出现在远离蝙蝠种群的位置,即使这个位置可能会好于当前最好位置。

具有量子系统的QBA可以克服传统蝙蝠算法的不足,这是由于:

(1)量子系统是态叠加原理作用的一个复杂的非线性系统,所以一个量子系统比一个线性系统能描述的状态更多。

(2)量子系统与经典随机系统不同,是一个不确定系统，即在测量之前没有既定的轨道。

(3)概率密度函数描述的束缚状态的蝙蝠可以以一定概率出现在整个可行搜索空间的任何区间。

本文在蝙蝠算法中引入量子理论,提出了基于势阱的具有量子行为的蝙蝠算法。实验结果表明,量子行为蝙蝠算法QBA(Quantum-behaved Bat Algorithm)性能优越,具有较好的收敛性。

2 蝙蝠算法

蝙蝠是一种神奇的动物,它靠一种声纳(也称回声定位器)来探测猎物,避免障碍物,在黑暗中找到他们的栖息地，其探测猎物和避免障碍的原理都是基于回声定位的声学原理。虽然蝙蝠发射出的脉冲的持续时间很短,但是蝙蝠发出的脉冲的频率通常为25 kHz 到150 kHz,波长λ的范围在2 mm到14 mm,波长类同于蝙蝠搜寻猎物的大小。蝙蝠发出的声波的响度能达到110 dB,且响度可以从搜索猎物时的最高变化到靠近猎物时的最小。

2.1 蝙蝠的速度更新和位置更新

Fi=Fmin+(Fmax-Fmin)ε

(1)

(2)

(3)

其中,Fi、Fmax、Fmin分别表示第i只蝙蝠在当前时刻发出的声波的频率、声波频率的最大值和最小值；ε∈[0,1]是随机产生的数；x*表示当前全局最优解。

一旦从现有最优解集中选择一个解(蝙蝠),该蝙蝠所处的新位置可通过公式(4)产生:

xnew(i)=xold+AVt

(4)

其中,xold表示从当前最优解集中随机选择的一个解,AVt表示当前蝙蝠种群响度的平均值,为每个分量属于[-1,1]的d维随机向量。

2.2 响度和脉冲速率

脉冲的响度A(i)和发射速率R(i)要随着迭代过程的进行来更新。通常,在接近猎物的过程中,响度会逐渐降低,脉冲发射的速率会逐渐提高。更新方程如式(5)和式(6):

At+1(i)=θAt(i)

(5)

Rt+1(i)=R0(i)×[1-exp(-ϑt)]

(6)

其中,0<θ<1,ϑ>0,均为常量。不难发现，当t→∞时，At(i)→0,Rt(i)→R0(i)。

相比于现存的其他元启发式算法,蝙蝠算法具有以下两个优势:频率调谐;条件满足时会自动从全局搜索转换到局部搜索上来,从而实现了动态控制全局搜索和局部搜索的相互转换。

3 量子行为蝙蝠算法

QBA是一种具有量子行为的蝙蝠算法。QBA中的每只蝙蝠都是量子中的一个粒子。量子空间中,依据粒子的势场,通过概率密度函数|Ψ(X)|2来获得粒子在某一点出现的概率。为使粒子不发散,能够汇聚到它们的局部点P,在点P(p2,p2,…,pd)使用可变的势阱,从而使粒子具有聚集态[10]。

简单地说,首先考虑粒子在一维空间时的情形。在一维空间中,点作为势的中点,粒子的势能δ势阱可表示为:

V(X)=-γδ(X-P)

(7)

因此,根据一维定态Schrödinger方程获得归一化的波函数:

(8)

概率密度函数:

(9)

分布函数:

(10)

参数L是δ势阱的特征长度,是进化方程中最重要的参量。使用蒙特卡罗方法,可以得到粒子的位置:

(11)

参数L由下面的方程求得:

L(t)=2α|P-X(t)|

(12)

从而,粒子的迭代方程可由下式表示:

(13)

用平均最优位置mbest表示所有粒子当前的平均最优解,如下式所示:

(14)

其中，N表示蝙蝠的个数;Pi是蝙蝠i所经历的位置;L的值由下式给出:

L(t)=2α|mbest-X(t)|

(15)

α称为收缩-扩张系数。从而蝙蝠位置的迭代方程可以写为:

(16)

为了保证算法的收敛性,每个粒子必须收敛于各自的局部点P点,它是每个粒子唯一的局部吸引子,可表示为:

(17)

需要指出的是:应用到下文所提的量子蝙蝠算法,当进行局部搜索时,

(18)

P=Pbest

(19)

综上所述,方程(16)～(19)即为QBA的量子搜索优化的核心迭代方程。综合基本蝙蝠算法的步骤,则QBA步骤如下:

步骤1初始化蝙蝠种群大小为n,初始种群中第i只蝙蝠位置为x(i,:),脉冲发射速率为R(i),脉冲响度为A(i),脉冲频率为F(i),计算个体适应值fitness(i,:)=f(x(i)),i=1,2,…,n。

步骤2判断是否满足算法结束条件,如果满足,则转步骤8,否则转步骤3。

步骤3利用式(16)和式(17)产生xnew。

步骤4产生一个[0 1]的随机数rand,如果rand>R(i),则从当前最优解集中随机选择一个解xold,并利用式(18)和式(19)得到xnew。

步骤5计算fnew=f(xnew)。

步骤6产生一个[0 1]的随机数rand,如果rand<(A(i)+0.93)且fnew

步骤7更新当前最优解x*,转步骤2。

步骤8算法结束,输出、分析和处理实验数据。

4 仿真实验

利用表1中的七个整数规划问题的测试函数来检验QBA算法的性能。

Table1 Test functions表1 测试函数

本文选取文献[4]中的粒子群(PSO)算法和量子行为粒子群(QPSO)算法与QBA算法进行比较。其中PSO算法和QPSO算法针对上述函数的实验结果,直接引用其最好的实验结果。

Table 2 Some parameters of test functions表2 测试函数的部分参数

算法初始化参数如下:初始群体均匀分布在d维空间中，每个个体在每一维的取值区间为[-100,100]。每个测试函数将用QBA算法各独立求解50次,记录每次的求解结果和达到最优解需要的迭代次数,在迭代过程中,保留算法寻优过程产生的一切值；另外，单独对实数领域的蝙蝠位置进行取整并求整数空间领域的函数值,同时进行相应的整数最优解和函数最优值的更新操作。算法的收缩-扩张系数也在三个不同区间[1.4,0.4]、[1.4,0.6]、[1.4,0.8]内随迭代次数的增加而线性减少。测试函数的维数、对应的群体规模和最大迭代次数设置情况完全与文献[4]中一致,详见表2。另外,Qmax=0.05,Qmin=0,θ=0.9,ϑ=0.9初始响度均为7,初始发射速率均为0.5,初始频率均为0。

算法的运行环境为Win7系统下的MATLAB7.8(R2009a),实验结果见表3,比较结果见表4。

Table 3 Results of solving test functions with QBA表3 QBA算法求解测试函数的结果

由表3可看出:QBA对不同区间的收缩-扩张系数均能以100%的成功率找到每个函数的最优解,而文献[4]中的PSO和QPSO却无法保证,PSO的惯性系数w和QPSO的收缩-扩张系数α需要在合适的区间才能保证,PSO中惯性系数的区间为[1.0,0.4],QPSO中收缩-扩张系数的区间为[1.2,0.4],这说明QBA对收缩-扩张系数的区间的设置的敏感度更小,故而比PSO和QPSO具有更好的性能。

由表4可看出，QBA相比较于PSO和QPSO的另外一个性能优势在于QBA能够以更快的速度收敛到最优解。

Table 4 Comparison of the results with PSO、QPSO and QBA表4 PSO、QPSO和QBA求解结果比较

5 结束语

本文所提出的基于Delta势阱的具有量子行为的蝙蝠算法,虽然比粒子群算法和量子行为粒子群算法具有更好的性能,但在实验的过程中发现,该算法对控制全局搜索和局部搜索动态转换进程的脉冲响度和脉冲发射速率的初始设置具有较强的敏感度,至于其原因,是接下来要研究的课题。

[1] Ma Liang, Zhu Gang, Ning Ai-bing. Ant optimization algorithm[M].Beijing:Science Press, 2008.(in Chinese)

[2] Liu Yong, Ma Liang. Bee colony foraging algorithm for integer programming[C]∥Proc of IEEE Business Management and Electronic Information (BMEI), 2011:199-201.

[3] Omran M G H, Engelbrecht A, Salman A. Barebones particle swarm for integer programming problems[C]∥Proc of IEEE Swarm Intelligence Symposium, 2007:170-175.

[4] Sun Jun, Fang Wei, Wu Xiao-jun, et al. Quantum-behaved particle swarm optimization:Theory and application[M]. Beijing:Tsinghua University Press, 2011.(in Chinese)

[5] Gao Shang,Yang Jing-yu.Ant colony optimization algorithm for nonlinear integer programming[J]. Journal of Nanjing University of Science and Technology, 2005, 29(suppl):120-123.(in Chinese)

[6] Yang X S. A new metaheuristic bat-inspired algorithm[C]∥Proc of Nature Inspired Cooperative Strategies for Optimization(NICSO 2010), 2010:65-74.

[7] Yang X S. Bat algorithm for multi-objective optimization[J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.

[8] Yang X S, Gandomi A H. Bat algorithm:A novel approach for global engineering optimization[J]. Engineering Computation, 2012, 29(5):267-289.

[9] Gandomi A H, Yang X S, Alavi A H, et al. Bat algorithm for constrained optimization tasks [J]. Neural Computing &Applications,2013,22(6):1239-1255.

[10] Sun Jun, Feng Bin, Xu Wen-bo. Particle swarm optimization with particles having quantum behavior [C]∥ Proc of 2004 Congress on Evolutionary Computation, 2004:325-331.

附中文参考文献:

[1] 马良,朱刚,宁爱兵.蚁群优化算法[M].北京:科学出版社,2008.

[4] 孙俊,方伟,吴小俊,等.量子行为粒子群优化:原理及其应用[M].北京:清华大学出版社,2011.

[5] 高尚,杨静宇.非线性整数规划的蚁群算法[J].南京理工大学学报, 2005, 29(增刊):120-123.