文章快速检索 高级检索

Bat algorithm for the multi-objective 0-1 programming problem
LI Zhiyong , MA Liang , ZHANG Huizhen
School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Obtaining more Pareto solutions is very important for the multi-objective problem. This paper presented an improved bat algorithm for solving the multi-objective 0-1 programming problem with linear constrains. The proposed algorithm, which is based on redefining the updating formulas of the velocity and position about every bat, is implemented through several tests. The algorithm is compared with a genetic algorithm, an ant colony optimization algorithm, a cellular ant colony algorithm and a particle swarm optimization algorithm. The comparisons showed that the proposed algorithm can get more Pareto solutions and be much more effective to solve such problems.
Key words: intelligent optimization     combinatorial optimization     multi-objective 0-1 programming problem     bat algorithm

1 基本蝙蝠算法

 ${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)

 ${x_{{\rm{new}}}} = {x_{{\rm{old}}}} + \varepsilon {A^t}$ (4)

 $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)

2 求解多目标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)

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)$，即至少存在一个子目标，使得pq好。这里，p为支配的，q为被支配的，可以表示成$p \succ q$。

 $\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)

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)

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最优解集。

3 数值实验

 算法 目标函数集 对应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)

 $\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}$

 $\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}$

 $\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}$

 $\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.$

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.
DOI: 10.3969/j.issn.1673-4785.201310038

0

#### 文章信息

LI Zhiyong, MA Liang, ZHANG Huizhen

Bat algorithm for the multi-objective 0-1 programming problem

CAAI Transactions on Intelligent Systems, 2014, 9(6): 672-676
http://dx.doi.org/10.3969/j.issn.1673-4785.201310038