07. August 2013 · Comments Off · Categories: Programming · Tags: , ,

This article will demonstrate an implementation of Hybrid Grouping Genetic Algorithm (HGGA) proposed by Falkenauer for solving grouping problems such as bin packing using GALex library.

Bin Packing Problem

Bin packing problem belongs to the class of NP-hard problems, like the others that were discussed in previous articles. The task is to pack a set of items of different size into bins of fixed size in such way that minimal number bins is used. Depending on the requirements, bin packing can be single-dimensional (1D) or multi-dimensional (2D, 3D…) Genetic algorithm describe in this article is designed for solving 1D bin packing problem.

Hybrid Grouping Genetic Algorithm (HGGA)

Solution representation and genetic operations used in standard and ordering genetic algorithms are not suitable for grouping problems such as bin packing. Genetic operations, such as crossover and mutation, used in these algorithms are not aware of groups (bins). These operations will often disrupt these groups so they will not be able to pass meaningful information and good groups to offspring chromosomes. Hybrid Grouping Genetic Algorithm is proposed to solve this problem, by changing representation so the individual genes represent groups, not the individual items. Crossover and mutation operations are also changed so they are aware of groups. Original article discusses Hybrid Grouping Genetic Algorithm in more details and compares it to the ordering genetic algorithms. This article is focused on implementation of the algorithm using GALex library and provides some additional explanations.

Chromosome Representation

In Hybrid Grouping Genetic Algorithm, representation is designed with bins in mind, not individual items so each gene in a chromosome represents a single bin (group of items) not an individual item. This allows crossover operations to handle bins correctly and allows them to pass whole bins to offspring chromosomes instead of cutting them in the middle and disrupting good bins.

Not only that standard/ordering genetic algorithms disrupt good bins , but the items copied from the other parent has completely different meaning as their membership to the bins depends on position in encoding and the items that come before them in the encoding. So the items copied from parent to offspring are out of context. This problem reduces chances that crossover operation will pass useful information to future generation.

The following diagram illustrates chromosome representations of a few solutions in Hybrid Grouping Genetic Algorithm:

bin packing chromosome representation

Implementation

Chromosome configuration block is implemented by BinConfigBlock:


class BinConfigBlock : public Chromosome::GaChromosomeConfigBlock
{
public:
  struct Item
  {	
    std::string _label;
    float _size;

    Item() : _size(0) { }

    Item(const std::string& label,
      float size) : _label(label),
      _size(size) { }

    Item(const Item& src) : _label(src._label),
      _size(src._size) { }

    inline Item& operator =(const Item& rhs)
    {
      _label = rhs._label;
      _size = rhs._size;
      return *this;
    }
  };

private:
  Common::Data::GaSingleDimensionArray<Item> _items;
  Common::Data::GaSingleDimensionArray<int> _indices;
  float _binCapacity;

public:
  BinConfigBlock(
    const Common::Data::GaSingleDimensionArray<Item>& items,
    float binCapacity) : _binCapacity(binCapacity) { SetItems( items ); }

  BinConfigBlock(const BinConfigBlock& rhs) :
    GaChromosomeConfigBlock(rhs),
    _binCapacity(rhs._binCapacity) { SetItems( rhs._items ); }

  virtual GaChromosomeConfigBlock* GACALL Clone() const
    { return new BinConfigBlock( *this ); }

  inline const Common::Data::GaSingleDimensionArray<Item>& GACALL
    GetItems() const { return _items; }

  void GACALL SetItems(
    const Common::Data::GaSingleDimensionArray<Item>& items);

  const Common::Data::GaSingleDimensionArray<int>& GACALL
    GetIndices() const { return _indices; }

  inline float GACALL GetBinCapacity() const { return _binCapacity; }

  inline void GACALL SetBinCapacity(float binCapacity)
    { _binCapacity = binCapacity; }
};

Item class handles information about item such as its size and label.

As it was already discussed, single gene in the chromosome represents a single bin. The chromosome gene is represented by Bin class:

class Bin
{
public:
  typedef Common::Data::GaList<int> ItemList;

private:
  ItemList _items;
  float _capacity;
  float _fill;

public:
  Bin(float capacity) : _capacity(capacity),
    _fill(0) { }

  Bin(const Bin& src) : _items(src._items),
    _capacity(src._capacity),
    _fill(src._fill) { }
	
  /* getters, setters and other methods */
};

Class keeps track about items the bin contains, how much it is filled as well as its capacity (all bins have the same capacity). It also provides various supporting methods for handling items (adding, replacing, removing and transferring them to other bins).

After the gene is defined, representation can be completed by choosing appropriate chromosome class from the library. In this case it is GaListChromosome class, so the definition of chromosome is this:

typedef Common::Data::GaList<Bin> BinList;
typedef Chromosome::Representation::GaListChromosome<Bin>::GaType
  BinChromosome;

Now it is possible to define chromosome initializator, which is responsible for creating random chromosomes and filling initial population.

Initialization is simple, all items are shuffled and then they are added sequentially to the first bin that can accommodate them. If there is no such a bin, new one is created and the item is added to it.

Initializator is implemented by BinInitializator class:

class BinInitializator : public Chromosome::GaInitializator
{
public:
  virtual Chromosome::GaChromosomePtr GACALL operator ()(
    bool empty,
    const Chromosome::GaInitializatorParams& parameters,
    Common::Memory::GaSmartPtr<Chromosome::GaChromosomeConfigBlock>
      configBlock) const;

  virtual Common::GaParameters* GACALL CreateParameters()
    const { return NULL; }
};

operator () implements creation and initialization of new chromosome according to provided chromosome configuration block.

CreateParameters does not create new object for operation parameters as they are not required.

Fitness Operation

The most obvious fitness function for this problem is the number of items used by the solution, but it does not create smooth search space that genetic algorithm can explore. To make search space smooth, function that takes the fill of bins in the solution into account is used and it looks like this:

bin packing fitness function

F – fitness of the solution, n – number of bins, fi – fill of the ith bin, c – capacity of the bin, k – constant greater then 1

k constant controls whether the more filled bins are preferred or equally filled bins. Larger values should be used in case more filled bins are preferred. This example sets value of k to 2. More details about this constant are given in the original article.

Genetic algorithm should maximize this value.

Implementation

Fitness function has a single objective, so a simple fitness object can be used to represent it:

typedef Fitness::Representation::GaSVFitness<float> BinFitness;

Parameters of fitness operation are handled by BinFitnessOperationParams class.

class BinFitnessOperationParams :
  public Fitness::GaFitnessOperationParams
{
private:
  float _kParam;

public:
  BinFitnessOperationParams() : _kParam(2) { }
  BinFitnessOperationParams(float kParam) : _kParam(kParam) { }
  BinFitnessOperationParams(const BinFitnessOperationParams& params) :
    _kParam(params._kParam) { }

  virtual GaParameters* GACALL Clone() const
    { return new BinFitnessOperationParams( *this ); }
  inline float GACALL GetKParam() const { return _kParam; }
  inline void GACALL GetKParam(float kParam) { _kParam = kParam; }

};

The operation parameters stores k constant described in previous section.

Fitness operation which is responsible for calculating fitness value of the chromosome is implemented by BinFitnessOperation class.

class BinFitnessOperation :
  public Chromosome::GaChromosomeFitnessOperation
{
public:
  virtual Fitness::GaFitness* GACALL CreateFitnessObject(
    Common::Memory::GaSmartPtr<const Fitness::GaFitnessParams>
    params) const { return new BinFitness( params ); }

  virtual void GACALL operator ()(const GaObjectType& object,
    Fitness::GaFitness& fitness,
    const Fitness::GaFitnessOperationParams& operationParams) const;

  virtual Common::GaParameters* GACALL CreateParameters() const
    { return new BinFitnessOperationParams(); }

};

