GeneticAlgorithm Class Reference

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

#include <GeneticAlgorithm.h>

Inheritance diagram for GeneticAlgorithm:

Collaboration diagram for GeneticAlgorithm:

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

Individual & Individuals (int i)

Returns the ith individual.

const Individual & Individuals (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< Individual > m_individuals

Individual m_best_individual

Private Member Functions

GeneticAlgorithm (const GeneticAlgorithm &)

GeneticAlgorithm & operator= (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 )

Evaluate an individual.

References BEST_FITNESS, BinSet::Count(), Optimizer::Evaluate(), Individual::Fitness(), m_best_individual, Params::m_bins_theo, m_cur_gen, Individual::m_fitness, Individual::m_genome, Optimizer::m_params, Params::m_theoretical, and Params::m_verbose.

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:

Selecting crossover points (sections) on both parents.
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.
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".
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().

Individual GeneticAlgorithm::m_best_individual [protected]

The best individual so far.

Referenced by Evaluate(), and Evolve().

int GeneticAlgorithm::m_cur_gen [private]

Current generation.

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

unsigned GeneticAlgorithm::m_tournament_size [private]

Tournament size.

Referenced by GeneticAlgorithm(), and TournamentN().

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


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
Individual &	Individuals (int i)
	Returns the ith individual.
const Individual &	Individuals (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< Individual >	m_individuals
Individual	m_best_individual
Private Member Functions
	GeneticAlgorithm (const GeneticAlgorithm &)
GeneticAlgorithm &	operator= (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