期刊
SWARM AND EVOLUTIONARY COMPUTATION
卷 14, 期 -, 页码 66-75出版社
ELSEVIER
DOI: 10.1016/j.swevo.2013.09.002
关键词
0-1 knapsack problem; Multidimensional knapsack; Artificial fish swarm; Decoding algorithm
资金
- Ciencia of FCT (Foundation for Science and Technology), Portugal [C2007-UMINHO-ALGORITMI-04]
- FEDER COMPETE (Operational Programme Thematic Factors of Competitiveness)
- FCT [FCOMP-01-0124-FEDER-022674]
The 0-1 multidimensional knapsack problem (MKP) arises in many fields of optimization and is NP-hard. Several exact as well as heuristic methods exist. Recently, an artificial fish swarm algorithm has been developed in continuous global optimization. The algorithm uses a population of points in space to represent the position of fish in the school. In this paper, a binary version of the artificial fish swarm algorithm is proposed for solving the 0-1 MKP. In the proposed method, a point is represented by a binary string of 0/1 bits. Each bit of a trial point is generated by copying the corresponding bit from the current point or from some other specified point, with equal probability. Occasionally, some randomly chosen bits of a selected point are changed from 0 to 1, or 1 to 0, with an user defined probability. The infeasible solutions are made feasible by a decoding algorithm. A simple heuristic add item is implemented to each feasible point aiming to improve the quality of that solution. A periodic reinitialization of the population greatly improves the quality of the solutions obtained by the algorithm. The proposed method is tested on a set of benchmark instances and a comparison with other methods available in literature is shown. The comparison shows that the proposed method gives a competitive performance when solving this kind of problems. (C 2013 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据