CreateFitnessObject method is called by the library to create appropriate object for storing fitness value of chromosome.

operator () implements calculation of chromosome’s fitness value, and stores it in provided fitness object.

CreateParameters() method creates object for storing parameters required by the fitness operation. In this case it is object of previously discussed BinFitnessOperationParams class.

Crossover Operation

The first thing crossover operation do to produce offspring is creation selected parents’ clones. These clones are going to be used as base of offspring chromosomes. Then the operation chooses two crossover points per clone.

bin packing crossover

The next step is transferring bins between parents. Crossover copies and inserts bins between crossover points from the first parent into second parent’s clone at the first crossover point. Then it swaps parents and copies bins from second parent into the first parent’s clone at the second crossover point.

bin packing crossover

Copying bins like this will produce invalid solutions, as the image illustrates. Now there are items that appear twice in the solution. Because of this algorithm has to perform corrections to make valid solution. To do so, it searches for finds all bins not copied from the other parent that contains duplicates and removes them. In this way gene transferred from the other parent are preserved, which is the point of crossover operation.

bin packing crossover

Removing these bins will also cause removal of some items that are not duplicates, because they were stored in the same bins with duplicates. Algorithm needs to create list of these items (unassigned items), and reinserts them back in to the solution.

bin packing crossover

Inserting unassigned items back into solution is process that has two steps. The first step is replacement of items, which will be discussed later in section that explains mutation.

When replacement step is finished and there are still unassigned items, crossover operation will sort list of remaining items by their size in descending order and insert them into the first bin that has enough free space. If there is no bin which can accommodate item, new bin is created and the item is stored in it. This technique is called first-fit descending heuristic.

bin packing crossover

Implementation

Crossover operation is implemented by BinCrossoverOperation class that inherits GaCrossoverOperation.

class BinCrossoverOperation : public Chromosome::GaCrossoverOperation
{
public:
  virtual void GACALL operator ()(
    Chromosome::GaCrossoverBuffer& crossoverBuffer,
    const Chromosome::GaCrossoverParams& parameters) const;

  virtual int GACALL GetParentCount(
    const Chromosome::GaCrossoverParams& parameters) const { return 2; }

  virtual int GACALL GetOffspringCount(
    const Chromosome::GaCrossoverParams& parameters) const { return 2; }

  virtual Common::GaParameters* GACALL CreateParameters() const
    { return new Chromosome::GaCrossoverPointParams(); }
};

operator () implements crossover operation.

GetParentCount returns number of parent chromosomes required to perform crossover operation (in this case it always 2) and GetOffspringCount method returns the number of offspring chromosomes that crossover operation natively produces (it is also always 2).

CreateParameters method creates parameters object required by the operation. Type of parameter object is GaCrossoverPointParams which holds number of crossover points in addition to crossover probability.

Mutation Operation

Mutation operation is simple: few bins are selected randomly and destroyed. Destruction of bins will allow those items that were in destroyed bins to be rearranged after reinsertion. This, hopefully, will lead to improvements of bin space usage.

bin packing mutation

The items that were in removed bins are preserved in the list of unassigned items.

bin packing mutation

The next step of the mutation algorithm is to reinsert those unassigned items into bins in the same fashion as it is done in crossover operation.

This is good opportunity to explain replacement of items mentioned during the discussion about crossover operation. Replacement work in the following way: If there is currently unassigned item U and set of items P in a single bin B, such that size(U) > size(P) and size(B) – size(P) + size(U) <= capacity(B), then items from P are removed from B and U is inserted instead of them. Number of items that algorithm search for set P is limited to three for performance reasons. The idea behind this technique is discussed in the original article.

bin packing mutation

Here, the item 10 replaced items 6 and 5 from bin 2, as the sum these two items is less than size of item 10 and it can fit the bin. Then item 1 replaced item 5 from bin 3 for the same reason.

Just like it was the case with crossover operation, when algorithm cannot find any more items that satisfy criteria for replacement, it switches to first-fit descending heuristics to insert unassigned items into bins.

bin packing mutation

I this case, no items could fit into existing bin so new bin has to be created.

Implementation

Mutation operation is implemented by BinMutationOperation class that inherits GaMutationOperation.

class BinMutationOperation : public Chromosome::GaMutationOperation
{
public:
  virtual void GACALL operator ()(Chromosome::GaChromosome& chromosome,
    const Chromosome::GaMutationParams& parameters) const;

  virtual Common::GaParameters* GACALL CreateParameters() const 
    { return new Chromosome::GaMutationSizeParams(); }
};

operator () implements mutation operation.

CreateParameters method creates parameters object required by the operation. Type of parameter object is GaMutationSizeParams which holds number genes that should be mutated in addition to mutation probability. Number of genes can be absolute, meaning it is fixed despite the size of chromosome on which the operation is preformed, or relative, meaning that certain percent of genes are changed.

Genetic Algorithm

Population size is set to 100 individuals. In each generation tournament selection is used to select two parents that will produce 50 offspring chromosomes. For each parent two rounds of roulette wheel selection is performed and the parent with better fitness is selected.

Crossover probability is 100%, so each offspring is produced by crossover operation and none is cloned.

In the original article mutation is performed on 33 of 50 individuals, so that is 66% probability of mutation occurring which is the probability used in this implementation.

mutation probability: 66%
mutation size: 2 genes
only accept mutations that improve fitness: yes
crossover probability: 100%
crossover points: 2 (implicit)
algorithm type: incremental (overlapping population)
population size: 100 chromosomes
sorted population: yes
fitness sorting: maximization
selection type: tournament (roulette wheel)
tournament selection rounds: 2
selection size: 2
coupling type: simple coupling
number of offspring to produce: 50
scaling type: no scaling
replacement type: replace worst
chromosomes to replace: 50
stop criterion type: fitness change
stop criterion depth: 100 generations

Implementation

The code that puts all the pieces together to create genetic algorithm looks like this:

// mating setup:
// - crossover: 100% probability, produces 2 child
// - mutation: 66% probability, 2 genes are modified, improvements accepted
Problems::BPP::BinCrossoverOperation crossover;
Problems::BPP::BinMutationOperation mutation;
Chromosome::MatingOperations::GaBasicMatingOperation mating;
Chromosome::GaMatingConfig matingConfiguration(
  Chromosome::GaCrossoverSetup(
    &crossover, &Chromosome::GaCrossoverParams( 1.0f, 2 ), NULL ),
  Chromosome::GaMutationSetup(
    &mutation, &Chromosome::GaMutationSizeParams( 0.66f, true, 2L ), NULL ) );

// initilizator setup
Problems::BPP::BinInitializator initializator;
Chromosome::GaInitializatorSetup initializatorSetup( &initializator, NULL,
  &Chromosome::GaInitializatorConfig(
    &Problems::BPP::BinConfigBlock( items, binSize ) ) );

// fitness comparator setup: maximize fitness value
Fitness::Comparators::GaSimpleComparator fitnessComparator;
Fitness::GaFitnessComparatorSetup fitnessComparatorSetup( &fitnessComparator,
  &Fitness::Comparators::GaSimpleComparatorParams(
    Fitness::Comparators::GACT_MAXIMIZE_ALL ), NULL );

// create population statistics trackers 
// for fitness values and population size 
Population::GaPopulationSizeTracker sizeTracker;
Population::GaRawFitnessTracker rawTracker;
Population::GaScaledFitnessTracker scaledTracker;
Algorithm::Stubs::GaSimpleGAStub::GaStatTrackersCollection trackers;
trackers[ Population::GaPopulationSizeTracker::TRACKER_ID ] =  &sizeTracker;
trackers[ Population::GaRawFitnessTracker::TRACKER_ID ] =  &rawTracker;
trackers[ Population::GaScaledFitnessTracker::TRACKER_ID ] =  &scaledTracker;

