Real-valued genetic algorithm offspring out-of-bounds

Question

I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, I use the following method to produce 3 children/offspring $(c_{1,2,3})$ from 2 parents $(p_{1,2})$: $$c_{1} = 0.5p_{1}+0.5p_{2}$$ $$c_{2} = 1.5p_{1}-0.5p_{2}$$ $$c_{3} = -0.5_{1}+1.5p_{2}$$

For example, if we consider a problem where the bounds are $0\leq x\leq 10$, and I have 2 parents with $x$-values given by $p_{1} = 2.55$ and $p_{2} = 9.92$, then we produce 3 children with the following $x$-values:

$$c_{1} = 6.235$$ $$c_{2} = -1.135$$ $$c_{3} = 13.605$$

As can be seen, child 1 will always be within the problem bounds since it's simply an average of its parents, however children 2 and 3 have $x$-values that are outside the bounds of the problem $(0\leq x\leq 10)$. As such, what I then do is simply have a loop that adds 1 to the value of child 2 and subtracts 1 from the value of child 3 until they go back within bounds, and then carry on with the rest of the algorithm. But this seems like a "cheap trick". As such, I was wondering if better methods are used to deal with children/offspring that have values outside of the problem bounds, or if my method is actually acceptable.

Answer 1

Anything is acceptable. These are all heuristics; all that matters is results (i.e., whether it helps you find a good solution to the problem, and how quickly it does so).

One standard method is to "clip" all values to be within the bounds. In other words, if the value is smaller than 0, you replace it with 0; if it is larger than 10, you replace it with 10. This ensures that the value will be within bounds.

There are other methods as well. For instance, you could let $y = 10 \sigma(x)$ where $\sigma(x) = 1/(1+e^{-x})$. You apply genetic programming to the values $x$ (so you do mutation and crossover operations on the $x$ values), but then you calculate $y$ and use that as the actual output. Note that $x$ can be any real number ($-\infty < x < \infty$) and the definition of $y$ will ensure that $0 \le y \le 10$.

Answer 2

In GAs, there are two main strategies for generating new solutions:

1. Ensuring solutions are feasible (i.e. meet the problem constraints).

2. Allowing infeasible solutions to be generated and then repairing them.

The latter can often be preferable, particularly when good solutions lie on the boundaries of the feasible region.

Here is a survey of alternative methods for repairing infeasible solutions.