A Method Of Using Lethal Chromosome Of Genetic Algorithm

Genetic Algorithm is widely applied to the large-scale combinatorial optimization problems for its global search performance and robust performance. In practical, many optimization problems are used to solve the constrained optimization problems. Genetic Algorithm to solve constrained optimization problem is searching the feasible satisfied the constrain condition in the global genetic type space. The chromosome unsatisfied constrain condition is called lethal chromosome.With the population of Genetic Algorithm evolving, due to crossover operator and mutation operator, lethal chromosomes occur in a high rate. Especially to the combinatorial optimization problems with rigorous constrain, the number of lethal chromosomes become very large in population. The more the number of lethal chromosomes are in population, the worse the searching performance is. The algorithm will stop on some occasions. If the produce of the lethal chromosome obey some order, lethal chromosomes will be avoided via algorithm designing. But for most of instance, it's difficult to design an algorithm to avoid the produce of lethal chromosomes. The general method for lethal chromosome is to eliminate it from its population.During the evolving process, some excellent genes are contained in the lethal chromosome. If the lethal chromosome is reused instead of being eliminated, the search performance of the algorithm will be improved. This paper propose a method of reviving the lethal chromosomes and reuse them based on the artificial immune theory, which marriage the evolutional information of the chromosome and the characteristic information of the problem, epurate vaccine and vaccinating. The lethal chromosome is reused through moving the lethal and revived chromosomes between the two islands. In the immune operator, according to the characteristic information of the lethal chromosome, excellent chromosome and the problem, three different immune methods are designed. Appling the algorithm to the constrained optimization problem such as 0-1 knapsack problem and multiple choose knapsack problem, the numerical experiment results show the validity of the proposed algorithm. The method proposed in this paper can be applied to GA for solving constrained optimization problem, to improve the application performance and the searching performance of GA.