Genetic Algorithm for Bin Packing Problem

• Download Demo application - 218.8 KB
• Download Source Code with GALex - 375.8 KB
• Original Article
• Up to Date GALex Source Code
• GALex Online Documentation

Introduction

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:

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:

F - fitness of the solution, n - number of bins, f_i - 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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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::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();

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.

Progress of fitness values during generations

Number of bins used by the best solution in the generation