1
votes

I am reading up on an example of a very general genetic algorithm on this website and I have some questions.

  1. How do I handle negative fitness values ? I am unsure how roulette wheel selection would work if some chromosomes have negative fitness. Do I normalize all fitness values ? Scale it ? Is there a general equation that handles negative fitness?

  2. The fitness function to convert a minimization problem to a maximization one is F(x) = 1 / (1 + f(x)). I read somewhere that 1 is there to prevent F(x) from going to infinity. But what if f(x) turns out to be -1 ? So again, how do i prevent f(x) from becoming negative ?

  3. What happens if one of the chromosomes generate an infeasible solution ? For a very simple example, max(f(x) = x) where f(x) < 10. What if one of the chromosome has a solution of 11 ? Do I reject it, pick the second maximum value and end the iteration ? Or do I reject it and use the remaining chromosomes and continue reproducing ?

These are all very very general questions as I have just begun studying genetic algorithms. I hope someone can help me on this or send me a simple example handling all 3 scenarios above.

2
Hello, I have edited my question. I have also posted a link to the example that I was studying. The questions are all very general indeed but i have been unable to find the answers for it unfortunately. - cschua

2 Answers

1
votes

So, one at a time:

1. Negative fitness values

Negative fitness is a problem only if you use roulette wheel (or similar proportional) selection strategy. If you really want to use such a strategy then you need to somehow get positive fitness values. And there are several possibilities.

If you know the range of the original fitness values, say from -10 to +2 (I'm just drawing that out of thin air), you can just scale this range onto another range that is going to be positive.

If your range is not limited, e.g. from -infinity to +infinity, or you really don't know the range, then you cannot just scale as it might happen that the result would be negative. However, you can use a different monotonic transformation than linear scaling. For example, the hyperbolic tangent maps such a range onto the range -1 to +1. However, such a transformation has the drawback that the further the original fitness is from zero, the lower "resolution" such transformation has (naturally, as it maps an infinite range onto a finite one).

The third, and in my opinion the most elegant, solution is to transform the fitness using ranking - you sort the members of the population according to their original fitness from the worst to the best and their new fitness is just the position in this ordering, i.e. the worst individual would have a transformed fitness of 1, the second to the worst would have 2, etc. Then you have positive fitness values that have the same "resolution" regardless of where the individuals really are. However, it can also be a drawback, as you throw the original fitness values out of the window so if there was one individual that had an enormously large original fitness value compared to the other individuals, after the ranking it would have just 1 more than the second to the best individual.

Last but not least "workaround" is not to use roulette wheel selection strategy but a different one, e.g. tournament selection where you don't need the fitness values but just the ability to compare two individuals and say which one of them is better. It is very similar to the ranking I described above.

2. Maximisation/minimisation conversion

The transformation you described is one possible transformation. Basically any decreasing function can serve as such transformation, so pick one that gives you desirable properties. These could be the range of the transformation (e.g. you might want positive values), domain of the function (e.g. you don't want to divide by zero), etc...

Also, if you use tournament selection, you don't need to modify the fitness value at all, you just flip the comparison operator (or you don't flip it and just multiply the original fitness by -1).

3. Constrained solutions

Constraint satisfaction in evolutionary computation is quite a topic of its own. However, there are three major approaches:

  1. Penalize bad solutions - if a solution violates a constraint, penalize it. The simplest case is a "death penalty", i.e. such a solution receives the worst possible fitness so it is never selected (i.e. it is killed). If you can measure how much is (are) the constraint(s) violated, you can make the penalty proportional to that. However, the major drawback is, especially with the death penalty, that solutions that violate some constraint can, in fact, contain good building blocks but are killed because they had the misfortune of violating the constraint(s) too much. But is is usually very simple to implement.

  2. Safe encoding / correction operators

    a. Safe encoding - use such encoding of the solutions so that when you decode them for evaluation, you always get a feasible solution. There is a brilliant example for permutation problems: you need the solution to represent a permutation of elements, i.e. each element must be present exactly once. Instead of having the elements be used directly for evolution, instead you evolve a sequence of decimal numbers in the range [0, 1]. When you decode the solution you sort the numbers and their indexes from the original order then represents the permutation. Example - [0.33, 0.12, 0.77, 0.69] will be translated to [1, 0, 3, 2].

    However, it is often very hard to design such encoding and is is totally domain-dependent.

    b. Correction operators - if a solution violates a constraint, modify it so that it doesn't. In your case, if you have a solution of 11 when the maximum allowed is 10, just modify it so that it is 10, if your encoding allows you to do so.

    It is generally good to modify the solution as little as possible so you retain its building blocks. It may happen that there is no (simple) way to design the correction operators - ridiculous, exaggarated example: you evolve a big neural network and you want the output function to have 2 local optima; how would you modify the weights so that it has them? That is not simply possible.

  3. Multi-objective optimisation - you make new objectives out of the constraints. Instead of driving the evolution by the objective function, you drive it by the objective function AND by the degree of constraint violation at the same time. This is probably beyond your scope so I'll direct you to other sources. You want to look for multi-objective evolutionary algorithm(s). One such algorithm, a very popular one, is NSGA-II.

Final remark

As @IkechiMichael already said, evolutionary algorithms are not exact. In the end it's all about what works for your application. If you have enough time, just try what comes to your mind and you'll see.

0
votes

For your first and second questions, you have complete control over how your fitnesses are represented. If Normalization works for you, cool! If you can scale to between 0 and 1 and that solves your problem, fantastic!! Equations for finding fitness values are usually modeled in such a way that fitness values lie in the range 0 to 1. This isn't compulsory though. Lots of NP problems have upper and lower bounds that are yet to be determined, so it is difficult to represent their fitness values in such a way.

There are multiple approaches to handle chromosomes generating infeasible solutions. The solutions could be ignored, or the operation that generated it retried until a feasible solution is obtained, or the infeasible solution could even be used in hope of re-entering the solution-space in a more favorable area than previously explored.

Evolutionary Algorithms provide general rules. How you implement them is completely up to you.