Genetic Algorithms

I'll talk about Genetic Algorithms at this post.

Genetics Algorithms (G. A.) are a type of evolutionary computation, wich the software "upgrade itself" for solve a problem.

The principle of G. A. is the Theory of Evolution (Biology).

In terms of system's engineering, we use G. A. with 4 steps:

1. Identify the problem and make it solution as a vector of numbers (preferentially, binary numbers);
2. Generate a lot of possible solutions (population), without think "what's the best solution for my problem?" (the software will find a good solution);
3. Create a measure for the solutions (G(.)), this measure indicates the "solution's adaptability" (for each solution);
   
4. Cross the solutions until a satisfiable solution is find.
   

Observations:

• The more adaptable solutions have more probability of cross with others solution.
• The function G(.) is higher as better is the solution for solve the problem.
• The cross between 2 solutions occurs with a changing of some numbers of the vectors.
• The worst solutions are discarded and the new solutions just be better than the old solutions.
  

A example: give a room with N lamps, which lamps should be lit for best lighting and less power consume?

{Making N = 10}

Each possible solution is a 10 positions vector: s = [l0 l1 l2 l3 l4 l5 l6 l7 l8 l9] which s[i] indicates the status of i-st lamp (s[i] = 1 -> lamp on, s[i] = 0 -> lamp off).

Creating a population of solutions:
s1 = [0 1 1 0 0 0 1 1 1 1]
s2 = [0 1 0 0 1 1 0 1 1 0]
s3 = [1 1 0 1 1 0 0 0 1 0]
s4 = [0 0 0 0 1 1 1 1 1 0]

(Of course that's very few solutions.)

Let's suppose that:
G(s1) = 18%
G(s2) = 32%
G(s3) = 35%
G(s4) = 15%

(The developer invents the G(.) according the problem.)

Thus, in this case, the result of G(.) is the probability of each solution cross with other solution.
(Is not possible make a "self-cross")

One very possible crossing is {s1, s3}.
s1= [0 1 1 0 0 0 1 1 1 1] and s3 = [1 1 0 1 1 0 0 0 1 0]

Determine a random point in the vector (for example 6) and change the numbers.
The cross' result:
s1' = [s1[0] s1[1] s1[2] s1[3] s1[4] s1[5] s3[6] s3[7] s3[8] s3[9]]
s1' = [0 1 1 0 0 0 0 0 1 0]
s2' = [s3[0] s3[1] s3[2] s3[3] s3[4] s3[5] s1[6] s1[7] s1[8] s1[9]]
s2' = [1 1 0 1 1 0 1 1 1 1]

So, the function G(.) is used in all new solutions, and the cross occurs until find a good solution.

I explained a simple form of develop a genetic algorithm, but the algorithm's complexity can be higher if you use many points in the cross, non-binaries vectors or insert mutation in the algorithm (if the algorithm don't result to good solutions).

Now, let's play with the Genetic Algorithms.