ABSTRACT

This paper presents a new adaptive mutation approach for fastening the convergence of immune algorithms (IAs). This method is adopted to realize the twin goals of maintaining diversity in the population and sustaining the convergence capacity of the IA. In this method, the mutation rate (p_m) is adaptively varied depending on the fitness values of the solutions. Solutions of high fitness are protected, while solutions with sub-average fitness are totally disrupted. A solution to the problem of deciding the optimal value of p_m is obtained. Experiments are carried out to compare the proposed approach to traditional one on a set of optimization problems. These are namely: 1) an exponential multi-variable function; 2) a rapidly varying multimodal function and 3) design of a second order 2-D narrow band recursive LPF. Simulation results show that the proposed method efficiently improves IA’s performance and prevents it from getting stuck at a local optimum.

1. Introduction

Finding an appropriate set of parameter values for evolutionary algorithms (EAs) has been a longstanding major challenge of the evolutionary computation community. Such difficulty has directed researchers’ attention towards devising an automated ways of controlling EAs parameters [1]. Immune Algorithm (IA) is one of recently EAs that based on the mechanism of the amalgamation between antigen and antibody in biologic immune system [2]. IAs have been used widely and successfully in many computational intelligence areas including medical data processing, biomedical and satellite image processing, spectrum analysis and design of digital filters [3-6]. The performance of IAs depends on many factors, such as selection schemes and control parameters. In spite of the research carried out up to date, there are no general rules on how the control parameters of IA can be selected. In literature [5-8], the choice these parameters is still left to the user to be determined statically prior to the execution of the IA. Mutation rate (p_m) is considered to be one of the most sensitive control parameters that an immune algorithm works with. This is due to the fact that it increases the diversity in population. The choice of mutation rate is essentially a tradeoff between conservatism and exploration [9].

In this paper we investigate an efficient technique for multi-modal function optimization using IAs. We recommend the use of adaptive probability of mutation to realize the twin goals of maintaining diversity in the population and sustaining the convergence capacity of the IA. In adaptive mutation approach, the value of is varied depending on the fitness values of the solutions. The fitness values of the solution in relation to an objective function to be optimized. During each generation, the fitness of each solution is evaluated, and solutions are selected for reproduction based on their fitness. Selection embodies the principle of survival of the fittest. Good solutions are selected for reproduction while bad solutions are eliminated. The goodness of a solution is determined from its fitness value. The adaptation probability of mutation provides a solution to the problem of choosing the optimal value of the probability of mutation in IA.

The paper is organized as follows. Section 2 describes definition of the optimization problem. The proposed method for fastening the convergence of IA is described in Section 3. Section 4 presents the three experiments that we have conducted to compare the performance of the adaptive and traditional mutation approaches on IA. Section 5 shows the results and discussion of the experiments. Finally, Section 6 offers some conclusions.

2. Problem Definition

The global optimization problem is considered as [10, 11]:

(1)

where, is the objective function, is the optimizing function and is the desired function. The vector is a variable vector and and define the feasible solution space. Since the IAs mimic the antigen-antibody reaction of the immune system in mammals. The antigen and the antibody in the IA are equivalent to the objective function and the feasible solution for a conventional optimization method, respectively. The antibodies (chromosomes) population is generated either by using binary coding representation or real coding representation. In the binary coding representation, each variable (gene) is encoded as a binary string and the resulting strings are concatenated to form single antibody [12]. However, in the real coding representation, each antibody is encoded as a vector of floating point numbers (i.e., where is a random value), with the same length as the vector of decision variables. This representation is accurate and efficient because it is closest to the real design space, and the string length represents the number of design variables. The hyper-mutation mechanism of the clonal proliferation and mutation mechanism play a critical role in creating diverse antibodies based on minimization of the difference between the optimizing and desired functions. The diversity is measured between the antibodies, and it is increased to prevent local optimization during the optimal search [6].

In optimizing functions, it is important that the IA should be able to converge to the optimal value in as few generations as possible. The convergence speed heavily depends on its main control parameters: population size, replication rate, mutation rate, clonal rate and hypermutation rate [13]. Mutation rate is considered to be one of the most sensitive control parameters that an immune algorithm works with, because it increases the diversity in population to prevent the solution to get stuck at a local optimal value during the optimization search. So, the adaptive mutation approach is considered here.

3. Adaptive Mutation Approach

