A Heuristic Genetic Algorithm Based on Schema Replacement for 0-1 Knapsack Problem

摘要

This paper investigates the 0-1 knapsack problem using genetic algorithms. The work is based on heuristic strategies that takes into account the characteristics of 0-1 knapsack problem. In this article, a heuristic Genetic Algorithms(GA) is proposed to solve the 0-1 knapsack problem, in each generation, populations are divided into two sections: superior clan and inferior clan, and excellent schema in superior clan are pick up to replace the chromosomes in inferior clan. This approach of schema replacement will promote individual evolution effectively and achieve best solution of the problem. Simulations show that the proposed method can obtain the best solution and convergence fast than conventional GA and Greedy algorithms.