Generational Parallel Varying Mutation GAs and their Applications


Abstract

This work focuses on varying mutation genetic algorithms (GAs). From the application of operators standpoint, deterministic, adaptive, and self-adaptive varying mutation GAs have been mostly designed similar to a canonical GA. That is, crossover is applied with high probability pc and then follows mutation. Thus, under these standard varying mutation approaches, higher mutations are mostly applied serial to crossover. This model of standard varying mutation GAs raises several important questions regarding the interference between crossover and high mutation, how this affects performance of the algorithm, whether this affect the mutation rate control itself in the case of (adaptive) self-adaptive varying mutation algorithms, and more generally whether this is an appropriate model for combining forms of control (co-adaptation of strategy parameters). This work proposes a model of parallel varying mutation GA that addresses the questions raised by the standard model of varying mutation GAs. The proposed model detaches varying mutation from crossover, applies "background" mutation (or none at all) after crossover (CM) and varying mutations (SRM) only parallel to crossover, putting the operators CM and SRM in a cooperative -competitive stand with each other by subjecting their offspring to extinctive selection. The model relies in adaptive (self-adaptive) mutation schedules to increase the effectiveness of SRM and enhance selection by eliminating fitness duplicates, which postpones genetic drift and creates a fair competition between the offspring created by both operators. The motivation of this work comes from the desire to design effective and efficient varying mutation GAs that can be used in real-world applications. There are several advantages in the proposed model. First, it gives an efficient framework to achieve better balances for varying mutation and crossover in which the strengths of the operators can be kept without interfering one with the other. Second, since varying mutation is detached from crossover, the instantaneous effectiveness of the varying mutation operator depends only upon itself and its relative success can be directly tied to the mutation rate to create adaptive (self-adaptive) schemes for mutation rate control. The same can be said for crossover, especially if no "background" mutation is applied after it. Third, parallel varying mutation can be studied on its own seeking to increase the performance of GAs. Fourth, the individual roles and the interaction of crossover and varying mutation throughout the run of the algorithm can be better understood, which could be important for co-adaptation studies. The model is studied using two test problem generators. One of the generators is for 0/1 multiple knapsack problems, which allows to test the model on a broad range of classes of constrained problems by varying the feasible region of the search space, number of constraints, and the size of the search space. The second test problem generator is the well known Kauffman's NK-Landscapes model of epistatic interactions between bits. NK-Landscapes allow testing the model in a broad range of classes of epistatic, non-linear, problems. First, the internal structure of the proposed model (GA-SRM) is studied in depth using an adaptive schedule for mutation. Important structural issues are the balance for offspring creation between CM and SRM, the ratio between number of parents and number of offspring (extinctive selection pressure), "background" mutation probability in CM, and the threshold to trigger adaptation in SRM. The effect of population size and number of evaluations is observed, too. Two mutation strategies to select the bits that will undergo mutation are investigated. In addition, the importance and effect on performance of extinctive selection and the interaction of varying mutation parallel to crossover is assessed. Second, the proposed model is compared with the standard model of varying mutations GAs across a broad range of problems using deterministic and self-adaptive schedules for mutation rate control. The statistical significance of the results is verified with ANOVA tests. It is found that the proposed model is more effective and efficient than the standard model. In deterministic varying mutation GAs, a GA with varying mutation parallel to crossover showed faster convergence and higher robustness to initial settings of mutation rate than a GA with varying mutation serial to crossover. In self-adaptive varying mutation GAs, the convergence velocity of a parallel self- adaptive mutation GA was matched by a serial self-adaptive mutation GA only when initial diversity of parameters was allowed. Convergence reliability of the parallel varying mutation model was higher than the standard model of varying mutation in both deterministic and self-adaptive GAs. It was also found that the standard model of varying mutations in fact affects negatively the (adaptive) self-adaptive mutation rate control. This strongly suggests that the standard model of varying mutation GAs may not be appropriate for combining forms of control. Then, the behavior of the parallel varying mutation GA-SRM is examined on epistatic problems using NK-Landscapes. Properties of NK-Landscapes are discussed and the effect on performance of selection, drift, mutation, and recombination is verified. Mutation strategy for the varying mutation operator is also studied in detail. Experiments are conducted using NK-Landscapes with nearest neighbor and random patterns of epistasis. Comparisons are made with a canonical GA, a simple GA with extinctive selection, a mutation only EA, and a random bit climber RBC+. It is shown that GAs can be robust algorithms on NK-Landscapes postponing drift by eliminating fitness duplicates and using selection pressure higher than a canonical GA. Different to previous works, even simple GAs with these two features perform better than the single bit climber RBC+ for a broad range of classes of problems. It is also shown that the interaction of parallel varying mutation with crossover (GA-SRM), similar to constrained problems, improves further the reliability of the GA. Contrary to intuition it is found that a mutation only EA can perform as well as GA-SRM that includes crossover for small values of K, where crossover is supposed to be advantageous; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone for medium and high K. Better overall performance by population based mutation only evolutionary algorithms over random bit climbers is also observed. With regards to mutation strategy for parallel varying mutation, it is found that a dynamic segment mutation strategy improves further the performance of GAs on problems with nearest neighbor patterns of epistasis. After analyzing the proposed model and comparing it with the standard model of varying mutation GAs, it is shown that the fundamental concept of the model can be successfully extended to other important classes of GAs and that it can be effectively applied to real-world problems. An important area of research is the parallelization of GAs. It is shown that the proposed model extended to a parallel distributed GA (DGA-SRM) achieves higher search speed, higher convergence reliability, and less communication cost for migration than a canonical distributed GA. It is also shown that DGA-SRM scales up better as the difficulty of the problem increases and tolerates population reductions better than a canonical distributed GA. Next, it is shown that GA-SRM can be successfully applied to real world problems in which efficiency in processing time and computer memory is a major issue. The improved GA-SRM is extended to the two dimensional image halftoning problem and an accelerated image halftoning technique using GA-SRM with tiny populations is proposed. Simulation results verify that the proposed scheme impressively reduces computer memory and processing time, making the improved approach appealing for practical implementation. Furthermore, it is shown that the concept of GA-SRM can also be effective for multi-objective optimization of real world applications, which is important due to the multi-objective nature of most real-world problems. The improved GA-SRM is extended to a multi-objective optimization GA to simultaneously generate halftone images with various combinations of gray level precision and spatial resolution. Simulation results verify that the proposed scheme can effectively generate several high quality images simultaneously in a single run reducing even further the overall processing time.