download PDF
with first 40 pages
from my latest eBook
if you need more operators
click here
The literature
on Genetic Algorithms or more widely on Evolutionary Computation is full
of many excellent books and articles which are texts of introductory or
review character. These texts concentrate on presentation of fundamental
(or most popular at a given time) methods of selection, recombination
and mutation etc., so, at the same time, for obvious reasons they
overlook (or only mention) most of the output from that field. The
similar situation occurs as far as websites on Genetic Algorithms as
well as software applying Genetic Algorithms are concerned – the scope
of presented or applied methods is considerably limited. Because of that
a researcher who is a beginner in that field (though not only beginner)
is forced to individually dig in the source texts for less popular
methods, new inspirations or answers to the question whether the method
he is currently working on is new. Eventually, it is very often the case
(which is proved in this book) that the new method which is
published, is a duplication of an already existing method or is a slight
and not very significant modification of it. The need for comprehensive
study is, therefore, obvious and that is the motivation which led to the
idea of preparation of this book. .
This book is the
first of the series of reference books I am working on, with the aim to
provide a possibly most comprehensive review of methods developed in the
field of Genetic Algorithms. The necessity to concentrate on certain
thematic areas is the result of the character of these books. The choice
of those areas, even though performed arbitrarily will hopefully reflect
their degree of importance and popularity. Hence, in this book which
begins the whole series, an operator of the greatest importance for
Genetic Algorithms will be presented i.e. crossover operator and its
area of application will be single-objective numerical optimization
problems. Following publications from this series will be dedicated to
selection and mutation operators from the same area of application.
After that I will be concentrating on multi-objective optimization
problems to, in the end, cover the area of combinatorial optimization
problems.
The
layout of this book is the following. At the beginning I will present 11
standard operators, where by the term standard I mean
those operators which most often appeared in source materials in the 80s
and in the beginning of the 90s as a reference point for the newly
published methods. The standard operators are presented in an
abbreviated form in comparison to the other operators; therefore, some
operators which could be undoubtedly qualified to the group of standard
operators (e.g Arithmetical Crossover) are described in latter parts of
this book in order to make a more complete presentation. The second part
of this book presents 66 operators developed for the binary coded
problems and the third one presents
89 operators developed for the real-coded problems. In many cases of the
presented operators this division is somewhat artificial because they
may be applied to solve one as well as the other class of problems.
Hence, my decision to present a certain operator in the group of binary
or real coded operators is based on the source texts in which, the
authors usually specify the application area of that operator. The last
part of this book includes the list of statistic-based operators
indicating source texts as well as read-also texts..
Let Figure 1
represent
quantitative
summary, in which the number of operators described in this book is
presented according to the years of their publication.
Figure 1 Number of operators described
In
the second and third part of this book every operator is presented
according to the same scheme, which is presented below:
●
Keywords – are supposed to help with searching through the book and
also with mutual association of the presented in it operators.
●
Motivation – showing the motivation which was the base for
development of a given operator. This motivation has been formulated by
the authors éxplicite or has been drawn up arbitrarily.
●
Source text – source text pointing to the website from which that
text may be downloaded – most of these sites are free of charge.
●
Read also – suggested additional texts, the subject matter of which
is directly connected with the discussed operator. The choice of these
texts, even though it is made arbitrarily, is based mainly on the
bibliography list included in the source text or points to the texts
describing further development of a given operator or other operators
connected with it ideologically. Links to sites where the suggested
texts may be downloaded from are also provided.
●
See also – other operators that in my opinion it is worth to become
acquainted with in connection with a given operator. The names of
operators are in the same time hyperlinks to these pages of the book
that they are discussed on.
●
Algorithm – presents the discussed operator in the form of a
pseudo-code, often in a couple of options. I decided to choose this form
of presentation of an operator because it enables, in most cases,
immediate application of that operator in practice. On the other hand I
decided against usage of a specific programming language because
elements appearing in the code additionally, resulting from grammar
could make it difficult to understand the presented operator. A
presented algorithm may often differ from its original form presented in
the source text, it is often the case when the form of an operator was
closely connected with the problem for which a given operator has been
developed. However, the key idea of an operator is always presented.
●
Comments – commentary or description of the presented operator,
depending on whether in my opinion pseudocode of an algorithm is a
sufficient description or not.
●
Experiment domains – problems that a given operator has been
developed to solve or has been tested on, especially in consideration
with standard testing functions.
●
Compared to – list of other crossover operators the presented
operator has been compared to (in the source text). The names of
operators are in the same time hyperlinks to these pages of the book
that they are discussed on.
Even though it
may be disapproved of, I treat the following terms as synonyms:
„recombination–crossover”, „solution vector–chromosome”,
„gene–variable”, „generation–iteration” and use them as such throughout
the text. Moreover, if it is not indicated éxplicite to be otherwise, I
use following symbols throughout the text:
t – generation (iteration) counter
M – maximum number of generations (iterations)
P() – population of solution vectors (chromosomes)
P(0)
– initial population
P(t)
– current population
P(t+1) – next population
pcross, pc – crossover probability
pm
– mutation probability
n – length of
solution vector (chromosome)
Binary coded operators
A(t)=(a1(t),...,an(t))
-
binary solution vector (chromosome)
for all
i=1,...,n ai(t)={0 or 1}
f(A(t)) – fitness of binary solution
vector A(t)
{A1(t),...,Ak(t))
-
binary solution vectors (chromosomes)
Aj(t)=(aj1(t),...,ajn(t))
(for all j,i aj,i(t)={0 or
1})
f(Aj(t)) - fitness of binary
solution vector Aj(t)
Real coded operators
X(t)={x1(t),...,xn(t)) – real solution vector (chromosome)
for all i=1,...,n
xil≤xi≤ xiu
where:
xil
– lower boundary of ith variable
(gene),
xiu – upper boundary of ith variable
(gene)
f(X(t)) – fitness of real solution
vector X(t)
{X1(t),...,Xk(t)} – real solution vectors (chromosomes)
f(Xj(t)) – fitness of real solution
vector Xj(t)
Upon publishing of
whole series of the planned e-books, I plan to prepare supplements once
every two years which will cover two years from the date that e-book was
published. I plan to send them to all interested readers. Hence, if you
wish to receive such a supplement in the future please contact me by
e-mail.
|