A novel genetic algorithm based on immunity

A novel algorithm, the immune genetic algorithm (IGA), is proposed based on the theory of immunity in biology which mainly constructs an immune operator accomplished by two steps: 1) a vaccination and 2) an immune selection. IGA proves theoretically convergent with probability 1. Strategies and methods of selecting vaccines and constructing an immune operator are also given. IGA is illustrated to be able to restrain the degenerate phenomenon effectively during the evolutionary process with examples of TSP, and can improve the searching ability and adaptability, greatly increase

the converging speed. Index Terms—Convergence, genetic algorithm, immune genetic algorithm, immunity, TSP. I. INTRODUCTION D URING the last three decades, there has been a growing interest in algorithms which rely on analogies to nat- ural phenomena such as evolution, heredity, and immunity. The emergence of massively parallel computers made these algorithms of practical interest. The genetic algorithm (GA) belongs to one category of these best known algorithms, whose beginnings can be traced back to the early 1950s when several biologists used computers for simulations of biological systems [1]. However, the work done in the late 1960s and the early 1970s at the University of Michigan under the direction of J. Holland led to GA as it is known today [2]. With the characteris- tics of easier application, greater robustness, and better parallel processing than most classical methods of optimization, GA has been widely used for combinatorial optimization [3], [4], structural designing [5], machine learning rule-based classifier systems [6], [7], and other engineering problems [8]–[10]. It is well known that GA pertains to searching al- gorithms with an iteration of generation-and-test. Two operators—crossover and mutation—give each individual the chance of optimization and ensure the evolutionary tendency with the selection mechanism of survival of the fittest. GA also proves to be convergent under the condition of maintaining the best individual found over time after selection [11]. Because the two genetic operators make individuals change randomly and indirectly during the whole process, they not only give the individuals the evolutionary chance but also cause certain degeneracy. In some cases, these degenerative phenomena are very obvious. On the other hand, there are many basic and obvious characteristics or knowledge in a pending problem. However the crossover and mutation operators in GA lack Manuscript received November 5, 1999; revised July 5, 2000. This work was supported by the National Science Foundation of China under Grant 69772029 and the Project “863.” This paper was recommended by Associate Editor W. Pedrycz. The authors are with the Key Lab for Radar Signal Processing, Xidian Uni- versity, Xi’an 710071, China. Publisher Item Identifier S 1083-4427(00)07992-3. the capability of meeting an actual situation, so that some torpidity appears when solving problems, which is conducive to the universality of the algorithm but neglects the assistant function of the characteristics or knowledge. The loss due to the negligence is sometimes considerable in dealing with some complex problems. It is also realized from...

Website: bit.csc.lsu.edu | Filesize: -
No of Page(s): 10
Download A novel genetic algorithm based on immunity ... - Computer Science.pdf