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

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.

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.