The Improvement Of Genetic Algorithm And It's Application On Knapsack Problem And Function Optimization

The genetic algorithm is an effective way to solve the problem of discrete and continuity. By studying several effective genetic algorithms about knapsack problem and function optimization, the dissertation proposes the Attribute Gene-reserved Algorithm (ARGA), which combined with genetic algorithm of elitist strategy can reserve the difference of each gene-bit data attributing in genetics of different generations as well as solving the early convergence and GA deceptive problem easily. Finally, on the basis of classic test cases, the efficiency of the algorithm is verified. Methods and the conclusions of the research are as follows:1. The concept of Attribute Gene-reserved Algorithm(ARGA) is proposed. Using the attribute gene-reserved strategy, we can reserve the difference of each gene-bit data attributing in genetics of different generations, which essence is a chromosome amendment process. All the work is to avoid that the lack of difference would not continue to evolve. By this way, the algorithm settles GA deceptive problems well.2. The concept of simple groups is put forward, which is done to keep non-redundancy, and thus solve the problem GA premature better.3. An improved elitist strategy is proposed, which is not only the way to keep the best individual in each generation, but also to ensure the offspring fitness of each individual no less than the parent individual adaptation in the evolution progress of each generation.4. In addition, basing on a large-scale empirical calculation on knapsack problem, the dissertation finds out that the evolutional algebra of Genetic Algorithm has much more impact on optimal results than population size does. Also, the dissertation gives quantitative values of various parameters of the specific, which is that if numbers of knapsack is N, then initial population can set as 2N,evolutional algebra 4N. These are very efficient genetic algorithm parameters.