Improvements of Genetic Algorithm to the Knapsack Problem

Abstract

This paper constructs a Genetic Algorithm to the Knapsack Problem and makes several modifications to improve the algorithm. By keep the group of best chromosomes the best solutions can be improved step by step. Adaptive hybrid probability and mutation probability are applied when more duplicated answers appears, constantly increasing hybrid probability and mutation probability can enlarge the searching horizon base on the preliminary results. Multi-point crossover can also make searching scope larger and conducive to better outcomes. A roulette function is defined that provides a comparative series of probabilities, by which definitly priority of chromosomes at front position is achieved. This paper also provides contrastive results to show the effect of these improvements. the measures of keeping top chromosomes and the new roulette function is new.