Evolutionary computing - soft computing

Evolutionary Computing is a research area within computer science. As the name suggest, it is a special flavour of computing, which draws inspiration from the process of natural evolution. The fundamental metaphor of evolutionary computing relates this powerful natural evolution to a particular style of problem solving – that of trial and error.

1. EVOLUTIONARY COMPUTING Submitted By: Sakshi Mahto M.Sc IV sem

2. Introduction Evolutionary Computing is a research area within computer science. As the name suggest, it is a special flavour of computing, which draws inspiration from the process of natural evolution. The fundamental metaphor of evolutionary computing relates this powerful natural evolution to a particular style of problem solving – that of trial and error. Evolutionary Computing: Why? Evolutionary processes are subjects of scientific studies where the main objective is to understand how evolution work. From the perspective of evolutionary computing Represents the possibility of performing experiments differently from traditional biology. Evolutionary computation techniques can produce highly optimized solutions in a wide range of problem settings, making them popular in computer science. Many variants and extensions exist, suited to more specific families of problems and data structures. Evolutionary computation is also sometimes used in evolutionary biology as an in silico experimental procedure to study common aspects of general evolutionary processes.

3. Flow chart of Evolutionary Computing

4. Evolutionary algorithms form a subset of evolutionary computation in that they generally only involve techniques implementing mechanisms inspired by biological evolution such as reproduction, mutation, recombination, natural selection and survival of the fittest. Candidate solutions to the optimization problem play the role of individuals in a population, and the cost function determines the environment within which the solutions "live" (see also fitness function). Evolution of the population then takes place after the repeated application of the above operators . In this process, there are two main forces that form the basis of evolutionary systems: Recombination and mutation create the necessary diversity and thereby facilitate novelty, while selection acts as a force increasing quality . Many aspects of such an evolutionary process are stochastic. Changed pieces of information due to recombination and mutation are randomly chosen. On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness have a higher chance to be selected than individuals with a lower fitness, but typically even the weak individuals have a chance to become a parent or to survive.

5. Genetic algorithms and optimization Genetic algorithms, as powerful and broadly applicable search and optimization techniques, are perhaps the most widely known types of evolutionary computation method today. In general, a genetic algorithm has five basic components, as summarized by Michalewicz . A genetic representation of solutions to the problem. A way to create an initial population of solutions. An evaluation function rating solutions in terms of their fitness. Genetic operators that alter the genetic composition of children during reproduction. Values for the parameters of genetic algorithms.

6. Flow Chart of Genetic Algorithm

7. The genetic algorithm maintains a population of individuals, say P(t), take t for generations. Each Individual represents a potential solution to the problem. Some individual undergo stochastic ( having a random probability distribution) transformation means of genetic operations to form new individuals There are two type of transformation: 1.Mutation – Which creates new individuals by making changes in a single individual. 2.Crossover – Which creates new individuals by combining parts of two individuals. New individuals called offspring C(t). A new populations is formed by selecting the more fit individuals from parent population and offspring population. The algorithim converges to the best individual, which hopefully represent an optimal or suboptimal solution to the problem.

8. Procedure: Genetic Algorithm begin t 0; initialize P(t); evaluate P(t); while (not termination condition) do begin recombine P(t) to yield C(t); evaluate C(t); select P(t + 1) from P(t) and C(t); t t + 1; end end One general principle for developing an implementation of genetic algorithms for a real-world problem is to make a good balance between exploration and exploitation of the search space .

9. The Schema Theorem The two most important theoretical foundations of Genetic Algorithm are Holland’s schema theorem and Goldberg’s building-block hypothesis. The convergence analysis of simple genetic algorithm is based on concept of schema. A schema is a bit pattern that functions as a set of binary strings. The schema theorem asserts that the proportions of the better schemata(similarly template) to the overall population increases as the generation progresses and the search converges to the best solution with respect to the optimization function. The schema theory of genetic algorithm aims to predict the expected numbers of solution in a given schema(a subset of the search space). According to schema theorem, schemata with high fitness and small defining lengths grow exponentially with time. The exact schema theorem for genetic algorithm have been derived for exactly predicting expected characteristics of the population of next generation. The schema theorem based on concept of effective fitness.

10. Here  m( H,t )  is the number of strings belonging to schema  H  at generation  t ,  f(H)  is the  observed  average fitness of schema  H and  a t  is the  observed  average fitness at generation  t . The probability of disruption  p is the probability that crossover or mutation will destroy the schema  H . where  o(H)  is the order of the schema,  l  is the length of the code, p m  is the probability of mutation and  p c is the probability of crossover. So a schema with a shorter defining length  δ (H)  is less likely to be disrupted.

11. Genetic Operators A  genetic operator  is an operator used in genetic algorithms to guide the algorithm towards a solution to a given problem. There are three main types of operators ( mutation, crossover and selection ), which must work in conjunction with one another in order for the algorithm to be successful. Genetic operators are used to create and maintain genetic diversity (mutation operator), combine existing solutions (also known as chromosomes) into new solutions (crossover) and select between solutions (selection).  Mutation (or mutation-like) operators are said to be  unary  operators, as they only operate on one chromosome at a time. In contrast, crossover operators are said to be  binary  operators, as they operate on two chromosomes at a time, combining two existing chromosomes into one new chromosome.

