This project is currently under review, see bugzilla Genetic Algorithm Solver:
Below reflects the earlier implementation and has been poorly translated to English.
This package contains the sources for:
A chromosome is a chain of nucleotides, the elements of the chromosomes. In nature these nucleotides a represented with the following four bases: Adenine (A), Guanine (G), Cytosine (C) und Thymine (T). The different sequences of these nucleotides, bases, on the chromosome, does code the genome[2].
The nature optimizes it's lifeforms with different methods. One of these methods is the sexual reproduction, so called mating. While mating, the genome of the mating partners are mixed, this is called "crossing over" [1,2,3,6]. The result of the mix is the genome of the partners child(s). E.g.:
Father : A G C T A G | A G G G T C | A C T A G
Mother : A A C T C G | A G C G T G | T C T A C
------------------------------------------------------
1st Child: A G C T A G | A G C G T G | A C T A G
2nd Child: A A C T C G | A G G G T C | T C T A C
Besides the "normal" crossing over (homologous or symmetric crossing over[2]),
asymmetric crossing over exists[2].
Within the asymmetric crossing over, at least in the version
of this genetic algorythm, one child contains the whole
genome of both parents.During the reproduction process so called mutations are possible. This mutations modifies the sequence of chromosomes with the following possible ways:
Mutation : Nucleotides are changed randomized.
In the nature, e.g. by radioactive radiation[1,2,3,4,6].
Inversion : A segment of a chromosome is transferred in reversed
order (last in - first out) [2,6].
E.g.: A G T A | A G C A T | C A G T ==>
A G T A | T A C G A | C A G T .
Translocation : A segment of a chromosome is transferred
to a different position to the destination (progeny). [6]
E.g.: A G T A | A G C A T | C A G T ==>
A G | A G C A T | T A C A G T .
On chromosomes the genome is stored. The logical whit (minimal part) of this genome is called gene. The gene represents a segment of a chromosome, but the definition of this noun is not that sharp since this documentation was written in March 1994. A chromosome, e.g. with a length of 10 000 bases, contains not only usable (useful) information. So useless information is also within the chromosomes. The chromosome's genes are often fractional.
The segments of genes/chromosomes with useful information are called exons[2]. The segments of genes/chromosomes with useless/junk information are called introns[2].
The fractional genes/chromosomes are spliced (splicing[2]), before they are transferred and used for the working process, e.g. the production of protein. The results of splicing is the useful meaning information, non fractional extrons. So the working process receives just the (you can call this compressed) useful information.
Using this generation process, the nature is able to create new life forces (creatures). With or without purpose, well, this is a philosophical or theological matter.
The natural environment defines the viability of it's creatures.
Darwin's thesis says, that only the best of a population can prevail, so called "Survival of the Fittest".
This natural selection prefers consequently the best of a generation. These "best" are able to reproduce itself more often (than the "worse"), so they can take care of a better condition of it's progeny. The next generation is thus more optimized as its predecessor (may be). So it is possible, that a population creates it's next optimized version.
This natural evolution principle, describes with crossing over(symmetrical and asymmetrical), mutations, splicing and selection, is the role model for this genetic algorithm. Well, I think that I can think, so it may works ;-)
This look will be terminated, if the chosen target fitness is reached, or is a chosen number of non optimized generations in a row.
The selection (c) of the parents occurs with the roulette system. The better individuals receives higher probability as the worse individuals of the generation. The probability, that parents are composed outta individuals with a better fitness is most probably. But it is not impossible, that parents are composed outta individuals, which fitness may be worse at the current time. Herewith it is avoided, that currently questionable worse solutions are rejected.[1,3,4,6]
The decease within the population can be regulated in two ways. One way is to create a complete new generation[4], which replaces the parents generation. in this case, the birth rate equals one. The other way is to use a lower birth rate, e.g. 0.6. In this case 60 percent new individuals are created, whereby their parents must die. Because bigamously relationships are allowed for both methods, after the decease of the parents as much individuals with a worse fitness must die, as the population's maximum is not exceeded.
The class 'Chromosom' contains the nukleotides of one chromosome and u.a. the methods for splicing and mutations. For details, please have a look at the file 'GENTECH.H'.
The class 'Chromosomen' (many chromosomes -> population) contains the methods for selection, crossing over and the whole evolution process.
The fitness method within the class 'Chromosomen' is a virtual one. The user, who want's to define the problem, must define this one regarding his problem. It must return a normal floating value within [0..1].
For example: In the river-problem (see 1.3.1 below), the combination of the boat crew must be encoded.
Christian Mueller implemented an encoding which only results in possible valid crew combinations.
In this case, one nucleotide has the following range of values within [0..4]:
0 : 1 Monk
1 : 2 Monks
2 : 1 Cannibal
3 : 2 Cannibal2
4 : 1 Monk und 1 Cannibal
An encoded (solution) chromosome of this kind, supplies the alternating boat crew from shore-a to shore b and vice versa.
The implementations of the game itself is contained within the files 'RIVER.[H|CPP]' using the class 'RiverGame'.
The chromosomes encoding of this game is contained within the files 'RIVERGEN.H[CPP]'. Here you find the class 'RiverProblem' as an derivation of the class 'Chromosomen'.
[1] Holland, John H. : Genetische Algorithmen,
Spektrum der Wissenschaft, September 1992, S.44-51
[2] Chambon, Pierre : Gestueckelte Gene - ein Informations-Mosaik,
Spektrum der Wissenschaft, Juli 1981, S.104-117
[3] Dewdney, A.K. : Genetische Algorithmen,
Computer-Kurzweil, Spektrum-der-Wissenschaft-Verlagsgesellschaft
1988, ISBN 3-922508-50-2, S.68-72
[4] Weckwerth, Guido : Zeugende Zahlen,
MC, Oktober 1993, S.54-58, Januar 1994, S.72-75
[5] Schader, Kuhlins : Programmieren in C++,
Springer-Verlag Heidelberg 1993, ISBN 3-540-56524-8
[6] Schoeneburg, Eberhard : Genetische Algorithmen und Evolutionsstrategien
Addison-Wesley 1994, ISBN 3-89319-495-2
We wish you fun in solving problems following the methods of natural reproduction ;-)
Authors: Christian Mueller and Sven Gothel Sven Gothel, Bielefeld den 11.3.1994 (last changes) Sven Gothel, Bielefeld den 1.4.2001 (translation to english) Sven Gothel, Bremerhaven, 16th April 2019 (New formatting, still needs proper translation)