Improved binary artificial fish swarm algorithm for the 0–1 multidimensional kn...

• Author(s): Azad, Md. Abul Kalam ; Rocha, Ana Maria A. C. ; Fernandes, Edite Manuela da G. P.
• Date: 2013
• Persistent ID: http://hdl.handle.net/1822/26661
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): 0–1 knapsack problem; Multidimensional knapsack; Artificial fish swarm; Decoding algorithm
• Document Type: Preprint
• Language: English

Description

Documento submetido para revisão pelo pares a publicar em Swarm and evolutionary computation. ISSN 2210-6502. Versão "In Press, Corrected Proof" disponível em http://www.sciencedirect.com/science/article/pii/S2210650213000552?np=y 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.