The most important objects when discussing genetic algorithms are chromosomes (or individuals), and populations.
A chromosome 
may be defined as a vector of genes, 
, where n is the length
of the chromosome (the number of genes). Furthermore, an individual 
(sometimes called an agent) is defined as a chromose during a certain
interval I, formally 
. In order to
emphasize the temporal connection we will whenever appropriate write
for an individual. Conversely, we will also write 
or
for the interval during which the individual is `alive';
with a preference for the former syntax.
Central to the genetic algorithm is the concept of fitness. We define a variant of the standard fitness as follows.
When we want to emphasize the fitness of a certain individual
we use the expression 
. In terms of the logic the
fitness is a number, which may be manipulated using standard numerical
operators. This means that we have a two-sorted logic, in line with that of
Bacchus' [106] probabilistic logic with its probability operator. We
will omit the specifier whenever the distinction is immaterial.
In this way we have equated the phenotypic fitness (the relative ability of an organism to survive in its current environment) with the probability of occurrence (probabilistic fitness); the genetic fitness (the relative ability of a an organism to propagate its genotype) is used when determining which agents may reproduce [131] . The genetic fitness is what connects the agent to the problem at hand, i.e. the problem-specific connection to the chromosome and its genes with their encoded information.
Strictly speaking, there need be no one-to-one connection between the two types of fitness. For example, consider pleiotropy, the effect that a single gene may simultaneously affect several phenotypic traits, and polygeny, the effect that a single phenotypic trait may be determined by the simultaneous interaction of many genes [187] .
Indeed, as has been pointed out by Nettleton [438] , citing Lewontin [368] , the interaction between genotypic space G and phenotypic space P is complex, and may be characterised by four functions between the phenotype and genotype space. In this work we will simply assume that they are connected. This leads us to formulate the following assumption.
To see that such an assumption is necessary, one need only consider a lethal mutation (on the genotypic level) that makes the individual extremely fecund (on the phenotypic level). Then the mutation would very quickly spread, but would make the population very 'unfit', in terms of the genotypic fitness and at time same time very 'fit' in terms of the phenotypic fitness (since it would be exhibited by a large proportion of the population). In other words, there is no necessary correlation, either positive or negative, between the phenotypic and genotypic fitness. Of course, this is only true on the individual level; on the population level there must be a positive correlation, otherwise the population dies out.
Using the CA we may omit the qualifier genetic or phenotypic, except where we want to explicitly emphasize which kind of fitness we are referring to.
In practice, we use a fitness function (see below) that produces a value that is used to grade individuals. This value may (and often is) be called fitness as well; strictly speaking, it is an external fitness, one that is used by the selection function in determining which individuals shall survive to the next generation. In other words, the probabilistic fitness may be seen as the external fitness normalised to the open interval (0,1] after selection has taken place. The reason for an open interval is clear from the definition of a population below. This means that the probabilistic fitness cannot be used for selection, as we shall see.
Finally, we define a population as follows.
is normally very small compared with 
, i.e. 
.
The population 
within a base interval I is then given by
