Instance Selection Using Evolutionary Algorithms: An Experimental Study - Advanced Techniques in Knowledge Discovery and Data Mining - page 138

1. Select two parents from the population P .
2. Create an offspring using crossover and mutation.
3. Evaluate the offspring with the fitness function.
4. Select an individual in P , which may be replaced by the offspring.
5. Decide if this individual will be replaced.
In Step 4, one can choose the replacement strategy (e.g., replacement of the
worst, the oldest, or a randomly chosen individual). In Step 5, one can choose the
replacement condition (e.g., replacement if the new individual is better or
unconditional replacement). A widely used combination is to replace the worst
individual only if the new individual is better (this is the one we have assumed in
our experiments).
The major difference between SGAs and GGAs is that for each P members of
the population generated in the GGA there are 2• P selections. Consequently, the
selection strength and generic drift for an SGA is twice that of the GGA. The SGA,
therefore, appears twice as fast, although it can lose out in the long term because it
does not explore the landscape as well as the GGA.
5.4.3 CHC Algorithm [12]
During each generation, the CHC algorithm uses a parent population of size N to
generate an intermediate population of N individuals, which are randomly paired
and used to generate N potential offspring. Then a survival competition is held
where the best N chromosomes from the parent and offspring populations are
selected to form the next generation.
CHC also implements a form of heterogeneous recombination using HUX, a
special recombination operator. HUX exchanges half of the bits that differ
between parents, where the bit positions to be exchanged are randomly determined.
CHC also employs a method of incest prevention. Before applying HUX on two
parents, the Hamming distance between them is measured. Only those parents that
differ from each other by some number of bits ( mating threshold ) are mated. The
initial threshold is set at L /4, where L is the length of the chromosomes. When no
offspring are inserted into the new population the threshold is reduced by 1.
No mutation is applied during the recombination phase. Instead, when the
population converges or the search stops making progress (i.e., the difference
threshold has dropped to zero and no new offspring are being generated that are
better than any members of the parent population), the population is reinitialized
to introduce new diversity to the search. The chromosome representing the best
solution found over the course of the search is used as a template to reseed the
population. Reseeding of the population is accomplished by randomly changing
35% of the bits in the template chromosome to form each of the other N -1 new
chromosomes in the population. Search is then resumed.
The CHC generally does well with small populations. Limited resources and
the computational cost of the simulations led to our use of small populations and
selection of the CHC for this work.