GeneticAlgorithm Class Reference

This class implements a Genetic Algorithm system as search algorithm. More...

#include <GeneticAlgorithm.h>

Inheritance diagram for GeneticAlgorithm:

Inheritance graph
[legend]
Collaboration diagram for GeneticAlgorithm:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 GeneticAlgorithm (Input &)
void Evolve ()
 Genetic Algorithm search.
bool Evaluate (int i)
 Evaluate an individual.
bool Evaluate (Individual &)
 Evaluate an individual.
void FirstFit (BinSet &, const std::vector< const SizeName * > &) const
 Allocate items via FirstFit Algorithm.
void FirstFitDecreasing (BinSet &, std::vector< const SizeName * > &) const
 Allocate items via FirstFitDecreasing Algorithm.
void DominanceOptimizer (BinSet &bs, std::vector< const SizeName * > &unassigned) const
 Try to reallocate items via Dominance Criterion.

Protected Member Functions

bool InitPopulation ()
bool Generation ()
Params::Size_t Fitness (int index) const
Params::Size_t Fitness (const Individual &i) const
int Select (int a, int b) const
int Select (int a, int b, int p) const
int Select (int a, int b, int p1, int p2) const
bool Crossover (unsigned, unsigned, unsigned, unsigned)
 Promotes the crossover between two individuals, generating two children.
void Mutate (int i)
 Mutate the ith individual.
std::pair< int, int > Tournament2 (int, int) const
std::pair< int, int > TournamentN (int, int) const
IndividualIndividuals (int i)
 Returns the ith individual.
const IndividualIndividuals (int i) const
 Returns the ith individual; const version.
std::vector< Individual > & Individuals ()
 Returns the vector of individuals.
const std::vector< Individual > & Individuals () const
 Returns the vector of individuals; const version.
std::ostream & Write (std::ostream &) const

Protected Attributes

std::pair< int, int >
(GeneticAlgorithm::* 
Tournament )(int, int) const
std::vector< Individualm_individuals
Individual m_best_individual

Private Member Functions

 GeneticAlgorithm (const GeneticAlgorithm &)
GeneticAlgorithmoperator= (const GeneticAlgorithm &)
int DominanceForOne (Bin &bin, std::vector< const SizeName * > &unassigned) const
 Tries to replace one item per time via Dominance Optimizer.
int DominanceForTwo (Bin &bin, std::vector< const SizeName * > &unassigned) const
 Tries to replace two items per time via Dominance Optimizer.
int DominanceForThree (Bin &bin, std::vector< const SizeName * > &unassigned) const
 Tries to replace three items per time via Dominance Optimizer.

Private Attributes

int m_cur_gen
unsigned m_tournament_size


Detailed Description

This class implements a Genetic Algorithm system as search algorithm.

This implementation is based on Falkenauer's HGGA (Hybrid Grouping Genetic Algorithm).

In the HGGA, the genes represent each one a group of items, i.e., each gene is treated as a bin and their items act as an unit, a building block; therefore, the crossover operator does not mixes items on an individual basis, but, rather, it combines groups of bins. Besides, HGGA uses a local optimizer inspired on the Dominance Criterion of Martello and Toth, which basically tries iteratively to replace a few items of a certain bin by fewer items that fit better in. This procedure not only optimizes the bin, but also eases the reallocation of the replaced items, since smaller items are easier to fit.

Reference:

A Hybrid Grouping Genetic Algorithm for Bin Packing http://citeseer.ist.psu.edu/falkenauer96hybrid.html


Constructor & Destructor Documentation

GeneticAlgorithm::GeneticAlgorithm ( Input i  ) 

If not specified, the constructor will automatically adjust population size and number of generations. The Random::Seed is also set.

References Optimizer::m_files, Params::m_ga_num_gens, Params::m_ga_pop_size, Params::m_ga_seed, Params::m_ga_sel_pressure, m_individuals, Optimizer::m_params, m_tournament_size, Random::Seed(), Tournament, Tournament2(), and TournamentN().

GeneticAlgorithm::GeneticAlgorithm ( const GeneticAlgorithm  )  [private]

Copies are not allowed.


Member Function Documentation

