Title: Optimising the bi-objective multidimensional integer knapsack problem using non-dominated sorting particle swarm optimisation

Authors: Jafar Bagherinejad; Mina Dehghani

Addresses: Department of Industrial Engineering, Academic member of Industrial Engineering, Alzahra University, Tehran, Iran ' Department of Industrial Engineering, Alzahra University, Tehran, Iran

Abstract: The knapsack problem (KP) and its multidimensional version are basic problems in combinatorial optimisation. In this paper, we consider the bi-objective multidimensional integer knapsack problem (BOMIKP), for which the aim is to approximate the set of non-dominated solutions using an evolutionary algorithm named non-dominated sorting particle swarm optimisation (NSPSO). The proposed methodology is based on a new variant of particle swarm optimisation (PSO) specialised in multi-objective optimisation. To aid the decision maker choosing the best compromise solution from the Pareto front, the fuzzy-based mechanism is employed for this purpose. For ensuring the robustness of the proposed method, the computational results are compared with those obtained by non-dominated sorting genetic algorithm II (NSGA-I) and multi-objective particle swarm optimisation (MOPSO) algorithm. Results show the advantages and effectiveness of the used procedures in reporting the optimal Pareto front. In addition, the results indicate that while MOPSO is able to generate Pareto solutions in significantly less amount of time, NSPSO and NSGA-II are capable of providing better quality results and better distribution of solutions in the trade-off surface.

Keywords: integer knapsack problem; multidimensional; bi-objective optimisation; particle swarm optimisation; non-dominated sorting PSO; NSPSO; NSGA-II; MOPSO; genetic algorithms; fuzzy logic.

DOI: 10.1504/IJISE.2016.076867

International Journal of Industrial and Systems Engineering, 2016 Vol.23 No.3, pp.263 - 289

Received: 08 Feb 2014
Accepted: 11 Sep 2014
Published online: 05 Jun 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article