Study Of Chemical Reaction Based Algorithms For Knapsack Problems

Knapsack problems are encountered in numerous industrial sectors such as transportation, logistics, cutting and packing, telecommunication, reliability, advertisement, investment, budget allocation, and production management. They appear either as standalone problems or as sub-problems of more complex programming models. Knapsack problems have many variants. A multitude of aspects have been considered:multiple-choice, multiple-dimension, multiple knapsacks, multiple objectives, quadratic and non-linear objectives, correlated, uncorrelated, stochastic, fuzzy parameters, etc. Most of them are NP-hard problems.Recently, researchers have proposed many approaches to solve knapsack problems. There are many metaheuristics successful in solving knapsack problems such as simulated annealing algorithm, tabu search, genetic algorithm, ant colony algorithm, quantum-inspired evolutionary algorithm, etc. The advantages of metaheuristics are finding out approximate optima of hard problems in reasonable time. We focused in this type of approach for knapsack problems.Chapter1presents background and motivation, research objectives, chemical reaction optimization, artificial chemical reaction optimization, and two knapsack problems. This dissertation focuses in two knapsack problems that are0-1knapsack problem (KP01) and multiple-choice knapsack problem (MCKP). These problems are NP-hard problems which play important roles in computing theory and in many real life applications. A brief introduction of chemical reaction optimization and artificial chemical reaction optimization is proposed. Litareture review of two knapsack problems can be found.Chapter2presents a new artificial chemical reaction optimization algorithm with a greedy strategy algorithm to solve KP01. A new repair operator integrating a greedy strategy and random selection is used to repair the infeasible solutions. The repair operator consists of two phases. The first phase (called ADD) examines each variable in decreasing order of pi/qi and changes the variable from zero to one as long as feasibility is not violated. The second phase (called DROP) examines randomly one variable and changes the variable from one to zero if feasibility is violated. The aim of the DROP phase is to obtain a feasible solution from an infeasible solution, whilst the ADD phase seeks to improve the fitness of a feasible solution.Chapter3presents a new chemical reaction optimization with greedy strategy algorithm (CROG) to solve KP01. The report also explains the operator design and parameter turning methods for CROG. A new repair function integrating a greedy strategy and random selection is used to repair the infeasible solutions.Chapter4presents a new algorithm based on metaheuristic chemical reaction optimization for multiple-choice knapsack problem(MCKP). The new method is proposed that shown better performance than genetic algorithm (GA) in a large test set in solving MCKP.In chapter5, a parallel chemical reaction optimization algorithm is proposed to solve Multiple-choice knapsack problem that is an well-known NP-hard problem. The simulation results solved that the proposed approach better than chemical reaction optimization in both quality solutions and computing time. The new method showed potential in solving this hard problem. An artificial chemical reaction optimization algorithm for multiple-choice knapsack problem is presented in chapter6. Conclusions along with a brief discussion about some future directions.