I have a multi-objective optimization problem that I am applying genetic algorithm (GA) to solve. Currently, there are only 2 objectives:
- minimize cost
- 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.