12. Operators Selection : Selection operators give preference to better solutions (chromosomes), allowing them to pass on their 'genes' to the next generation of the algorithm. The best solutions are determined using some form of objective function (also known as a 'fitness function' in genetic algorithms), before being passed to the crossover operator. Different methods for choosing the best solutions exist, for example, fitness proportionate selection and tournament selection. Crossover : Crossover is the process of taking more than one parent solutions (chromosomes) and producing a child solution from them. By recombining portions of good solutions, the genetic algorithm is more likely to create a better solution. The 'cut and splice crossover' and 'uniform crossover' methods. The crossover method is often chosen to closely match the chromosome's representation of the solution, this may become particularly important when variables are grouped together as building blocks, which might be disrupted by a non-respectful crossover operator.

13. Mutation: The mutation operator encourages genetic diversity amongst solutions and attempts to prevent the genetic algorithm converging to a local minimum by stopping the solutions becoming too close to one another. In mutating the current pool of solutions, a given solution may change entirely from the previous solution. By mutating the solutions, a genetic algorithm can reach an improved solution solely through the mutation operator. Again, different methods of mutation may be used; these range from a simple  bit mutation  (flipping random bits in a binary string chromosome with some low probability) to more complex mutation methods, which may replace genes in the solution with random values chosen from the uniform distribution or the Gaussian distribution. As with the crossover operator, the mutation method is usually chosen to match the representation of the solution within the chromosome. While each operator acts to improve the solutions produced by the genetic algorithm working individually, the operators must work in conjunction with each other for the algorithm to be successful in finding a good solution. Using the selection operator on its own will tend to fill the solution population with copies of the best solution from the population. If the selection and crossover operators are used without the mutation operator, the algorithm will tend to converge to a local minimum, that is, a good but sub-optimal solution to the problem.

14. Genetic Algorithms with neural networks An neural network, in general is a highly interconnected network of a large number of processing elements called neurons in an architecture inspired by the brain. An NN can be massively parallel and therefore is said exhibit parallel distributing processing. Neuro -Genetic Hybrids: Genetic algorithms offered themselves as potential candidate to neural network in 1989,1990). The integration of GA(genetic algorithms) with NN(neural network) has turned out useful(Schaffer et al., 1992). Genetic algorithms encode the parameters of NN as a string of the properties of the network, this is, chromosomes. A large population of chromosomes representing the many possible parameter sets for the given NN is generated. Combined GA-NN technology also known as ‘GANN’ have ability to locate the neighbourhood of the optimal solution . Drawbacks of GANN algorithim are: The large amount of memory required to handle and manipulate chromosomes for a given network.

15. Fuzzy-Genetic Hybrids Fuzzy systems have been integrated with GA. Kosko (1992) has shown that fuzzy systems line NN are universal approximates in the fact that they exhibit the capability to approximate general nonlinear functions to any desired degree of accuracy. When it comes to automatically identifying and building a fuzzy system, given the high degree of nonlinearity of the output, traditional linear optimization tools have several limitations. Therefore, in the framework of soft computing, genetic algorithms (GAs) and genetic programming (GP) methods have been used successfully to identify structure and parameters of fuzzy systems. Genetic algorithms for fuzzy system identification: Given the high degree of nonlinearity of the output of a fuzzy system, traditional linear optimization tools do have their limitations. Genetic algorithms have demonstrated to be a robust and very powerful tool to perform tasks such as the generation of fuzzy rule base, optimization of fuzzy rule bases, generation of membership functions, and tuning of membership functions ( Cordón et al., 2001a). All these tasks can be considered as optimization or search processes within large solution spaces (Bastian and Hayashi, 1995) (Yuan and Zhuang , 1996) ( Cordón et al., 2001)

16. Fuzzy genetic algorithm approach

17. Issues In GA There are two important issues with respect to search strategies: exploiting the best solution and exploring the search space. The genetic algorithm provide a directed random search in complex landscapes. Genetic operators perform essentially a blind search. Encoding Issue: How to encode a solution of the problem into a chromosome is a key issue when using genetic algorithms. The issue has been investigated from many aspects, such as mapping characters from genotype space to phenotype space

18. Bibliography Google Books: https://books.google.co.in/books?id=U7MuV1q6P1oC&printsec=frontcover&dq=genetic+algorithm+and+optimization&hl=en&sa=X&ved=0ahUKEwjtpKvL14LpAhWqyDgGHRiKAw4Q6AEIMDAB#v=onepage&q=genetic%20algorithm%20and%20optimization&f=false https://books.google.co.in/books?id=0eznlz0TF-IC&pg=PA30&dq=the+schema+theorem&hl=en&sa=X&ved=0ahUKEwiy2rfB54LpAhXfxDgGHTMrB88Q6AEIKzAA#v=onepage&q=the%20schema%20theorem&f=false https:// books.google.co.in/books?id=bVbj9nhvHd4C&printsec=frontcover&dq=Genetic+algorithm+with+neural+network&hl=en&sa=X&ved=0ahUKEwja9oGvioPpAhWizjgGHaVGDwAQ6AEIPTAC#v=onepage&q=Genetic%20algorithm%20with%20neural%20network&f=false Wikipedia

19. THANK YOU