GeneticAlgorithm& GeneticAlgorithm::operator= ( const GeneticAlgorithm  )  [private]

Attributions are not allowed.

void GeneticAlgorithm::Evolve (  )  [virtual]

Genetic Algorithm search.

GA searches for optimal (though not guaranteed) solutions by means of Darwinian evolution.

Implements Optimizer.

References Generation(), InitPopulation(), m_best_individual, m_cur_gen, Params::m_ga_num_gens, Individual::m_genome, Optimizer::m_params, Optimizer::m_solution, and Params::m_verbose.

bool GeneticAlgorithm::Evaluate ( int  i  )  [inline]

Evaluate an individual.

References m_individuals.

Referenced by Generation(), and InitPopulation().

bool GeneticAlgorithm::Evaluate ( Individual ind  ) 

bool GeneticAlgorithm::InitPopulation (  )  [protected]

Create the population of individuals and put it in m_individuals

As usually in GA, the creation of individuals is basically a random process. For each individual a new permutation over the m_files is generated and then those randomized items are inserted via the First Fit algorithm.

References Evaluate(), FirstFit(), Random::Int(), m_cur_gen, Optimizer::m_files, Params::m_ga_pop_size, m_individuals, and Optimizer::m_params.

Referenced by Evolve().

bool GeneticAlgorithm::Generation (  )  [protected]

Runs the GA for one generation. Returns true if a perfect fit was found; or the stop criterion was reached; false otherwise.

A perfect fit occurs when either (1) just one bin is suffice to pack all files; or (2) an individual reaches the maximum fitness (1.0).

References Crossover(), Evaluate(), Individuals(), m_cur_gen, Params::m_ga_cross_prob, Params::m_ga_mut_prob, m_individuals, Optimizer::m_params, Mutate(), Random::Probability(), and Tournament.

Referenced by Evolve().

Params::Size_t GeneticAlgorithm::Fitness ( int  index  )  const [inline, protected]

Just for notation convenience.

References m_individuals.

Referenced by Tournament2(), and TournamentN().

Params::Size_t GeneticAlgorithm::Fitness ( const Individual i  )  const [inline, protected]

Returns how well is the given individual. The objective is to maximize its fitness.

References Individual::Fitness().

int GeneticAlgorithm::Select ( int  a,
int  b 
) const [inline, protected]

Select in [a,b] a random individual.

References Random::Int().

Referenced by Crossover(), Mutate(), Select(), Tournament2(), and TournamentN().

int GeneticAlgorithm::Select ( int  a,
int  b,
int  p 
) const [inline, protected]

Select in [a,b] a random individual 'r' not equal 'p'.

References Select().

int GeneticAlgorithm::Select ( int  a,
int  b,
int  p1,
int  p2 
) const [inline, protected]

Select in [a,b] a random individual 'r' not equal 'p1' and 'p2' Required: b - a > 2

References Select().

bool GeneticAlgorithm::Crossover ( unsigned  dad,
unsigned  mom,
unsigned  child1,
unsigned  child2 
) [protected]

Promotes the crossover between two individuals, generating two children.

Basically, the crossover involves:

  1. Selecting crossover points (sections) on both parents.
  2. Inserting the crossover section of a parent into the crossover section of the another parent, and vice-versa. Actually, this is done on the children, so the parents' genomes remain intact.
  3. After the insertion procedure, likely some old bins of the children will contain items that were again inserted by the new bins that came from the crossover section of the other parent. Thus, those old bins containing duplicate items will be removed and their items (just the non-duplicates) will be marked as "unassigned".
  4. Finally, the DominanceOptimizer is applied in order to try to reallocate the unassigned bins. The remaining items--i.e., those that could not be reallocated--will be inserted on children via FirstFitDecreasing method.

References DominanceOptimizer(), FirstFitDecreasing(), Intersect(), Params::m_ga_pop_size, m_individuals, Optimizer::m_params, and Select().

Referenced by Generation().

void GeneticAlgorithm::Mutate ( int  i  )  [protected]

Mutate the ith individual.

The mutation operator removes a random bin, makes its items "unassigned", calls DominanceOptimizer to try to better reallocate those items and finally insert the remaining unassigned items via FirstFitDecreasing.

