Cover of Swarm Intelligence Book

Evolutionary Computation Algorithms

The following classes are available (all discussions assume CIlib version 0.5, and therefor assumes the same directory structure as used in CIlib):

  • Genetic Evolutionary Algorithm [ Hide ]

    Find below the XML specification for a Genetic Algorithm (sections 8.1 and 9.1).

    <simulator>
      <algorithms>
        <algorithmid="ga"class="ec.EC">
          <iterationStrategyclass="ec.iterationstrategies.GeneticAlgorithmIterationStrategy">
            <crossoverStrategyclass="entity.operators.crossover.UniformCrossoverStrategy">
              <crossoverProbabilityclass="controlparameter.ConstantControlParameter"parameter="0.5"/>
            </crossoverStrategy>
            <mutationStrategyclass="entity.operators.mutation.GaussianMutationStrategy"operator="+">
              <mutationProbabilityclass="controlparameter.ConstantControlParameter"parameter="0.3"/>
            </mutationStrategy>
          </iterationStrategy>
          <initialisationStrategyclass="algorithm.initialisation.ClonedPopulationInitialisationStrategy">
            <prototypeEntityclass="ec.Individual"/>
            <entityNumbervalue="50"/>
          </initialisationStrategy>
        </algorithm>
      </algorithms>
      <problems>
        <problemid="griewank"class="problem.FunctionMinimisationProblem">
          <functionclass="functions.continuous.Griewank"domain="R(-600, 600)^30"/>
        </problem>
      </problems>
      <measurementsid="measurements"class="simulator.MeasurementSuite"resolution="5"samples="30">
        <addMeasurementclass="measurement.single.Fitness"/>
        <addMeasurementclass="measurement.single.Diversity"/>
        <addMeasurementclass="measurement.single.FitnessEvaluations"/>
      </measurements>
      <simulations>
        <simulation>
          <algorithmidref="ga">
            <addStoppingConditionclass="stoppingcondition.MaximumIterations"maximumIterations=" 1000 "/>
          </algorithm>
          <problemidref="griewank"/>
          <measurementsidref="measurements"file="data/griewank.ga.p_50.cross_0.5.mutation_0.3.txt"/>
        </simulation>
      </simulations>
    </simulator>

    Click here to download this file.

    The XML file above provides a specification for a simulation which executes a Basic Genetic Algorithm (Algorithm 8.1 on page 128) on the griewank function (page 556, Equation A.15). Using the simulator provided with CIlib and running the command ./simulator.sh xml/ga.xml for Linux users or simulator.bat xml\ga.xml for Windows users, the simulation as specified in the above XML will be executed, and the results of the simulations are written to data/griewank.ga.p_50.cross_0.5.mutation_0.3.txt.

    How is a simulation defined? A simulation is specified using the simulator tag.

    What are the main things that need to be specified for a simulation? For each simulation, you need to specify the algorithms that are used in the simulation, the problems on which these algorithms will be applied, the measurements used to extract information from a simulation, and then lastly, the specific simulations need to be specified (this is which algorithms are applied to which problems). More than one algorithm can be specified. The same for the problems, measurements and simulations.

    How is the genetic algorithm specified? An algorithm is specified using the algorithm tag. The main CIlib class from which all evolutionary computation algorithms inherit is the EC class in the ec package. The algorithm is therefore specified as ec.EC (package.class). The next step is to specify the iteration strategy used, which is the GeneticAlgorithmIterationStrategy to be found in the ec.iterationstrategies package. The only alternative at this stage is the DifferentialEvolutionIterationStrategy class.

    How do you specify the crossover operator? Two crossover operators have been implemented for the genetic algorithm iteration strategy in CIlib, namely the One-Point (see Algorithm 9.2 on page 145) and Uniform crossover (see Algorithm 9.4 on page 146) operators, They are implemented in the entity.operators.crossover package. The default crossover strategy for the GeneticAlgorithmIterationStrategy class in CIlib is UniformCrossoverStrategy, but can be changed via the crossoverStrategy tag. This simulation specifies the uniform crossover operator.

    How do you specify the mutation operator? Three mutation operators have been implemented for the genetic algorithm iteration strategy in CIlib and they are the Uniform (see Algorithm 9.6 on page 155), Gaussian (see section 9.3.1 on page 154) and Cauchy mutation operators, They are implemented in the entity.operators.mutation package. The default strategy for the GeneticAlgorithmIterationStrategy class in CIlib is GaussianMutationStrategy, but can be changed via the mutationStrategy tag. This simulation specifies the Gaussian mutation operator.

    The number of individuals? This is done by invoking the the ec.EC.setInitialisationStrategy method using the initialisationStrategy tag. Within it, you would need to specify that the entities to be used in the algorithm are the individuals of a GA population by setting the prototypeEntity to ec.Individual. You can then specify any number of entities via the entityNumber tag. For this simulation, 50 individuals are used.

    How are stopping conditions specified? This is done using the addStoppingCondition tag to the algorithm, either at the algorithm's point of definition or within the algorithm reference in the simulation. All stopping conditions are implemented under the stoppingcondition package. For this simulation, the genetic algorithm will be stopped after 1000 iterations (generations) of the algorithm have been executed.

    How do we specify the parameters of the crossover and mutation operators within the genetic algorithm? These are specified within the corresponding tags for crossoverStrategy and mutationStrategy. For crossover, the crossoverProbability tag is used to specify the probability based on which a given bit (gene) in an individual will be swapped in the crossover operation. The mutationProbability specifies the probability at which mutation is applied to each offspring gene. The operator tag defined for the mutationStrategy determines whether the mutation is achieved by adding or multiplying the randomly generated mutation variable to the current gene value. You do not have to specify all of the above. What is given above are implemented as defaults. Should you want to change the default values for any aspect, only then do you need to specify these as illustrated in the XML example. Also, have a look at the ec of CIlib and work out what else could be modified and how.

    How are problems specified? All problems are implemented in the problem package. This package currently allows for a number of different problem types, including FunctionMinimisationProblems and FunctionMaximisationProblems. The former is specified for this simulation, using the problem tag. Function types to be optimised are implemented in the functions package. In this case, continuous functions are used. The actual functions are implemented in the functions.continuous package, where you will find the Griewank class, which is the prolem that we will be optimising here. The domain of each function can be defined using the domain attribute. The specified domain is the default for this function, and is given as a 30-dimensional problem, with floating-point parameters (specified by the "R"), each within the range [-600,600].

    How is information extracted from a simulation? To do this, you need to use a Measurement, implemented in the measurement package. For this simulation, 3 measurements are used, namely the Fitness of the best entity (individual), the number of FitnessEvaluations, and the Diversity of the population. Measurements are written to a file at frequency specified by the resolution attribute. In this case, information is written to a file each 5th iteration. Through the samples attribute, you can specify how many times the algorithm has to be executed on the problem (starting from different random initial conditions). In this case, the genetic algorithm will be executed 30 times for the problem specified (Griewank). Results for each simulation will be written to the file specified in a tab-delimited format. First, the fitness of the best particle will be given for each simulation, then the swarm diversity for each simulation, then the number of fitness evaluations for each simulation. Each line contains this information for the specific iteration.

    How is the output file specified? Using the measurements tag, the measurements to use is specified via the "measurements" idref attribute, and the output file is specified using the file attribute.

    The actual simulation is effected via the simulations tag, where more that one different simulation can be specified. For each simulation the algorithm, the problem, and the measurements need to be specified.

    Exercise: Download CIlib, and install it (remember you need JDK 1.6). Then, using the provided simulator, execute the above XML file, and see what happens. Then, try to change some of the parameters and behaviours, before you look at the rest of the algorithms and explanations on this site. Browse through the packages and see what options are available.

  • Differential Evolution [ Show ]