Real Life Applications of Soft Computing 7

147 5 Evolutionary Algorithms 5.1 evolutionary algorithMS Evolution is a novel system that has led to the creation of great systems in the natural and artificial world. The systems we see today show tremendous performance, in part because they have adapted to and evolved from the changing environment over time. Evolution is a predominant phenomenon in most natural systems. In artificial systems, evolution is attributed to the study of the success of this phenomenon in its natural counterparts. We see that these systems keep getting better over time as a result of continuous adjustment, adaptation, and learning. Looking at any species in the natural world can give us a clear idea of evolution. The most com- plex species is the result of continuous evolution over time. Evolution started with a simple species. Over time, these species evolved into newer and newer species, each more complex and better suited to the changing environments than the last. In general, each new species performs much better when compared with the earlier ones. This makes it possible for the continuous generation of new species from older ones that keep performing even better. The results are the most beautifully adapted spe- cies that we find today. The best example is of human beings, who have outperformed everyone in terms of intelligence. Inspired by the natural systems, the artificial systems are also trying to learn from evolutionary principles. The systems now model a problem in such a way that the solution evolves over time. This makes possible the generation of various kinds of solutions, which keep improving with time. The artificial systems being built are better adaptive to the changing environment. Optimization has always been one of the major problems in the field of computation. In these computations, we must optimize the solutions to any problem. If the number of possible solutions were constant, it would make sense to find all the possible solutions and then compare their perfor- mances. In reality, however, the number of solutions is so large that any machine would not be able to generate them all in a finite duration of time. The large number of possible solutions has always made researchers think about and come up with newer means of finding the most optimized solu- tions to problems in a finite duration of time. Optimization problems always have multiple solutions with varying degree of goodness or accu- racies. The best solution is the one that has the most optimal (maximum or minimum) value of the objective function. The objective function is a means of measuring the goodness or accuracy of a solution to these optimization problems. In other words, the aim of optimization is to minimize or maximize the value of the objective function. This is achieved by varying the parameters or vari- ables upon which the objective function depends. Every set of values of variables corresponds to some level of goodness as measured by the fitness function. The final output of the algorithm is the value set of these variables, which gives the most optimal value of the objective function. Optimization problems are also studied as search problems. The goal is to search for the best possible combination of values of the parameters that gives the most optimal objective value of the objective function. The total number of possible combinations of values for the various param- eters is infinite, which is what makes the problem interesting. We must search for a point in the entire world where the extent of the world can be infinite. To better understand the problem, let us understand a space known as search space. Imagine a very high-dimensional space that has as many dimensions as the number of variables in the optimization problem plus one. In this space, each dimension corresponds to a variable, and the last dimension corresponds to the value of the K11169_Book.indb 147 4/21/10 9:31:23 AM © 2010 by Taylor and Francis Group, LLC 148 Real Life Applications of Soft Computing objective function for the values of these variables. We take this axis as the output axis, pointing vertically upward. Now we plot the surface of the objective function in this space. This would be a surface in the high-dimensional space, which is the search space. The plotted surface would be filled with valleys and hills as the objective function value increases or decreases. The problem of optimization may now be viewed as the problem of finding the deepest valley in this search space; hence it is a search problem. Consider the case in which we need to minimize the total revenue of any firm. We are given the various parameters and constraints of the firm. The largest possible revenue that satisfies all the constraints is the best, or the most optimized, solution to the problem. Evolutionary computation has many applications in the optimization problems, which keep gen- erating solutions with each newer generation obtaining solutions better than those obtained by the previous generation. Some of these applications include robotics, functional optimizations, and character and other recognition systems, to name a few. 5.2 hiStoriCal note Work in the field of evolutionary computation started in 1950s and the 1960s, when researchers tried to model systems inspired by evolution. In the 1960s, I. Rechenberg introduced evolution strategies, a method he used to optimize real-value parameters for devices such as airfoils. Later evolutionary programming was developed by L. K. Fogel, A. J. Owens, and M. F. Walsh. Here candidate solu- tions were represented as finite-state machines, which were evolved by randomly mutating their state-transition diagrams and selecting the fittest. Since then, these machines are being used for the problems of optimizations. Other work in the field include that done by G. E. P. Box, G. J. Friedman, W. W. Bledsoe, H. J. Bremermann, J. Reed, R. Toombs, and N. A. Baricelli. In the 1950s and 1960s, computer simulations and controlled experiments were used by Baricelli, A. S. Fraser, F. G. Martin, and C. C. Cockerham. In the 1960s, John Holland led to the development of genetic algorithms. Holland studied adaptation to find a means of incorporating this natural adaptation into machines. In 1975, he published Adaptation in Natural and Artificial Systems. I. Rechenberg, L. K. Fogel, A. J. Owens, and M. F. Walsh also proposed various models for evolutionary programming. Genetic algorithm today has been greatly modified since it was initially proposed by J. H. Holland. 5.3 BiologiCal inSPiration As discussed earlier, evolutionary computation, or evolutionary algorithms (EAs), is an inspiration derived from its biological counterparts. In this section, we discuss the evolution process in the bio- logical world so we can better understand evolution in the artificial systems by genetic algorithms (GAs), which we discuss in the next section. Note that the strong correlation between the artificial and the natural evolution systems has resulted in many terminologies of the artificial systems being borrowed from the natural evolution system. The GA is inspired from the survival and reproductive systems of the natural species. A species consists of populations. These populations comprise the set of individuals of the species at that point in time. The capability of the species may be taken as the average capability, or fitness, of all the individuals of that species. An individual, in this case, represents a single entity, or creature, in this population. The different individuals in the population sexually interact to generate newer indi- viduals. Thus, the sexual interaction among the individuals of a population results in a newer set of individuals of a newer population. In natural systems, the generation of newer populations is in the form of generations. A generation sexually interacts to generate the next generation. It is generally observed that the average fitness of the newer generation is better than that of the preceding genera- tions, and thus the newer generations can better adapt to the changing environment, as theorized by Charles Darwin’s survival of the fittest. His theory states that only the traits of the fittest individuals K11169_Book.indb 148 4/21/10 9:31:23 AM © 2010 by Taylor and Francis Group, LLC Evolutionary Algorithms 149 pass from one generation to the next, while the traits of the others die out. In other words, the better characteristics are retained from one generation to the next, whereas the poorer characteristics are killed in the process. Any species is internally composed of cells. These cells are, in turn, made up of chromosomes. The chromosomes, which are strings of DNA, are the individual’s identity. The chromosomes and DNA decide the behavior, characteristics, and other properties of that individual. Internally every chromosome is divided into genes. Each gene encodes a particular region. Genes may be combined in numerous ways to generate various kinds of chromosomes or features in the individual. The dif- ferent kinds of encoding for a gene for a trait are called alleles. Each gene is located at a particular locus, or position, on the chromosome. Many organisms have multiple chromosomes in each cell. The complete collection of genetic material (all chromosomes taken together) is called the organ- ism’s genome. Two more important terms are genotype and phenotype. Genotype refers to the particular set of genes contained in a genome. The genotype decides all the characteristics of the individual. If two people have the same genotype, they may be considered identical. The phenotype consists of the set of observed characteristics of the individual. The genotype decides these characteristics, whereas the phenotype is a collection of observed features in any order or manner or representation. Most sexual organisms have a paired chromosome structure called a diploid. During sexual reproduction, there is a recombination of chromosomes from the two parents. This recombination is also referred to as crossover. In this step, exchange of genes takes place between the two parents to form a gamete, or a single chromosome. These gametes pair up to create a full set of diploid chromosomes. There is often a change of nucleotides from the parents to the child. This change is referred as mutation. Normally the change is the result of copying errors. Another concept in the natural systems is that of fitness, or the ability of the individual to survive in the entire population. A high-fitness individual means a high chance of survival. Fitness is also a measure of the individual’s reproductive power, or fertility. 5.4 genetiC algorithMS In this section, we give a brief overview of the genetic algorithms. Much of our discussion is restricted to the traditional GA, commonly known as the simple genetic algorithm (SGA). The GA is an effective way to solve real life problems based on evolutionary ideas. It is the most commonly used technique of evolutionary algorithms. In this section, we study the basic algorithm and its working. The details of the various steps are then discussed in the rest of the chapter. 5.4.1 concept We talked much about the concept of GA when we discussed its biological counterparts. When we compare the biological systems with systems of the SGA, we find that many of the concepts are the same. The GA starts with a set of solutions or populations. Each individual in the population set rep- resents a solution to the problem. The nature of the solution, however, varies. Some solutions may be very good, while others are very bad. The goodness of the solution varies from individual to individual within the population. To measure the goodness of the solution, we use a function called the fitness function, which must be made according to the program logic. Initially the population set contains all randomly generated solutions that are initially generated. This is called the first generation of the population. Then the various genetic operators are applied over the population. The genetic operators help in the generation of a new population set from the old population set. The new population set is formed by the genetic reproduction of the parents to form the children. Various other genetic operators are also applied that help generate the new popu- lation set. These specialized operators help in better optimization of the solution. K11169_Book.indb 149 4/21/10 9:31:24 AM © 2010 by Taylor and Francis Group, LLC 150 Real Life Applications of Soft Computing In this manner, we generate higher-order generations from the lower order. The fitness of any solu- tion or individual may be measured by the fitness function. A higher value of the fitness function means better solutions. The fitness of the population is measured by the average fitness of all the individuals that make up the population. It is observed that the fitness keeps increasing as we move forward with the algorithm. The higher-order generations are more fit when compared with the lower-order genera- tions. This is true for all best fitness individuals in the population, average fitness in the population as well as the worst fitness in the population. The GA results in improvisation as the generation proceeds. This improvisation is very rapid in the first few generations. After that, however, the algorithm more or less converges to some point to give the most optimal solution to the problem. The general algorithm of GA is given in Figure 5.1. We discuss each step of the algorithm, as well as the other details of the algorithm, in the next subsections. The basic algorithm follows an iterative approach and continues to generate newer generations. For the most part, the solution keeps improving with time until it finally converges or the improvement in the solution is unnoticeable. There must be a stopping criterion at which the loop terminates. This step may be based on various criterions that we will study later. The iterative nature of these algorithms is a very important aspect, especially with respect to soft computing. We know that the search space is infinite and cannot be explored to generate solutions; the time is always infinite. The beauty of this algorithm is that it finds the best point in this infinite search space as early as possible. The amount of search space traversed in the algorithm’s run time may be a very minute proportion of the total search space. The iterative approach is thus a very use- ful tool that gives valuable solutions per the time constraints. 5.4.2 Solution The GA is applied to the optimization problems, in which we are required to optimize an objective function by varying some variables or parameters. The real life problem first must be converted to Generate random solutions. While stopping criterion Generate next order generation by genetic operators. Evaluation by fitness function Return best solution. No Yes Figure 5.1 The simple genetic algorithm. K11169_Book.indb 150 4/21/10 9:31:24 AM © 2010 by Taylor and Francis Group, LLC Evolutionary Algorithms 151 this optimization problem before GA is applied over it. Whenever we talk of problem in this section, we are referring to this optimization problem. Solution is an individual in the population set that represents a set of parameters or variables of the problem to be optimized. The solution may be good or bad, depending on the fitness measured by the fitness function. Consider the problem of functional optimization, in which we are given a set of input variables. We have an objective function that we must optimize, which is the goal of the problem. In addition, we have a set of constraints that every solution must follow. An example of this problem is given by Equation 5.1. In this problem, a solution may be represented by two values, one corresponding to the value of a and the other corresponding to the value of b. The general form of any solution may be taken as (a, b). Maximize: a * b (5.1) Constraints: 0 ≤ a, b ≤ 5 a + b > 5 The solution may be feasible or infeasible. Infeasible solutions usually disobey some constraint of the problem and are hence not valid solutions. Infeasible solutions cannot be returned as the final solutions by the GA and are usually not accepted in the solutions at all. Thus whenever these solu- tions try to enter into the population set, they are rejected. We rather repair them to make them fea- sible and then allow them to enter the population set. Another possibility for dealing with infeasible solutions is to assign them a very low fitness value. According to the theory of survival of the fittest, it may be assumed that they would then die out with the passage of time. In the above problem, the solution (2, 10) is infeasible because it does not obey the constraint 0 ≤ a, b ≤ 5. So far we have represented the solution in an easy-to-understand format. This type of solution, known as the phenotype solution, may be used for computation of fitness or other comparisons or operations. The GA, however, may require a different representation of the solution, in this case the genotype solution, to perform and function. The genotype solution is usually a sequence of bits or numbers. Each bit may be either 0 or 1. The whole phenotype solution is represented in such a way that we may represent it in the form of continuous bits. The entire bit sequence is the solution in the genotype form. The conversion of the solution into this format of bit string comes from the classic theory of GA. The various genetic operators were designed assuming the individuals were a series of bits. We shall later see that repre- sentation of the solution in the form of a continuous series of numbers (not necessarily binary) also works and often gives better performance. In our example, we represented a solution in the form (a, b), where each a and b can take any value between 0 and 5 (6 values in total). To represent a, we require a minimum of three bits (23 = 8 ≤ 6). Similarly to represent b, we require at least three bits. The entire solution may hence be rep- resented as a sequence of six bits, with first three bits denoting a and the next three bits denoting b (see Figure 5.2). The solution (2, 3) is represented as a = (010)2 = 2 and b = (011)2 = 3. Another way of representing the solutions is directly by their numbers. The other genetic operators can be modified to handle the solutions with a numeral representation, which saves the a 0 1 0 0 1 1 b Figure 5.2 The genotype representation of a solution. K11169_Book.indb 151 4/21/10 9:31:25 AM © 2010 by Taylor and Francis Group, LLC 152 Real Life Applications of Soft Computing overhead of continuously converting binary to decimal and vice versa. We will see in the later sec- tions some specific genetic operators for this type of implementation that are widely used for their ease of handling. In general, for any problem that we need to optimize with the help of GA, we first must represent it in the form of a solution. Once this has been done, we can apply the various genetic operators to optimize and find the most optimal solution. The use of the other GA operators is quite a trivial task. Hence one of the major design and implementation issues is a good solution design that deals with the manner in which we convert the solution to a sequence of bits or numbers. The solutions may take different representations. If we try to train an ANN by GA, the solution represents the different weights and biases if the structure is kept constant. If the network is allowed to change, we must work to again with some means of network representation. In many cases, the solution may be represent