References DominanceOptimizer(), FirstFitDecreasing(), Individuals(), Random::Int(), and Select().

Referenced by Generation().

pair< int, int > GeneticAlgorithm::Tournament2 ( int  from,
int  to 
) const [protected]

Choose an individual via tournament (need 2 or more competitors). This is a two-competitor optimized version.

See also:
TournamentN()

References Fitness(), and Select().

Referenced by GeneticAlgorithm().

pair< int, int > GeneticAlgorithm::TournamentN ( int  from,
int  to 
) const [protected]

Choose an individual via tournament (need 2 or more competitors). This is a three+ competitor version.

See also:
Tournament2()

References Fitness(), m_tournament_size, and Select().

Referenced by GeneticAlgorithm().

Individual& GeneticAlgorithm::Individuals ( int  i  )  [inline, protected]

Returns the ith individual.

References m_individuals.

const Individual& GeneticAlgorithm::Individuals ( int  i  )  const [inline, protected]

Returns the ith individual; const version.

References m_individuals.

std::vector<Individual>& GeneticAlgorithm::Individuals (  )  [inline, protected]

Returns the vector of individuals.

References m_individuals.

Referenced by Generation(), and Mutate().

const std::vector<Individual>& GeneticAlgorithm::Individuals (  )  const [inline, protected]

Returns the vector of individuals; const version.

References m_individuals.

void GeneticAlgorithm::FirstFit ( BinSet ,
const std::vector< const SizeName * > &   
) const

Allocate items via FirstFit Algorithm.

The FirstFit algorithm fit a given item into the first bin able to accommodate it.

Referenced by InitPopulation().

void GeneticAlgorithm::FirstFitDecreasing ( BinSet ,
std::vector< const SizeName * > &   
) const

Allocate items via FirstFitDecreasing Algorithm.

The FirstFitDecreasing algorithm first sort in descending order the given list of items and then pass this sorted list to FirstFit.

Referenced by Crossover(), and Mutate().

void GeneticAlgorithm::DominanceOptimizer ( BinSet bs,
std::vector< const SizeName * > &  unassigned 
) const

Try to reallocate items via Dominance Criterion.

Basically, the DominanceOptimizer algorithm tries to replace smaller items with bigger (possibility fitter) items. It tries iteratively to replace a few items of a certain bin by fewer items that fit better in. This procedure not only optimizes the bin, but also eases the reallocation of the replaced items, since smaller items are easier to fit.

Referenced by Crossover(), and Mutate().

int GeneticAlgorithm::DominanceForOne ( Bin bin,
std::vector< const SizeName * > &  unassigned 
) const [private]

Tries to replace one item per time via Dominance Optimizer.

int GeneticAlgorithm::DominanceForTwo ( Bin bin,
std::vector< const SizeName * > &  unassigned 
) const [private]

Tries to replace two items per time via Dominance Optimizer.

int GeneticAlgorithm::DominanceForThree ( Bin bin,
std::vector< const SizeName * > &  unassigned 
) const [private]

Tries to replace three items per time via Dominance Optimizer.

std::ostream& GeneticAlgorithm::Write ( std::ostream &   )  const [protected, virtual]

Writes some information (like algorithm name and parameters) in ostream object (usually cout).

Reimplemented from Optimizer.


Member Data Documentation

std::pair<int,int>(GeneticAlgorithm::* GeneticAlgorithm::Tournament)(int, int) const [protected]

Pointer to Tournament2() or TournamentN(), depending on the tournament size.

Referenced by Generation(), and GeneticAlgorithm().

std::vector<Individual> GeneticAlgorithm::m_individuals [protected]

The population (vector) of individuals.

Referenced by Crossover(), Evaluate(), Fitness(), Generation(), GeneticAlgorithm(), Individuals(), and InitPopulation().

The best individual so far.

Referenced by Evaluate(), and Evolve().

Current generation.

Referenced by Evaluate(), Evolve(), Generation(), and InitPopulation().

Tournament size.

Referenced by GeneticAlgorithm(), and TournamentN().


The documentation for this class was generated from the following files: