1
$\begingroup$

I am optimising function that can have both positive and negative values in pretty much unknown ranges, might be -100, 30, 0.001, or 4000, or -0.4 and I wonder how I can transform these results so I can use it as a fitness function in evolutionary algorithms and it can be optimised in a way that, for example, it can go from negative to positive along the optimisation process (first generation best chromosome can have -4.3 and best at 1000 generation would have 5.9). Although the main goal would always be to maximise the function.

Adding a constant value like 100 and then treating it simply as positive is not possible because like I said, the function might optimise different ranges of results in different runs for example (-10000 to +400 and in another run from -0.002 to -0.5).

Is there a way to solve this?

$\endgroup$
3
  • 1
    $\begingroup$ What make you think that you can't use negative number in your fitness function ? The objective of the fitness function is to tell how much your solutions are close to the optimum solution so that you can rank them. From what you are describing it look like your function is doing exactly this or am I missing something ? $\endgroup$
    – kirua
    Feb 8 at 15:55
  • $\begingroup$ @kirua in evolutionary algorithms, choice of chromosomes to the new population is based on their scores from the fitness function, to achieve we take fitness function score of each chromosome and divide it by sum of all fitness function results and if we add negative values it will simply not make sense, because sum will be lower than it really should be. $\endgroup$
    – Makintosz
    Feb 8 at 18:49
  • $\begingroup$ You can always try and see if taking the logarithm of the objective function improves your situation. This makes them positive and their distribution uniform (if it was exponential before). Might make sense if you have such a huge range of values. Also maybe you can somehow normalize (e.g. divide by the range between highest and lowest value) if the range changes that much from iteration to iteration. After all, you only need to compare the members of each generation to each other. $\endgroup$
    – Mafu
    Feb 10 at 0:00
0
$\begingroup$

If I understand correctly your problem, you always want to maximize some function $h(x)$, which is defined as follows $h: \Gamma \rightarrow \mathbb{R}$, where $\Gamma$ is the space of genotypes. However, at every generation $g$, you don't know exactly $h(i)$ of each individual $i$, i.e., maybe in one generation $g$, all $h(i)$, for $i=1, \dots, N$ (where $N$ is the size of the population), are negative, but in the next generation $g+1$, due to the mutations and crossovers, that may not be the case anymore, so you don't know how to shift $h(i), \forall i$, so that they are all positive and you can compute the probability of being selected, assuming you are using the fitness proportionate selection.

If my intepretation is correct, then, at every generation $g$, you just need to find $w = \operatorname{min}_i h(i)$, then shift all $h(i)$ by adding $|w| + \epsilon$ (where $\epsilon$ can be zero or a very small number) to all $h(i)$, so you would compute the fitness as follows $f(i) = h(i) + |w| + \epsilon$, for all $i$. Here are all the steps to compute the probability of individual $i$ being selected $p(i)$

  1. $w = \operatorname{min}_i h(i)$
  2. $f(i) \leftarrow h(i) + |w| + \epsilon, \forall i$
  3. $p(i) \leftarrow \frac{f(i)}{\sum_{j=1}^{N} f(j)}, \forall i$

This technique is known as windowing, which I have used in the past to solve the exact same problem that you seem to be trying to solve (check it here).

$\endgroup$
3
  • $\begingroup$ In one generation there can be chromosomes with both positive and negative values, not as you assumed all must have one sign inside one generation. But it looks like the solution of adding absolute value of the generation's minimum would actually work. $\endgroup$
    – Makintosz
    Feb 9 at 6:00
  • $\begingroup$ @Makintosz I assumed that there can be both positive and negative values of $h(i)$ in one generation. If you shift by the absolute value of the smallest $h(i)$, you make all positives, and that allows you to convert the fitness into a probability of being selected. That's the idea. $\endgroup$
    – nbro
    Feb 9 at 11:14
  • $\begingroup$ ahhh ok, I was misslead because you wrote: "ALL h(i), for i=1,…,N (where N is the size of the population), are negative" and "so that they are ALL positive and you can compute the probability". But it doesnt matter, I will try the solution later. $\endgroup$
    – Makintosz
    Feb 9 at 12:27

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.