Ch7_Fuzzy evaluationary algorithms1.pptx

It is about fuzzy algorithms

1. Fuzzy Evolutionary Algorithms By: Shimaa Gamal

2. Contents Introduction Fuzzy Control of Evolution Fuzzy Government Architecture of an Adaptive Evolutionary Algorithm Using Expert Knowledge Automatic learning Co-evolution with a Fuzzy Government Evolutionary Algorithms with Fuzzy Components Fuzzy Fitness Recombination Operators Based on Fuzzy Connectives Soft Genetic Operators Recombination Using Templates Representation

3. 1. Introduction Synergy between evolutionary algorithms and fuzzy logic can occur in three complementary forms The most obvious form exploits the optimum searching ability of evolutionary algorithms to synthesize and optimize fuzzy systems . (chapter 5) The second possibility, evolutionary algorithms are relatively easy to implement and in general their performance tends to be rather satisfactory in comparison with the small amount of knowledge about the problem they need in order to work; however, typically they would require some sort of human supervision during their use as practical tools . The idea is then to use a fuzzy knowledge base (or fuzzy government) to detect the emergence of a solution , dynamically tune algorithm parameters, and monitor the evolutionary process to avoid undesired behaviors such as premature convergence . A third option is to embed fuzziness into the evolutionary algorithm itself .

4. 2. Fuzzy Control of Evolution The SETTING of evolutionary algorithm parameters is a key factor in the determination of the exploitation versus exploration trade-off. The effects of poor settings can range from a slow-down of the search process to premature convergence. However, finding robust control parameters valid for any problem is difficult and perhaps even impossible . Furthermore , different settings of control parameters may be optimal in different moments of the same evolutionary process . For this reason, an evolutionary algorithm typically requires some sort of human supervision during its use to solve real world problems

5. A human supervisor can observe the process and tweak parameters as evolution proceeds until a satisfactory behavior is obtained. Finally , there is the problem of deciding when to stop the search and be content with the solution produced by the evolutionary process. This is in general the result of a trade-off between solution quality and time constraints and another area of discretionary human intervention . The alternative to human supervision is an adaptive evolutionary algorithm , capable of adjusting its own control parameters during evolution to attain the best performance. Starting from the observation that the evolutionary process is a complex system with non-linear behavior, it seems sensible to take advantage of a powerful technique such as fuzzy control to manage it. 2. Fuzzy Control of Evolution (cont.)

6. 2.1 Fuzzy Government This name can be given to the collection of fuzzy rules and routines in charge of controlling the evolution of a population, detecting the emergence of a solution , tuning algorithm parameters "on flight ", and avoiding undesirable behaviors such as premature convergence . A fuzzy controller implements an expert operator's approximate reasoning process in the selection of a control action. The fuzzy government dynamically adjusts selected control parameters or genetic operators during operation of an evolutionary algorithm to offer the most appropriate exploration and exploitation behavior . the fuzzy government operates on the population of individuals of an evolutionary algorithm so that the most favorable conditions for the improvement of their fitness are always maintained .

7. 2.2 Architecture of an Adaptive Evolutionary Algorithm

8. 2.2 Architecture of an Adaptive Evolutionary Algorithm (cont.) The idea is to use a fuzzy rule-based controller, the fuzzy government , whose inputs are statistics of the evolutionary algorithm and whose outputs are the control parameters of the same algorithm. Statistics are gathered from the evolutionary algorithm at a given sampling rate, for instance once in r generations, but anyway not more than once per generation, and they are sent to the fuzzy government. The fuzzy government performs one inference, producing new values for all control parameters. These are updated with the new values and control is given back to the evolutionary algorithm.

9. 2.2.1 Evolutionary Algorithm Statistics It can be divided into two classes : genotypic statistics, which summarize aspects related to the genotypes of individuals in a population, regardless of their meaning when decoded, and phenotypic statistics, which concern properties of individual performance for the problem at hand, or fitness. Diversity measures constitute a general kind of genotypic statistics. They rely on the definition of a (fuzzy) similarity measure where and K; are two genotypes . Examples of phenotypic statistics are: phenotypic diversity measures ( such as fitness range, best/average fitness ratio, or fitness variance ), maximum, average, and minimum fitness.  

10. 2.2.2 Control Parameters Outputs of the fuzzy government may be directly control parameter values or changes in these parameters It may be the usual parameters of an evolutionary algorithm, such as population size, mutation and crossover rate, selection pressure ( if applicable ), or other parameters specific to a particular application . One parameter could also include indicators for the user . These "improper" parameters tell the user of the evolutionary algorithm something about the state of optimization. For instance , one such indicator could be the degree to which a satisfactory solution has been obtained.

