Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems

被引:34
作者
Beheshti, Zahra [1 ]
Shamsuddin, Siti Mariyam [1 ]
Yuhaniz, Siti Sophiayati [1 ]
机构
[1] Univ Teknol Malaysia, Fac Comp Sci & Informat Syst, Soft Comp Res Grp, Skudai 81310, Johor, Malaysia
关键词
Combinatorial Optimization Problem; NP-hard problem; Meta-heuristic algorithm; Binary Particle Swarm Optimization; Binary Accelerated Particle Swarm Algorithm; Multidimensional Knapsack Problem; ANT COLONY OPTIMIZATION; GENETIC ALGORITHM; SCHEDULING PROBLEM; TABU SEARCH; KNAPSACK; VERSION; DESIGN; BRANCH; SOLVE; MODEL;
D O I
10.1007/s10898-012-0006-1
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The majority of Combinatorial Optimization Problems (COPs) are defined in the discrete space. Hence, proposing an efficient algorithm to solve the problems has become an attractive subject in recent years. In this paper, a meta-heuristic algorithm based on Binary Particle Swarm Algorithm (BPSO) and the governing Newtonian motion laws, so-called Binary Accelerated Particle Swarm Algorithm (BAPSA) is offered for discrete search spaces. The method is presented in two global and local topologies and evaluated on the 0-1 Multidimensional Knapsack Problem (MKP) as a famous problem in the class of COPs and NP-hard problems. Besides, the results are compared with BPSO for both global and local topologies as well as Genetic Algorithm (GA). We applied three methods of Penalty Function (PF) technique, Check-and-Drop (CD) and Improved Check-and-Repair Operator (ICRO) algorithms to solve the problem of infeasible solutions in the 0-1 MKP. Experimental results show that the proposed methods have better performance than BPSO and GA especially when ICRO algorithm is applied to convert infeasible solutions to feasible ones.
引用
收藏
页码:549 / 573
页数:25
相关论文
共 74 条
[51]  
Li H, 2006, LECT NOTES COMPUT SC, V4221, P696
[52]   A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan [J].
Lian, Zhigang ;
Gu, Xingsheng ;
Jiao, Bin .
CHAOS SOLITONS & FRACTALS, 2008, 35 (05) :851-861
[53]   Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [J].
Liang, J. J. ;
Qin, A. K. ;
Suganthan, Ponnuthurai Nagaratnam ;
Baskar, S. .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2006, 10 (03) :281-295
[54]   A discrete version of particle swarm optimization for flowshop scheduling problems [J].
Liao, Ching-Jong ;
Tseng, Chao-Tang ;
Luarn, Pin .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (10) :3099-3111
[55]   A multidimensional knapsack model for asset-backed securitization [J].
Mansini, R ;
Speranza, MG .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (08) :822-832
[56]   Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems [J].
Mavrotas, George ;
Figueira, Jose Rui ;
Antoniadis, Alexandros .
JOURNAL OF GLOBAL OPTIMIZATION, 2011, 49 (04) :589-606
[57]   The fully informed particle swarm: Simpler, maybe better [J].
Mendes, R ;
Kennedy, J ;
Neves, J .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2004, 8 (03) :204-210
[58]   A review of intelligent approaches for designing dynamic and robust layouts in flexible manufacturing systems [J].
Moslemipour, Ghorbanali ;
Lee, Tian Soon ;
Rilling, Dirk .
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 60 (1-4) :11-27
[59]  
Neapolitan R. E., 2004, Foundations of Algorithms Using C Pseudocode
[60]   MINTO, A MIXED-INTEGER OPTIMIZER [J].
NEMHAUSER, GL ;
SAVELSBERGH, MWP ;
SIGISMONDI, GC .
OPERATIONS RESEARCH LETTERS, 1994, 15 (01) :47-58