在很多实际问题中,往往难以用一个指标来衡量和判断一个方案的优劣,而是需要用多个目标。与单目标问题不同的是,多目标优化问题有着多种提法和模型。多目标0-1规划问题是一个经典的难题,已被归入所谓的NP-难问题,是否存在有效算法尚不可知。目前已有的精确算法都是指数级的,对于现实中的问题,特别是当问题规模较大时,根本无法使用传统的优化方法和技术来求解,而对于多目标的0-1规划来说,由于增加了目标函数的个数,使问题的求解复杂度进一步加大。本文主要讨论多目标0-1线性规划问题。
蝙蝠算法[2](bat algorithm,BA)是X.S.Yang于2010年提出的一种新型启发式算法,它模拟的是微型蝙蝠的回声定位原理。自该算法提出以来,已有学者将该算法应用于优化问题[2~5],他们的研究成果表明:在解决实际问题中,蝙蝠算法比粒子群算法、遗传算法和和声算法具有更大的潜能。
本文首先介绍了蝙蝠算法在迭代寻优过程中的核心方程,接着根据多目标0-1规划问题的特点,重新定义蝙蝠速度和位置的更新公式,提出了求解多目标0-1规划问题的蝙蝠算法,最后,对4个测试算例进行仿真实验,并将其计算结果与遗传算法、蚁群算法、元胞蚁群算法和粒子群算法的计算结果进行比较,比较结果不但验证了本文所提算法的有效性,而且体现出了在解决多目标0-1规划问题上,所提算法比上述算法具有更好的优越性。
1 基本蝙蝠算法假设在一个d维搜索空间中,第i只蝙蝠在第t代蝙蝠的位置为xit,速度为vit,脉冲频率为Fi,且当前蝙蝠种群最好的位置为x*,则关于xit和vit的更新方程为
${F_i} = {F_{{\rm{min}}}} + ({F_{{\rm{max}}}} - {f_{{\rm{min}}}})\beta $ | (1) |
$\upsilon _i^t = \upsilon _i^{t - 1} + \left( {x_i^t - {x^*}} \right){f_i}$ | (2) |
$x_i^t = x_i^{t - 1} + \upsilon _i^t$ | (3) |
式中:β∈[0, 1]是一随机向量,Fmax和Fmin分别为脉冲频率的最大值和最小值,其各个元素均服从均匀分布。
上述更新方程是针对全局搜索的,对于局部搜索,可以首先从现有的最优解集中随机选择出一个当前最好解xold,然后在其附近就近产生每只蝙蝠新待定的位置,如式(4) 所示:
${x_{{\rm{new}}}} = {x_{{\rm{old}}}} + \varepsilon {A^t}$ | (4) |
式中:ε∈[-1, 1]是一个任意的数字,At=〈Ait〉是所有蝙蝠在该时间步骤里的平均响度。
为保证算法在全局搜索和局部搜索之间达成一种良好的平衡关系,要求脉冲发射的响度Ai和速率ri要随着迭代过程的进行而有所更新。通常情况下,响度会逐渐降低,脉冲的发射速率会逐渐增加。具体的实现方式如式(5) 和式(6) 所示:
$A_i^{t + 1} = \alpha A_i^t$ | (5) |
$r_i^{t + 1} = r_i^0\left[ {1 - {\rm{exp}}\left( { - \gamma t} \right)} \right]$ | (6) |
式中:α和γ是常量。对于任何0<α<1和γ>0,当t→∞时,有:Ait→0,rit→ri0。
2 求解多目标0-1规划问题的蝙蝠算法考虑如下形式的多目标0-1规划问题:
$\begin{array}{l} \max Z = \left\{ {\begin{array}{*{20}{c}} {{Z_1} = \sum\limits_{j = 1}^n {c_j^1{x_j}} }\\ {{Z_2} = \sum\limits_{j = 1}^n {c_j^2{x_j}} }\\ \cdots \\ {{Z_i} = \sum\limits_{j = 1}^n {c_j^i{x_j}} }\\ {{Z_k} = \sum\limits_{j = 1}^n {c_j^k{x_j}} } \end{array}} \right.\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ {\begin{array}{*{20}{l}} {\sum\limits_{j = 1}^n {{a_{ij}}{x_j}} \le {b_i},i = 1,2, \cdots ,m}\\ {{x_j} \in \left\{ {0,1} \right\},j = 1,2, \cdots ,n} \end{array}} \right. \end{array}$ | (7) |
式中:x为决策变量,Z为目标向量,记D为决策变量的可行域。
在具体求解时,采用罚函数的方法,将约束条件转化到目标函数中,将问题转化为无约束形式。
通常情况下,类似于单目标优化的最优解在多目标优化中是不存在的,只存在Pareto 最优解,而且大都具有很多个Pareto最优解[1]。其含义为:记当前Pareto最优解为x0,则不存在任何其他解x,使得Zi(x)≥Zi(x0),i=1,2,…,k,其中,至少有一个不等式严格成立。
定义:假设p和q是群体中任意2个不同的个体,若称p支配q,则必须满足以下2个条件:
1)$\forall m \in \left\{ {1,2, \cdots ,k} \right\},{{\rm Z}_m}\left( p \right) \ge {{\rm Z}_m}\left( q \right)$,即对所有的子目标,p不比q差;
2)$\exists l \in \left\{ {1,2, \cdots ,k} \right\},{{\rm Z}_l}\left( p \right) \ge {{\rm Z}_l}\left( q \right)$,即至少存在一个子目标,使得p比q好。这里,p为支配的,q为被支配的,可以表示成$p \succ q$。
由于基本蝙蝠算法是用来求解连续域的函数优化问题,所以要将基本蝙蝠算法进行离散化地改进才能求解离散问题。为了将寻优领域控制在0和1 2个整数之间,这里对蝙蝠算法的(2)~(4) 进行重新定义:
$\upsilon _i^{t + 1} = {\rm{xor}}\left( {\upsilon _i^k,{\rm{round}}\left( {{\rm{xor}}\left( {x_i^t,{x^*}} \right) \times {F_i}} \right)} \right)$ | (8) |
式中:round指四舍五入取整,xor和or分别指逻辑运算符的异或和或,xold为从当前Pareto最优解集中随机产生的一个解,n指种群个数,d指维数。
下面给出求解多目标0-1规划问题的蝙蝠算法的基本步骤:
1) 初始化。蝙蝠种群大小为n,初始种群中第i只蝙蝠位置x(i),速度v(i),脉冲发射速率R(i),脉冲响度A(i),脉冲频率F(i),个体目标函数集Zi(x(i)),i=1,2,…,n,确定当前Pareto最优解集。
2) 判断是否满足算法结束条件,如果满足,则转9),否则转3)。
3) 利用式(1)、(8)、(9) 产生一个新的解xnew,并更新速度和位置。
4) if rand >R(i)
从当前最优解集中随机选择一个解xold,并利用式(10) 得到一个局部解xnew;
endif
5) 计算个体目标函数集Zixnewnew。
6)$\begin{array}{*{20}{c}} {{\rm{if rand}}\langle A\left( i \right)\& {{\rm Z}_i}\left( {{x_{{\rm{new}}}}} \right){\rm{new}}\rangle }\\ {{{\rm Z}_i}\left( {x\left( i \right)} \right)}\\ {x\left( i \right) = {x_{{\rm{new}}}}}\\ {{{\rm Z}_i}\left( {x\left( i \right)} \right) = {{\rm Z}_i}\left( {{x_{{\rm{new}}}}} \right){\rm{new}}} \end{array}$ 通过式(5) 减小A(i),式(6) 增大R(i);
endif
7) 更新当前Pareto最优解集。如果xnew支配当前Pareto最优解集的一个或几个解,则将被xnew支配的所有解移出当前Pareto最优解集,而将xnew移入当前Pareto最优解集;如果xnew与当前Pareto最优解集不存在任何支配关系,则直接加入到当前Pareto最优解集中;其他情况则保持当前Pareto最优解集不变。
8) 转2)。
9) 输入所求的Pareto最优解集。
从算法的流程可以看出,所提算法的时间复杂度大小取决于Pareto最优解集的构造和产生办法。本文选取的是排除法,其时间复杂度为:O(kN)。故所提算法的时间复杂度为:O(dknN)。其中,d为变量的维数,k为目标函数个数,n为群体个数,N为Pareto最优解集的容量。需要指出的是:下文中,由于所求问题的规模较小,所以并没有给出其具体值,所以在运行过程中,N的值是动态变化的。
3 数值实验为了验证本算法的性能,分别与遗传算法、蚁群算法[1]、元胞蚁群算法[6]、蜂群算法[7]和粒子群算法[8]进行试验比较,采用文献[9]中4个多目标0-1规划问题进行测试。参数设置为:蝙蝠个数为20,Fmax=1,Fmin=0,α=γ=0.9,初始频率和初始速度均为0,脉冲的响度和发射速率从[0,1]随机产生。环境为Win7系统下的MATLAB 7.8(R2009a).计算结果见表 1~表 5。
算法 | 目标函数集 | 对应Pareto最优解 |
遗传算法 | ||
蚁群算法 | ||
元胞蚁群算法 | (31,50) | (1,0,1,0) |
蜂群算法 | (35,35) | (0,1,1,0) |
枚举法 | ||
蝙蝠算法 |
算法 | 目标函数集 | Pareto最优解 |
(0,0) | (0,0,0,0) | |
(4,3.5) | (0,0,0,1) | |
(5,4) | (0,1,0,0) | |
元胞蚁群算法 | (7.5,6) | (0,0,1,1) |
(8,6.5) | (1,0,0,1) | |
(9,7.5) | (0,1,0,1) | |
(0,0) | (0,0,0,0) | |
(3.5,2.5) | (0,0,1,0) | |
(4,3.5) | (0,0,0,1) | |
(5,4) | (0,1,0,0) | |
(7.5,6) | (0,0,1,1) | |
枚举法 | (8,6.5) | (1,0,0,1) |
(9,7.5) | (0,1,0,1) | |
(0,0) | (0,0,0,0) | |
(3.5,2.5) | (0,0,1,0) | |
(4,3.5) | (0,0,0,1) | |
蝙蝠算法 | (5,4) | (0,1,0,0) |
(7.5,6) | (0,0,1,1) | |
(8,6.5) | (1,0,0,1) | |
(9,7.5) | (0,1,0,1) |
序号 | 目标函数集 | Pareto最优解 |
1 | (12,40,16) | (1,1,0,0,1,1,1,0,1,0) |
2 | (15,37,18) | (1,1,1,0,1,1,0,0,1,1) |
3 | (20,30,28) | (1,1,1,1,1,0,0,1,1,0) |
4 | (21,31,26) | (1,1 1 1 1 0 1 0 1,0) |
5 | (22,28,26) | (1,1 1 1 1 0 1 0 0,1) |
6 | (22,36,20) | (1,1 1 0 1 0 1 1 1,0) |
7 | (23,33,20) | (1,1 1 0 1 0 1 1 0,1) |
8 | (27,30,23) | (1,0 1 1 1 0 1 0 1,1) |
9 | (28,20,19) | (0,0 1 1 1 0 1 1 0,1) |
10 | (28,35,17) | (1,0 1 0 1 0 1 1 1,1) |
算法 | 遗传算法 | 蚁群算法 | 元胞蚁群算法 | 蜂群算法 | 粒子群算法 | 枚举法 | 蝙蝠算法 |
目标函数集 | (20,30,28) | (12,40,16) | (12,40,16) | (12,40,16) | (12,40,16) | (12,40,16) | (12,40,16) |
(21,23,25) | (20,30,28) | (20,30,28) | (20,30,28) | (20,30,28) | (15,37,18) | (15,37,18) | |
(21,29,17) | (21,23,25) | (21,31,26) | (21,31,26) | (21,31,26) | (20,30,28) | (20,30,28) | |
(22,21,22) | (21,29,17) | (22,28,26) | (22,28,26) | (23,33,20) | (21,31,26) | (21,31,26) | |
(22,21,22) | (22,36,20) | (22,36,20) | (27,30,23) | (22,28,26) | (22,28,26) | ||
(28,20,19) | (23,33,20) | (23,33,20) | (28,20,19) | (22,36,20) | (22,36,20) | ||
(28,27,17) | (28,20,19) | (27,30,23) | (28,35,17) | (23,33,20) | (23,33,20) | ||
(28,30,14) | (28,35,17) | (28,20,19) | (27,30,23) | (27,30,23) | |||
(28,35,17) | (28,20,19) | (28,20,19) | |||||
(28,35,17) | (28,35,17) |
序号 | 目标函数集 | Pareto最优解 |
1 | (1,1,0,0,1,0,1,1,0,0,1,0) | (182,294,318) |
2 | (0,0,0,0,1,0,1,1,1,1,0,1) | (185,405,316) |
3 | (0,0,1,0,1,0,1,1,1,1,0,0) | (203,345,293) |
4 | (0,0,1,0,1,0,1,1,0,1,0,1) | (209,376,285) |
5 | (1,0,0,0,1,1,1,1,0,0,1,0) | (215,319,279) |
6 | (1,0,0,0,1,0,1,1,1,0,1,0) | (219,305,275) |
7 | (1,0,0,0,1,0,1,1,0,0,1,1) | (225,336,267) |
8 | (1,0,0,0,1,1,0,1,0,1,1,0) | (227,334,264) |
9 | (1,0,0,0,1,0,0,1,1,1,1,0) | (231,320,260) |
10 | (1,0,0,0,1,0,1,0,1,0,1,1) | (234,384,250) |
11 | (1,0,0,0,1,0,0,1,0,1,1,1) | (237,351,252) |
12 | (1,0,1,0,1,0,1,1,0,0,1,0) | (243,276,244) |
13 | (1,0,0,0,1,0,0,0,1,1,1,1) | (246,399,235) |
14 | (1,0,1,0,1,1,1,0,0,0,1,0) | (248,338,231) |
15 | (1,0,0,0,0,1,1,1,0,1,1,0) | (249,317,242) |
16 | (1,0,0,0,0,0,1,1,1,1,1,0) | (253,303,238) |
17 | (1,0,0,0,0,0,1,1,0,1,1,1) | (259,334,230) |
18 | (1,0,1,0,1,1,0,0,0,1,1,0) | (260,353,216) |
19 | (1,0,1,0,1,0,0,0,1,1,1,0) | (264,339,212) |
20 | (1,0,1,0,1,0,0,0,0,1,1,1) | (270,370,204) |
21 | (1,0,0,1,0,0,1,0,1,0,1,1) | (271,329,169) |
22 | (1,0,1,1,1,0,0,0,0,0,1,1) | (273,317,160) |
23 | (1,0,0,1,0,0,0,1,0,1,1,1) | (274,296,171) |
24 | (1,0,1,0,0,0,1,1,0,1,1,0) | (277,274,207) |
25 | (1,0,1,0,0,1,0,1,0,1,1,0) | (283,276,175) |
26 | (1,0,1,0,0,0,0,1,1,1,1,0) | (287,262,171) |
27 | (1,0,1,0,0,0,0,1,0,1,1,1) | (293,293,163) |
28 | (1,0,1,1,0,0,0,1,0,0,1,1) | (296,240,119) |
算例1:
$\begin{array}{l} \max {Z_1} = 10{x_1} + 14{x_2} + 21{x_3} + 42{x_4}\\ \max {Z_2} = 30{x_1} + 15{x_2} + 20{x_3} + 18{x_4}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ {\begin{array}{*{20}{l}} {2{x_1} + 2{x_2} + 7{x_3} + 14{x_4} \le 11}\\ {9{x_1} + 6{x_2} + 3{x_3} + 6{x_4} \le 14}\\ {{x_{\rm{j}}} \in \left\{ {0,1} \right\},j = 1,2,3,4} \end{array}} \right. \end{array}$ |
试验结果见表 1。
算例2:
$\begin{array}{l} \min {Z_1} = 4{x_1} + 5{x_2} + 3.5{x_3} + 4{x_4}\\ \min {Z_2} = 3{x_1} + 4{x_2} + 2.5{x_3} + 3.5{x_4}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ {\begin{array}{*{20}{l}} {4{x_1} + 5{x_2} + 3.5{x_3} + 4{x_4} \le 10}\\ {{x_i}\left( {{x_i} - 1} \right) = 0,i = 1,2,3,4} \end{array}} \right. \end{array}$ |
试验结果见表 2。
算例3:
$\begin{array}{l} \max {Z_1} = 4{x_3} + 5{x_4} + 7{x_7} + 6{x_8} + 5{x_9} + 6{x_{10}}\\ \max {Z_2} = 9{x_1} + 4{x_2} + 6{x_5} + 9{x_6} + 6{x_7} + 5{x_8} + 6{x_9} + 3{x_{10}}\\ \max {Z_3} = 6{x_1} + 3{x_2} + 2{x_3} + 8{x_4} + 7{x_5} + 2{x_8}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\left\{ {\begin{array}{*{20}{l}} {3{x_2} + 4{x_3} + 8{x_4} + 4{x_5} + 7{x_6} + 6{x_7} + 5{x_8} + }\\ {2{x_9} + 6{x_{10}} \le 37}\\ {5{x_1} + 3{x_2} + 6{x_4} + 8{x_6} + 5{x_7} + 6{x_8} + 3{x_9} + }\\ {5{x_{10}} \le 24}\\ {2{x_1} + 2{x_2} + 7{x_3} + 4{x_4} + 8{x_5} + 9{x_6} + 9{x_7} + }\\ {3{x_8} + 7{x_9} + 5{x_{10}} \le 43}\\ {2{x_1} + 3{x_2} + 3{x_3} + 6{x_4} + 3{x_5} + 8{x_7} + 4{x_8} + }\\ {6{x_9} \le 31}\\ {{x_j} \in 0,1,j = 1,2, \cdots ,10} \end{array}} \right. \end{array}$ |
用蝙蝠算法解得Pareto最优解见表 3。对比结果分析见表 4。
算例4:
$\begin{array}{l} {\rm{max}}{Z_1} = 89{x_1} + {x_2} + 62{x_3} + 43{x_4} + 6{x_5} + \\ 34{x_6} + 28{x_7} + 29{x_8} + 38{x_9} + \\ 40{x_{10}} + 29{x_{11}} + 44{x_{12}}\\ {\rm{max}}{Z_2} = 59{x_1} + 48{x_2} + 30{x_3} + 33{x_4} + 88{x_5} + \\ 73{x_6} + 71{x_7} + 11{x_8} + 59{x_9} + \\ 86{x_{10}} + 17{x_{11}} + 90{x_{12}}\\ {\rm{max}}{Z_3} = 19{x_1} + 75{x_2} + {x_3} + 9{x_4} + 90{x_5} + \\ 36{x_6} + 68{x_7} + 49{x_8} + 32{x_9} + \\ 53{x_{10}} + 17{x_{11}} + 24{x_{12}} \end{array}$ |
${\rm{s}}{\rm{.t}}{\rm{.}}\left\{ {\begin{array}{*{20}{l}} {{g_1}\left( x \right) = 63{x_1} + 70{x_2} + 28{x_3} + 99{x_4} + 67{x_5} + }\\ {41{x_6} + 75{x_7} + 3{x_8} + 28{x_9} + }\\ {96{x_{10}} + 8{x_{11}} + 30{x_{12}} \le 304}\\ {{g_2}\left( x \right) = 91{x_1} + 77{x_2} + 74{x_3} + 41{x_4} + 57{x_5} + }\\ {95{x_6} + 41{x_7} + 47{x_8} + 83{x_9} + }\\ {37{x_{10}} + 6{x_{11}} + 86{x_{12}} \le 367.5}\\ {{g_3}\left( x \right) = 23{x_1} + 89{x_2} + 83{x_3} + 43{x_4} + 24{x_5} + }\\ {66{x_6} + 60{x_7} + 33{x_8} + 59{x_9} + }\\ {45{x_{10}} + 83{x_{11}} + 71{x_{12}} \le 339.5}\\ {{x_i} \in 0,1,i = 1,2, \cdots ,12} \end{array}} \right.$ |
试验结果见表 5。
通过观察和分析上述4个算例的测试结果,不难发现:文中所提出的算法能够找到上述4个算例的所有Pareto最优解,而遗传算法、蚁群算法、元胞蚁群算法、蜂群算法和粒子群算法却不能保证找到上述4个算例的所有Pareto最优解,从而突出了文章所提出的算法性能的优越性。
4 结束语蝙蝠算法是一种元启发式算法,启发于微型蝙蝠利用回声定位功能寻找食物、避开障碍物这一特殊现象。从实验结果来看,它比目前应用广泛的蚁群算法、蜂群算法、遗传算法、元胞蚁群算法和粒子群算法具有更好的适应性。文章所提的算法是对多目标规划问题的一种新的尝试,更多的工作尚待于进一步展开,诸如将其应用扩展到多目标整数规划中去,以及其他的经典组合优化问题中去,从而丰富蝙蝠算法的应用领域。
[1] | 马良, 朱刚, 宁爱兵. 蚁群优化算法. 北京:科学出版社[M]. 2008 : 185 -189. |
[2] | YANG X S. A new metaheuristic bat-inspired algorithm. Berlin Heidelberg: Springer[M]. 2010 : 65 -74. |
[3] | YANG X S. Bat algorithm for multi-objective optimisation[J]. International Journal of Bio-Inspired Computation,2011, 3 (5) : 267 –274. |
[4] | YANG X S, GANDOMI A H. Bat algorithm: a novel approach for global engineering optimization[J]. Engineering Computation,2012, 29 (5) : 267 –289. |
[5] | GANDOMI A H, YANG X S, ALAVI A H, et al. Bat algorithm for constrained optimization tasks[J]. Neural Computing and Applications,2013, 22 (6) : 1239 –1255. |
[6] | 刘勇, 马良, 许秋艳. 多目标0-1规划问题的元胞蚁群优化算法[J]. 系统工程,2009, 27 (2) : 119 –122. LIU Yong, MA Liang, XU Qiuyan. Solving multi-objective 0-1 programming by cellular ant algorithm[J]. Systems Engineering,2009, 27 (2) : 119 –122. |
[7] | 韩燕燕, 马良, 赵小强. 多目标0-1规划问题的蜂群算法[J]. 运筹与管理,2012, 21 (2) : 23 –26. HAN Yanyan, MA Liang, ZHAO Xiaoqiang. Bee colony algorithm for the multi-objective 0-1 programming problem[J]. Operations Research and Management Science,2012, 21 (2) : 23 –26. |
[8] | 孙滢, 高岳林. 一种求解多目标0-1规划问题的自适应粒子群算法[J]. 计算机应用与软件,2009, 26 (12) : 71 –73. SUN Ying, GAO Yuelin. An adaptive particle swarm optimization algorithm for solving multi-objective 0-1 programming problem[J]. Computer Application and Software,2009, 26 (12) : 71 –73. |
[9] | 杨玲玲, 马良, 张惠珍. 多目标0-1规划的混沌优化算法[J]. 计算机应用研究,2012, 29 (12) : 4486 –4488. YANG Lingling, MA Liang, ZHANG Huizhen. Chaotic optimization algorithm for multi-objective 0-1 programming problem[J]. Application Research of Computers,2012, 29 (12) : 4486 –4488. |