Transcript Slide 1
Immune Genetic Algorithms By Jeremy Moreau References • Licheng Jiao, Senior Member, IEEE, and Lei Wang, “A Novel Genetic Algorithm Based on Immunity,” IEEE Transactions on Systems, Man, AND Cybernetics—Part A: Systems and Humans, Vol. 30, No. 5, September 2000 Outline • Introduction • Immune genetic algorithm (IGA) – Vaccination – Immune Selection • The immune operator • Simulations • Conclusions Introduction • All genetic algorithms use the mutation and crossover operators • This gives individuals the chance to evolve into a more fit individual • If target is difficult to reach, crossover and mutation may introduce degeneracy into generations of individuals • Immunity can be introduced to help prevent degeneration The Immune Genetic Algorithm (IGA) • Uses local information to intervene in the global process of mutation and crossover • Curtails the degenerative phenomena from arising during the evolution process • Consists of two basic steps: – The vaccination – The immune selection The Vaccination • Given an individual, vaccination means modifying the bits of some genes using prior knowledge • Satisfies two conditions: – If each gene bit of an individual y is wrong, the probability of transforming to y is 0 – If each gene bit of an individual y is optimal, the probability of transforming to y is 1 The Immune Selection • Consists of two steps: – Perform an immunity test: If the fitness of an individual is less than that of its parent, degeneration occurred during crossover and mutation. Use the parent instead of the child – Annealing selection: an individual is selected from the present offspring to join with the new parents The Algorithm • The immune genetic algorithm – 1. Create initial random population A1. – 2. Abstract vaccines according to the prior knowledge. – 3. If the current population contains the optimal individual, then the algorithm halts. – 4. Perform crossover on the kth parent and obtain the results Bk. – 5. Perform mutation on Bk to obtain Ck. – 6. Perform vaccination on Ck to obtain Dk. – 7. Perform immune selection on Dk and obtain the next parent Ak+1, and then go to step 3). Algorithm Flow Convergence • General GA algorithms are not guaranteed to converge • The IGA is convergent with a probability of 1 The Immune Operator • Uses the vaccination and immune selection operators • During these operations, the basic problem characteristics are abstracted into a schema • Theorem 2: Under the immune selection, if the vaccination makes the fitness of an individual higher than the average fitness of the current population, then the schema of the corresponding vaccine will be diffused at an index level within the population. If not, it will be restrained or attenuated by an index level Simulations • Simulations were performed on the Traveling Salesman Problem (TSP) • The following results were for the 75 city TSP • Were L is the side of the smallest square containing all cities, N is the number of cities (75), and D is the path length of the current permutation, the fitness function used was: Results for GA and IGA Fitness of GA and IGA (Bad Vaccine) Conclusions • Introducing the immunity operator guarantees convergence of the genetic algorithm • Proper vaccine selection causes the algorithm to converge quickly. However, even poor vaccine selection causes the algorithm to converge, just more slowly • For most large and/or complex problems, the IGA speeds up performance drastically Questions??