// selection setup:
// 2 tournament rounds using roulette wheel method, selects 2 parents
Population::SelectionOperations::GaTournamentSelection selection;
Population::GaSelectionSetup selectionSetup( &selection,
  &Population::SelectionOperations::GaTournamentSelectionParams( 2, -1, 2, 2,
    Population::SelectionOperations::GaTournamentSelectionParams::
	  GATST_ROULETTE_WHEEL_SELECTION ),
  &Population::SelectionOperations::GaTournamentSelectionConfig(
    fitnessComparatorSetup, Chromosome::GaMatingSetup() ) );

// coupling setup:
// produces 50 offspring chromosomes using defined mating operation
Population::CouplingOperations::GaSimpleCoupling coupling;
Population::GaCouplingSetup couplingSetup( &coupling,
  &Population::GaCouplingParams( 50, 1 ),
  &Population::GaCouplingConfig(
    Chromosome::GaMatingSetup( &mating, NULL, &matingConfiguration ) ) );

// replacement setup:
// replaces 50 of the worst chromosomes
Population::ReplacementOperations::GaWorstReplacement replacement;
Population::GaReplacementSetup replacementSetup( &replacement,
  &Population::GaReplacementParams( 50 ), &Population::GaReplacementConfig() );

// scaling setup: no scaling
Population::ScalingOperations::GaNoScaling scaling;
Population::GaScalingSetup scalingSetup( &scaling, NULL,
  &Population::GaScalingConfig() );

// fitness setup: individual based evaluation, k = 2
Problems::BPP::BinFitnessOperation fitnessOperation;
Population::GaCombinedFitnessOperation populationFitnessOperation(
  &fitnessOperation );
Population::GaPopulationFitnessOperationSetup fitnessSetup(
  &populationFitnessOperation, &Problems::BPP::BinFitnessOperationParams( 2 ),
  &Fitness::GaFitnessOperationConfig( NULL ) );
	
// incremental genetic algorithm with:
//  - population: size 100 individuals, sorted by raw fitness
Algorithm::Stubs::GaSimpleGAStub simpleGA(
  WDID_POPULATION, WDID_POPULATION_STATS,
  initializatorSetup,
  fitnessSetup,
  fitnessComparatorSetup,
  Population::GaPopulationParams( 100, 0,
    Population::GaPopulationParams::GAPFO_FILL_ON_INIT ),
  trackers,
  Chromosome::GaMatingSetup(),
  selectionSetup,
  couplingSetup,
  replacementSetup,
  scalingSetup,
  Population::GaFitnessComparatorSortingCriteria( fitnessComparatorSetup,
    Population::GaChromosomeStorage::GAFT_RAW ) );

// 2 workflow branches will execute algorithm
simpleGA.SetBranchCount( 2 );

// create workflow
Common::Workflows::GaWorkflow workflow( NULL );
workflow.RemoveConnection(
  *workflow.GetFirstStep()->GetOutboundConnections().begin(), true );

// connect algorithm stub to workflow 
Common::Workflows::GaWorkflowBarrier* br1 =
  new Common::Workflows::GaWorkflowBarrier();
simpleGA.Connect( workflow.GetFirstStep(), br1 );

Common::Workflows::GaBranchGroup* bg1 =  (Common::Workflows::GaBranchGroup*)
  workflow.ConnectSteps( br1, workflow.GetLastStep(), 0 );

   
// create stop criteria that will stop the algorithm if: 
// raw fitness of the best chromosome in the population 
// has not been changed for the last 100 generations. 
Algorithm::StopCriteria::GaStopCriterionStep* stopStep = 
  new Algorithm::StopCriteria::GaStopCriterionStep(
    Algorithm::StopCriteria::GaStopCriterionSetup( &stopCriterion,
      &Algorithm::StopCriteria::GaStatsChangesCriterionParams(
	    Population::GADV_BEST_FITNESS, 100),
  	NULL ),
    workflow.GetWorkflowData(), WDID_POPULATION_STATS );

Common::Workflows::GaBranchGroupTransition* bt1 =
  new Common::Workflows::GaBranchGroupTransition();

// connect stop criterion to workflow and algorithm stub
bg1->GetBranchGroupFlow()->SetFirstStep( stopStep );
bg1->GetBranchGroupFlow()->ConnectSteps( stopStep, bt1, 0 );
workflow.ConnectSteps( bt1, simpleGA.GetStubFlow().GetFirstStep(), 1 );

// subscribe handler to event raised before new generation cycle begins
Common::Workflows::GaDataCache population(
  workflow.GetWorkflowData(), WDID_POPULATION );
population.GetData().GetEventManager().AddEventHandler(
  Population::GaPopulation::GAPE_NEW_GENERATION, &newGenHandler );

// start algorithm and wait for it to finish
workflow.Start();
workflow.Wait();

Source code of the example is available with the rest of GALex project at github.

Results

The following section presents results of a single run where the bin size is set to 150, number of items is 500 and their sizes are chosen randomly between 20 and 100. It shows progress of chromosomes’ fitness values and number of bins used. X-axis represents generations of the population and Y-axis represents fitness value or number of bins used by the solution.

fitness progress graph
Progress of fitness values during generations

bin count progress graph
Number of bins used by the best solution in the generation

17. June 2013 · Comments Off · Categories: Programming · Tags: , ,

This example demonstrates a genetic algorithm that is designed to solve the problem introduced by this xkcd comic. The genetic algorithm is going to be implemented using GALex library.

xkcd_app

About the Problem

A group of people walk into a restaurant and want to spend exactly $15.05 on appetizers. They also want them as fast as possible. This leaves waiter with an NP-hard problem to solve, a variation of knapsack problem.

The problem waiter have to solve is selection of items from the menu, so they cost exactly the amount customers specified. This problem by itself is NP-hard, but that is not enough for the snarky customers. They want it as fast as possible. So the waiter cannot select any combination that satisfy price requirement. He must find all the combinations, so he can choose the one which will take the least amount of time to make.

Chromosome

Defining chromosome representation that is going to be used by the genetic algorithm as well as designing good crossover and mutation operations are crucial steps and they are most often specific to the problem that has to be solved.

Representation

One of the first things that should be done when designing a genetic algorithm is choosing the adequate representation for the solutions. There are several ways to encode a solution. Some of the possible representations are:

  • unordered linked list where list nodes contains items that should be served
  • array that stores count of items that should be served

Linked List Representation
Linked list representation

Array Representation
Array representation

Chosen representation will greatly influence the design of other genetic operations such as crossover or mutation operation. For this example the linked list representation is chosen.

One advantage of the representation is that it allows genetic algorithm to optimize representation itself. Crossover can shuffle blocks of items around the chromosome without affecting its fitness value. This way genetic algorithm can group good combinations of items close together. These combinations are known as building block. Such grouping reduces the chances of building blocks disruption, which is a good thing since such disruptions most often degrade quality of a solution and its fitness value.

Each node in the list will store index of the item on the menu. Since each node can have fixed set of values, GaAlleleGene are going to be used to represent genes. This gene stores allele set in addition to gene value. Allele set is a set of values that are allowed for gene to have them. GaAlleleGene is a complex type gene so GaAdvanceListChromosome class has to be used as chromosome type. So with a few typedefs chromosome representation is almost ready:

typedef Chromosome::Representation::GaAlleleGene<int> XkcdGene;
typedef Common::Data::GaList<XkcdGene> XkcdGeneList;