Mutation alters one or more genes (unknown variables) depending on the mutation rate. For a given antibody, if the gene x_i is selected for mutation depending on mutation rate and the other x_k is randomly selected to join in, the resulting offspring antibody becomes, where the new gene is and β is selected randomly in the range [0,1]. The choice of is essentially a tradeoff between conservatism and exploration [9]. It has been well established in IA literature [8] that when the value of is selected nearby the range of [0.02, 0.05], the time spent on searching is relatively short and the searching process is stable as well as the search efficiency is better [13]. In the proposed approach, we aim at achieving this trade-off between conservatism and exploration in a different manner, by varying the adaptively in response to the fitness values of the solutions; is increased when the population tends to get stuck at a local optimum and is decreased when the population is scattered in the solution space. So, it is essential to be able to identify whether the IA is converging to an optimum solutions or it diverges. The average of fitness value () of the population in relation to maximum fitness value () of the population is used to detect the conversance of IA. is likely to be less for a population that has converged to an optimum solution than that for a population scattered in the solution space. Therefore the difference in the maximum and average fitness values () is used as a yardstick for detecting the convergence of IA. The value of is varied depending on the value of to prevent premature convergence of the IA to a local optimum. Since has to be increased when the IA converge to a local optimum, will have to be varied inversely with. The expression that we have chosen for is of the form:

(2)

From Equation (2), it can be noticed that do not depend on the fitness value of any particular solution, and have the same value for all the solutions of the population. Consequently, solutions with high fitness values as well as solutions with low fitness values are subjected to the same levels of mutation. When a population converges to a globally optimal solution (or even a locally optimal solution), increases and may cause the disruption of the near-optimal solutions. To overcome this problem and to preserve good solutions of the population should have lower value for high fitness solutions and higher value for low fitness solutions. While the high fitness solutions aid in the convergence of the IA, the low fitness solutions prevent the IA from getting stuck at a local optimum. The value of should depend not only on, but also on the fitness value f of the solution. The closer f is to, the smaller should be, i.e., should vary directly as. So, the expression in Equation (2) is modified to become:

(3)

Note that is zero for the solution with the maximum fitness. Also for a solution with. For solutions with sub-average fitness values (i.e. f < f_av), might assume value larger than 1.0. To prevent the overshooting of beyond 1.0, we also have the following constraints,

(4)

where,

For convenience, the expression for is given as:

(5)

The values of and are in the range [0,1] and are selected to prevent the IA from getting stuck at a local optimum. For solutions with sub-average fitness the search space is searched for the region containing the global optimum solution. Such solutions need to be completely disrupted, and for this purpose the value of is selected to be 0.5. But, the value of is selected by 1/L as state in [14], where L is the encoding string length.

4. Experiments

This section presents the three experiments that we have conducted to compare the performance of the adaptive and traditional mutation approaches on IA. For this purpose we have employed three test problems with varying complexities.

Experiment 1: This experiment considers the optimization of the exponential function shown in Figure 1 and described by the following Equation [13]:

(6)

with the following desired specified values at x=.

Experiment 2: This experiment considers the rapidly varying multimodal function of two variables described by Equation (7). This function is symmetric about the origin with the barrier height between adjacent minima approaching zero as the global optimum is approached and is considered in [15] to test the performance of adaptive genetic algorithm. Figure 2 illustrates the function in biand uni-dimensional plots for

and.

(7)

Experiment 3: This experiment considers the design of a second order 2-D narrow-band recursive LPF with magnitude and group delay specifications. The specified magnitude is shown in Figure 3 [7,13]. Namely, it is given by Equation (8) with the additional constant group delay over the passband

and the design space is [-3 3]. To solve this problem, the frequency samples are taken at in the ranges , and.

(8)

5. Results and Discussion

For the three experiments [16] considered, the program implementation for each chosen approach is run 30 times. The population size is set to 100 for all experiments and the values of mutation rate for all experiments are given in Table 1. Table 2 gives the average number of generations required by each approach for attaining a solution, the number of instances (out of 30 trials) for which the IA have gotten stuck at a local optimum, and the maximum number of generations. Figures 4, 5 and 6 show the objective value of the three experiments respectively that obtained using adaptive and traditional muta-

tion approaches. From Table 2 and Figures 4, 5 and 6 can be noticed that the adaptive mutation approach improves the performance of the IA and give better results than traditional mutation approach.

6. Conclusion

In this paper, we adopt an efficient adaptive mutation approach to provide a solution to the problem of finding the optimal value of p_m for immune algorithms. In this approach, the value of p_m is varied depending on the fitness values of the solutions. The proposed approach decreases the value of p_m for high fitness solutions to sustain the convergence capacity of the IA and increases the value of p_m for low fitness solutions to maintain diversity in the population. This method not only improves the convergence of IA, but also prevents the IA from getting stuck at a local optimum. Simulation results show that the proposed mutation approach efficiently improves IA’s performance.

REFERENCES