Modified symbiotic organisms search (MSOS) algorithm for solving 0-1 Knapsack problems

The 0-1 knapsack problem is a NP-complete classical discrete combinatorial optimization problem. Hence finding an exact solution is difficult especially for high dimension knapsack problem instances. In this paper, a modified symbiotic organisms search (MSOS) algorithm as a hybridization of symbiotic organisms search (SOS) and genetic algorithm is implemented for solving 0-1 Knapsack Problem (KP01). The proposed MSOS simulates the symbiotic interaction strategies such as mutualism, commensalism, and parasitism adopted by organisms for surviving and propagating in the ecosystem. Symbiotic organism search is a newly implemented metaheuristic optimization technique for solving numerical optimization problems. A mathematical model of Modified Penalty Function (MPF) is developed and used to check feasibility as well as compute fitness of an organism efficiently. Accordingly, the present algorithm can find a high-quality optimal solution with a better convergence evolution. MSOS is tested with certain KP01 instances of four datasets in literature. The results are compared with other metaheuristic algorithms. Under the same preconditions, MSOS shows competitive optimization capacities for finding solutions for KP01 instance than some other metaheuristic algorithms.