typedef Chromosome::Representation::GaAdvanceListChromosome<
  int, Chromosome::Representation::GaAlleleGene>::GaType XkcdChromosome;

Next thing that needs to be defined is chromosome configuration block (CCB). CCB will contain list of appetizers, with their prices and time required to make, as well as allele set for chromosomes’ genes.

Definition of appetizer:

struct Appetizer
{
  std::string _name;
  float _price;
  float _time;

  Appetizer();
  Appetizer(const std::string& name,
    float price,
    float time);
};

Definition of CCB:


class XkcdConfigBlock : public Chromosome::GaChromosomeConfigBlock
{
private:
  Common::Data::GaSingleDimensionArray<Appetizer> _appetizers;
  Chromosome::Representation::GaIntervalAlleleSet<int> _interval;

public:
  XkcdConfigBlock(
    const Common::Data::GaSingleDimensionArray<Appetizer>& appetizers) : 
  _appetizers( appetizers ),
  _interval (
    Chromosome::Representation::GaValueIntervalBounds<int>(
      0, appetizers.GetSize() - 1 ),
    Chromosome::Representation::GaValueIntervalBounds<int>(
      0, appetizers.GetSize() - 1 ),
    GaGlobalRandomIntegerGenerator ) { }

  XkcdConfigBlock(const XkcdConfigBlock& rhs) :
    GaChromosomeConfigBlock(rhs),
    _appetizers(rhs._appetizers),
    _interval(rhs._interval) { }

  virtual GaChromosomeConfigBlock* GACALL Clone() const
    { return new XkcdConfigBlock( *this ); }
};

XkcdConfigBlock class that inherits GaChromosomeConfigBlock represents CCB specific for this problem. Notice that user defined CCBs must implement Clone method and it has to have copy constructor.

Allele set that is used is GaIntervalAlleleSet. This set contains all values in the defined range. This is enough since the values should be indices of items in appetizer list. Every allele set also takes set of inverted values, required by some genetic operations. In this case it is the same set.

Now that the chromosome type is ready following genetic operations have to be defined:

  • chromosome initialization
  • chromosome comparator
  • fitness operation
  • crossover operation
  • mutation operation

Chromosome Initialization

The approach for chromosome initialization is simple: determine random number of items, and then randomly select items until the desired count is reached. In case that new chromosome is needed for crossover operation and empty chromosome is returned. The operation also sets the CCB for the chromosome.

XkcdInitializator class is responsible for creation of new chromosomes. It is inherited from GaInitializator which represents the base class for user-defined initializators. operator () is called by the library to create and initialize new chromosome.

class XkcdInitializator : public Chromosome::GaInitializator
{
public:
  virtual Chromosome::GaChromosomePtr GACALL operator ()(
    bool empty,
    const Chromosome::GaInitializatorParams& parameters,
    Common::Memory::GaSmartPtr<
      Chromosome::GaChromosomeConfigBlock> configBlock) const;

  virtual Common::GaParameters* GACALL CreateParameters() const
    { return NULL; }
};

Since operation parameters are not used by this implementation of the initializator CreateParameters returns NULL.

Chromosome Comparator

Chromosome comparator is implemented by XkcdChromosomeComparator class and it is inherited from XkcdChromosomeComparator which is base class for user-defined comparators.

class XkcdChromosomeComparator :
  public Chromosome::GaChromosomeComparator
{
public:

  virtual float GACALL operator ()(
    const Chromosome::GaChromosome& chromosome1,
    const Chromosome::GaChromosome& chromosome2,
    const Chromosome::GaChromosomeComparatorParams& parameters) const
  { return Equal( chromosome1, chromosome2, parameters ) ? 0.0f : 1.0f; }

  virtual bool GACALL Equal(
    const Chromosome::GaChromosome& chromosome1,
    const Chromosome::GaChromosome& chromosome2,
    const Chromosome::GaChromosomeComparatorParams& parameters) const
  { return ( (const XkcdChromosome&)chromosome1 ).GetGenes() ==
    ( (const XkcdChromosome&)chromosome2 ).GetGenes(); }

  virtual Common::GaParameters* GACALL CreateParameters() const
    { return NULL; }
};

This implementation use simple comparison method defined by the list container, and returns true/false (or 1/0). In case the fitness sharing scaling (GaShareFitnessScaling) should used by the algorithm, different implementation is required and comparison have to return rate of similarity between the chromosomes.

Fitness Operation

Fitness operation is responsible for calculating fitness value of a chromosome. Stated problem has two criteria: cost of appetizers and time needed to make them, so the genetic algorithm should take both of these into account when calculating fitness of the chromosome. Since price is more important criterion then time in this case, weights can be assigned to these values accordingly and real multi-objective optimization with pareto sets is not required. Taking into the account all the values and their weights fitness function should look like this:
Fitness function
Fitness function: f – fitness value, wp – weight of price criterion, wt – weight of time criterion, tp – target price, n – number of appetizer, api – price of i-th appetizer, ati – required time to make i-th appetizer

Since the price is more important higher weight should assigned to wp then to wt. In this example wp is set to 2.0 and wt is set to 1.0.

Wight-based fitness value representation, available in library and implemented by GaWeightedFitness class, is nicely fitted for this example. It can preserve values of both criteria (price and time) so they can be displayed, weights can be assigned to these values by the fitness parameters and the implementation calculates total fitness automatically by summing weighted values.

typedef Fitness::Representation::GaWeightedFitness<float, float> XkcdFitness;

That is enough to have fitness value representation that can be used by fitness operation and the rest of the library.

GALex has two different approaches to evaluate fitness value of chromosomes:

  1. population-based – fitness of all chromosomes in population is evaluated at once. This approach has to be used when fitness function of a chromosome is not independent from other chromosomes in population.
  2. individual-based – fitness of a chromosome is evaluated independently from other chromosomes. This approach is preferred as it allows library to optimize other genetic operations such as selection and coupling…

Fitness function for this problem is defined in such way that it can use individual based approach.

Operation is implemented by XkcdFitnessOperation class and it inherits GaChromosomeFitnessOperation which is base class for individual-based fitness operations. Since there is targeted price, it must be specified by operation parameters which are implemented by XkcdFitnessOperationParams class that uses GaFitnessOperationParams as base.

class XkcdFitnessOperationParams :
  public Fitness::GaFitnessOperationParams
{
private:
  float _targetPrice;

public:
  XkcdFitnessOperationParams(float targetPrice) :
    _targetPrice( targetPrice ) { }

  XkcdFitnessOperationParams(const XkcdFitnessOperationParams& params) :
    _targetPrice( params._targetPrice ) { }

  virtual GaParameters* GACALL Clone() const
    { return new XkcdFitnessOperationParams( *this ); }

  inline float GACALL GetTargetPrice() const { return _targetPrice; }

  inline void GACALL SetTargetPrice(float price)
    { _targetPrice = price; }
};

class XkcdFitnessOperation :
  public Chromosome::GaChromosomeFitnessOperation
{
public:
  virtual Fitness::GaFitness* GACALL 
    CreateFitnessObject(
    Common::Memory::GaSmartPtr<
      const Fitness::GaFitnessParams> params) const
  { return new XkcdFitness( params ); }

  virtual void GACALL operator ()(const GaObjectType& object,
    Fitness::GaFitness& fitness,
    const Fitness::GaFitnessOperationParams& operationParams) const;

  virtual Common::GaParameters* GACALL CreateParameters() const
    { return new XkcdFitnessOperationParams(); }
};

CreateFitnessObject is called by the library when it needs to creating fitness value object and code operator () is responsible for evaluationg fitness value of the chromosome.

Crossover Operation

