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.