The effect of using evolutionary algorithms on Ant Clustering Techniques.

u l
n
Abstract—In this paper, we propose an extension of Self-adaptive Differential Evolution algorithm (SaDE) to solve optimization problems with constraints. In comparison with the original SaDE algorithm, the replacement criterion was modified for handling constraints. The performance of the proposed method is reported on the set of 24 benchmark problems provided by CEC2006 special session on constrained real parameter optimization.
2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada July 16-21, 2006
Self-adaptive Differential Evolution Algorithm for Constrained Real-Parameter Optimization
“DE/rand/1”: Vi ,G = Xr ,G + F ⋅ Xr ,G − Xr G
1 2 3,
(
“DE/best/1”: Vi ,G = Xbest ,G + F ⋅ Xr ,G − X r G 1 2,

附录I 英文翻译第一部分英文原文文章来源：书名：《自然赋予灵感的元启发示算法》第二、三章出版社：英国Luniver出版社出版日期：2008Chapter 2Genetic Algorithms2.1 IntroductionThe genetic algorithm (GA), developed by John Holland and his collaborators in the 1960s and 1970s, is a model or abstraction of biolo gical evolution based on Charles Darwin’s theory of natural selection. Holland was the first to use the crossover and recombination, mutation, and selection in the study of adaptive and artificial systems. These genetic operators form the essential part of the genetic algorithm as a problem-solving strategy. Since then, many variants of genetic algorithms have been developed and applied to a wide range of optimization problems, from graph colouring to pattern recognition, from discrete systems (such as the travelling salesman problem) to continuous systems (e.g., the efficient design of airfoil in aerospace engineering), and from financial market to multiobjective engineering optimization.There are many advantages of genetic algorithms over traditional optimization algorithms, and two most noticeable advantages are: the ability of dealing with complex problems and parallelism. Genetic algorithms can deal with various types of optimization whether the objective (fitness) functionis stationary or non-stationary (change with time), linear or nonlinear, continuous or discontinuous, or with random noise. As multiple offsprings in a population act like independent agents, the population (or any subgroup) can explore the search space in many directions simultaneously. This feature makes it ideal to parallelize the algorithms for implementation. Different parameters and even different groups of strings can be manipulated at the same time.However, genetic algorithms also have some disadvantages.The formulation of fitness function, the usage of population size, the choice of the important parameters such as the rate of mutation and crossover, and the selection criteria criterion of new population should be carefully carried out. Any inappropriate choice will make it difficult for the algorithm to converge, or it simply produces meaningless results.2.2 Genetic Algorithms2.2.1 Basic ProcedureThe essence of genetic algorithms involves the encoding of an optimization function as arrays of bits or character strings to represent the chromosomes, the manipulation operations of strings by genetic operators, and the selection according to their fitness in the aim to find a solution to the problem concerned. This is often done by the following procedure:1) encoding of the objectives or optimization functions; 2) defining a fitness function or selection criterion; 3) creating a population of individuals; 4) evolution cycle or iterations by evaluating the fitness of allthe individuals in the population,creating a new population by performing crossover, and mutation,fitness-proportionate reproduction etc, and replacing the old population and iterating again using the new population;5) decoding the results to obtain the solution to the problem. These steps can schematically be represented as the pseudo code of genetic algorithms shown in Fig. 2.1.One iteration of creating a new population is called a generation. The fixed-length character strings are used in most of genetic algorithms during each generation although there is substantial research on the variable-length strings and coding structures.The coding of the objective function is usually in the form of binary arrays or real-valued arrays in the adaptive genetic algorithms. For simplicity, we use binary strings for encoding and decoding. The genetic operators include crossover,mutation, and selection from the population.The crossover of two parent strings is the main operator with a higher probability and is carried out by swapping one segment of one chromosome with the corresponding segment on another chromosome at a random position (see Fig.2.2).The crossover carried out in this way is a single-point crossover. Crossover at multiple points is also used in many genetic algorithms to increase the efficiency of the algorithms.The mutation operation is achieved by flopping the randomly selected bits (see Fig. 2.3), and the mutation probability is usually small. The selection of anindividual in a population is carried out by the evaluation of its fitness, and it can remain in the new generation if a certain threshold of the fitness is reached or the reproduction of a population is fitness-proportionate. That is to say, the individuals with higher fitness are more likely to reproduce.2.2.2 Choice of ParametersAn important issue is the formulation or choice of an appropriate fitness function that determines the selection criterion in a particular problem. For the minimization of a function using genetic algorithms, one simple way of constructing a fitness function is to use the simplest form F = A−y with A being a large constant (though A = 0 will do) and y = f(x), thus the objective is to maximize the fitness function and subsequently minimize the objective function f(x). However, there are many different ways of defining a fitness function.For example, we can use the individual fitness assignment relative to the whole populationwhere is the phenotypic value of individual i, and N is the population size. The appropriateform of the fitness function will make sure that the solutions with higher fitness should be selected efficiently. Poor fitness function may result in incorrect or meaningless solutions.Another important issue is the choice of various parameters.The crossover probability is usually very high, typically in the range of 0.7~1.0. On the other hand, the mutation probability is usually small (usually 0.001 _ 0.05). If is too small, then the crossover occurs sparsely, which is not efficient for evolution. If the mutation probability is too high, the solutions could still ‘jump around’ even if the optimal solution is approaching.The selection criterion is also important. How to select the current population so that the best individuals with higher fitness should be preserved and passed onto the next generation. That is often carried out in association with certain elitism. The basic elitism is to select the most fit individual (in each generation) which will be carried over to the new generation without being modified by genetic operators. This ensures that the best solution is achieved more quickly.Other issues include the multiple sites for mutation and the population size. The mutation at a single site is not very efficient, mutation at multiple sites will increase the evolution efficiency. However, too many mutants will make it difficult for the system to converge or even make the system go astray to the wrong solutions. In reality, if the mutation is too high under high selection pressure, then the whole population might go extinct.In addition, the choice of the right population size is also very important. If the population size is too small, there is not enough evolution going on, and there is a risk for the whole population to go extinct. In the real world, a species with a small population, ecological theory suggests that there is a real danger of extinction for such species. Even the system carries on, there is still a danger of premature convergence. In a small population, if a significantly more fit individual appears too early, it may reproduces enough offsprings so that they overwhelm the whole (small) population. This will eventually drive the system to a local optimum (not the global optimum). On the other hand, if the population is too large, more evaluations of the objectivefunction are needed, which will require extensive computing time.Furthermore, more complex and adaptive genetic algorithms are under active research and the literature is vast about these topics.2.3 ImplementationUsing the basic procedure described in the above section, we can implement the genetic algorithms in any programming language. For simplicity of demonstrating how it works, we have implemented a function optimization using a simple GA in both Matlab and Octave.For the generalized De Jong’s test function where is a positive integer andr > 0 is the half length of the domain. This function has a minimum of at . For the values of , r = 100 and n = 5 as well as a population size of 40 16-bit strings, the variations of the objective function during a typical run are shown in Fig. 2.4. Any two runs will give slightly different results dueto the stochastic nature of genetic algorithms, but better estimates are obtained as the number of generations increases.For the well-known Easom functionit has a global maximum at (see Fig. 2.5). Now we can use the following Matlab/Octave to find its global maximum. In our implementation, we have used fixedlength 16-bit strings. The probabilities of crossover and mutation are respectivelyAs it is a maximization problem, we can use the simplest fitness function F = f(x).The outputs from a typical run are shown in Fig. 2.6 where the top figure shows the variations of the best estimates as they approach while the lower figure shows the variations of the fitness function.% Genetic Algorithm (Simple Demo) Matlab/Octave Program% Written by X S Yang (Cambridge University)% Usage: gasimple or gasimple(‘x*exp(-x)’);function [bestsol, bestfun,count]=gasimple(funstr)global solnew sol pop popnew fitness fitold f range;if nargin<1,% Easom Function with fmax=1 at x=pifunstr=‘-cos(x)*exp(-(x-3.1415926)^2)’;endrange=[-10 10]; % Range/Domain% Converting to an inline functionf=vectorize(inline(funstr));% Generating the initil populationrand(‘state’,0’); % Reset the random generatorpopsize=20; % Population sizeMaxGen=100; % Max number of generationscount=0; % counternsite=2; % number of mutation sitespc=0.95; % Crossover probabilitypm=0.05; % Mutation probabilitynsbit=16; % String length (bits)% Generating initial populationpopnew=init_gen(popsize,nsbit);fitness=zeros(1,popsize); % fitness array% Display the shape of the functionx=range(1):0.1:range(2); plot(x,f(x));% Initialize solution <- initial populationfor i=1:popsize,solnew(i)=bintodec(popnew(i,:));end% Start the evolution loopfor i=1:MaxGen,% Record as the historyfitold=fitness; pop=popnew; sol=solnew;for j=1:popsize,% Crossover pairii=floor(popsize*rand)+1; jj=floor(popsize*rand)+1;% Cross overif pc>rand,[popnew(ii,:),popnew(jj,:)]=...crossover(pop(ii,:),pop(jj,:));% Evaluate the new pairscount=count+2;evolve(ii); evolve(jj);end% Mutation at n sitesif pm>rand,kk=floor(popsize*rand)+1; count=count+1;popnew(kk,:)=mutate(pop(kk,:),nsite);evolve(kk);endend % end for j% Record the current bestbestfun(i)=max(fitness);bestsol(i)=mean(sol(bestfun(i)==fitness));end% Display resultssubplot(2,1,1); plot(bestsol); title(‘Best estimates’); subplot(2,1,2); plot(bestfun); title(‘Fitness’);% ------------- All sub functions ----------% generation of initial populationfunction pop=init_gen(np,nsbit)% String length=nsbit+1 with pop(:,1) for the Signpop=rand(np,nsbit+1)>0.5;% Evolving the new generationfunction evolve(j)global solnew popnew fitness fitold pop sol f;solnew(j)=bintodec(popnew(j,:));fitness(j)=f(solnew(j));if fitness(j)>fitold(j),pop(j,:)=popnew(j,:);sol(j)=solnew(j);end% Convert a binary string into a decimal numberfunction [dec]=bintodec(bin)global range;% Length of the string without signnn=length(bin)-1;num=bin(2:end); % get the binary% Sign=+1 if bin(1)=0; Sign=-1 if bin(1)=1.Sign=1-2*bin(1);dec=0;% floating point.decimal place in the binarydp=floor(log2(max(abs(range))));for i=1:nn,dec=dec+num(i)*2^(dp-i);enddec=dec*Sign;% Crossover operatorfunction [c,d]=crossover(a,b)nn=length(a)-1;% generating random crossover pointcpoint=floor(nn*rand)+1;c=[a(1:cpoint) b(cpoint+1:end)];d=[b(1:cpoint) a(cpoint+1:end)];% Mutatation operatorfunction anew=mutate(a,nsite)nn=length(a); anew=a;for i=1:nsite,j=floor(rand*nn)+1;anew(j)=mod(a(j)+1,2);endThe above Matlab program can easily be extended to higher dimensions. In fact, there is no need to do any programming (if you prefer) because there are many software packages (either freeware or commercial) about genetic algorithms. For example, Matlab itself has an extra optimization toolbox.Biology-inspired algorithms have many advantages over traditional optimization methods such as the steepest descent and hill-climbing and calculus-based techniques due to the parallelism and the ability of locating the very good approximate solutions in extremely very large search spaces.Furthermore, more powerful new generation algorithms can be formulated by combiningexisting and new evolutionary algorithms with classical optimization methods.Chapter 3Ant AlgorithmsFrom the discussion of genetic algorithms, we know that we can improve the search efficiency by using randomness which will also increase the diversity of the solutions so as to avoid being trapped in local optima. The selection of the best individuals is also equivalent to use memory. In fact, there are other forms of selection such as using chemical messenger (pheromone) which is commonly used by ants, honey bees, and many other insects. In this chapter, we will discuss the nature-inspired ant colony optimization (ACO), which is a metaheuristic method.3.1 Behaviour of AntsAnts are social insects in habit and they live together in organized colonies whose population size can range from about 2 to 25 millions. When foraging, a swarm of ants or mobile agents interact or communicate in their local environment. Each ant can lay scent chemicals or pheromone so as to communicate with others, and each ant is also able to follow the route marked with pheromone laid by other ants. When ants find a food source, they will mark it with pheromone and also mark the trails to and from it. From the initial random foraging route, the pheromone concentration varies and the ants follow the route with higher pheromone concentration, and the pheromone is enhanced by the increasing number of ants. As more and more ants follow the same route, it becomes the favoured path. Thus, some favourite routes (often the shortest or more efficient) emerge. This is actually a positive feedback mechanism.Emerging behaviour exists in an ant colony and such emergence arises from simple interactions among individual ants. Individual ants act according to simple and local information (such as pheromone concentration) to carry out their activities. Although there is no master ant overseeing the entire colony and broadcasting instructions to the individual ants, organized behaviour still emerges automatically. Therefore, such emergent behaviour is similar to other self-organized phenomena which occur in many processes in nature such as the pattern formation in animal skins (tiger and zebra skins).The foraging pattern of some ant species (such as the army ants) can show extraordinary regularity. Army ants search for food along some regular routes with an angle of about apart. We do not know how they manage to follow such regularity, but studies show that they could move in an area and build a bivouac and start foraging. On the first day, they forage in a random direction, say, the north and travel a few hundred meters, then branch to cover a large area. The next day, they will choose a different direction, which is about from the direction on the previous day and cover a large area. On the following day, they again choose a different direction about from the second day’s direction. In this way, they cover the whole area over about 2 weeks and they move out to a different location to build a bivouac and forage again.The interesting thing is that they do not use the angle of (this would mean that on the fourth day, they will search on the empty area already foraged on the first day). The beauty of this angle is that it leaves an angle of about from the direction on the first day. This means they cover the whole circle in 14 days without repeating (or covering a previously-foraged area). This is an amazing phenomenon.3.2 Ant Colony OptimizationBased on these characteristics of ant behaviour, scientists have developed a number ofpowerful ant colony algorithms with important progress made in recent years. Marco Dorigo pioneered the research in this area in 1992. In fact, we only use some of the nature or the behaviour of ants and add some new characteristics, we can devise a class of new algorithms.The basic steps of the ant colony optimization (ACO) can be summarized as the pseudo code shown in Fig. 3.1.Two important issues here are: the probability of choosing a route, and the evaporation rate of pheromone. There are a few ways of solving these problems although it is still an area of active research. Here we introduce the current best method. For a network routing problem, the probability of ants at a particular node to choose the route from node to node is given bywhere and are the influence parameters, and their typical values are .is the pheromone concentration on the route between and , and the desirability ofthe same route. Some knowledge about the route such as the distance is often used so that ,which implies that shorter routes will be selected due to their shorter travelling time, and thus the pheromone concentrations on these routes are higher.This probability formula reflects the fact that ants would normally follow the paths with higher pheromone concentrations. In the simpler case when , the probability of choosing a path by ants is proportional to the pheromone concentration on the path. The denominator normalizes the probability so that it is in the range between 0 and 1.The pheromone concentration can change with time due to the evaporation of pheromone. Furthermore, the advantage of pheromone evaporation is that the system could avoid being trapped in local optima. If there is no evaporation, then the path randomly chosen by the first ants will become the preferred path as the attraction of other ants by their pheromone. For a constant rate of pheromone decay or evaporation, the pheromone concentration usually varies with time exponentiallywhere is the initial concentration of pheromone and t is time. If , then we have . For the unitary time increment , the evaporation can beapproximated by . Therefore, we have the simplified pheromone update formula:where is the rate of pheromone evaporation. The increment is the amount of pheromone deposited at time t along route to when an ant travels a distance . Usually . If there are no ants on a route, then the pheromone deposit is zero.There are other variations to these basic procedures. A possible acceleration scheme is to use some bounds of the pheromone concentration and only the ants with the current global best solution(s) are allowed to deposit pheromone. In addition, certain ranking of solution fitness can also be used. These are hot topics of current research.3.3 Double Bridge ProblemA standard test problem for ant colony optimization is the simplest double bridge problem with two branches (see Fig. 3.2) where route (2) is shorter than route (1). The angles of these two routes are equal at both point A and pointB so that the ants have equal chance (or 50-50 probability) of choosing each route randomly at the initial stage at point A.Initially, fifty percent of the ants would go along the longer route (1) and the pheromone evaporates at a constant rate, but the pheromone concentration will become smaller as route (1) is longer and thus takes more time to travel through. Conversely, the pheromone concentration on the shorter route will increase steadily. After some iterations, almost all the ants will move along the shorter route. Figure 3.3 shows the initial snapshot of 10 ants (5 on each route initially) and the snapshot after 5 iterations (or equivalent to 50 ants have moved along this section). Well, there are 11 ants, and one has not decided which route to follow as it just comes near to the entrance.Almost all the ants (well, about 90% in this case) move along the shorter route.Here we only use two routes at the node, it is straightforward to extend it to the multiple routes at a node. It is expected that only the shortest route will be chosen ultimately. As any complex network system is always made of individual nodes, this algorithms can be extended to solve complex routing problems reasonably efficiently. In fact, the ant colony algorithms have been successfully applied to the Internet routing problem, the travelling salesman problem, combinatorial optimization problems, and other NP-hard problems.3.4 Virtual Ant AlgorithmAs we know that ant colony optimization has successfully solved NP-hard problems such asthe travelling salesman problem, it can also be extended to solve the standard optimization problems of multimodal functions. The only problem now is to figure out how the ants will move on an n-dimensional hyper-surface. For simplicity, we will discuss the 2-D case which can easily be extended to higher dimensions. On a 2D landscape, ants can move in any direction or , but this will cause some problems. How to update the pheromone at a particular point as there are infinite number of points. One solution is to track the history of each ant moves and record the locations consecutively, and the other approach is to use a moving neighbourhood or window. The ants ‘smell’ the pheromone concentration of their neighbourhood at any particular location.In addition, we can limit the number of directions the ants can move by quantizing the directions. For example, ants are only allowed to move left and right, and up and down (only 4 directions). We will use this quantized approach here, which will make the implementation much simpler. Furthermore, the objective function or landscape can be encoded into virtual food so that ants will move to the best locations where the best food sources are. This will make the search process even more simpler. This simplified algorithm is called Virtual Ant Algorithm (VAA) developed by Xin-She Yang and his colleagues in 2006, which has been successfully applied to topological optimization problems in engineering.The following Keane function with multiple peaks is a standard test functionThis function without any constraint is symmetric and has two highest peaks at (0, 1.39325) and (1.39325, 0). To make the problem harder, it is usually optimized under two constraints:This makes the optimization difficult because it is now nearly symmetric about x = y and the peaks occur in pairs where one is higher than the other. In addition, the true maximum is, which is defined by a constraint boundary.Figure 3.4 shows the surface variations of the multi-peaked function. If we use 50 roaming ants and let them move around for 25 iterations, then the pheromone concentrations (also equivalent to the paths of ants) are displayed in Fig. 3.4. We can see that the highest pheromoneconcentration within the constraint boundary corresponds to the optimal solution.It is worth pointing out that ant colony algorithms are the right tool for combinatorial and discrete optimization. They have the advantages over other stochastic algorithms such as genetic algorithms and simulated annealing in dealing with dynamical network routing problems.For continuous decision variables, its performance is still under active research. For the present example, it took about 1500 evaluations of the objective function so as to find the global optima. This is not as efficient as other metaheuristic methods, especially comparing with particle swarm optimization. This is partly because the handling of the pheromone takes time. Is it possible to eliminate the pheromone and just use the roaming ants? The answer is yes. Particle swarm optimization is just the right kind of algorithm for such further modifications which will be discussed later in detail.第二部分中文翻译第二章遗传算法2.1 引言遗传算法是由John Holland和他的同事于二十世纪六七十年代提出的基于查尔斯·达尔文的自然选择学说而发展的一种生物进化的抽象模型。

