Research Article
On Convergence of a Novel Artificial Immune Algorithm
Department of Electronic Engineering, Huaihai Institute of Technology, Lianyungang, Jiangsu Province, 222005, China
Recently, Artificial Immune System (AIS) is experiencing an increasing development as a new branch of bio-inspired computing and has become a new leading edge research direction following the artificial neural networks, fuzzy systems, evolutionary computation (Dasgupata et al., 2011). Artificial immune algorithm inspired by biological immune system are used in pattern recognition, network security, fault detection, combinatorial optimization and a variety of other applications in the fields of science and engineering (Burczynski, 2009). But there are still little literatures related to theory research about these artificial immune algorithms. Currently, the research of artificial immune algorithm is mainly focused on the fields of algorithm implementations, improvements and engineering applications (Timmis, 2007). Convergence theory research of the algorithm is extremely rare. For example, there are only few papers present a complete proof of convergence for specific immune algorithms using Markov chains (Villalobos-Arias et al., 2004). The means and methods of convergence analysis of artificial immune algorithm are rather monotonous (Clark et al., 2005), so these researches have considerable limitations. A Novel Artificial Immune Algorithm (NAIA) based on the clonal selection principle and the idiotypic immune network theory exhibited in biology immune system is proposed in this paper. In order to improve the global convergence performance of the new algorithm, some enhancements based on the characteristics of the chaos and niche technique are introduced. From the definition of probability convergence, a new method of proving the convergence of the NAIA is obtained by using the properties of pure probability and iterative formula method.
THE NOVEL ARTIFICIAL IMMUNE ALGORITHM
Clone selection principle is one of the best-known mechanisms of biological immunology. Clonal selection algorithm based on the mechanism has been widely used in many areas of optimal control, data processing, intrusion detection and fault diagnosis and has become another research focus in the artificial immune computation (De Castro and von Zuben, 2002). The clonal selection algorithm based on the clonal selection principle proposed by de Castro and Von Zuben can explain how the immune system reacts to pathogens and how it improves its capability of recognizing and eliminating pathogens. It was proved to be capable of solving complex problems, such as pattern recognition problems, intrusion detection and combination optimization. Emergence of clonal selection algorithm indicates the beginning of developing intelligent optimization algorithms from the biology immune system mechanism to solve optimization problems. Through further analysis of cloning process, the selected antibody is subject to affinity maturation process and there is only a simple copy of the information but no information exchange between the parent and the offspring of clones. The algorithm does not reflect the dynamic adjustment mechanism of promotion and suppression between antibodies, which leads to the deficiency of diversity of the population. When the algorithm is applied to multi-modal optimization problems, the global search efficiency is not very good (Villalobos-Arias et al., 2004).
Chaos is the essential characteristics of the nonlinear system and has a series of special nature, such as randomness, ergodicity, regularity and sensitivity of the initial value and so on. Recent Modern biology studies have shown that chaos phenomenon also exists in the biology immune system (Canabarro et al., 2004). In order to improve the efficiency of the search and increase the diversity of the population, the paper use the ergodicity and randomness of chaos and design an adaptive chaotic mutation operator through binding the antibodies prior knowledge and evolution iteration. The new algorithm also introduces the niche ideas, the selection strategy based on antibody density and fitness vector matrix and the antibody update strategy.
The design steps of the NAIA algorithm are as follows:
• | Randomly generate an initial population of N antibodies |
• | While stopping criterion is not met, do: |
• | Calculate the fitness of each antibody | |
• | Generate clones for each antibody proportionally according to its fitness | |
• | Apply adaptive chaos mutation operator mutates each clone antibody but keeps the parent antibody | |
• | For each clone set, using niche strategy to choose N antibodies with highest fitness from N mutation sets into next generation and copy the best n antibodies to the memory set | |
• | Compute selection probability of antibodies based on antibody density and fitness vector matrix | |
• | Remove d antibodies with low fitness and replace them with new randomly generated higher fitness members (diversity introduction) |
• | Check the best antibody in the memory set and go to step 2 |
The details of NAIA operators are given as follows: |
• | Antibody clone Tc: This operation is to generate copies of every individual proportionally to its fitness with the antigen. The amount of clones of antibody Xi is given by: |
(1) |
where, Nc is the clone size. F (Xi) is the fitness of the antibody Xi, round (.) is the integral function. Obviously, the antibody with higher fitness means the greater number of copies and vice versa.
• | Adaptive chaos mutation Tm: In order to improve the ability of global search, the adaptive chaos mutation operator is introduced into the algorithm. The mutation operation is defined as the following expression: |
(2) |
where, is the mutated antibody Xi, f (Xi) is the fitness of antibody Xi normalized in the interval [0, 1]; β, γ are parameters of the inverse exponential function; t is the current evolution iteration and T is the total evolution iteration; Lxi (t) is the value of the ith chaotic variable Xi produced by Logistic equation. A mutation is only accepted if the mutated antibody is within its range of domain.
• | Immune selection Ts: Based on the Jernes idiotypic networks principle (Jerne, 1974), a selection mechanism based on density and fitness vector matrix is introduced into NAIA to maintain diversity of population. |
The similarity between two antibodies can be defined as follows:
(3) |
where, ED(.) is the Euclidean distance, L is the length of antibody. f (X) is the fitness function, ε and are positive threshold value. If (4) is satisfied, these two antibodies are called similar ones. The density of antibody Xi, named Di, can be defined as:
(4) |
where, Sim (Xi) is the number of antibodies which are similar to Xi, N is the antibody population size. The fitness vector matrix of antibody Xi is defined as follows:
(5) |
According to the regulation of activating and suppressing between antibodies in immune system, the selection probability of individual Xi can be expressed as:
(6) |
where, υ is regulation factor, D (Xi) is the density of Xi,ρ (Xi) is the fitness vector matrix of Xi.
The above formula reflects the uncertainty of antibody selection and dynamic adjustment mechanism of the idiotypic immune network theory. So NAIA can not only maintain the individuals of high affinity but also guarantee the diversity of population.
• | Immune update : Randomly generate d new antibodies with higher fitness and replace d antibodies with low fitness. |
CONVERGENCE ANALYSIS OF NAIA BASED ON PURE PROBABILITY
While there are lots of successes in the applications of artificial immune algorithm to date, there are limited achievements in theoretical research, especially convergence aspect of algorithms. Convergence results obtained by traditional Markov chain model generally refers to the corresponding Markov chain tending to a stationary distribution and are different from the general convergence definition of optimization. Furthermore, the number of states of the corresponding Markov chain is usually very large, which makes it very difficult to analyze the performance of the transition matrix. For large-scale of artificial immune algorithm, Markov chain analysis can only obtain some rough convergence conclusions of artificial immune algorithm based on ergodic property. The traditional ergodic analysis is substituted by pure probability and iterative formula method to analyze the global convergence of the improved artificial immune algorithm and it will make the algorithm convergence analysis greatly simplified.
For convenience, some parameters are defined at first:
• | Ω: The antibody space |
• | S = ΩN: The population space |
• | P(•): The probability distribution |
• | Γt: ΩN→ΩN: The operator of NAIA |
• | : The Markov chain of NAIA in the space ΩN |
• | M = {X; ∀Y∈S, f (X)≥f (Y)}: The global optimal set |
Let us give the formal definition of some terms as follows:
Definition 1: If sequence is probab ility convergent to the global optimal solution set, then:
is denoted .
Through the previous analysis, NAIA algorithm can be described as random search sequence and can be expressed as:
where, Ts is the immune selection operator; Tm is the Chaos mutation operator; is the Immune update operator.
Let:
There is the following theorem.
Theorem 1: If sequences , satisfy following properties:
• |
• |
Then, the random sequence is said to probability convergent to the satisfied solution set M, then:
Space limitations on this paper do not allow us to prove this theorem here and the proof is given in our full-length paper.
From the theorem 1, the convergence of sequence is closely related to parameters and .
In order to prove the probability convergence of NAIA, the following result is given.
, ∃σ>0, from NAIA, then:
(7) |
where, is the minimum mutation rate.
Theorem 2: For any initial distribution, NAIA algorithm is said to convergence in probability to the global optimal solution set M.
Proof: Let be the antibody population at generation t and XN be the best individual. From the steps of NAIA, then:
, as t = t+1.
Where:
Hence,
(8) |
There are two kinds of cases to consider the state transition probability:
If , from formula (8) and have , then:
(9) |
If , then:
(10) |
(11) |
As , then:
(12) |
From (7), (8), (10), (11), then:
(13) |
Hence:
(14) |
From (7), (9) and (14), the proof is completed.
By integrating chaos mechanism and niche technique, a Novel Artificial Immune Algorithm (NAIA) based on the clonal selection principle and the idiotypic immune network theory is proposed in this paper. Replacing the traditional Markov chain model analysis, the convergence of NAIA with a new pure probability and iterative formula method is analyzed and some useful conclusions are derived. These theoretical analyses can be helpful for the further research of artificial immune algorithm. At the same time, there is still much work left for us to do in the artificial immune algorithm theory field. As part of our future work, the impact of the parameters on the convergence of artificial immune algorithm will be extended.