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

Evolutionary computation, as a new and powerful intelligent optimization technology, has been utilized extensively in almost every branch of engineering science. It has more advantages over traditional optimization methods when solving problems with global search, complex design domain and complicated target functions, and it is easier to use. Genetic algorithm(GA) is one of the most important algorithms in evolutionary computation. Genetic algorithm is a kind of random searching method using lives'natural selection and genetic mechanism.Genetic algorithm(GA) is an important branch of evolutionary computing originally invented by Holland in 1975. As it is known, genetic algorithm is inspired by Darwins theory about evolution. GA is an inherently parallel optimization procedure, which utilizes an approach of"survival of the fittest". A basic GA employs selection, crossover and mutation operators. The whole process can be referred to as"reproduction". The main characteristic of the GA is that it is simple, universal and robust. After 30 year's development, GA has been successfully used in a lot of fields such as the combinational optimization ,scheduling, function optimization, machine learning etc.So far,many scholars have proposed many kinds of genetic algorithms,such as genetic quantum algorithm,immune genetic algorithm,good point set based genetic algorithm,adaptive genetic algorithm and all kinds of improved genetic algorithm, and so on. Based on the research of many scholars,we have analysed the adaptive genetic algorithms that had been proposed, and have proposed two new adaptive genetic algorithms,which are used to solve the 0-1 knapsack problem.1.The mutation only genetic algorithm(MOGA) have been proposed. Based on the MOGA, we introduce transposition and greedy process of illegal individual, and formed a new algorithm MTGA(Mutation and Transposition Genetic Algorithm). In the new algorithm,the transposition probability and mutation probability are adjusted automatically with time and individual fitness,and don't need to be input.MTGA is used to solve 0-1 knapsack problem.We program with C language in the environment of VC++.According to the experiments,compared with Simple Genetic Algorithm, MTGA gets better results in the times that the result exceeds the greedy algorithm and in the best result; MTGA can get better result faster in average evolution generation when exceeding the greedy algorithm.Compared with hybrid GA,they almost have the same result,but MTGA is faster than Hybrid GA distinctly.In addition, MTGA is better than MOGA markedly.2.There are increasing structure in complexity in the open system exchanging energy with environment.Prigogine generalized the dissipation structure which is a routine thermodynamics concept from it.We can analyze the GA using dissipation structure.The population keep progressing under the process of original gene,slection,crossover and mutation operator.This can form a dissipation structure.When the dissipation structure graduates away,the algorithm runs into local optimization.The crossover operator and mutation operator can decide the astringency of GA,so we can avoid the local optimization by the operation of them.It can make the system keep on progressing by augmenting the mutation probability which corresponds to exchanging more substance and energy with outside.Based on the adaptive GA which has crossover and mutation,we import the dissipation structure.Between the individual number of successful crossover and mutation probability we establish relation which makes the individual number of crossover successfully affect the mutation probability.We also dispose the illegal individuals using greedy algorithm.These form a new algorithm(DAGA),which is used to solve the 0-1 knapsack problem.In the experiments there are three kinds of the number of goods,which are 100,250 and 500. According to the experiments, the algorithm can more easily to get better results except the special case. At last, the algorithms proposed in this paper are compared and analysed.