Born on May 12, 1926 in Bedford Indiana. Graduated from Purdue University in 1949, recieved bachelor degree in Chemical Engineering. Entered Columbia University in 1951 In 1955, graduated from CU,and recieved his PHD. 1956 -- 1958, worked in Stanford University, Chicago University . 1959 -- 1973, tought at Johns Hopkins University in 1973，return to the University of Chicago, and directed the NORC (National Opinion Research Center) In 1992, elected as chairman of the ASA In 1995, died.
科尔曼的方法论与理论倾向
理性行动理论是以“理性人”为出发点的，在这一假设 下，行动者的行动原则可以表述为“最大限度地获取效 益”。 科尔曼认为选择这样的行为假设，一是为了提高理论的 预测能力，二是有利于保持理论的简洁。
科尔曼的方法论与理论倾向
（2）理性行动
理性行动是为达到一定目的而通过人际交往或社会交换 所表现出来的社会性行动，这种行动需要理性地考虑（或 计算）对其目的有影响的各种因素。但是判断理性与非理 性不能以局外人的标准，而是要用行动者的眼光来衡量。 理性行动不包括不具有目的性的情感行动和不具有社会 性的私人行动。

Evolutionary Programming Made Faster Xin Yao,Senior Member,IEEE,Yong Liu,Student Member,IEEE,and Guangming LinAbstract—Evolutionary programming(EP)has been applied with success to many numerical and combinatorial optimization problems in recent years.EP has rather slow convergence rates, however,on some function optimization problems.In this paper, a“fast EP”(FEP)is proposed which uses a Cauchy instead of Gaussian mutation as the primary search operator.The re-lationship between FEP and classical EP(CEP)is similar to that between fast simulated annealing and the classical version. Both analytical and empirical studies have been carried out to evaluate the performance of FEP and CEP for different function optimization problems.This paper shows that FEP is very good at search in a large neighborhood while CEP is better at search in a small local neighborhood.For a suite of23benchmark problems,FEP performs much better than CEP for multimodal functions with many local minima while being comparable to CEP in performance for unimodal and multimodal functions with only a few local minima.This paper also shows the relationship between the search step size and the probability offinding a global optimum and thus explains why FEP performs better than CEP on some functions but not on others.In addition,the importance of the neighborhood size and its relationship to the probability of finding a near-optimum is investigated.Based on these analyses, an improved FEP(IFEP)is proposed and tested empirically. This technique mixes different search operators(mutations).The experimental results show that IFEP performs better than or as well as the better of FEP and CEP for most benchmark problems tested.Index Terms—Cauchy mutations,evolutionary programming, mixing operators.I.I NTRODUCTIONA LTHOUGH evolutionary programming(EP)wasfirstproposed as an approach to artificial intelligence[1],it has been recently applied with success to many numerical and combinatorial optimization problems[2]–[4].Optimization by EP can be summarized into two major steps:1)mutate the solutions in the current population;2)select the next generation from the mutated and thecurrent solutions.These two steps can be regarded as a population-based version of the classical generate-and-test method[5],where mutation isManuscript received October30,1996;revised February3,1998,August 14,1998,and January7,1999.This work was supported in part by the Australian Research Council through its small grant scheme and by a special research grant from the University College,UNSW,ADFA.X.Yao was with the Computational Intelligence Group,School of Computer Science,University College,The University of New South Wales,Australian Defence Force Academy,Canberra,ACT,Australia2600.He is now with the School of Computer Science,University of Birmingham,Birmingham B15 2TT U.K.(e-mail:X.Yao@).Y.Liu and G.Lin are with the Computational Intelligence Group,School of Computer Science,University College,The University of New South Wales, Australian Defence Force Academy,Canberra,ACT,Australia2600(e-mail: liuy@.au;glin@.au).Publisher Item Identifier S1089-778X(99)ed to generate new solutions(offspring)and selection is used to test which of the newly generated solutions should survive to the next generation.Formulating EP as a special case of the generate-and-test method establishes a bridge between EP and other search algorithms,such as evolution strategies,genetic algorithms,simulated annealing(SA),tabu search(TS),and others,and thus facilitates cross-fertilization among different research areas.One disadvantage of EP in solving some of the multimodal optimization problems is its slow convergence to a good near-optimum(e.g.,paper and the CEP used to solve it.The CEP algorithm given follows suggestions from Fogel[3],[6]and B¨a ck and Schwefel [7].Section III describes the FEP and its implementation. Section IV gives the23functions used in our studies.Section V presents the experimental results and discussions on FEP and CEP.Section VI investigates FEP with different scale parameters for its Cauchy mutation.Section VII analyzes FEP and CEP and explains the performance difference between FEP and CEP in depth.Based on such analyses,an improved FEP(IFEP)is proposed and tested in Section VIII.Finally, Section IX concludes with some remarks and future research directions.II.F UNCTION O PTIMIZATION BYC LASSICAL E VOLUTIONARY P ROGRAMMINGA global minimization problem can be formalized as apairis a bounded setonsuchthat.More specifically,it is required tofindandoes not need to be continuous but it must bebounded.This paper only considers unconstrained functionoptimization.Fogel[3],[8]and B¨a ck and Schwefel[7]have indicatedthat CEP with self-adaptive mutation usually performs betterthan CEP without self-adaptive mutation for the functions theytested.Hence the CEP with self-adaptive mutation will beinvestigated in this paper.According to the description byB¨a ck and Schwefel[7],the CEP is implemented as followsin this study.11)Generate the initial populationof.Each individual is taken as a pair of real-valuedvectors,,where,of the population based on the objectivefunction,.3)Eachparent,creates a singleoffspring-thcomponent of thevectors,respectively..Thefactorsand[7],[6].1A recent study by Gehlhaar and Fogel[9]showed that swapping the orderof(1)and(2)may improve CEP’s performance.4)Calculate thefitness of eachoffspring.5)Conduct pairwise comparison over the union of parentsandoffspring.Foreachindividual,individuals out ofand,that have the most wins to be parentsof the next generation.7)Stop if the halting criterion is satisfied;otherwise,resembles that of the Gaussian densityfunction but approaches the axis so slowly that an expectationdoes not exist.As a result,the variance of the Cauchydistribution is infinite.Fig.1shows the difference betweenCauchy and Gaussian functions by plotting them in the samescale.The FEP studied in this paper is exactly the same as theCEP described in Section II except for(1)which is replacedby the following[11]and is generated anew for each valueofparison between Cauchy and Gaussian density functions.IV.B ENCHMARK F UNCTIONSTwenty-three benchmark functions [2],[7],[12],[13]were used in our experimental studies.This number is larger than that offered in many other empirical study papers.This is necessary,however,since the aim here is not to show FEP is better or worse than CEP,but to find out when FEP is better (or worse)than CEP and why.Wolpert and Macready [14],[15]have shown that under certain assumptions no single search algorithm is best on average for all problems.If the number of test problems is small,it would be very difficult to make a generalized ing too small a test set also has the potential risk that the algorithm is biased (optimized)toward the chosen problems,while such bias might not be useful for other problems of interest.The 23benchmark functions are given in Table I.A more detailed description of each function is given in the Appendix.Functionsare high-dimensional problems.Functions aremultimodal functions where the number of local minima increases exponentially with the problem dimension [12],[13].They appear to be the most difficult class of problems for manyoptimization algorithms (including EP).Functions–are low-dimensional functions which have only a few local minima [12].For unimodal functions,the convergence rates of FEP and CEP are more interesting than the final results of optimization as there are other methods which are specifically designed to optimize unimodal functions.For multimodal functions,the final results are much more important since they reflect an algorithm’s ability of escaping from poor local optima and locating a good near-global optimum.V.E XPERIMENTAL S TUDIESA.Experimental SetupIn all experiments,the same self-adaptive method [i.e.,(2)],the same populationsize,and the sameinitial population were used for both CEP and FEP.These parameters follow the suggestions from B¨a ck and Schwefel [7]and Fogel [2].The initial population was generated uniformly at random in the range as specified in Table I.B.Unimodal FunctionsThe first set of experiments was aimed to compare the convergence rate of CEP and FEP forfunctionsTABLE IT HE23B ENCHMARK F UNCTIONS U SED IN O UR E XPERIMENTAL S TUDY,W HERE n I S THE D IMENSION OF THE F UNCTION,f minI S THE M INIMUM V ALUE OF THE F UNCTION,AND S R n.A D ETAILED D ESCRIPTION OF A LL F UNCTIONS I S G IVEN IN THE A PPENDIXTABLE IIC OMPARISON B ETWEEN CEP AND FEP ON f1–f7.A LL R ESULTS H A VE B EEN A VERAGED OVER50R UNS,W HERE“M EAN B EST”I NDICATES THEM EAN B EST F UNCTION V ALUES F OUND IN THE L AST G ENERATION,AND“S TD D EV”S TANDS FOR THE S TANDARD D EVIATIONof the global optimum.CEP is capable of maintaining itsnearly constant convergence rate because its search is muchmore localized than FEP.The different behavior of CEP andFEP on(a)(b)parison between CEP and FEP on f1–f4.The vertical axis is the function value,and the horizontal axis is the number of generations. The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best results,and(b)shows the average results.Both were averaged over50runs.(a)(b)parison between CEP and FEP on f 5–f 7.The vertical axis is the function value,and the horizontal axis is the number of generations.The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best results,and (b)shows average results.Both were averaged over 50runs.generating long jumps than CEP.Such long jumps enable FEP to move from one plateau to a lower one with relative ease.The rapid convergence of FEP shown in Fig.3supports our explanations.C.Multimodal Functions1)Multimodal Functions with Many Local Min-ima:Multimodal functions having many local minimaare often regarded as being difficult tooptimize.are such functions where the number of local minima increases exponentially as the dimension of the function increases.Fig.4shows the two-dimensional versionofwere all set to 30in our ex-periments.Table III summarizes the final results of CEP and FEP.It is obvious that FEP performs significantly better than CEP consistently for these functions.CEP appeared to become trapped in a poor local optimum and unable to escape from it due to its smaller probability of making long jumps.According to the figures we plotted to observe the evolutionary process,CEP fell into a poor local optimum quite early in a run whileFig.4.The two-dimensional version of f 8.TABLE IIIC OMPARISON B ETWEEN CEP AND FEP ON f 8–f 13.T HE R ESULTS A RE A VERAGED OVER 50R UNS ,W HERE “M EAN B EST ”I NDICATESTHEM EAN B EST F UNCTION V ALUES F OUND IN THE L AST G ENERATION AND “S TD D EV ”S TANDS FOR THE S TANDARD DEVIATIONTABLE IVC OMPARISON B ETWEEN CEP AND FEP ON f 14–f 23.T HE R ESULTS A RE A VERAGED OVER 50R UNS ,W HERE “M EAN B EST ”I NDICATESTHEM EAN B EST F UNCTION V ALUES F OUND IN THE L AST G ENERATION AND “S TD D EV ”S TANDS FOR THE S TANDARD DEVIATIONFEP was able to improve its solution steadily for a long time.FEP appeared to converge at least at a linear rate with respect to the number of generations.An exponential convergence rate was observed for some problems.2)Multimodal Functions with Only a Few Local Minima:To evaluate FEP more fully,additional multimodal benchmarkfunctions were also included in our experiments,i.e.,–,where the number of local minima for each function and thedimension of the function are small.Table IV summarizes the results averaged over 50runs.Interestingly,quite different results have been observed forfunctions–.For six(i.e.,–)out of ten functions,no statistically significant difference was found between FEP and CEP.In fact,FEP performed exactly the same as CEP forTABLE VC OMPARISON B ETWEEN CEP AND FEP ON f 8TO f 13WITH n =5.T HE R ESULTS A RE A VERAGED OVER 50R UNS ,W HERE “M EAN B EST ”I NDICATES THE M EAN B ESTF UNCTION V ALUES F OUND IN THE L ASTG ENERATION AND “S TD D EV ”S TANDS FOR THE S TANDARD DEVIATIONand .For the four functions where there was statistically significant difference between FEP and CEP,FEP performedbetterfor,but was outperformed by CEPfor–.The consistent superiority of FEP over CEP forfunctions was not observed here.The major difference betweenfunctionsand–is thatfunctions–appear to be simplerthandue to their low dimensionalities and a smaller number of local minima.To find out whether or not the dimensionality of functions plays a significant role in deciding FEP’s and CEP’s behavior,another set of experiments on thelow-dimensionalwas carried out.The resultsaveraged over 50runs are given in Table V.Very similar results to the previous ones onfunctionswere obtained despite the large difference in the dimensionality of functions.FEP still outperforms CEP significantly evenwhen the dimensionality offunctionsislow inits Cauchy mutation.This value was used for its simplicity.To examine the impact of differentvalues for the Cauchy mutation.Seven benchmark functions from the three different groups in Table I were used in these experiments.The setup of these experiments is exactly the same as before.Table VI shows the average results over 50independent runs of FEP for different parameters.These results showthatis problemdependent.As analyzed later in Section VII-A,the optimalfor a given problem.A good approach toTABLE VIT HE M EAN B EST S OLUTIONS F OUND BY FEP U SING D IFFERENT S CALE P ARAMETER t IN THE C AUCHY M UTATION FOR F UNCTIONS f 1(1500);f 2(2000);f 10(1500);f 11(2000);f 21(100);f 22(100);AND f 23(100).THE V ALUES IN “()”I NDICATE THE N UMBER OF G ENERATIONS U SED INFEP.A LL R ESULTS H A VE B EEN A VERAGED OVER 50RUNSdeal with this issue is to use self-adaptation so thatvalues in a population so that the whole popu-lation can search both globally and locally.The percentage of each type of Cauchy mutation will be self-adaptive,rather than fixed.Hence the population may emphasize either global or local search depending on different stages in the evolutionary process.VII.A NALYSIS OF F AST AND C LASSICALE VOLUTIONARY P ROGRAMMINGIt has been pointed out in Section III that Cauchy mutation has a higher probability of making long jumps than Gaussian mutation due to its long flat tails shown in Fig.1.In fact,the likelihood of a Cauchy mutation generating a larger jump than a Gaussian mutation can be estimated by a simple heuristic argument.Fig.5.Evolutionary search as neighborhood search,where x3is the global optimum and >0is the neighborhood size. is a small positive number(0< <2 ).It is well known thatifthen(i.e.,It is obvious that Gaussian mutation is much more localizedthan Cauchy mutation.Similar results can be obtained for Gaussian distributionwithexpectationandvarianceis often regardedas the step size of the Gaussian mutation.Fig.5illustrates thesituation.Thederivative can be used toevaluate the impactof.Accordingto the mean value theorem for definite integrals[17,p.322],there exists anumber suchthat(7)That is,thelarger willbe,ifis,thesmaller will be.Similar analysis can be carried out for Cauchy mutationin FEP.Denote the Cauchy distribution defined by(3)as.Then wehavemay not be the same as that in(6)and(7).It is obviousthat(9)That is,thelarger will be,ifis,thesmaller will be.Since could be regarded as search step sizes forGaussian and Cauchy mutations,the above analyses show thata large step size is beneficial(i.e.,increases the probabilityoffinding a near-optimal solution)only when the distancebetween the neighborhoodofand.The analytical results explain why FEP achieved betterresults than CEP for most of the benchmark problems wetested,because the initial population was generated uniformlyat random in a relatively large space and was far away from theglobal optimum on average.Cauchy mutation is more likely togenerate larger jumps than Gaussian mutation and thus betterin such cases.FEP would be less effective than CEP,however,near the small neighborhood of the global optimum becauseGaussian mutation’s step size is smaller(smaller is better inthis case).The experimental results onfunctionsvalue for its Cauchy mutation would perform better wheneverCEP outperforms FEPwithfor a problem,it implies that this FEP’s search stepsize may be too large.In this case,using a Cauchy mutationwith a smaller(i.e.,Shekel-5)wasused here since it appears to pose some difficulties to FEP.First we made the search points closer to the global optimumby generating the initial population uniformly at random inthe rangeof ratherthan andrepeated our previous experiments.(The global optimumofisat.)Such minor variation to the experiment isexpected to improve the performance of both CEP and FEPsince the initial search points are closer to the global optimum.Note that both Gaussian and Cauchy distributions have higherprobabilities in generating points around zero than those ingenerating points far away from zero.Thefinal experimental results averaged over50runs aregiven in Table VII.Fig.6shows the results of CEP and FEP.It is quite clear that the performance of CEP improved muchmore than that of FEP since the smaller average distancebetween search points and the global optimum favors a smallstep size.The mean best of CEP improved significantly from7.90,while that of FEP improved only from5.62.Then three more sets of experiments were conducted wherethe search space was expanded ten times,100times,and1000times,i.e.,the initial population was generated uniformly atrandom in the rangeofC OMPARISON OF CEP’S AND FEP’S F INAL R ESULTS ON f21W HEN THE I NITIAL P OPULATION I S G ENERATED U NIFORMLY AT R ANDOM IN THE R ANGE OF0 x i 10AND2:5 x i 5:5.T HE R ESULTS W ERE A VERAGED OVER50R UNS,W HERE“M EAN B EST”I NDICATES THE M EAN B EST F UNCTION V ALUESF OUND IN THE L ASTG ENERATION,AND“S TD D EV”S TANDS FOR THE S TANDARD D EVIATION.T HE N UMBER OF G ENERATIONS FOR E ACH R UN W AS100(a)(b)parison between CEP and FEP on f21when the initial population is generated uniformly at random in the range of2:5 x i 5:5.The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best result,and(b)shows the average result.Both were averaged over50runs.The horizontal axis indicates the number of generations.The vertical axis indicates the function value.space is expected to make the problem more difficult and thusmake CEP and FEP less efficient.The results of the sameexperiment averaged over50runs are shown in Table VIIIand Figs.7–9.It is interesting to note that the performance ofFEP was less affected by the larger search space than CEP.When the search space was increased todisappeared.There was no statistically significant differencebetween CEP and FEP.When the search space was increasedfurther to,FEP even outperformed CEPsignificantly.It is worth pointing out that a population size of100and the maximum number of generations of100are verysmall numbers for such a huge search space.The populationmight not have converged by the end of generation100.This,however,does not affect our conclusion.The experimentsstill show that Cauchy mutation performs much better thanGaussian mutation when the current search points are far awayfrom the global optimum.Even if’s were not multiplied by10,100,and1000,similar results can still be obtained as long as the initialpopulation was generated uniformly at random in the rangeofC OMPARISON OF CEP’S AND FEP’S F INAL R ESULTS ON f21W HEN THE I NITIAL P OPULATION I S G ENERATED U NIFORMLY AT R ANDOM IN THER ANGE OF0 x i 10;0 x i 100;0 x i 1000;AND0 x i 10000,AND a i’S W ERE M ULTIPLIED BY10,100,AND1000.T HE R ESULTS W ERE A VERAGED OVER50R UNS,W HERE“M EAN B EST”I NDICATES THE M EAN B EST F UNCTION V ALUES F OUND IN THEL AST G ENERATION,AND“S TD D EV”S TANDS FOR THE S TANDARD D EVIATION.T HE N UMBER OF G ENERATIONS FOR E ACH R UN W AS100.(a)(b)parison between CEP and FEP on f21when the initial population is generated uniformly at random in the range of0 x i 100and a i’s were multiplied by ten.The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best result,and(b)shows the average result.Both were averaged over50runs.The horizontal axis indicates the number of generations.The vertical axis indicates the function value.(a)(b)parison between CEP and FEP on f21when the initial population is generated uniformly at random in the range of0 x i 1000and a i’s were multiplied by100.The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best result,and(b)shows the average result.Both were averaged over50runs.The horizontal axis indicates the number of generations.The vertical axis indicates the function value.parison between CEP and FEP on f21when the initial population is generated uniformly at random in the range of0 x i 10000and a i’s were multiplied by1000.The solid lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best result,and(b)shows the average result.Both were averaged over50runs.The horizontal axis indicates the number of generations.The vertical axis indicates the function value.TABLE IXC OMPARISON OF CEP’S AND FEP’S F INAL R ESULTS ON f21W HEN THE I NITIAL P OPULATION I S G ENERATED U NIFORMLY AT R ANDOM INTHE R ANGE OF0 x i 10;0 x i 100;0 x i 1000;and0 x i 10000.a i’S W ERE U NCHANGED.T HE R ESULTS W ERE A VERAGED OVER50R UNS,W HERE“M EAN B EST”I NDICATES THE M EAN B EST F UNCTION V ALUES F OUND IN THE L ASTG ENERATION,AND“S TD D EV”S TANDS FOR THE S TANDARD D EVIATION.T HE N UMBER OF G ENERATIONS FOR E ACH R UN W AS100and the time used tofind the solution?This issue can be approached from the point of view of neighborhood size,i.e.,on the probability of generating a near-optimum in that neighborhood can be worked out.(The probability offinding a near-optimum would be the same as that of generating it when the elitism is used.)Although not an exact answer to the issue,the following analysis does provide some insights into such impact.Similar to the analysis in Section VII-A7,the following is true according to the mean value theorem for definite integrals[17,p.322]:forThat is,for)is governed by thetermThatis,grows exponentially fasteras increases.TABLE XC OMPARISON A MONG IFEP,FEP,AND CEP ON F UNCTIONS f1;f2;f10;f11;f21;f22;AND f23.A LL R ESULTS H A VE B EENA VERAGED OVER50R UNS,W HERE“M EANB EST”I NDICATES THE M EAN B EST F UNCTION V ALUES F OUND IN THE L AST GENERATIONA similar analysis can be carried out for Cauchy mutationusing its density function,i.e.,(3).Let the density functionbe.ForHence the probability of generating a near-optimum in theneighborhood always increases as the neighborhood size in-creases.While this conclusion is quite straightforward,it isinteresting to note that the rate of increase in the probabilitydiffers significantly between Gaussian and Cauchy mutationsince.VIII.A N I MPROVED F AST E VOLUTIONARY P ROGRAMMINGThe previous analyses show the benefits of FEP and CEPin different situations.Generally,Cauchy mutation performsbetter when the current search point is far away from theglobal minimum,while Gaussian mutation is better atfindinga local optimum in a good region.It would be ideal ifCauchy mutation is used when search points are far away fromthe global optimum and Gaussian mutation is adopted whensearch points are in the neighborhood of the global optimum.Unfortunately,the global optimum is usually unknown inpractice,making the ideal switch from Cauchy to Gaussianmutation very difficult.Self-adaptive Gaussian mutation[7],[2],[8]is an excellent technique to partially address theproblem.That is,the evolutionary algorithm itself will learnwhen to“switch”from one step size to another.There is roomfor further improvement,however,to self-adaptive algorithmslike CEP or even FEP.This paper proposes an improved FEP(IFEP)based onmixing(rather than switching)different mutation operators.The idea is to mix different search biases of Cauchy andGaussian mutations.The importance of search biases has beenpointed out by some earlier studies[18,pp.375–376].Theimplementation of IFEP is very simple.It differs from FEPand CEP only in Step3of the algorithm described in SectionII.Instead of using(1)(for CEP)or(4)(for FEP)alone,IFEPgenerates two offspring from each parent,one by Cauchy mu-tation and the other by Gaussian.The better one is then chosenas the offspring.The rest of the algorithm is exactly the sameas FEP and CEP.Chellapilla[19]has recently presented somemore results on comparing different mutation operators in EP.A.Experimental StudiesTo carry out a fair comparison among IFEP,FEP,andCEP,the population size of IFEP was reduced to half ofthat of FEP or CEP in all the following experiments,sinceeach individual in IFEP generates two offspring.ReducingIFEP’s population size by half,however,actually puts IFEPat a slight disadvantage because it does not double the timefor any operators(such as selection)other than mutations.Nevertheless,such comparison offers a good and simplecompromise.IFEP was tested in the same experimental setup as before.For the sake of clarity and brevity,only some representativefunctions(out of23)from each group were tested.Functionsand are multimodal functions with many local minima.Functions–are multimodal functions with only a fewlocal minima and are particularly challenging to FEP.Table Xsummarizes thefinal results of IFEP in comparison with FEPand CEP.Figs.10and11show the results of IFEP,FEP,andCEP.B.DiscussionsIt is very clear from Table X that IFEP has improved FEP’sperformance significantly for all test functions exceptfor.Even in the caseof,IFEP is better than FEP for25out of50runs.In other words,IFEP’s performance is still rather closeto FEP’s and certainly better than CEP’s(35out of50runs)on.These results show that IFEP continues to perform(a)(b)parison among IFEP,FEP,and CEP on functions f 1;f 2;f 10;and f 11.The vertical axis is the function value,and the horizontal axis is the number of generations.The solid lines indicate the results of IFEP.The dashed lines indicate the results of FEP.The dotted lines indicate the results of CEP.(a)shows the best results,and (b)shows the average results.All were averaged over 50runs.at least as well as FEP on multimodal functions with many minima and also performs very well on unimodal functions and multimodal functions with only a few local minima with which FEP has difficulty handling.IFEP achieved performance similar to CEP’s on these functions.For the two unimodal functions where FEP is outperformed by CEP significantly,IFEP performs better than CEPon–,the difference be-tween IFEP and CEP is much smaller than that between FEP and CEP.IFEP has improved FEP’s performance significantly。