They're not. Individuals are evaluated only if their evaluated flag
is turned off; that is, you've requested that they be reevaluated.
Your description of tournament selection is somewhat _true_, but only
formally so and it's *far* from the big deal of the procedure. Let's
say I have 100 individuals, and I am generating a new population of
100 individuals. In that procedure I use tournament selection of,
say, 2, with just mutation. The probability that a certain
individual will *not* be picked in one selection operation is (99/100)
^2. The probability that this will continue to be true for that
individual over all 100 independent operations is (99/100)^200, or
0.13397967485796172. So roughly 87 individuals out of the 100 will
require evaluation if you do it lazily, and you've seen an
improvement of just 13% over evaluating everyone beforehand. If you
increase the tournament size to 7, you get just a 0.1% improvement.
This general line of reasoning holds for steady-state evaluation as
Hope my math's right there.
The big deal behind tournament selection, and various ranked and
truncation selection methods, is that they're *nonparametric* --
they're not based on a parametric statistical model of the actual
fitness values of the individuals. Instead they're based only on the
rank ordering of individuals relative to one another. This allows
for a number of significant statistical advantages over parametric
methods, notably roulette selection. For example, late in the
evaluation procedure, your whole population may have fitnesses in the
high .999 range. Roulette selection will view these as essentially
identical, producing uniform selection. But nonparametric methods
will still view them as all different from one another because all
they look is the rank order.
At this point this is a discussion which is out of ECJ's realm and
more specifically in EC -- it might be a question better further
pursued on the genetic programming mailing list, so as to keep to
ECJ's bandwidth contract.
On Oct 30, 2006, at 4:17 PM, Serethos wrote:
> I am not sure if I got the point. The big deal of Tournament
> selection is that you
> evaluate a very little amout of individuals at once. This means,
> once a population is
> initialized I have only to measure the fitness of the guys taking
> the tournament.
> The default tournament size is 7, why do why _all_ individuals are
> sent to the
> problem's evaluate method although most of the individuals did not
> Sean Luke wrote:
>> Ah, I understand. ECJ's steady-state evaluator does not support
>> lazy evaluation. It doesn't mean it can't be hacked in -- but
>> it's not there by default.
>> While it's true you can generate a population from a previous
>> population without having to create all the individuals, that
>> doesn't help you much when you're trying to identify the best
>> individual you discover along the way though.
>> On Oct 30, 2006, at 2:12 PM, Serethos wrote:
>>> Sure its all a matter of definition. But afaik tournament
>>> selection is one of the most popular
>>> steady state selection, because not all individuals are
>>> evaluated. there is no replacement
>>> of a whole generation (if you assume, the not evaluated
>>> individuals do not use reproduction).
>>> Sean Luke wrote:
>>>> Generations are independent of the selection procedure. In
>>>> generational selection, individuals are evaluated, and then
>>>> through a process of selection and breeding, a new population is
>>>> formed. Once the new population is in place, it replaces the
>>>> old one and the cycle repeats. That's one generation.
>>>> The only exception to this is in steady state evolution, where
>>>> ECJ used to abuse the "generation" marker to mean something else
>>>> -- but we've since changed that and there is a formal definition
>>>> in steady state evolution as to what everything is.
>>>> On Oct 30, 2006, at 8:41 AM, Serethos wrote:
>>>>> I am wondering how a Generation is defined in ECJ if Tournament
>>>>> is used. Is there a generation change, after _one_ tournament
>>>>> has been executed
>>>>> or after enough individuals have been produced so that
>>>>> numWinners == numIndividualsOfPopulation?