Solved – Genetic algorithm maximization of 2 variables

genetic algorithmsmachine learningoptimization

I am trying to teach myself more machine learning concepts. I have found a textbook and am trying to work through the exercises in it. Could anyone help me with this example?

Example:

Use genetic algorithm to solve the following optimization problem, including the initialize population, fitness function and each iteration until you find the optimal solution.

max f(x1, x2) = 2x(1)^2 + x(2)^2 + 3x(3)^2


s.t.     x1 ∈{0,1,2,3,4,5,6}
         x2 ∈{0,1,2,3,4,5,6}
         x3 ∈{0,1,2,3,4,5,6}

I've only seen examples that deal with a minimization and only deal with one variable. I believe I'm correct in saying that the maximization of a function is equal to the negation of the minimization of that function. So I understand that part. But I still haven't seen anyone using 2 variables.

Any information that anyone could give me or even resources that work through examples like this would be greatly appreciated.
Thanks.

Best Answer

Genetic algorithms are really only useful in multi-variable problems because you need a problem for which the potential solutions can be cut into parts which can be fitted together in new ways. Your problem is of this type. You want to maximise

f(x1, x2, x3) = 2x1^2 + x2^2 + 3x3^2

This function is your fitness function.

You start by finding an initial population of possible solutions. I am going to generate random values between $0$ and $6$, so the initial population looks like this:

[1,]    0    0    4
[2,]    2    1    5
[3,]    5    5    6
[4,]    6    2    6
[5,]    1    2    5

Each row is one possible solution. Now loop over the following steps:

  • Plug each solution in the population into f.
  • Choose the two solutions with the highest fitness. Call them the mother and father.
  • Create three child solutions by combining the mother and father with random mutations.
  • Form a new population from the mother, father and children
  • Go back to beginning of loop

Here is the first iteration of the loop. The fitness values for the $5$ vectors in the initial population are:

48 84 183 184 81

So the mother is 5 5 6 with a value of 183 and the father is 6 2 6 with a value of 184. Now we have to create the children. This is usually done by choosing a place to cut and following the mother up to that place and the father beyond it, or vice versa. Here, we can either cut after the first entry, to give 5 2 6 and 6 5 6, or after the second entry to give 5 5 6 and 6 2 6. Usually, some children will be produced by randomly choosing from these. So let's suppose we got the first three. Then our new population is

[1,]    5    5    6  (mother)
[2,]    6    2    6  (father)
[3,]    5    2    6  (child 1)
[4,]    6    5    6  (child 2)
[5,]    5    5    6  (child 3)

Now we should also do some mutations (otherwise, in fact, we will never reach the solution in this example.) One way of doing this is to change the values in the children up or down with some (small) probability. Let's suppose, after these random mutations, child 1 changes to 5 3 6 and child 3 changes to 6 5 6, and child 2 stays the same. Then the population at the end of the first iteration of the loop is now:

[1,]    5    5    6  (mother)
[2,]    6    2    6  (father)
[3,]    5    3    6  (child 1)
[4,]    6    5    6  (child 2)
[5,]    6    5    6  (child 3)

In the second generation, the new mother and father will be 6 5 6. All the children will be 6 5 6 as well, and we have to keep going until we get a lucky mutation when the middle 5 mutates to a 6. This is the only way to reach the maximum in this example.

Note that there are many variations on this procedure. Your book may well teach a different one. But the basic steps are

  • choose some fit solutions in each generation
  • produce new solutions from these using recombination and mutation
  • repeat as desired

Note that this particular problem is not well-suited to genetic algorithms. You really want to use them when the fitness function is complicated with many local maxima (or minima) or possibly when you want to increase the value of a function without necessarily maximising it (like in real-life evolution.)

And (as you can see) they are slow!

Here is a really cool example if you haven't seen it before: Boxcar2d.

Related Question