fitness for coevolution - Computational Intelligence and Co-evolution

Message from discussion fitness for coevolution
MIME-Version: 1.0
Message-ID: <fa4d1506-c427-481d-8958-cb3aeae9c6a8@s8g2000prg.googlegroups.com>
Date: Sat, 15 Dec 2007 14:27:21 -0800 (PST)
User-Agent: G2/1.0
Subject: fitness for coevolution
From: phi <PhilipHings...@gmail.com>
To: Computational Intelligence and Co-evolution <coevolve@googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Hi all

We have discussed this topic before, but I have been thinking about a
specific application lately which I think provides a different
perspective on the question. I thought I'd ask what you all think.

The question is: what is the "correct" fitness function for co-
evolution?

Xin Yao gave a very nice plenary at CEC (http://www.cs.bham.ac.uk/~xin/
papers/cec07keynote.pdf) around this topic. His assumption is that the
"correct" fitness function is the expected payoff against a randomly
selected (according to some probability distribution) opponent.

However, I wonder if this is always appropriate. The example
application is a defence scenario. In a given scenario, with given
resources, one side - call it the blue team - wants to defend some
asset, for example. The other side - call it the red team - wants to
carry out a successful attack. Neither side knows the other's
strategy, but you can simulate the outcome given a blue and a red team
strategy.

The question for blue is how best to defend against an unknown attack
- for red it is how best to attack when the defence strategy is
unknown.

This looks like a problem ideally suited to a co-evolutionary
approach : co-evolve blue and red team strategies.

But what should the fitness function(s) be?

You might object that the problem is not well-posed, but in a real
situation, each side must do *something*, even if the problem isn't
well-posed!

To expand a bit: as the blue side, would you be satisfied with the
best outcome *on average*? What if some possible outcomes are *very
bad indeed*? Would it be better to choose a strategy that never does
worse than a certain level? Your answer might depend on what the
measure(s) of goodness are for a particular outcome too. (It could be
multi-objective and the outcomes could be noisy, but this is just
extra complication.) Conversely, as the red team, maybe you would
prefer a plan that provides at least a slim chance of a devastating
attack, rather than a strong chance of a moderately successful one.
Think of a terrorist cell.

I'm leaning here towards some combination of best, worst, and expected
outcome. This suggests to me a multi-objective approach (even it the
measure of goodness is single objective). Is much known about multi-
objective co-evolution? I know - check the literature! I'll do that.
(A quick look shows that co-evolution has been used as an approach to
multi-objective optimisation - but this is the other way around!) Then
again, perhaps some different kind of selection scheme would be the
way to go.

Anyway, I thought it was an interesting question and that I would try
to tap into your collective wisdom for a response.