next up previous
Next: Looking at chromosomes Up: Doing GAs with Previous: Creating chromosomes

Genetic Operators

 

Genetic operators are used in genetic algorithms to generate diversity (mutation-like operators) and to combine existing solutions into others (crossover-like operators). The main difference among them is that the former operate on one chromosome, that is, they are unary, while the latter are binary operators. In GAGS, genetic operators need not be coerced into the mutation/crossover paradigm, they are just functions that act on chromosomes.

In GAGS, operators constitute a class, that is, they are not methods of the chromosome class as is usual. That means that they can be created, destroyed and changed in runtime, and besides, that they can be subclassed to create new operators. This class is designed to act as a functor, i.e., function-syntax objects, which have operator () overloaded; this is only syntactic sugar, but allows to approach the looks of the C++ implementation to the actual algorithm.

They act in two different ways: non-directed, which means that they act on a random part of the chromosome, or directed, that is, they act on a preselected part of the chromosome. Besides, many operators consider the chromosome is divided in chunks, usually called genes; the size of those chunks must be pased as a parameter to their constructors.

Some operators are variable-length operators: they alter the length of the chromosome; chromosome length is always computed in every method that needs it, which means that GAGS is prepared for variable-length chromosomes. Length is always change by a discrete amount of genes. Note also that binary operators acting on variable length chromosomes can also change the length of the resulting chromosome.

An example that includes binary and unary operators is as follows

#include <genop.hpp>            // Chromosomes already included

main () {
    const unsigned NUMGENES = 4;
    const bitLength_t SIZEGENES = 3;
    seed_random( time( (time_t) 0 ) );// From randcl
    chrom aChromosome( NUMGENES*SIZEGENES ); // Create chromosome
    cout << "aChromosome\t\t\t" << aChromosome << endl;
    genOp creeper( SIZEGENES, genOp::CREEP ); // Apply unary genOp
    creeper( &aChromosome );
    cout << "aChromosome creeped\t\t" << aChromosome << endl;
    genOp mutator( (mutRate_t) 0.1 ); // Another unary genOp
    mutator( &aChromosome );
    cout << "aChromosome mutated 0.1\t" << aChromosome << endl;
    genOp SGA2pt( (unsigned char) 2 ); // Binary genOp, 2-point crossover
    bitString aBS ="111111111111"; // 
    chrom anotherChrom( aBS );  // Define other Chromosome from string
    cout << "Crossovering with anotherChrom\n\t\t\t" 
         << aChromosome << "\n\t\t\t" << anotherChrom << endl ;
    SGA2pt( &aChromosome, &anotherChrom );
    cout << "Result\t\t" << aChromosome << endl;
}

This program defines two unary operators: creeper, which changes a gene by plus or minus one and mutate, which does the usual thing; and a binary operator, SGA2pt, a simple two point crossover, and applies them to the chromosomes defined. A gene has been defined as a 3-bit segment, and each chromosome has got 4 genes. Output would look like this:

aChromosome             100011011110
aChromosome creeped     100010011110
aChromosome mutated 0.1 100010011010
Crossovering with anotherChrom
                        100010011010
                        111111111111
Result                  100010011110

Al The genetic operator type is computed in two different ways: if its constructor has got unique parameters, the genetic operator type is deduced; if not, typed enums are used. There are 9 predefined operators, shown in box 1

  figure44
Figure 1: Genetic operators and modes.  

Using the modes shown in table 1, genetic operators use three different constructors:

 genOp( mutRate_t _rate,
        genOpMode _mode = MUT);   // Mutation and uniform crossover
 genOp( bitLength_t _lenBits,
        genOpMode _mode = TRANSP); // Most operators acting on genes
 genOp( unsigned char _numPts  ); // number of xOver points > 1

Genetic operators can also be applied in a directed way, by using the applyAt method

    const unsigned toKill = 1;
    chrom thisChrom( "111000111000");
    genOp killer( SIZEGENES, genOp::KILL);
    killer.applyAt( toKill*SIZEGENES, &thisChrom );
    cout << "Result\t\t\t" << thisChrom << endl;

Once again, you will not be able to solve many problems with chromosomes if the only thing you can do is watch its binary face and change it at will. Usually, running a genetic algorithm involves decoding a chromosome, gene by gene, and applying some function to it. We will show how to do this in the next section.


next up previous
Next: Looking at chromosomes Up: Doing GAs with Previous: Creating chromosomes

J.J. Merelo Guervos
Fri Aug 22 12:58:28 MDT 1997