11. 2.2.3 The Fuzzy-Rule-Base Each input and output variable is to be associated with a set of linguistic values, defined by membership functions. The fuzzy rules in the fuzzy government are defined in terms of such linguistic values . Different approaches to the construction of a suitable fuzzy-rule-base are found: study the behavior of the evolutionary algorithm and gain some expertise about its dynamics . automatic learning of the fuzzy rules, membership functions, or both.

12. 2.3 Using Expert Knowledge a fuzzy government is used to solve two problems evolutionary algorithms may incur: very slow convergence speed and premature convergence. These problems may be due to at least three factors : P arameters are not well chosen initially for a given task; Parameters do not change through a run, even though evolutionary conditions may vary; Interaction between distinct parameters is complex and difficult to understand . A fuzzy government can help in all three situations: it can be used to choose control parameters before starting the algorithm, to adjust them on-line to dynamically adapt to changing conditions, and to assist the user in assessing, designing, implementing, and validating an evolutionary algorithm for a given task.

13. Population size Generation Small Medium Large short Medium small small medium large large medium long Very large Very large large Population size Generation Small Medium Large short Medium small small medium large large medium long Very large Very large large Population size Generation Small Medium Large short large medium small medium medium small Very small long small Very small Very small Population size Generation Small Medium Large short large medium small medium medium small Very small long small Very small Very small These tables show two sets of rules to dynamically adjust the crossover and mutation rates of a genetic algorithm.

14. Visualization is a central issue in studying the behavior of an evolutionary algorithm , mainly because of the huge quantity of data and the need to provide them in a concise, clear, and readable form. Besides, the fact should be stressed that almost everything one learns on how an evolutionary algorithm works, is learned through the inspection of the automatically generated execution reports of a large number of test runs. For this reason a comprehensive yet terse visualization and report generation is a vital step toward the implementation of a fuzzy government. The quantity of data associated to each generation complicates the development of a good report-generating function. Because it is impossible to visualize all the data, a small but significant subset thereof must be selected, that captures the situation at a given time. The size of this data set is constrained by the need to keep the computational cost of the report-generating function below a small percentage of the overall cost.

15. 2.4 Automatic learning It was proposed by Lee and Takagi to find out fuzzy rule bases along with the appropriate definition of the relevant membership functions . As an initial demonstration of their method, Lee and Takagi used a fuzzy system taking three input variables (statistics) and producing three output variables (parameters ). The three input variables are the ratio between the average fitness and the best fitness , the ratio between the worst fitness and the average fitness , the change in fitness since the last control action. The evolutionary algorithm parameters under control are population size , mutation rate, and crossover rate. These parameters are not acted upon directly; rather, the output variables of the fuzzy government are the changes in these parameters Experiments showed that an evolutionary algorithm for the design of fuzzy controllers for the inverted pendulum using the fuzzy government obtained by their method exhibited much better performance than a simple static algorithm.

16. 2.5 Co-evolution with a Fuzzy Government It is an alternative approach to writing a fuzzy government or learning it once and for all using a set of test problems as a benchmark for evolutionary algorithm performance. During the application of the genetic operator being controlled, a random assignment is made between each member of the population of fuzzy behaviors and sets of parents. Then , the genetic operator is applied to each set using the control parameter value obtained by applying a fuzzy government using the rule represented by the corresponding fuzzy behavior. The population of fuzzy behaviors will undergo evolution, through the effects of its own selection process as well as mutation and crossover . The fitness of the fuzzy behaviors will depend on the effectiveness of the genetic operators they controlled. Operator effectiveness may be measured according to different criteria, such as whether the operator generated offspring fitter than their parents , or introduced diversity in the population.

17. 3 Evolutionary Algorithms with Fuzzy Components 3.1 Fuzzy Fitness In all cases, a better fitness estimate can be obtained at the cost of repeating its calculation as many times as desired. However , it might be argued that knowing the fitness of an individual beyond a certain precision is useless, given the random nature of evolutionary algorithms . In other words, what is the point of knowing the fitness of an individual up to 8 decimal digits if that fitness is used by a stochastic selection operator ? A sensible approach to spare computational resources is to treat fitness imprecision with the instruments provided by fuzzy set theory , (like in chapter 3)

18. An example of how a fuzzy fitness is the following , based on a control problem, where pairs of controllers play competitions which can end up in a success of either competitor, in a tie, or in a failure of either competitor: in such setting, a fuzzy estimate of the fitness of individuals m ay be given based on the recorded outcomes of competitions . This estimate is based on three quantities: the number c of competitions undergone by an individual, the number w of its wins, and the number s of successes . The more competitions an individual has gone through, the less fuzzy its fitness will be.

