期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 57, 期 2, 页码 549-573出版社
SPRINGER
DOI: 10.1007/s10898-012-0006-1
关键词
Combinatorial Optimization Problem; NP-hard problem; Meta-heuristic algorithm; Binary Particle Swarm Optimization; Binary Accelerated Particle Swarm Algorithm; Multidimensional Knapsack Problem
资金
- Ministry of Higher Education (MOHE) [LRGS/TD/2011/UTM/ICT/03 - 4L805]
- Research Management Centre (RMC), Universiti Teknologi Malaysia (UTM)
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据