APPLICATION OF FITNESS SWITCHING GENETIC ALGORITHM FOR SOLVING 0-1 KNAPSACK PROBLEM

摘要

Fitness switching genetic algorithm is a sort of genetic algorithm, which was initially developed for solving combinatorial optimization problems with rare feasible solutions. Compared to previous genetic algorithms, fitness switching genetic algorithm has three distinguishing procedures including fitness switching, fitness leveling and simple local search, which enable the infeasible solutions to be included within the population. Consequently, fitness switching genetic algorithm can effectively explore the search space of given problem by utilizing infeasible solutions, even if it is difficult to find arbitrary feasible solutions. On the contrary, 0-1 knapsack problem is a well-known combinatorial optimization problem that typically has many feasible solutions, and this paper aims to apply fitness switching genetic algorithm to solve this problem in order to investigate applicability of the algorithm. To this end, fitness switching, fitness leveling and simple local search procedures are tailored to 0-1 knapsack problem, and a revised algorithm structure is proposed. Consequently, this paper demonstrates that combinatorial optimization problems with many feasible solutions also can be solved by applying fitness switching genetic algorithm. Especially, fitness switching genetic algorithm is easy to implement in that it does not require repair or penalization procedures for handling infeasible solutions.