The purpose of crossover operation is to produce new solution by combining existing ones. Implementation of crossover operation depends on the representation. As it was already discussed, the algorithm uses linked-list representation, so simple single-point crossover operation can be used:

Crossover Operation
Crossover operation

The library already has implementation of such crossover operation. It is represented by GaListMultipointCrossover class.

Mutation Operation

Mutation operation is responsible for retaining genetic diversity of the chromosomes in the population. It is done by randomly changing genes in newly produced chromosomes:

Mutation Operation
Mutation operation

The operation is implemented by XkcdMutationOperation class. It inherits GaMutationOperation which is base for all user-defined mutation operations. operator () is responsible for performing mutation on the chromosome. This operation requires parameters that tell it how many genes it should change for which GaMutationSizeParams class is used.

class XkcdMutationOperation : public Chromosome::GaMutationOperation
{
public:

  virtual void GACALL operator ()(Chromosome::GaChromosome& chromosome,
    const Chromosome::GaMutationParams& parameters) const;

  virtual Common::GaParameters* GACALL CreateParameters() const 
    { return new Chromosome::GaMutationSizeParams(); }
};

Mating Operation

Mating operation controls production cycle of new chromosomes. Cycle includes all the genetic operations that should executed to produce new chromosome and their parameters. Basic cycle consists of invoking crossover operation to produce new chromosomes and invoking mutation operation on those chromosomes. This cycle is implemented in the library by GaBasicMatingOperation class. User can customize production cycle by implementing custom mating operation. GaMatingOperation is base class for all mating operations.

Putting the Pieces Together

The final stage is to a define population, select the appropriate algorithm and chose selection and replacement operations. Algorithm configuration and parameters:

mutation probability: 30%
mutation size: 1 gene
only accept mutations that improve fitness: yes
crossover probability: 80%
crossover points: 1
algorithm type: incremental (overlapping population)
population size: 32 chromosomes
sorted population: yes
fitness sorting: maximization
fitness weights: 2.0, 1.0
selection type: roulette wheel
selection size: 8
coupling type: none (selection performs mating)
number of offspring to produce: 8
scaling type: no scaling
replacement type: replace worst
chromosomes to replace: 8
stop criterion type: fitness change
stop criterion depth: 1000 generations

The code that puts all the pieces together to create genetic algorithm looks like this:

// create mating operation with:
// crossover - 80% probability, 2 offspring, 1 crossover point
// mutation - 30% probability, accept only improving mutations, 1 gene
Chromosome::CrossoverOperations::GaListMultipointCrossover crossover;
Problems::XKCD::XkcdMutationOperation mutation;
Chromosome::MatingOperations::GaBasicMatingOperation mating;
Chromosome::GaMatingConfig matingConfiguration(
  Chromosome::GaCrossoverSetup( &crossover,
    &Chromosome::GaCrossoverPointParams( 0.8f, 2, 1 ), NULL ),
  Chromosome::GaMutationSetup( &mutation,
    &Chromosome::GaMutationSizeParams( 0.3f, true, 1L ), NULL ) );

Problems::XKCD::XkcdConfigBlock::Appetizer appetizers[] =
{
  Problems::XKCD::XkcdConfigBlock::Appetizer("mixed fruit", 2.15f, 3),
  Problems::XKCD::XkcdConfigBlock::Appetizer("french fries", 2.75f, 2),
  Problems::XKCD::XkcdConfigBlock::Appetizer("side salad", 3.35f, 5),
  Problems::XKCD::XkcdConfigBlock::Appetizer("hot wings", 3.55f, 3),
  Problems::XKCD::XkcdConfigBlock::Appetizer("mozzarella sticks", 4.20f, 4),
  Problems::XKCD::XkcdConfigBlock::Appetizer("sampler plate", 5.80f, 7),
};

// create chromosome initializator
Problems::XKCD::XkcdInitializator initializator;
Chromosome::GaInitializatorSetup initializatorSetup( &initializator,
  NULL, &Chromosome::GaInitializatorConfig(
    &Problems::XKCD::XkcdConfigBlock(
      Common::Data::GaSingleDimensionArray<
        Problems::XKCD::XkcdConfigBlock::Appetizer>( appetizers, 6 ) ) ) );

// create fitness comparator for maximizing fitness value
Fitness::Comparators::GaSimpleComparator fitnessComparator;
Fitness::GaFitnessComparatorSetup fitnessComparatorSetup(
  &fitnessComparator,
  &Fitness::Comparators::GaSimpleComparatorParams(
    Fitness::Comparators::GACT_MAXIMIZE_ALL ), NULL );

// fitness operation
Problems::XKCD::XkcdFitnessOperation fitnessOperation;
Population::GaCombinedFitnessOperation populationFitnessOperation(
  &fitnessOperation );

// create population statistics trackers
// for fitness values and population size
Population::GaPopulationSizeTracker sizeTracker;
Population::GaRawFitnessTracker rawTracker;
Algorithm::Stubs::GaSimpleGAStub::GaStatTrackersCollection trackers;
trackers[ Population::GaPopulationSizeTracker::TRACKER_ID ] =  &sizeTracker;
trackers[ Population::GaRawFitnessTracker::TRACKER_ID ] =  &rawTracker;
trackers[ Population::GaScaledFitnessTracker::TRACKER_ID ] =  &scaledTracker;

// create selection operation that:
// uses roulette wheel method and
// selects 8 parents and produces 8 offspring chromosomes
// using defined mating
Population::SelectionOperations::GaRouletteWheelSelection selection;
Population::GaSelectionSetup selectionSetup( &selection,
  &Population::SelectionOperations::GaDuplicatesSelectionParams( 8, 1, 2 ),
  &Population::GaCouplingConfig(
    Chromosome::GaMatingSetup( &mating, NULL, &matingConfiguration ) ) );

// create replacement operation that:
// replaces 8 worst chromosomes in the population
Population::ReplacementOperations::GaWorstReplacement replacement;
Population::GaReplacementSetup replacementSetup( &replacement,
  &Population::GaReplacementParams( 8 ),
  &Population::GaReplacementConfig(
    Chromosome::GaChromosomeComparatorSetup(
      &chromosomeComparator, NULL, NULL ) ));

// creates scaling operation that just copies raw fitness value
Population::ScalingOperations::GaNoScaling scaling;
Population::GaScalingSetup scalingSetup( &scaling, NULL, 
  &Population::GaScalingConfig() );

// weights used to calculate fitness value
float fitnessWights[] = { 2.0f, 1.0f };

// create fitness operation that uses weighted fitness
// with specified weights
Population::GaPopulationFitnessOperationSetup fitnessSetup(
  &populationFitnessOperation,
  &Problems::XKCD::XkcdFitnessOperationParams( targetPrice ),
  &Fitness::GaFitnessOperationConfig(
    &Fitness::Representation::GaWeightedFitnessParams<float>( 
      fitnessWights, 2 ) ) );

// population - 32 chromosomes, 0 crowding size
Population::GaPopulationParams populationParams( 32, 0,
    Population::GaPopulationParams::GAPFO_FILL_ON_INIT );

// create criteria for sorting population 
Population::GaFitnessComparatorSortingCriteria sortCriteria(
    fitnessComparatorSetup,
    Population::GaChromosomeStorage::GAFT_RAW );

// create simple incremental algorithm stub:
Algorithm::Stubs::GaSimpleGAStub simpleGA(
  WDID_POPULATION, 
  WDID_POPULATION_STATS,
  initializatorSetup,
  fitnessSetup,
  fitnessComparatorSetup,
  populationParams,
  trackers,
  Chromosome::GaMatingSetup(),
  selectionSetup,
  Population::GaCouplingSetup(),
  replacementSetup,
  Population::GaScalingSetup(),
  sortCriteria);

