A simplified binary artificial fish swarm algorithm for 0–1 quadratic knapsack ...

• 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/26403
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): 0–1 knapsack problem; Heuristic; Artificial fish swarm; swap move; Local search
• Document Type: Article
• Language: English

Description

Documento submetido para revisão pelos pares. A publicar em "Journal of computational and applied mathematics". ISSN 0377-0427. Available online 8 October 2013 (http://www.sciencedirect.com/science/article/pii/S0377042713005074) This paper proposes a simplified binary version of the artificial fish swarm algorithm (S-bAFSA) for solving 0–1 knapsack problems. This is a combinatorial optimization problem, which arises in many fields of optimization. In S-bAFSA, trial points are created by using crossover and mutation. In order to make the points feasible, a random heuristic drop item procedure is used. The heuristic add item is also implemented to improve the quality of the solutions, and a cyclic reinitialization of the population is carried out to avoid convergence to non-optimal solutions. To enhance the accuracy of the solution, a local search is applied on a predefined number of points. The method is tested on a set of benchmark 0–1 knapsack problems.