Quote:
| [Originally Posted by shaddar]isn't the implementation a bit too much work for the given targe |
Hmmm, maybe you are right but I need something *easy* to introduce this subject; we had spoken only few times and we never treated the subject in this forum. Take it as an introduction plus a simple example on coding a Genetic Algorithm
.
--------------------------------------------------------------------------
The idea behind Genetic Algorithm is simple: you start with an initial population and then, applying some rules the population evolve, trying to reach the goal. In this case the goal is the value of the sum and the members of the population are the serials.
The scheme of a generic GA is:
Code:
BEGIN
1. Create the initial population
while (goal is not yet reached)
BEGIN
2. Calculate the fitness of every member of the population
3. Sort the population using the fitness value
4. if (goal is reached)
Solution is find, quit from the while
; --- Reproduction process ---
5. Elitism
6. CrossOver
7. Mutation
END
Print solution
END
1. Create the initial population
--------------------------------
The initial population is filled with random solutions. In this specific case we will have a lot of 16-chars_serial where each character it is choosen randomly. How many members should be in the population? It's not easy to answer to this question; with a big population you have the possibilities to explore much more solutions than a small population but on the other hand the process could take much more time... as you can see there is not a fixed rule and it's up to you to decide the size of the population.
2. Calculate the fitness of every member of the population
----------------------------------------------------------
For every different problem, we have to create a specific fitness function; the fitness function is the core of the GA. The function is applied to each member of the population; in this way, every member of the population will have a fitness *score*. The score represents the *distance* between the current solution and the goal solution. For many problems, like maths optimization problems, the fitness function is represented by the function itself. Due to the fact that the fitness function is a very important part of the GA process, it is fundamental to find a good fitness function if you want a nice GA.
3. Sort the population
----------------------
The population is sorted, with key equal to fitness value, from the best to the worst current solution. In this task you will have to apply a 'sort' algorithm to the population.
4. Check solution
-----------------
As suggested by the title, this is a simple check to find out if a member has reached the goal... nothing more.
Points number 5,6,7 are part of the reproduction process. These are the rules you can apply in order to evolve the population. You can use all of them or only some of them.
5. Elitism
----------
This strategy was born because when a new population is created there is the possibility to lose the best solution(s); the elitism is used to preserve few best solution(s). Elitism increases the performance of the GA.
6. CrossOver
------------
Crossover is a technique used to evolve the population. There are various version of this technique: One point crossover, Two point crossover, Uniform crossover, Partially Mixed Crossover and so on...
Which is the best? It's not easy to answer this question. I think that each version is suitable for a specific problem; for example, Partially Mixed Crossover is used for problem like 'Traveling Salesman'...
Here is a little description of some techniques:
- One Point Crossover(OPC): we have to choose a CrossOver Point, after that the children are created combining some genes of the father with some of the mother. I.e:
Code:
Father / Mother: 10110110 11100001
^ ^
| |
---------------- CrossOver Point
Children:
10110 + 001 = 10110001 <-- first part is taken from the father and the rest from the mother
11100 + 110 = 11100110 <-- first part is taken from the mother and the rest from the father
- Two point crossover: the idea behind is taken from the OPC. Each member is represented in a ring form, we have to find two crossover points and to exchange the genes of the father with the genes of the mother. I.e:
Code:
Father (10110110) and mother (11100001) in his circular form, the first gene is the one on the top:
1 1
0 0 <-| 1 1 <-|
1 1 | 0 1 |
1 1 | 0 0 |
0 | 0 |
^ | ^ |
| | | |
| ----------------------- First crossover point
| |
| |
| |
----------------------------------- Second crossover point
We will have children like:
1 + 1100 + 110 = 11100110 <-- start and end from father, middle from mother
1 + 0110 + 001 = 10110001 <-- start and end from mother, middle from father
- Uniform CrossOver: given two parents, a mask is used to decide which genes are taken from the father and which are taken from the mother. I.e.:
Code:
Father: 10110110
Mother: 11100001
Mask: 01001100 (1: take from the father, 0: take from the mother)
--------
Children: 10100101
7. Mutation
-----------
Mutation is a very important operation in the evolution process and, it's applied after Crossover. It consists on a simple mutation of a gene, nothing more. In some cases, it's possible to evolve the population with only this operation, removing the Crossover process (think about asexual reproduction...).
Well, (I hope) this might give you a little introdution to the Genetic Algorithm.
--------------------------------------------------------------------------
Now, we can try our first GA with this bruteme exercize...
Later,
ZaiRoN
