dr Tomasz D.Gwiazda
 Assistant Professor

 ———————
Home page
Short CV
    Publications
   
(e-)Books
   
Papers
My latest book
Students
Office hours
Teaching
 ———————

Contents of e-Book
Index of authors
Index of experiment domains


Introduction

Standard operators
1-Point Crossover
k-Point Crossover
Shuffle Crossover
Reduced Surrogate Crossover
Uniform Crossover
Highly Disruptive Crossover,Heuristic Uniform Crossover
Average Crossover
Discrete Crossover
Flat Crossover
Heuristic Crossover,Intermediate Crossover
Blend Crossover


Binary coded operators
Random Respectful Crossover
Masked Crossover
1bit Adaptation Crossover
Multivariate Crossover
Homologous Crossover
Count-preserving Crossover
Elitist Crossover


 
    Volume 1 - Introduction  
         

 

 

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 xilxi 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.

 
   

    :: Copyrights © tomaszgwiazda e-books 2006 :: webmaster ::