Long Schema Genetic Algorithms And Its Applications

Genetic Algorithm is an adaptive probability global optimization algorithm which simulated in natural environment of biological and genetic evolution, it provides a common framework to solve complex optimization problems, and now has been widely used in many disciplines. After analyzing and studying the deficiency of traditional genetic algorithms in solving a class of problems which can easily described using 0-1, an improved genetic algorithm is proposed, that is Long Schema Genetic Algorithms (LSGA).We design three specific reproduce operators and use them substitute crossover operator, so we obtained long schema genetic algorithms. Comparing traditional genetic algorithms which use crossover operator, long schema genetic algorithms can reflect the problems more directly in a class of problem which can easily described using 0-1. Long schema genetic algorithms mainly use binary code, Gary code and character code. Selection, fitness function and evolution of long schema genetic algorithm are the same as that of traditional genetic algorithms which use crossover operator. And we design three termination conditions to meet different needs.In order to study the way of coding options, selection options, reproduce operators, reproduce probability and mutate probability that all impact the performance of genetic algorithm, some test function have been selected carefully and some performance testing indicators such as success ratio, average generation, average runtime, are proposed. We make a large number of numerical simulation experiments and acquired some useful laws of parameters of Long Schema Genetic Algorithms.In order to study inheritance of schema, which has higher schema order, longer defining length and higher average fitness, Long Schema Genetic Algorithms are applied to One-Max function and the Royal Road Problem. Experimental results approve the effectiveness of reproduce operator.We apply Long Schema Genetic Algorithm, Simple Genetic Algorithm, Simulated Annealing Algorithm, Genetic-Simulating Annealing Algorithm, Greedy Algorithm based on the density of the value, Backtracking, Branch and Bound Approach and Dynamic Programming Approach to 0-1 knapsack problems. The experimental results show that the Long Schema Genetic Algorithms, as well as Backtracking and Dynamic Programming Approach, is the best,and approve the effectiveness of Long Schema Genetic Algorithms.On the analysis of multiple-choice knapsack problem and multi-constrained knapsack problem, we propose the coding based on the kind of goods and type of project and the coding method based on the serial number of knapsack respectively, design the reproduce operator and mutation operator accordingly, and propose the new method of fitness calculation. The simulation examples show the Long Schema Genetic Algorithm is efficient.