Context Navigation

Genetic evolution property class

This is a work-in-progress to develop a CEL property class implementing a genetic evolutionary algorithm for use in game AI.

Everything in this document is subject to change. It is meant only as an explanation of what we are doing for anyone who's interested. We will try to keep it up-to-date as it continues to be developed. A very basic knowledge of genetic algorithms is assumed. The property class is designed to require the minimum of knowledge about genetic algorithms.

This is being developed for use in the game Ecksdee, but it is intended that it will be generic enough for many different applications.

Initially this genetic algorithm will be used to train the neural network in PcNeuralNet, but it could be extended to allow other types of property classes to be evolved.

Contact: Mat Sutcliffe <oktal@…>

Usage

Set the properties of the class to your desired values.

Call cel.action.Generate, which will evolve one generation using pcevolve_fitness to evaluate the fitness of each individual.

For each individual candidate genome in the population, pcevolve_fitness will be sent, which instructs the behaviour to evaluate the fitness of the individual.

When the fitness of an individual has been evaluated, call cel.action.ReturnFitness to return the result. Steps 3 & 4 will be repeated for each individual genome in the population.

When the fitness of every candidate genome has been evaluated, pcevolve_result will be sent, which tells the behaviour the overall fitness of the new population.

If the fitness is not yet good enough, return to step 2 to evolve another generation.

Call cel.action.Select to copy the genome with the highest fitness into the genome of the subject property class. Then save this genome. Evolution is complete.

If you want to evolve something else, call cel.action.Reset and then return to step 1.

Properties

The property class has the following mutable properties:

cel.property.population (long): The size of the population to use when evolving (i.e. the number of different genomes in each generation).

cel.property.subject (iCelPropertyClass*): The property class that will be evolved. Meaning, the property class that will be used to evaluate the fitness of each candidate genome. The object must implement iPcNeuralNet. Other property classes may be supported in future.

cel.property.select_probability (float): The selection heuristic currently used is tournament selection. This means that each genome will be selected with a probability of p(1-p)^r, where p is this property (in the interval 0 < p < 1) and r is the genome's rank when placed in order of descending fitness (0 being the fittest), hence fitter genomes will have a greater probability of being selected. While the fittest genomes will be parents of most of the genomes in the new generation, it is desirable also to select a few of the less fit genomes since they may have some redeeming qualities and this helps to avoid local optima. Therefore this probabalistic randomness is used. Experiment with different values of this property. 0.3 is a reasonable starting point.

cel.property.mutate_probability (float): This is the average number of genes to mutate per genome during the evolution of one generation. For example, a value of 3.0 will result in an average of 3 genes being mutated in each genome, while a value of 0.25 will mean that one gene will be mutated in every 4th genome on average.

Actions

The property class supports the following actions:

cel.action.Generate: Causes the property class to evolve one generation. Sends the pcevolve_fitness message to the behaviour to evaluate the fitness of each candidate genome. When finished, sends the pcevolve_result message to the behaviour to indicate completion and return the results of the evolution.

cel.action.ReturnFitness (parameter: float fitness): When the behaviour has finished evaluating the fitness of an individual (begun after receipt of pcevolve_fitness message) it calls this action to return the fitness value to the property class.

cel.action.GetFitness (parameter: long index; returns float): Gets the evaluated fitness of a particular individual genome in the population (specified by index).

cel.action.Select (parameter: long index): Copies a particular individual genome (specified by index) from the population into the genome of cel.property.subject.

cel.action.Reset: Clears the population, returning the property class to its initial state, the state it was in before any call to cel.action.Generate.

Messages

The property class will send the following messages to the behaviour:

pcevolve_fitness: This asks the behaviour to evaluate the fitness of a candidate genome which will have been stored in cel.property.subject. When finished, it should call cel.action.ReturnFitness to indicate completion and return the evaluated fitness to the property class. After a call to cel.action.Generate, this message is sent for every candidate genome in the population in succession.

pcevolve_result (parameters: float max_fitness, float min_fitness, float avg_fitness): This tells the behaviour that the evolution of one generation has been completed (which was initiated by cel.action.Generate). Its parameters tell the behaviour about the overall fitness of the population. If it is satisfied that this fitness is good enough, then it can halt the evolution and keep the best genome in the population. Otherwise, it should call cel.action.Generate again to evolve another generation.