// create workflow
Common::Workflows::GaWorkflow workflow( NULL );
workflow.RemoveConnection(
  *workflow.GetFirstStep()->GetOutboundConnections().begin(), true );

// connect algorithm stub to workflow
Common::Workflows::GaWorkflowBarrier* br1 = 
  new Common::Workflows::GaWorkflowBarrier();
simpleGA.Connect( workflow.GetFirstStep(), br1 );

Common::Workflows::GaBranchGroup* bg1 = 
  (Common::Workflows::GaBranchGroup*)workflow.ConnectSteps(
    br1, workflow.GetLastStep(), 0 );

// create stop criteria that will stop the algorithm if:
// raw fitness of the best chromosome in the population
// has not been changed for the last 1000 generations.
Algorithm::StopCriteria::GaStatsChangesCriterion stopCriterion;
Algorithm::StopCriteria::GaStopCriterionStep* stopStep =
  new Algorithm::StopCriteria::GaStopCriterionStep(
    Algorithm::StopCriteria::GaStopCriterionSetup(
      &stopCriterion,
      &Algorithm::StopCriteria::GaStatsChangesCriterionParams(
        Population::GADV_BEST_FITNESS, 1000), NULL ),
    workflow.GetWorkflowData(), WDID_POPULATION_STATS );

// connect stop criterion to workflow and algorithm stub
Common::Workflows::GaBranchGroupTransition* bt1 =
  new Common::Workflows::GaBranchGroupTransition();
bg1->GetBranchGroupFlow()->SetFirstStep( stopStep );
bg1->GetBranchGroupFlow()->ConnectSteps( stopStep, bt1, 0 );
workflow.ConnectSteps( bt1, simpleGA.GetStubFlow().GetFirstStep(), 1 );

// subscribe handler to event raised before new generation cycle begins
Common::Workflows::GaDataCache<Population::GaPopulation> population(
  workflow.GetWorkflowData(), WDID_POPULATION );
population.GetData().GetEventManager().AddEventHandler(
  Population::GaPopulation::GAPE_NEW_GENERATION, &newGenHandler );

// start algorithm and wait for it to finish
workflow.Start();
workflow.Wait();

Source code of the example is available with the rest of GALex project at github.

Results

The following section presents results of a single run for target price of $15.05. It shows progress of chromosomes’ fitness values and their components during the run. X-axis represents generations of the population and Y-axis represents fitness value or one of its component.

xkcd_fitness_graph
Weighted fitness value of the best chromosome and the worst chromosome in population and average value

xkcd_price_graph
Price component of the best chromosome in the population – how far it is off the targeted price

xkcd_time_graph
Time component of the best chromosome in the population – how much time it is needed to make appetizers

09. April 2013 · Comments Off · Categories: Programming · Tags: , ,

Making class schedule belong to class of NP hard problems. The problem can be solved using heuristic search algorithm to find optimal solution, but it works for simple cases. For more complex inputs and requirements finding considerably good solution can take a while or it may be impossible. This is where genetic algorithms come in the game.

ga_class_sch_app

When you make class schedule you must take into consideration many requirements (number of professors, students, classes and classrooms, size of classroom, laboratory equipment in classroom and many other). These requirements can be divided into several groups by their importance. Hard requirements (if you break one of these then the schedule is infeasible):

  • Class can be placed only in spear classroom.
  • No professor or student group can have more then on class at one time.
  • Classroom must have enough seats to accommodate all students.
  • To place class in classroom, classroom must have laboratory equipment (computers in our case) if class requires it.

Some soft requirements (can be broken but schedule is still feasible):

  • Preferred time of class by professors.
  • Preferred classroom by professors.
  • Distribution (in time or space) of classes for student groups or professors.

Hard and soft requirements of course depend on situation. In this example only hard requirements are implemented. Let start by explaining object which makes on class schedule.

Objects of Class Schedule

Professor

Professor class has ID and name of professor. It also contains list of classes that professor teaches.

Student Group

StudentsGroup class has ID and name of student group, as well as number of students (size of group). It also contains list of classes that group attends.

Classroom

Room class has ID and name of classroom, as well as number of seats and if there are computers in it. If classroom has computers, it is expected that there is a computer for each seat. IDs are generated internally and automatically.

Course

Course class has ID and name of course.

Class

CourseClass holds reference to course to which class belongs, reference to professor who teaches and list of student groups that attend class. It also stores how many seats are needed (sum of student groups’ sizes), if class requires computers in classroom and duration of class (in hours).

Chromosome

The first thing we should consider when we deal with genetic algorithm is how to represent our solution in such way that is feasible for genetic operations such as crossover and mutation and we should know how to specify how good our solution is (called fitness).

Representation

How we represent chromosome? Well we need a slot (time-space slot) for each hour, we assume that time is in one hour granules, for every room of every day. Also we assume that classes cannot begin before 9am and should finish before or at 10pm (12 hours total) and working days are Monday to Friday (5 days total). So we need vector with size 12*5*number_of_rooms. Slot should be of std::list type because during execution of our algorithm we allow multiple classes at same slot. There is additional hash map which is used to obtain slot at which class begins (its position in vector) from address of class’s object. Each hour of a class has separate entry in vector, but there is only one entry per class in hash map. For instance if class starts at 1pm and lasts for three hours, it has entries in 1pm, 2pm and 3pm slots.

Class Schedule Chromosome Representation
Figure 1 – Chromosome Representation

As we have vector of slots we can use Chromosome::Representation::GaMultiValueChromosome<T> template class to represent our chromosome, but we must modify it by adding previously explained hash map.

class Schedule : public GaMultiValueChromosome<list><CourseClass*>>
{

    friend class ScheduleCrossover;
    friend class ScheduleMutation;
    friend class ScheduleFitness;
    friend class ScheduleObserver;

private:

    hash_map<CourseClass*, int> _classes;

    hash_map<CourseClass*, int> _backupClasses;

public:

    Schedule(GaChromosomeDomainBlock<list><CourseClass*>>* configBlock);

    Schedule(const Schedule& c, bool setupOnly);

    virtual ~Schedule();

    virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const;

    virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;

    virtual void GACALL PreapareForMutation();

    virtual void GACALL AcceptMutation();

    virtual void GACALL RejectMutation();

};

Chromosome has three major parts: code, fitness value and setup. Chromosome’s code contains representation of solution, in our case it is hash map and vector of slots. Fitness value keeps information about how good that solution is. Setup of chromosomes stores references to genetic operations which are used to operate on chromosome (such as fitness operation, crossover operation or mutation operation). It also stores parameters which are used by these genetic operation as well as parameters of chromosomes. Chromosome’s setup is stored in Chromosome Configuration Block (CCB). When we make first chromosome we must give reference to CCB. The CCB is then used for new chromosomes produced by copy constructor or MakeCopy and MakeFromPrototype methods.

_classes attribute stores hash map and _backupClasses used to save copy of it if improving only mutations are enabled. The first constructor takes configuration block and initialize empty chromosome (no chromosome’s code) with provided setup. The second constructor is copy constructor with additional parameter setupOnly. This parameter specifies weather constructor should copy only setup of chromosomes or it should copy chromosome’s code as well (hash map and vector of slots). Destructor must be declared even if it does not do anything to avoid memory leakage. MakeCopy does what it says – it makes copy of the chromosomes and returns smart pointer to it. It copies CCB to new chromosome as well as chromosome’s code and fitness (if specified so). MakeNewFromPrototype method makes new chromosome with same CCB but it initializes new chromosome’s code with random values (size of new code is same as size of prototype code). PreapareForMutation method called before algorithm performs mutation operation on chromosome, it is used to save current chromosomes code. AcceptMutation method is called if algorithm has accepted mutation that had been made, it is used to clear saved code. RejectMutation method is called if algorithm has rejected mutation that had been made, it is used to restore chromosome’s code. When overriding these methods, overridden methods of base class should also be called from child class.

