Mutation as a Diversity Enhancing Mechanism in Genetic Programming - Essay Example

Genetic programming (GP) is a novel approach to machine learning and artificial intelligence using evolutionary algorithms. It involves the use of operators that are metaphorical to biological processes such as gene mutations, alterations, deletions and crossovers. The aim of GP is to automatically create a program that solves a specific problem. It is aimed that via GP, machines will be able to learn through experience, which is a major requirement for the synthesis of artificial intelligence. Crossover and mutation operators are used in GP to generate diverse programs, and to search this population space for the one with a good fitness value and ability to solve a given problem most efficiently. This paper evaluates Jackson's (2011) paper on the role of mutations in enhancing diversity and in improving the performance of a GP process. The findings are criticized and compared to previous approaches, and a few shortcomings are also discussed briefly. I. Introduction: Genetic programming (GP) has emerged as a promising instrument in research on machine learning and artificial intelligence. According to Koza and Poli (2005), GP is a "systematic" method of "getting computers to automatically solve a problem" (p. 127). The temptation of creating artificial intelligence and enabling machines to "automatically" perform problem solving has led to the exploration of biologically inspired methods of programming, such as crossovers and mutations. The process of GP involves alterations in computer programs analogous to biological genetic processes. The genetic code in biological science is analogous to syntax trees in computer science, and these trees are altered in a similar fashion as that of gene mutation, deletion, crossover, duplication, etc. performed by nature. The aim of genetic programming is to create a novel and complex program without taking the trouble of predefining its structure. Background In the process of biological evolution, organisms underwent alterations in their genetic makeup, which led to an increase in their structural as well as genetic diversity. Only those who were genetically "fit" were able to survive during the dynamic changes in environmental conditions. Those who lacked the capacity to adapt to these changes went extinct. Thus, according to Charles Darwin, evolution of organisms occurred via natural selection in which nature selected the organisms that were most fit to survive, also known as survival of the fittest. Mutations are the most effective genetic alterations, which enabled the generation of diversity among organisms and ultimately led to their natural selection in the process of evolution. Mutations occur randomly in the genes, and may be natural or induced. These are sudden and heritable changes, and occur at a very small frequency. They, however, lead to beneficial or even harmful changes in an organism. Mutation is nature's way of generating diversity among living organisms. The fact that random mutations have led to the generation of successful species is enough to inspire the exploration of similar mechanisms in computer science, in a metaphorical sense. With the help of "mutations" in programming, it may be possible to create novel and successful genetic algorithms or programs with a higher fitness value, which have a high probability of arriving at the solution to a given problem. These may form an integral part of machine learning and help in the synthesis of artificial intelligence. Objective Many studies have explored the role of mutations in genetic programming for the induction of diversity in computer programs. It is hoped that through such a process, it would be possible to create programs with increased fitness and with more efficient problem solving capacities. This paper attempts at analyzing the importance of diversity in genetic programming and the efficiency of mutations in achieving the same. The paper, Mutation as a Diversity Enhancing Mechanism in Genetic Programming (Jackson 2011) is also reviewed and evaluated. II. Literature Review Genetic programming (GP) involves the genetic breeding of populations of computer programs for solving a problem (Koza and Poli 2005, p. 127). GP, a field first pioneered by Koza, involves the use of operators such as crossovers and mutations to "evolve" a program, and is an integral part of machine learning (Banzhaf et al. 1998, p. 4). According to Mitchell (1996 as cited in Banzhaf et al. 1998), machine learning is possible through the development of computer algorithms, which "improve automatically through experience" (p. 4). Therefore, as Banzhaf et al. write, the aim of genetic programming is to "induce a population of computer programs", which automatically improve with experience (p. 4). In plain terms, genetic programming automatically creates a program that solves a given problem. Importance of diversity in GP In the process of GP, many diverse programs are automatically generated and a genetic algorithm searches the space of programs to conclude which one of these best solves the specified problem. The more diverse these programs are, the more possibility there is of arriving at the best program for a given problem. Therefore, diversity in programs is the lifeblood of genetic programming. According to Ekart and Nemeth (2002), loss of genetic diversity in programs may result in "suboptimal solutions" (p. 122). Ensuring the maintenance of a certain level of diversity in a population is important for the prevention of convergence of the population towards a minimum, which may not successfully lead to a solution (Jackson 2011, p. 1371). Jackson (2011) argues that the homogenous nature of a non-diverse population reduces the chances of arriving at a program that would successfully solve a problem, and that introduction of diversity will enable a "wider and more fruitful exploration of the search space" (p. 1371). While diversity may appear to be a very important component for the success of a GP run, it is not the only factor for success in problem solving. From their studies on diversity in GP and on fitness of programs, Burke, Gustafson, and Kendall (2004) conclude that a single measure cannot be used to control diversity for improving fitness and that the relation between diversity and fitness of a program vary during the different stages of an evolutionary process (p. 47). Moreover, they also suggest that the efficiency of diversity may be problem specific. Daida et al (2004) have elaborately explored the relationship between diversity, problem solving ability and population size. They argue that simply enhancing the diversity is not "intrinsically helpful" in problem solving and that in spite of significant losses in diversity, improved performance in problem solving can still be demonstrated (p. 1232). Approaches to generation of diversity While the subject of diversity remains controversial, measures for controlling and inducing diversity are being extensively explored. Various important operators involved in GP include crossovers and mutations, and both are often performed together in one GP run. Poli and Langdon (1997) have demonstrated GP using one-point crossover and point mutation. A crossover is performed by recombining random parts of two programs to create a new program, while mutation involves the creation of a new program by mutating a random part of one program (Koza and Poli 2005). A mutation operator introduces a random change in a parent program and the crossover operator selectively combines two good parts belonging to two parent programs to give one program, and in genetic algorithms, both these operators are selected randomly (Langdon and Poli 2002, p. 9). Both these operators have been immensely helpful in genetic programming. The 'Crossovers & Mutations' debate In spite of their utility in genetic programming, both these operators have been a reason for debate on which one of these is more powerful and efficient in achieving the desired outcome. Studies by Luke and Spector (1997) have shown that though crossover yields better results more often than subtree mutations, there is no significant difference between the performances of the two. They however suggest that, overall, crossover is more successful than mutation but mutation is a better option for small populations. A drawback of crossovers is that if both the parents are identical, the program that results from their crossover is also identical, or more specifically, is a clone of its parents. However, mutation overcomes this shortcoming by introducing a new allele into the offspring that was not present in the parent programs (Jackson 2011, 1371). In his paper, Mutation as a Diversity Enhancing Mechanism in Genetic Programming, Jackson seeks to evaluate the effects of mutations in GP. He specifically examines whether GP mutation is successful in increasing the diversity of program population and whether an increase in diversity, if possible, affects the performance of the process. He also investigates whether mutations can be made more powerful in their ability to enhance diversity and if this would have any consequences on the performance of the GP process. III. Mutation as a Diversity Enhancing Mechanism in Genetic Programming—Paper Summary and Evaluation This paper by Jackson (2011) explores the role of mutation in enhancing diversity and in increasing the fitness value of a program. The paper is evaluated here and is compared with previous approaches to GP and mutations. A brief critical review of the paper is also attempted. Summary Jackson uses four different commonly used GP problems to investigate the performance of the programs. The first one belongs to the Boolean domain and is a 6-multiplexer problem, the second one too is a Boolean problem, namely the even-4 parity problem. The thirst problem is the Santa Fe ant trail problem, which involves the evolution of an algorithm to guide a virtual ant in a matrix by helping it discover a maximum number of food pellets. The final problem is a symbolic regression problem of a polynomial. Mutation at a frequency of 1, 5, 10 and 50% was carried out. Jackson defined diversity in three separate measures – structural, behavioral and fitness diversity (SD, BD, FD). After GP runs were performed for the even-4 parity problem, it was found that mutation has a very minor effect on diversity. In fact, diversity remains constant with or without mutation. Specifically, there was only a slight increase in BD and FD, and that too occurred only when mutation was performed at a very high frequency, i.e. 50%. The results were similar for the 6-mux problem and the Santa Fe ant trail, wherein, mutation did not have any significant effect on any one of the three diversity metrics, SD, BD and FD. Moreover, it did not increase the chances of finding a solution and the fitness values did not vary much with or without mutation. In contrast to this observation, the results for the symbolic regression problem are different. For this problem, the SD and FD values increased due to mutation, although the BD values did not undergo much variation. The fitness value and performance in finding a solution to the problem also increased in this case. Jackson further investigated these effects by inserting a loop in the mutation operator to selectively search for behaviorally and structurally unique programs, to further increase population diversity. Selectively increasing structural diversity did not lead to any significant improvement in performance. Selectively increasing behavioral diversity led to statistically significant improvements in just 50% of the cases. This study thus concludes that the effect of mutation on diversity depends on the nature of the problem tested. Jackson further concludes that mutation does not necessarily improve performance in solution finding. Altering the mutation operator for specifically targeting structural or behavioral diversity also does not help much. The improvement in performance in the latter case is similar to that achieved in standard mutation. The overall conclusion, as inferred by Jackson, is that mutation only when "coaxed into promoting diversity" may prove to be a useful operator in GP (1377). However, as to whether mutation is really successful in enhancing the outcome of a problem solving process, the results are still inconclusive and warrant future research. Significance and novelty of the study This study by Jackson is particularly relevant because of the issue it deals with and the way in which the issue is dealt. Firstly, the author divides the parameters of diversity into three groups, namely structural, behavioral and fitness diversity, for a cross-sectional evaluation of which diversity metric is actually affected by mutation. This approach is perhaps novel to the study and was not done in previous studies. Another notable feature of this study is that mutation rates are tested at 1, 5, 10 and 50% frequency. Four benchmark problems including two Boolean, one regression problem and the Santa Fe ant trail problem were extensively evaluated for each of the diversity metrics and also for each of the four mutation frequencies. This study thus successfully and exhaustively investigates the effect of mutation on diversity and program performance. The author not only evaluated the effect of mutation but also investigated the effect of controlling the mutation operator to achieve and magnify a selected diversity parameter. The mutation operator was altered to selectively search for programs that were behaviorally or structurally unique. Therefore, in a one-of-a-kind approach, the author successfully investigated the effect of selectively increasing structural diversity or behavioral diversity on problem solving performance of the program. To prevent bloat and exhaustive searching in the Santa Fe ant trail, Jackson allowed a maximum of 500 steps. Thus, this study does an in-depth investigation on the role of mutation in enhancing diversity, and its effects on program performance and fitness value. The population size was high, (n=500) and the number of runs was 100. The author also elaborately discusses his approach to measurement of diversity and fitness value of the operation. The study is reproducible. This study is the first to have intensively explored the effect of mutation on diversity and fitness value in a unique approach. Comparison with previous approaches A number of previous studies have investigated mutations in genetic programming. Banzhaf, Francone and Nordin (1996) have explored the effect of "extensive use of mutation" in GP. At the time of their study, crossovers were the most predominant operators and mutations were used rarely. The study involved studying the effects of 5-80% mutation rates on generalization capabilities. It was found that generalization capabilities improve with an increase in mutation rates. Based on this observation, it is expected that the mutation rates would improve performance, which is however not found to be true in the study by Jackson. In contrast to the present study, Beadle and Johnson (2009) used a sematically driven approach to mutation. In their study, Beadle and Johnson used "semantically driven mutation" (SDM) that can "detect and apply behavioral changes" resulting from mutation in programs. In their study, Beadle and Johnson have demonstrated that SDM increases the performance of GP in seven benchmark problems, including the 6-multiplexer problem and the Santa Fe ant trail, using ramped-half and half initialization similar to the approach by Jackson (2011). The results reveal that in all cases, SDM improves GP performance while standard mutation achieves negligible or no improvement. This observation that standard mutation does not improve GP performance is also confirmed in Jackson's study, wherein, increasing mutation rates are also ineffective in increasing problem solving performance, except for the symbolic regression problem. The findings by Jackson and Beadle & John are thus consistent. Burke, Gustafson, and Kendall (2004) have shown that the efficiency of diversity in improving performance is problem specific. This observation can also be extrapolated on Jackson's study in which the effect of mutation on diversity, and in turn on solution performance, is problem specific. Luke and Spector (1997) have indicated that mutation performs better for smaller populations. Contrary to this observation, the populations in Jackson's study were fairly small, and yet did not yield any significant improvement in performance. The population size in Luke and Spector's study ranged from 8 to 2048, while that in Jackson's study was 500. In a study, Koza and Poli (2005) have shown that induction of mutation by deleting an entire subtree improved fitness (from 1.67 to 1.00). However, in the study by Jackson, there is no statistically significant increase in the fitness values. Yet, there is one exception. When behavioral diversity was selectively magnified by altering the mutation operator, 50% of the test cases showed improved fitness values. The most notable fact here is that in case of the mux, ant, and the even-4 parity problems, increasing behavioral diversity with a 50% mutation rate led to 29%, 240%, and 110% increase in solution rates, respectively. Therefore, it is evident from the widely ranging results and observations that the effects of mutations and its utility in improving the performance of GP are inconclusive. IV. Critique: Jackson successfully evaluates the role of mutation in GP. The approach is unique, extremely useful and can be utilized in future studies. The fact that he not only evaluates the role of mutation in improving diversity and performance but also investigates how mutation can be made more powerful makes it an interesting read. Strengths The main strength of the study is its subjective approach, systematic style and replicability. The selection of four benchmark problems from different domains for testing the operator is also noteworthy. Another significant strength is the use of mutation rates at varying frequencies of 1%, 5%, 10% and 50%. Moreover, the division of the diversity parameters into structural, behavioral and fitness diversity and the evaluation of the effects of mutation on each of these diversity metrics contribute to the value of the study. The findings of the study are further strengthened by the comprehensive analysis on the effects of alteration of the mutation operator to search for programs that are structurally and behaviorally unique. This added to the population diversity in the study, enabling a better analysis of the results of mutation on GP performance. The study also enabled a brief contemplation on whether mutation can be made more powerful to achieve higher diversity or higher performance rates. Shortcomings and limitations As discussed earlier, the results obtained in this study appear inconclusive. It is found that mutation has no significant influence on SD, BD of FD, except for the regression problem. If this problem would not have been included in the study in the first place, it would not have been possible to know that mutation does increase these diversity metrics in some instances. Keeping this in mind, it can also be inferred that many other benchmark problems may reveal results similar to the regression problem. Therefore, more problems should have been included in the study to enable more decisive inferences. While on the one hand, mutation rates do not improve performance in any of the problems tested, they do increase the performance when done at a higher rate (50%) and that too only for the regression problem. This observation is not enough to count mutation as a useful operator in GP. Yet, with regards to the question that mutation is a useful operator in GP, the author infers "a carefully guarded yes" (p. 1377). This inference is questionable, as the results do not reveal significant improvements in performance in a majority of the cases at reasonable mutation rates. Another significant shortcoming of this study is that it measures the effect of mutation by using GP system parameters that are common to almost all other experiments. For instance, it maintains the evolutionary process in steady state and uses the ramped half-and-half method of initialization, which is similar to most other studies performed on this subject. Exploration of various other GP parameters may yield different and possibly more significant results. The author fails to discuss the reasons for wide-ranging results obtained in the study, especially those obtained for the symbolic regression problem. Moreover, the author does not highlight why performance rates are increased when behavioral diversity is selectively increased and why they do not change much when structural diversity is selectively increased. The reasons for such disparities and inconsistencies in results are subject to further research and studies. Perhaps by increasing the diversity in the problems tested or by testing newly created problems, and by increasing the population size and number of runs, it would be easier to arrive at conclusive and definite results. It is amazing how the effects of mutation on performance and program fitness values remain elusive in spite of the huge amount of research and investigation on the subject. V. Conclusion: Genetic programming is a fairly young offshoot of computer science and may hold the key to the development of artificial intelligence, as envisaged by Turing. Through evolutionary algorithms and biologically metaphorical operators such as mutation and crossovers, it may indeed by possible to enhance machine learning. Since mutation, as shown in the reviewed study, may or may not be helpful in genetic programming, other unconventional operators may also be sought. Perhaps a whole new approach to genetic programming and evolutionary algorithms is required to make that one breakthrough, which may unfold further advancements in artificial intelligence and machine learning. Read More