2
$\begingroup$

I recently learned about genetic algorithms and I solved the 8 queens problem using a genetic algorithm, but I don't know how to optimize any functions using a genetic algorithm.

$$ \begin{array}{r} \text { maximize } f(x)=\frac{-x^{2}}{10}+3 x \\ 0 \leq x \leq 32 \end{array} $$

I want a guide on how to find chromosomes and fitness functions for such a function? And I don't want code.

$\endgroup$
1
  • $\begingroup$ Here you can find another similar question. $\endgroup$ – nbro Nov 5 '20 at 12:37
1
$\begingroup$

Yours is a really nice and easy question: you've seen how to use GAs in a complex problem but you're missing how to apply them to the most basic of all. I'll show you:

In a real-world implementation we have to structure our problem to be solved with GAs; we need to modify it, finding an equivalent representation that accepts individuals, each one of these is built from a genome and must be evaluated using a fitness function.

If you see this graphically you'll discover that the fitness function is just describing an area (or line or volume, depending on the grade) on our space and we are randomly dropping individuals on it, awarding the ones that fell higher than the others. We then try to modify the genomes of these guys to move them towards peaks of this fitness function. Crossover vs mutation, I did this image, feel free to use it.

In practice the fitness function is our world, our ground truth and we are exploring it.

Now to the function optimization part: well, we do not need any abstraction here, any strange individual representation or transformation of the problem; we just want to find a maximum, and this is exactly what GAs are for!

So, let's have a look at the elements you need to solve your problem with GAs:

  • Fitness function => you have it already! It's the function you want to find the max of.
  • Individual => as the maximum is enough, so the individual will be just a point in space.
  • Genome => like every respective point in space, the genome will just be a collection of real numbers (one for each dimension).

Now, like in any GA, you will instantiate randomly an initial population (random points in the domain). The evaluation of course is the easy part, just put them into the function and you'll se the value of the individuals.
What about crossover and mutation though? You'll have to use techniques that work with real-number genes, like BLXalpha, BLXalphabeta. These are just defining ranges between values and picking random values inside these ranges, I wrote a pretty detailed answer about this, you can check it out at: https://ai.stackexchange.com/a/6323/15530

$\endgroup$
1
  • $\begingroup$ In my opinion, this answer provides little insight into how to really solve this problem. For instance, you say that the fitness function is the function you're trying to find the maximum of. However, this is not really true, although the fitness function is a function of the original function. See my answer. $\endgroup$ – nbro Nov 5 '20 at 12:02
0
$\begingroup$

People usually say that genetic algorithms are used to solve optimization problems, but when it comes to optimizing a specific function given in an analytic form (i.e. when it comes to finding a maximum or minimum of such a function), it may not be clear how to proceed. I have created a complete but simple implementation and explanation of how to solve this problem here, but let me also describe here the main idea behind the approach. Before that, let's briefly review genetic algorithms (GAs).

Genetic algorithms

Genetic algorithms are composed of

  • a population (i.e. a set) of individuals (also known as chromosomes or genotypes), which represent the solutions to some problem

  • a fitness function that evaluates each individual (i.e. how "good" it is, maybe compared to other individuals, where "good" depends on the problem)

  • genetic operations to stochastically change the individuals in the population: typically, these operations are the mutation and cross-over

  • a method to select individuals for the cross-over (where you combine 2 or more individuals to produce other individuals); the selection is also a genetic operation

How to solve your problem?

To solve any problem with genetic algorithms, you first need to address all the four points above, i.e. define what your individuals (i.e. solutions) are, how to compute the fitness of a solution (i.e. how good it is), and define the specific evolutionary operations (specifically, mutation, cross-over and selection).

In your specific problem, the solutions are $\hat{x} \in \mathbb{R}$, such that

$$f(x)=\frac{-x^{2}}{10}+3 x$$

is a (local or global) maximum, i.e. $f(\hat{x}) \geq f(x)$, for all $x \in \mathbb{R}$ in a neighbourhood of $\hat{x}$.

(Note that this is just the definition of the problem of function maximization: if you are not familiar with it, you should probably get familiar with it before trying to understand this answer or even trying to solve this problem with GAs).

Therefore, in this case, the individuals are real numbers (which are the inputs to $f$).

The fitness function can be a function that computes $f(x_i)$, for all $x_i$ in your population, then compares $f(x_i)$ to $f(x_j)$ for all $i \neq j$. The higher the $f(x_i)$, the closer it is to a maximum.

The genetic operations can be implemented in different ways. You should think about it. If you are familiar with GAs and you know now that solutions are real numbers, at least one way of implementing these genetic operations should come to your mind at this point. Keep in mind that your solutions should be in the range $[0, 32]$, i.e. this is a constrained optimization problem. If you do not have any idea on how to implement them, take a look at my implementation/explanation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.