Stochastic Diffusion Binary Differential Evolution to Solve Multidimensional Knapsack Problem
Ayed A. Salman, Imtiaz Ahmad, Mahmad G. H. Omran · International Journal of Machine Learning and Computing · 2016
Multi Knapsack Problem (MKP) is NP-hard combinational optimization problem, also known as the multi-constraint knapsack problem.MKP is one of the most studied problems in combinatorial optimization, with variety of real-life applications.In this paper a Stochastic Diffusion Binary differential evolution (SD-BDE) algorithm is applied for optimizing the Multidimensional Knapsack Problem (MKP).SD-BDE, is a Binary version of Differential Evolution hybridized with ideas extracted from Stochastic Diffusion search.SD-BDE algorithm, in this paper, is compared against state-of-the-art existing algorithms in solving MKP.Experimental results show that the SD-BDE algorithm outperformed the existing algorithms by finding either better or at least similar solutions for all tested benchmarks Index Terms-Differential evolution, stochastic diffusion search, np-complete problem, multidimensional knapsack problem.