## ECJ-INTEREST-L@LISTSERV.GMU.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Re: Generation count in Tournament Selection?

From:

Date:

Mon, 30 Oct 2006 19:21:36 -0500

Content-Type:

text/plain

Parts/Attachments:

 text/plain (102 lines)
 ```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 well. 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. Sean 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 > change? > > > > 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. >> >> Sean >> >> 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. >>>> >>>> Sean >>>> >>>> On Oct 30, 2006, at 8:41 AM, Serethos wrote: >>>> >>>>> I am wondering how a Generation is defined in ECJ if Tournament >>>>> Selection >>>>> is used. Is there a generation change, after _one_ tournament >>>>> has been executed >>>>> or after enough individuals have been produced so that >>>>> numWinners == numIndividualsOfPopulation? >>>> >> ```