## Abstract

We introduce taboo evolutionary programming, a very efficient global optimization method which combines features of single-point mutation evolutionary programming (SPMEP) and taboo search. As demonstrated by solving 18 benchmark problems, the algorithm is not trapped in local minima and quickly approaches the global minimum. The results are superior to those from SPMEP, fast evolutionary programming and generalized evolutionary programming. The method is easily applicable to real-world problems, and the central idea may be introduced into other algorithms.

## 1. Introduction

Many problems in virtually all fields of physical science as well as in chemistry, technology, economics, logistics, travel scheduling and in the design of microprocessor circuitry involve global optimization: the determination of the global minimum of a function of an arbitrary number of independent variables. In most cases of practical interest, global optimization is very difficult because of the omnipresence of local minima, the number of which tends to increase exponentially with the size of the problem. Conventional minimization techniques are time consuming and converge to whichever local minimum they first encounter.

Evolutionary programming is one of the number of general metaheuristics known as evolutionary algorithms (Fogel *et al*. 1966), which include genetic algorithms, evolutionary strategies, evolutionary programming and genetic programming (Eiben & Schoenauer 2002; Eiben & Smith 2003). Although evolutionary algorithms do not rely on gradient information, their global convergence is guaranteed (Fogel 1994).

Classical evolutionary programming relies solely on mutation (Fogel *et al*. 1966). Fogel (1992) and Bäck & Schwefel (1993) have shown that evolutionary programming with self-adaptive mutation usually performs well. Yao *et al*. (1999) put forward fast evolutionary programming (FEP) which replaces Gaussian mutation by Cauchy mutation. Lee & Yao (2001, 2004) used evolutionary algorithms with adaptive Lévy mutations and studied the relationship between the parameter *α* in Lévy distribution and evolutionary programming, while Iwamatsu's generalized evolutionary programming (GEP) is based on a Lévy-type distribution (Iwamatsu 2002). Tu & Lu (2004) significantly put forward a stochastic genetic algorithm, explored the search space region-by-region and obtained very good results. Ji *et al*. (2004) described single-point mutation evolutionary programming (SPMEP), in which only one component of each solution is mutated in each iteration.

While the results from these methods are satisfactory, the principal requirement from any global optimization algorithm is that it must be able to avoid entrapment in local minima and continue the search for the optimal solution whatever maybe the initial conditions. It is not easy for evolutionary programming to fulfil this condition.

Taboo search (TS), introduced by Cvijović & Klinowski (1995) for continuous functions, avoids entrapment in local minima, gives the optimal final solution, and was superior to other methods of global optimization available at the time. It has solved optimization problems such as the structure of clusters (Wales & Doye 1997), molecular docking (Westhead *et al*. 1997) and conformational energy optimization of oligopeptides (Morales *et al*. 2000). In theory, under the specified conditions, TS converges to the global minima with probability one (Ji & Klinowski 2006). We describe taboo evolutionary programming (TEP), a new evolutionary algorithm, using improved search paths and taboo conditions, and compare its performance with that of SPMEP, FEP and GEP.

## 2. Taboo evolutionary programming

Consider the following continuous global optimization problem,where . *f* is a real-valued continuous function defined on .

In classical evolutionary programming (Fogel *et al*. 1966), each parent , , creates a single offspring, , as follows:where and denote the *j*th component of the vectors and , respectively. is a normally distributed one-dimensional random number with a mean of zero and a standard deviation of one. indicates that the random number is generated anew for each value of *j*. The factors *τ* and are commonly set to and (Bäck & Schwefel 1993; Yao *et al*. 1999). FEP replaces the Gaussian random number by the Cauchy random . In GEP, is replaced by the Lévy-type random . In SPMEP, each parent , creates a single offspring by , where is randomly chosen from the set . Despite improving the probability of convergence to global minima, these algorithms are still easily entrapped when solving problems involving multimodal functions with many local minima.

### (a) Taboo evolutionary programming for solving global optimization problems

The TEP algorithm combines the characteristics of SPMEP and TS, and proceeds as follows:

Generate the initial population of

*μ*individuals based on a uniform distribution, and set*k*=1. Each individual is taken as a vector .Evaluate the fitness score for each individual, , of the population on the objective function, .

Each parent , , creates a single offspring bywhere is randomly chosen from the set . Other components of are equal to the corresponding

*x*_{i}'s. denotes a normally distributed one-dimensional random number with a mean of zero and a standard deviation of one. Here, the parameter . The initial value of*η*is . If , then .Calculate the fitness of each offspring .

Perform search using the following improved paths:

Choose an improved path as follows. For each , if , then , is an improved path. Put a pair of vectors into the set

*A*.Choose

*r*best fitness individuals from the set*A*as the parents with improved paths. Note that , where is an objective variable and is the corresponding improved path. Set .Calculate fitness: for each , . The initial value of

*ρ*is 1. If , then*ρ*=1.For each , if , then set as a parent of the next generation with improved search paths, and put into the set

*A*.Record the number,

*τ*, of members in set*A*.Choose the parents for the next generation.

Perform a comparison over the union of parents and offspring . For each individual,

*q*opponents are chosen uniformly at random from all the parents and offspring. For each comparison, if the individual's fitness is equal to or greater than the opponent's, it scores a ‘win’. Select the*μ*–*τ*individuals out of and , , which have the most wins to be put into the set*B*.Make the individuals

*x*, and*y*from sets*B*and*A*the parents of the next generation. Set .Check the taboo status.

Record the current optimal fitness, , and the current optimal solution, .

When

