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

李枝勇,马 良,张惠珍

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

1 引言

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

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

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

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

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

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