Fitness

Now we need to assign a fitness value to the chromosome. We will use minimal requirements for a class schedule (nothing fancy, for instance we assume that professor can have classes at any time). This is how we do it:

  • Each class can have from 0 to 5 points.
  • If class use empty room, we increment its score.
  • If class requires computers and it is located in room with them, we increment its score.
    But if class does not requires computers, well we increment its score anyway.
  • If class is located in room with enough available seats, guess what,
    we increment its score.
  • If professor is available (has no other classes) at the time,
    we increment class’s score once again.
  • And last criteria that we check is if student groups of the class has no other classes
    at same time, and if they do not we increment score of the class.
  • If class brakes some rule at any slot then the score is not incremented
  • Total score of schedule is sum of points of all classes.
  • Fitness value is calculated as schedule_score/maximum_score,
    and maximum_score is number_of_classes*5.

Fitness values are represented by single-precision floating point number (float). Fitness operation must inherit Chromosome::GaFitnessOperation.

class ScheduleFitness : public GaFitnessOperation
{

public:

    virtual float GACALL operator ()(const GaChromosome* chromosome) const;

    virtual GaParameters* GACALL MakeParameters() const;

    virtual bool GACALL CheckParameters(const GaParameters& parameters) const;
};

operator () calculates fitness value of chromosome and returns that value. MakeParameters and CheckParameters do not do anything they just override pure virtual functions from Common::GaOperation class.

Crossover

Crossover operation combines data in hash maps of two parent chromosomes, and then it creates vector of slots according to content of new hash map. Crossover ‘splits’ hash maps of both parents in parts of random size. Number of parts is defined by number of crossover points (plus one) in chromosome’s parameters. Then it alternately copies parts form parents to new chromosome, and forms new vector of slots.

Class Schedule Crossover Operation
Figure 2 – Crossover operation

GAL has some built-in crossover operations, but now we need specialized crossover, so we make our own. Crossover operation must inherit Chromosome::GaCrossoverOperation class.

class ScheduleCrossover : public GaCrossoverOperation
{

public:

    virtual GaChromosomePtr GACALL operator ()(const GaChromosome* parent1,
        const GaChromosome* parent2) const;

    virtual GaParameters* GACALL MakeParameters() const;

    virtual bool GACALL CheckParameters(const GaParameters& parameters) const;

};

operator () performs crossover operation, produces new chromosomes and returns smart pointer to it. MakeParameters and CheckParameters like in fitness operation do not do anything.

Mutation

Mutation operation is very simple. It just takes class randomly and moves it to another randomly chosen slot. Number of classes which are going to be moved in a single operation is defined by mutation size in chromosome’s parameters.

GAL also has built-in mutation operations, but now we need specialized crossover, so we make our own. Crossover operation must inherit Chromosome::GaMutationOperation class.

class ScheduleMutation : public GaMutationOperation
{

public:

    virtual void GACALL operator ()(GaChromosome* chromosome) const;

    virtual GaParameters* GACALL MakeParameters() const;

    virtual bool GACALL CheckParameters(const GaParameters& parameters) const;

};

operator () performs mutation operation. MakeParameters and CheckParameters like in crossover operation do not do anything.

Observing

GAL observer pattern to notify user about progress of the algorithm and changes of it state. Observer’s class must inherit Observing::GaObserver. All methods in this class are abstract and must be overridden:

  • StatisticUpdate – this method is called each time before algorithm progress
    to next generation
  • NewBestChromosome – this method is called each time when algorithm
    finds new best solution
  • EvolutionStateChanged – this method is called when user stops, starts,
    pauses or resumes execution of algorithm

If we do not have to handle all these events observer can inherit Observing::GaObserverAdapter class, and only override methods that handles desired events.

class ScheduleObserver : public GaObserverAdapter
{

private:

    HANDLE _event;

    void ReleaseEvent();

public:

    ScheduleObserver();

    virtual ~ScheduleObserver();

    void WaitEvent();
	
    virtual void GACALL NewBestChromosome(const GaChromosome& newChromosome,
        const GaAlgorithm& algorithm);

    virtual void GACALL EvolutionStateChanged(GaAlgorithmState newState,
        const GaAlgorithm& algorithm);

};

Putting all the pieces together

On top of all things what we need is genetic algorithm. We choose an incremental genetic algorithm (it replaces only few chromosomes in each generation). But to make an algorithm object we need stop criteria, population on which algorithm is going to operate and parameters for the algorithm. Desired algorithm use Algorithm::GaMultithreadingAlgorithmParams class as parameters because it only needs number of working threads. To specify stop criteria to the algorithm, there should be parameters for it. We use stop criteria based on fitness value (in our case, based on fitness value of best chromosome) Algorithm::StopCriterias::GaFitnessCriteria and its parameters Algorithm::StopCriterias::GaFitnessCriteriaParams.

Population is encapsulated in Population::GaPopulation class. To instantiate a population object we must provide prototype of chromosome, and configuration of population. Configuration is consists genetic operations which are performed over population (selection, coupling, scaling and replacement), comparator of chromosomes’ fitness values which is used to sort chromosome in population and sorted groups and parameters of population. Configuration of population is represented by GaPopulationConfiguration class. Because algorithm should maximize fitness values Chromosome::FitnessComparators::GaMaxFitnessComparator comparator should be used. Population::GaPopulationParameters class represents parameters of population. Incremental algorithm requires population with fixed size. Because random selection and replacement is used population do not have to be sorted. Also we want to track few best and few worst chromosomes. Last thing about population parameters is whether we’ll use scaled fitness values or non-scaled fitness values. Because we won’t use scaling operation population will use non-scaled fitness values. As said, we select chromosomes randomly produce few chromosomes and replace random chromosomes in each generation. As selection operation Population::SelectionOperations::GaSelectRandomBest is used with Population::SelectionOperations::GaSelectRandomBestParams class as parameters. Replacement operation is Population::ReplacementOperations::GaReplaceRandom with Population::ReplacementOperations::GaReplaceElitismParams class as parameters. Default coupling operation is used and scaling operation is not used.

Chromosome prototype is empty chromosome, has no code, with defined Chromosome Configuration Block (CCB) and defined size of code. Because our chromosome inherits Chromosome::Representation::GaMultiValueChromosome we must use Chromosome::Representation::GaChromosomeDomainBlock CCB even if we do not use value set. When constructing CCB we specify chromosomes parameters, which crossover, mutation and fitness operations are going to be used as well as fitness comparator. Chromosome parameters are represented by Chromosome::GaChromosomeParams class. This class also handles parameters for genetic operation which operates on chromosome. Parameters define how frequently crossover and mutation operation are going to be performed, size of mutation and number of crossover points. Also it tells if only the mutations that improve fitness value should be accepted.

And here is the code:

