# How do you avoid dominant solutions in multi-objective simulated annealing?

Imagine an RPG game were you can cary N items, and you want to maximise your damage, attack speed and armour, given a set of items.

I implemented simulated annealing where a permutation simply replaces a random item, and I compute the energy with some damage calculations.

This works well for attack speed and damage, and tends to find items that provide both. But adding armour never gives good results.

I have tried a weighted sum, but the result is always N armour items or N weapons.

This paper suggests picking a random or average energy function, but this gives very bad results as soon as I use conflicting objectives.

Are there good probability functions for this task, or should I use another algorithm?

• The problem with weighted sums is that when one weight is larger, that factor is always more important: in the target function `f(armour, attack) = 0.6*attack + 0.4*armour` with `f, armour, attack ∈ [0, 1]` attack would always be more important, so the best solution would be `f(armour=0, attack=1)` (you don't need SA to tell you that…). Instead, you probably want to penalize solutions that under-represent any input, but that requires a nonlinear function, e.g. `f(arm, att) = arm^1.2 * att`. – amon Aug 16 '15 at 10:12
• @amon If you can elaborate a bit on creating a non-linear "sum", I'd gladly accept it as an answer. – Pepijn Aug 16 '15 at 11:22

You say "maximise your damage, attack speed and armour". I think the answer to your question is to accurately define what this means.

You can only "maximise" a single value. If you have multiple values you need to provide a function to turn them into this single value you want to maximise.

What makes a "good" function for this is entirely application specific. When you say "random or average energy functions" gives bad results - what makes these results bad?

I think you end up a bit stuck if you say you want to "maximise" something and then say you also want to exclude certain types of solutions which do maximise that thing. So the key is to combine your values in a way that actually matches what you want to achieve rather than try to predetermine what outcomes are valid in the first place - if that makes sense!?

EDIT: If you took all your 3 values and normalised them to the range [0, 1] and then pass these into a quadratic function (e.g. 4x - 4x^2) and add the results then you are reducing the value of higher inputs (i.e. 1 maps to 0), so you are more likely to get solutions that combine inputs around (0.5).

But as mentioned all you're really doing here is picking a function to produce an output. What you should do is pick the function based on the "real world problem" - i.e. how the relative inputs of attack speed, armour etc perform in the game.

• Yea, the idea with the weighted sum was that I could configure how important armour was compared to attack damage. When I say bad, I mean no damage and no armour, not even a bit, it seems to just oscillate randomly. I'm trying to find a function that lets me trade off armour for attack. – Pepijn Aug 16 '15 at 9:57
• But that function needs to be based on your needs. Otherwise you're not really solving your original problem, the function you choose is determining the outcome. The problem you want to solve and the function you pick are essentially the same thing. As an example I'll add an idea that may generate results in the range you want - but as I've said this is just choosing the function to generate an outcome - which is of questionable value. – James Gaunt Aug 16 '15 at 10:10
• I'm not sure how you would normalise an unknown value. And it seems weird to say that high values can have a low energy. Maybe I should subtract the variance from the average, so that similar weighted sums score higher than dissimilar values. – Pepijn Aug 16 '15 at 11:19
• You need to normalize them somehow to compare them. If damage ranges from 0 - 10 and armour from 0 - 10000 clearly you need to somehow make them comparable. Yes agree the solution is weird - but that's the cost of trying to force the desired outcome onto it. – James Gaunt Aug 16 '15 at 14:09

Everyone who said your utility function needs to track the actual problem domain is correct. Here’s my advice on how, specifically, to do that.

The utility of weapons and armor in a D&D-like RPG is that they help you win battles. How useful at the margin better armor or a better weapon are is going to depend on what you’re fighting: more damage is useless if you already are killing a goblin with every hit, for example. So you need to come up with a reasonable list of encounters and a way to estimate how good a kit is against each encounter. This probably means calculating how likely you are to hit that opponent, how likely it is to hit you, and how much of the other’s health each of you will knock off with each hit. If you hit 80% of the time for 20 points of damage and it has 50 health, you’d expect, on average, to need 2.5 hits to kill it and 3.125 rounds to get those 2.5 hits.

The ratio of expected-rounds-for-you-to-kill-it to expected-rounds-for-it-to-kill-you is probably a good heuristic to use in a combat system derived from D&D, and you can probably figure it out with some basic statistics, but it can fail in some situations: it really doesn’t help you to do 90% damage instead of 51% if you’ll still need two hits to kill it. A more complex alternative would be to calculate instead how likely you are to win the fight. First calculate how likely the opponent is to die in one hit, two, three and so on; then how likely you are to have one hit on the first round, one hit on the second, two hits on the second, and so on, up to a reasonable number of rounds. Repeat for its attacks on you, and you can calculate the odds that each of you will die on each round.

For a much more complicated combat system, where generating a probability tree would be infeasible, you might need to do some Monte Carlo simulations of battles to get an accurate optimization.

The simple heuristic you want, though, is probably something like, (YourChanceToHit * YourDPS * YourHealth) / (TheirChanceToHit * TheirDPS * TheirHealth). That captures the intuition that the following are roughly equivalent: hitting twice as often, needing half as many hits to kill them, getting hit half as often, or surviving twice as many hits.