*k*>*L*, compare the optimal fitness of the current generation with the optimal fitness of the previous*L*generations. Thus, if , then , . Put the pair of the vectors into the taboo table . The length of taboo table is*l*.For any in , if the current optimal fitness and the optimal solution satisfies the taboo conditions, and , then generate the initial population of

*μ*individuals and set new individuals as the*k*th generation.Terminate if the halting criterion is satisfied. Otherwise, set and go to Step (3).

### (b) The features of taboo evolutionary programming

TEP introduces improved search paths in Step (5), and more quickly approaches the local or global minima. The taboo condition introduced in Step (7) increases the probability that the algorithm avoids entrapment in local minima.

TEP uses the same number of calculations as FEP, GEP and SPMEP. But, as a result of the No-Free-Lunch theorem (Wolpert & Macready 1997), TEP requires more CPU time because it generates

*r*solutions with improved paths in Step (5).

## 3. Computational results

We examined the performance of TEP by applying it to 18 benchmark functions used by Schwefel (1995), Yao *et al*. (1999) and Iwamatsu (2002) (see appendix A), a larger set of test functions than that considered by other empirical studies. The set includes unimodal, multimodal, low- and high-dimensional functions.

Functions are high-dimensional and functions are unimodal. Function is a discontinuous step function with a single minimum. Function is a noisy quartic function, where *random*[0, 1) is a uniformly distributed random variable in . Multimodal functions with the number of local minima increasing exponentially with the dimension of the problem appear to be the most difficult test for optimization algorithms. Functions are low-dimensional with only a few local minima. The final results for multimodal functions are important since they reflect the ability of the algorithm to escape from poor local optima.

Table 1 compares our results with those given by Yao *et al*. (1999) and Ji *et al*. (2004), where the initial population *μ*=90 and the number of opponents *q*=10. The halting criterion is that the maximum number of generations, *N*, is reached. The initial populations are generated uniformly at random in the domain. The number of individuals with improved search paths, *r*, is 10, which gives the same number of function evaluations as that used by Yao *et al*. (1999) and Ji *et al*. (2004). The error varies between . *L*=100 and 50 for high- and low-dimensional functions, respectively. The length of the taboo list *l* is chosen to be between 1 and 6.

Table 2 compares our results with those of Iwamatsu (2002) and Ji *et al*. (2004), where the dimensions *n* of functions and are fixed at 10 and the dimension *n* of function is 4. The initial population *μ*=40. Iwamatsu (2002) and Ji *et al*. (2004) used the same number of function evaluations. Other conditions are the same as those given in table 1.

Table 1 shows that the performance of TEP is better than that of SPMEP and FEP for functions , and is similar for function . Function is perturbed by the random variable *random*[0, 1). When *random*[0, 1)=0, the global optimum of is zero, and thus the algorithms are affected by the random variable. For function , the performance of FEP is better than that of TEP and SPMEP. For functions , TEP is the best of the three algorithms. Its precision is higher than that of SPMEP and times better than that of FEP. For low-dimensional functions , TEP is not obviously superior, and the three algorithms have the same precision. However, the standard deviations of TEP are better, showing that TEP is very robust.

Table 2 shows that with TEP the precision for functions and is -fold better than with GEP and also better than with SPMEP. For high-dimensional and multimodal functions, TEP is clearly superior to GEP and SPMEP. The standard deviations for TEP are smaller than for GEP and SPMEP, which indicates that the best values in all 50 runs are very close to the mean best objective values. TEP is therefore the most robust of the four algorithms.

Figures 1–3 show the status of TEP for functions . Since we recorded the current best objective value for a large number of iterations (see table 1), peaks caused by re-initializing the taboo condition are not visible. TEP increases the probability of escape from local minima by using the taboo conditions. Figures 1–3 show that all 50 runs have very high precision and converge to the global minima. TEP comes close to the global minimum within 1000 iterations for high-dimensional functions , and within 50 iterations for low-dimensional functions .

## 4. Analysis of taboo evolutionary programming

Consider the reasons why TEP obtains better results than SPMEP and FEP. The three algorithms use different mutation strategies. While TEP adopts and , SPMEP uses and FEP uses , where and *δ* are the Gaussian and Cauchy random variables, respectively. Figure 4 shows that the spread of points obtained by the Cauchy distribution is wider than the spread of points obtained by the Gaussian distribution. The large variation of the Cauchy points signifies the ease of escape from local minima while, conversely, the small variation of the Gaussian points means that it is more difficult to escape, but benefits the search of local regions. In addition, because TEP uses improved paths in Step (5), for unimodal function TEP gives better results than SPMEP and FEP.

Although TEP increases the probability of the search becoming locally entrapped (because Gaussian distribution is being used), the taboo condition introduced in Step (7) increases the probability of escape. Step (7.2) places the current best value on the taboo list when the current best value is not improved compared with the best value of the previous *L* generations. The current best value then becomes entrapped in a local minimum. In order to escape from it, we use the taboo condition in Step (7.3). As a result of this condition, the current population is replaced by a new initial population when the current best value and the optimal solution is entrapped in the vicinity of a local minimum. This increases the probability of escaping. In this way, TEP obtains good results for multimodal functions .

## 5. Conclusions

Our algorithm is superior to the other three for solving multimodal and high-dimensional functions. Since, unlike evolutionary programming, TEP only introduces better search paths and taboo conditions, it can easily be applied to real-world problems. The central idea may be introduced into other evolutionary algorithms. The TEP algorithm will be freely available on J.K.'s website (www-klinowski.ch.cam.ac.uk).

## Acknowledgements

We are grateful to the Royal Society of London for an International fellowship to M.-J.J., and to the referees for their constructive comments.

## Footnotes

- Received April 1, 2006.
- Accepted May 11, 2006.

- © 2006 The Royal Society