3
$\begingroup$

I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$.

The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.

What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ If you don't necessarily need a single function, you could minimize by a first, then by b, then by c, fixing the respective variable after each step. $\endgroup$
    – Andreas T
    Commented May 8, 2016 at 10:59
  • $\begingroup$ @AndreasT think of a fitness function in genetic algorithm. Given a solution I need to be able to tell directly how good it is. $\endgroup$
    – user5539357
    Commented May 8, 2016 at 13:37
  • $\begingroup$ You have just defined a goal function. Why does the goal function have to be numeric? Can't you use any partially ordered set? $\endgroup$
    – Yuval Filmus
    Commented May 8, 2016 at 14:09
  • $\begingroup$ @YuvalFilmus because if I decided to solve the problem using a genetic algorithm, I'd have to define a fitness function, that describes how good a solution is. And I'm wondering if it's possible to do. $\endgroup$
    – user5539357
    Commented May 8, 2016 at 15:32
  • 1
    $\begingroup$ The question is whether your fitness function has to be numeric (a number), or just an abstract datatype that supports comparisons. $\endgroup$
    – Yuval Filmus
    Commented May 8, 2016 at 15:48

2 Answers 2

Reset to default
3
$\begingroup$

If you know the minimum and maximum values for $a,b,c$, you can use a weighted linear combination. e.g., if $a,b,c \in [0,1000]$ (they are all between 0 and 1000), then you can use the objective function

$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$

Minimizing this function is guaranteed to be optimal under your partial order.

Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic. It's not guaranteed to give optimal results, but it might be good enough in your particular application.

Improve this answer
$\endgroup$
1
$\begingroup$

think of a fitness function in genetic algorithm. Given a solution I need to be able to tell directly how good it is

You can use vectors instead of simple scalars.

Comparison of fitness values should be based on lexicographical order:

$$(a,b) ≤ (a′,b′) \iff a < a′ \lor (a = a′ \land b ≤ b′)$$

The selection scheme is probably the main problem: tournament selection, truncation selection, ranking selection are not affected by this change; fitness proportionate selection (roulette wheel) can present difficulties.

The other steps of a classical genetic algorithm (recombination and, for steady state algorithms, replacement) stay the same.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.