Fitness function

The most involved part of using this property class is defining the fitness function, that is, the behaviour code that begins on receipt of the pcevolve_fitness message and ends with a call to cel.action.ReturnFitness. On reciept of pcevolve_fitness, the behaviour code should take the entity whose property class is stored in cel.property.subject and put it in a situation similar to what it might encounter in-game. Its performance should be evaluated and somehow quantified (e.g. how long it survives, how much damage it does to its opponent), and that number will be the fitness, which should be returned to the evolution property class in cel.action.ReturnFitness. During the evolution of one generation, pcevolve_fitness will be sent once for each individual candidate genome in the population, and this genome will have been stored in the cel.property.subject property class prior to it being sent each time. The genetic algorithm will use this fitness data to select the best genomes in the population.

In Ecksdee (a vehicular racing game) the fitness evaluation code will place the vehicle on a section of racetrack of steadily increasing complexity, and it will be evaluated on how long it takes to traverse the racetrack, or if it fails to fully traverse it, it will be evaluated on how far it gets before getting stuck. The fitness function should allow for genomes that cause the entity to behave extremely stupidly (e.g. crashing into the sides of the racetrack all the time) and still produce a usable fitness value, since this will be what happens for the first few generations, before it's been evolved very much.

Genetic operations

This section explains how the property class actually goes about evolving each successive generation. The genetic operators currently used are tournament selection, one-point crossover and mutation.

Each new genome in the population is created by joining one part of one genome to another part of another genome, forming a completely new genome. This is the crossover, or recombination, stage. The parent genomes are selected at random, but the randomness is weighted so that genomes with higher fitness have a greater chance of being selected.

After crossover, each child genome is randomly mutated. During this stage, zero or more genes in the genome are randomly changed to new values. The randomness element of selection and mutation help the algorithm to avoid local optima.

iPcEvolve interface

This is the C++ API:

struct iPcEvolve : public virtual iBase
{
  /// Set the number of genomes in the population.
  virtual void SetPopulationSize(size_t size) = 0;

  /// Returns the number of genomes in the population.
  virtual size_t GetPopulationSize() const = 0;

  /// Set the property class that will be evolved.
  virtual void SetSubject(iCelPropertyClass *pc) = 0;

  /// Returns the property class that is being evolved.
  virtual iCelPropertyClass* GetSubject() = 0;

  /// Set the probability properties.
  virtual void SetProbabilities(float select, float mutate) = 0;

  /// Evolves one generation of the population.
  virtual void Generate() = 0;

  /// Called after the fitness of a genome has been evaluated.
  virtual void FitnessCallback(float fitness) = 0;

  /// Returns the fitness of a specific genome in the population.
  virtual float GetFitness(size_t index) const = 0;

  /// Stores the specified genome in the subject propclass.
  virtual void SelectGenome(size_t index) = 0;

  /// Resets the population array to its initial state.
  virtual void ResetPopulation() = 0;
};

Genetic representation

All the code relating to the type of property class being evolved (and hence the type of data structure used to represent the genome) is abstracted out in the following interface, which represents one genome:

struct iCelGenome : public virtual iBase
{
  /// Copies the genome from pclass into this genome object.
  void Retrieve(iCelPropertyClass *pclass) = 0;

  /// Copies the genome from this genome object into pclass.
  void Store(iCelPropertyClass *pclass) const = 0;

  /// Sets the fitness value associated with this genome.
  void SetFitness(float fitness) = 0;

  /// Gets the fitness value associated with this genome.
  float GetFitness() const = 0;

  /// Gets a pointer to the internal representation of the genome data.
  void* GetInternalData() = 0;

  /// Fills the genome with random data.
  void Randomize() = 0;

  /// Returns the number of genes in the genome.
  size_t GetSize() const = 0;

  /// Creates a new genome using the crossover operation.
  csPtr<iCelGenome> Crossover(iCelGenome *other, size_t point) const = 0;

  /// Mutates the genome.
  void Mutate(float probability) = 0;
};

This interface is private to the plugin; it is not part of the public API.

The population of genomes is a csRefArray<iCelGenome>. This will make it easier to extend pcEvolve to support evolving other types of property classes. Presently there is only one iCelGenome implementation, which supports evolving PcNeuralNet.

Download in other formats:

Plain Text