int main()
{
    // parse config file
    Configuration::GetInstance().ParseFile( "GaSchedule.cfg" );

    // initialize GAL internal structures
    GaInitialize();

    // make chromosome parameters
    // crossover probability: 80%
    // crossover points: 2
    // no "improving only mutations"
    // mutation probability: 3%
    // number of moved classes per mutation: 2
    GaChromosomeParams chromosomeParams( 0.8F, 2, false, 0.03F, 2 );

    // instances of genetic operations
    ScheduleCrossover crossoverOperation;
    ScheduleMutation mutationOperation;
    ScheduleFitness fitnessOperation;

    // make CCB with fallowing setup:
    // there are no value set with ScheduleCrossover, 
    // ScheduleMutation, ScheduleFitness genetic operations
    // set fittnes comparator for maximizing fitness value
    // use previously defined chromosome's parameters
    GaChromosomeDomainBlock<list<CourseClass*>> configBlock( NULL, 
        &crossoverOperation, &mutationOperation, &fitnessOperation,
        GaFitnessComparatorCatalogue::Instance().GetEntryData(
        "GaMaxFitnessComparator" ),
        &chromosomeParams );

    // make prototype of chromosome
    Schedule prototype( &configBlock );

    // make population parameters
    // number of chromosomes in population: 100
    // population always has fixed number of chromosomes
    // population is not sorted
    // non-transformed(non-scaled) fitness values are used
    // for sorting and tracking chromosomes
    // population tracks 5 best and 5 worst chromosomes
    GaPopulationParameters populationParams( 100, false, false, false, 5, 5 );
    
    // make population parameters
    // number of chromosomes in population: 100
    // population always has fixed number of chromosomes
    // population is not sorted
    // non-transformed(non-scaled) fitness values are used
    // for sorting and tracking chromosomes
    // population tracks 5 best and 5 worst chromosomes
    GaPopulationParameters populationParams( 100, false, false, false, 5, 5 );

    // make parameters for selection operation
    // selection will choose 16 chromosomes
    // but only 8 best of them will be stored in selection result set
    // there will be no duplicates of chromosomes in result set
    GaSelectRandomBestParams selParam( 8, false, 16 );

    // make parameters for replacement operation
    // replace 8 chromosomes
    // but keep 5 best chromosomes in population
    GaReplaceElitismParams repParam( 8, 5 );

    // make parameters for coupling operation
    // coupling operation will produce 8 new chromosomes
    // from selected parents
    GaCouplingParams coupParam( 8 );

    // make population configuration
    // use defined population parameters
    // use same comparator for sorting as comparator used by chromosomes
    // use selection operation which randomly selects chromosomes
    // use replacement operation which randomly chooses chromosomes
    // from population which are going to be replaced,
    // but keeps best chromosomes
    // use simple coupling
    // disable scaling
    GaPopulationConfiguration populationConfig( populationParams,
        &configBlock.GetFitnessComparator(),
        GaSelectionCatalogue::Instance().GetEntryData( "GaSelectRandomBest" ),
        &selParam,
        GaReplacementCatalogue::Instance().GetEntryData( "GaReplaceRandom" ),
        &repParam,
        GaCouplingCatalogue::Instance().GetEntryData( "GaSimpleCoupling" ),
        &coupParam,
        NULL, NULL );

    // make population
    // with previously defined prototype of chromosomes
    // and population configuration
    GaPopulation population( &prototype, &populationConfig );

    // make parameters for genetic algorithms
    // algorithm will use two workers
    GaMultithreadingAlgorithmParams algorithmParams( 2 );
    // make incremental algorithm with previously defined
    // population and parameters
    GaIncrementalAlgorithm algorithm( &population, algorithmParams );

    // make parameters for stop criteria based on fitness value
    // stop when best chromosome reaches fitness value of 1
    GaFitnessCriteriaParams criteriaParams( 1, GFC_EQUALS_TO,
        GSV_BEST_FITNESS );

    // sets algorithm's stop criteria (base on fitness value)
    // and its parameters
    algorithm.SetStopCriteria(
        GaStopCriteriaCatalogue::Instance().GetEntryData( 
        "GaFitnessCriteria" ),
        &criteriaParams );

    // make observer and subscribe it on algorithms events
    ScheduleObserver observer;
    algorithm.SubscribeObserver( &observer );

    // start execution 
    algorithm.StartSolving( false );

    observer.WaitEvent();

    // free memory used by GAL internal structures
    GaFinalize();

    return 0;
}

Note that GaInitialize must be called before any part of GAL is used, and GaFinalize must be called before program exits or when GAL is not needed anymore.

Configuration

Configuration file

Types of objects:

  1. professor (#prof tag) – describes professor.
  2. course (#course tag) – describes course.
  3. room (#room tag) – describes room.
  4. group (#group tag) – describes student group.
  5. course class (#class tag) – describes class, binds
    professor, course and student groups.

Each object begins with its tag and finishes with #end tag, all tags must be in separate lines. In a body of an object each line contains only one key and value pair (attribute) separated by = character. Each attribute should be specified just one time except for group attribute in #group object which can have multiple group attributes. Tag and key names are case sensitive. List of objects’ attributes:

  1. #prof
    • id (number, required) – ID of the professor.
    • name (string, required) – name of the professor.
  2. #course
    • id (number, required) – ID of the course.
    • name (string, required) – name of the course.
  3. #room
    • name (string, required) – name of the room.
    • size (number, required) – number of seats in the room.
    • lab (boolean, optional) – indicates if the room is lab (has computers).
      If not specified, default value is false.
  4. #group
    • id (number, required) – ID of the student groups.
    • name (string, required) – name of the student groups.
    • size (number, required) – number of students in the group.
  5. #class
    • professor (number, required) – ID of a professor.
      Binds professor to class.
    • course (number, required) – ID of a course.
      Binds course to class.
    • group (number, required) – ID of a student group.
      Binds student group to class.
      Each class can be bound to multiple student groups.
    • duration (number, optional) – duration of class (in hours).
      If not specified, default value is 1.
    • lab (boolean, optional) – is the class requires computers in a room.
      If not specified, default value is false.

Note that professor, student group and course objects must be defined before they are bound to course class object.

Example of configuration file

#prof
    id = 1
    name = John Smith
#end

#course
    id = 1
    name = Introduction to Programming
#end

#room
    name = R1
    lab = true
    size = 24
#end

#group
    id = 1
    name = 1O1
    size = 19
#end

#group
    id = 2
    name = 1O2
    size = 20
#end

#class
    professor = 1
    course = 1
    duration = 2
    group = 1
    group = 2
#end

#class
    professor = 1
    course = 1
    duration = 3
    group = 1
    lab = true
#end

#class
    professor = 1
    course = 1
    duration = 3
    group = 2
    lab = true
#end

Parsing configuration

Parsing of configuration file is done by Configuration class. ParseFile method opens and parse configuration file. It searches for object tags and calls appropriate method for parsing object. ParseFile method also clears previously parsed object.

public:

    void ParseFile(char* fileName);

private:

    Professor* ParseProfessor(ifstream& file);
    StudentsGroup* ParseStudentsGroup(ifstream& file);
    Course* ParseCourse(ifstream& file);
    Room* ParseRoom(ifstream& file);
    CourseClass* ParseCourseClass(ifstream& file);

To parse file:

    Configuration::GetInstance().ParseFile( "GaSchedule.cfg" );

Parsed objects are kept in hash map except course classes, so they can be accessed easily and fast.

private:

    hash_map<int, Professor*> _professors;
    hash_map<int, StudentsGroup*> _studentGroups;
    hash_map<int, Course*> _courses;
    hash_map<int, Room*> _rooms;

    list<CourseClass*> _courseClasses;

Configuration class also contains methods for retrieving parsed information and objects.

public:

    inline Professor* GetProfessorById(int id) //...
    inline int GetNumberOfProfessors() const //...

    inline StudentsGroup* GetStudentsGroupById(int id) //...
    inline int GetNumberOfStudentGroups() const //...

    inline Course* GetCourseById(int id) //...
    inline int GetNumberOfCourses() const //...

    inline Room* GetRoomById(int id) //...
    inline int GetNumberOfRooms() const //...

    inline const list<CourseClass*>& GetCourseClasses() const //...
    inline int GetNumberOfCourseClasses() const //...

Downloads

Source code and Demo application