19. The membership function of fitness, for a given individual, is defined as: Where is a normalization factor and a = w+s , b= c-s. The mode of the membership function, where its value is one, is An intersecting predicate defined on pairs of individuals is their fitness overlap: i.e the maximum of the intersection of their fitness. This gives the degree to which and have the same fitness.  

20. The fuzzy fitness is employed to avoid carrying out useless competitions: when the fitness overlap of the two opponents is below a certain threshold, the one with the highest mode is awarded the match. Fuzzy fitnesses of individuals in the population are aggregated to yield statistics such as minimum, average, and maximum fitness for use by the fuzzy government.

21. 3.2 Recombination Operators Based on Fuzzy Connectives The observation that recombination plays a central role in the exploration / exploitation balance, which is essential to evolutionary algorithms , brings the question whether it is possible to design recombination operators allowing this balance to be tuned . At least for real-coded evolutionary algorithms, a solution consists in defining a recombination operator based on fuzzy connectives , those in turn based on triangular norms and co-norms and average functions.

22. Assume that x = (Xl, ... , XN) and y = (YI, ... , YN) are two real coded genomes to which recombination has to be applied . The gene in each locus i may have alleles comprised within a given interval , . Assuming without loss of generality that, for a given i , Xi < Yi, we observe that the space of alleles for that gene can be partitioned into three intervals: [ ai , Xi], [Xi, Yi], and [Yi, bi ]. The middle interval can be classified as an exploitation interval, whereas the external intervals can be thought of as exploration zones.  

23. Based on this idea, three functions can be defined to be used by the recombination operator that map the alleles in the two parents in the allele in a child, in such a way that the result falls respectively below , in the middle of, or above the parent alleles . Let us call these three families of functions L, M, and R. L functions have just the properties of triangular norms, while R functions have the properties of triangular co-norms. M functions are so-called averaging functions. three recombination operators can be defined based on these functions: L-, M-, and R- recombination, featuring different exploration/exploitation behaviors. By mixing these three recombination operators with different ( possibly dynamic) probabilities, one can achieve a fine control over the exploration/exploitation behavior of the whole evolutionary algorithm.

24. 3.3 Soft Genetic Operators Soft modal recombination and mutation operators for real-valued encodings , based on triangular probability distributions , used in the breeder genetic algorithm

25. 3.3.1 Soft Modal Recombination Operator This recombination operator, is also called fuzzy recombination for being inspired by fuzzy set theory. Given two parent chromosomes ( Xl, ... ,XN) and (YI, ... ,YN), the probability that the offspring have value Zi , for i = 1, ... ,N, has a bimodal distribution , Where equ.7.9 With d 1/2  

26. 3.3.2 Soft Modal Mutation Given a real-valued allele X for a gene defined in [a, b] to be mutated , soft modal mutation generates a new allele , where has a distribution p( ) randomly chosen from the family Where A<< b-a is the amplitude of mutation, > 1 called the base of the mutation and the lower limit of the relative mutation change and defined in a way analogous to equation 7.9  

27. 3.4 Recombination Using Templates When genotypes consist of strings of real numbers in the interval [ 0,1], representing fuzzy sets, a fuzzy recombination operator can be defined which makes use of templates. A genotype in binary coded genetic algorithms can be represented with the set of all loci where the alleles are 1, for example a chromosome would be described by set Recombination in binary-coded genetic algorithms could then be defined in terms of these sets of 1-1oci : far instance, one-point crossover between and k at position I, giving two offspring ,  

28. might be described in terms of the associated sets , by means of the set of loci where material is exchanged between the parents, the recombination template, as follows : Where is the complement of T in the universe of all possible loci . Having described a recombination operator this way, one can generalize by letting the template T be a fuzzy set.  

29. 3.5 Representation each feature of a solution to the object problem is determined by a number of associated fuzzy decision variables in [ 0,1 ]. when tackling continuous parameter optimization, each problem parameter might have m fuzzy decision variables associated with it. For e ach parameter , the decoding is carried out by means of a function and a linear transformation from the interval [ 0,1] to the relevant parameter domain [a, b].  

30. An example of g(.) is [ 233 ] where d is the vector of m fuzzy decision variables. When m > 1, this type of coding breaks the one-to-one correspondence between genotype and phenotype . Along with a fuzzy representation , genetic operators based on fuzzy logic can be defined Experimental evidence] suggests that the use of a fuzzy representation allows a robust behavior to be obtained, and a better performance for small-sized populations.