How do I design this multi-objective fitness function for use with genetic algorithm?

Question

I have a multi-objective optimization problem that I am applying genetic algorithm (GA) to solve. Currently, there are only 2 objectives:

1. minimize cost
2. maximize validity

The cost minimization is simple, it is simply $\sqrt{(c - t)^2}$, where $c$ is the cost and $t$ is an arbitrary, user-provided value (e.g. 1000, 2500, 900, etc.).

The validity maximization is also simple as it takes the chromosome (solution candidate) and maps it to the range $[0, 1]$, with 1 being better.

For a chromosome/solution, let's denote the associated cost as $p$ and the validity as $v$. For a chromosome $x$, the fitness function (for which I am trying to minimize) $f(x)$ could be defined as $f(x) = p + \frac{1}{v}$.

• if $p$ is low, then $f(x)$ is low or if $p$ is high, then $f(x)$ is high
• if $v$ is low, then $f(x)$ is high or if $v$ is high, then $f(x)$ is low

For the term $\frac{1}{v}$, the highest value $v$ can ever be is 1 if $v = 1$, and infinity $\infty$ if $v = 0$. However, when, $v - 0.0001 < \epsilon$, then we simply set $v = 0.001$, so $\frac{1}{v} \in [1, 1000]$. On the other hand, $p$ is in the range $[0, r]$ where certainly $r > 0$ and possibly $r \gg 1000$.

Both terms, $p$ and $\frac{1}{v}$ can be very large and dominate the evaluation of $f(x)$. We might get the following solutions.

• low cost, low validity //bad solution
• low cost, high validity //best solution
• high cost, low validity //bad solution
• high cost, high validity //ok solution

Since $p$ and $\frac{1}{v}$ are not in the same range, we could get a "good" fitness evaluation but is invalid. For example,

• if $p = 1$ and $v = 0.5$, then $f(x) = 3$ //lower cost, lower validity
• if $p = 2$ and $v = 0.8$, then $f(x) = 3.25$ //higher cost, but, higher validity

In this example, GA should favor the first solution since it has a lower score, but, it has a lower validity. So, I need to punish solutions with low validity. I could weight these terms as follows $f(x) = w_p p + w_v \frac{1}{v}$, where $w_p$ is the weight for $p$ and $w_v$ is the weight for $v$, but I do not think it's trivial to specify the weights or will work still (terms can still dominate and wash out the effects).

For now, the best I can do is specify a hard threshold $\theta$ for $v$ to punish all chromosomes where $v < \theta$.

• $f(x) = p$ when $v > \theta$ //valid solutions should be evaluated according to how they deviate from $t$
• $f(x) = 2t$ when $v < \theta$ //invalid solutions should cost twice as much as the target $t$

Is there a better way to approach formulating the objective function? I believe this is how constraint-based optimization works in some sense anyways.

Answer 1

You have a few options. First, you can often just scale the objectives to the same range. If that's viable for your domain, it can work fine. It can be difficult if you don't have a good known range of each function, and you might not know the appropriate way to weight them individually.

The other major approach is to just abandon the idea of trying to combine the objective functions into a single function and instead do true multiobjective optimization. Instead of finding a single solution that maximizes some function $f(p, v)$, you search for a set of pareto optimal solutions. So you'd get some number of solutions, some very good at $p$, some very good in terms of $v$, and others at various points on the trade-off surface between the two.

Multiobjective evolutionary algorithms are a very well-studied area. There are several approaches you can find in the literature (NSGA and SPEA were early approaches, each with several enhancements made over the years; decomposition-based methods like MOEA/D are more recent methods that often perform well).