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

被引：0
作者：
Bagherinejad J. [1 ]
Dehghani M. [1 ]
机构：
[1] Department of Industrial Engineering, Alzahra University, Tehran
来源：
International Journal of Industrial and Systems Engineering | 2016年 / 23卷 / 03期
关键词：
Bi-objective optimisation; Integer knapsack problem; MOPSO; Multidimensional; Non-dominated sorting particle swarm optimisation; NSGA-II; NSPSO; Particle swarm optimisation; PSO;
D O I：
10.1504/IJISE.2016.076867
中图分类号：
学科分类号：
摘要：
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. Copyright © 2016 Inderscience Enterprises Ltd.
引用
收藏
页码：263 / 289
页数：26
相关论文
共 38 条
  • [1] Bas E., An investment plan for preventing child injuries using risk priority number of failure mode and effects analysis methodology and a multi-objective, multi-dimensional mixed 0/1 knapsack model, Reliability Engineering and System Safety, 96, 7, pp. 748-756, (2011)
  • [2] Benson H.Y., Shanno D.F., Vanderbei R.J., A comparative study of large-scale nonlinear optimization algorithms, Operations Research and Financial Engineering, (2001)
  • [3] Bo Z., Yi-Jia C., Multiple objective particle swarm optimization technique for economic load dispatch, Journal of Zhejiang University Science A, 6, 5, pp. 420-427, (2005)
  • [4] Chu P.C., Beasley J.E., A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics, 4, 1, pp. 63-86, (1998)
  • [5] Chutima P., Sirovetnukul R., An application of particle swarm optimisation with negative knowledge on multi-objective U-shaped assembly line worker allocation problems, International Journal of Industrial and Systems Engineering, 14, 2, pp. 139-174, (2013)
  • [6] Clerc M., Kennedy J., The particle swarm-explosion, stability and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6, 1, pp. 58-73, (2002)
  • [7] Coello C.A.C., Lechuga M.S., MOPSO: A proposal for multiple objective particle swarm optimization, Congress on Evolutionary Computation IEEE Service Center, pp. 1051-1056, (2002)
  • [8] Coello C.A.C., Pulido G.T., Lechuga M.S., Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation, 8, 3, pp. 256-279, (2004)
  • [9] Deb K., Pratap A., Agarwal S., Meyarivan T., A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, pp. 182-197, (2002)
  • [10] Dhillon J.S., Parti S.C., Kothari D.P., Stochastic economic emission load dispatch, Electric Power Systems Research, 26, 3, pp. 179-186, (1993)
1234