CKGeneticAlgorithm1 Class Reference

A moderately greedy genetic algorithm for trying to globally optimize a function dreamed up by David Randall (Chip) Kent IV. More...

#include <CKGeneticAlgorithm1.h>

Inheritance diagram for CKGeneticAlgorithm1:

List of all members.

Public Member Functions

CKGeneticAlgorithm1 (QMCObjectiveFunction *function, int populationsize, double mutationrate, double distributionwidth)

Constructs and inializes this optimization algorithm.

Array1D< double > optimize (Array1D< double > &initialGuess, QMCDerivativeProperties &dp, double, int)

Optimize the function starting from the provided initial guess parameters.

Private Member Functions

void mutate (Array1D< double > &parameters, double width)

Mutates the input parameters by adding an N-dimensional gaussian random variable with a standard deviation of MutationRate.

Array1D< double > crossover (Array1D< double > &parent1, Array1D< double > &parent2)

Generates a child by breeding two parents.

int selectParent ()

Selects a parent for breeding.

void generateNewPopulation ()

Breeds and mutates the current population to generate a new population.

void initializePopulation (Array1D< double > &initialguess)

Create the initial population of points surrounding the initial guess.

Private Attributes

Stopwatch sw

QMCObjectiveFunction * OF

Objective function to optimize.

double MutationRate

Rate that there are mutations in the population.

int PopulationSize

Number of members in the population.

double InitialDistributionWidth

Spread of the initial population around the initial guess.

SortedParameterScorePairList Population

Population ordered so that the better parameter sets have smaller indices.

ParameterScorePair BestPopulationMember

Best parameter set found.

Detailed Description

A moderately greedy genetic algorithm for trying to globally optimize a function dreamed up by David Randall (Chip) Kent IV.

As is standard in the field, optimization means minimization.

Mutation is accomplished by adding a N-dimensional gaussian random variable to the population member.

The amount of each parent contributed to a child is determined by a uniform random variable.

A linear probability distribution is used to select which population member will be a parent. The best members have better probabilities of being selected.

Definition at line 39 of file CKGeneticAlgorithm1.h.

Constructor & Destructor Documentation

CKGeneticAlgorithm1::CKGeneticAlgorithm1	(	QMCObjectiveFunction *	function,
		int	populationsize,
		double	mutationrate,
		double	distributionwidth
	)

Constructs and inializes this optimization algorithm.

Parameters:

	function	function to optimize.
	populationsize	number of members in the population used to optimize the function. This is a positive number.
	mutationrate	a positive number describing how much mutation is introduced into the population. Larger numbers correspond to more mutation.
	distributionwidth	a positive number describing how far the initial population members spread from the initial guess.

Definition at line 15 of file CKGeneticAlgorithm1.cpp.

References InitialDistributionWidth, MutationRate, OF, and PopulationSize.

Member Function Documentation

Array1D< double > CKGeneticAlgorithm1::optimize	(	Array1D< double > &	initialGuess,
		QMCDerivativeProperties &	dp,
		double	,
		int
	)			`[virtual]`

Optimize the function starting from the provided initial guess parameters.

Parameters:

initialGuess

initial guess parameters for the optimization.

Returns:: optimized parameters.

Implements QMCOptimizationAlgorithm.

Definition at line 156 of file CKGeneticAlgorithm1.cpp.

References generateNewPopulation(), SortedParameterScorePairList::get(), ParameterScorePair::getParameters(), initializePopulation(), Population, PopulationSize, and sw.

void CKGeneticAlgorithm1::mutate	(	Array1D< double > &	parameters,
		double	width
	)			`[private]`

Mutates the input parameters by adding an N-dimensional gaussian random variable with a standard deviation of MutationRate.

It will make sure that no parameter goes below zero.

Parameters:

	parameters	parameters to be mutated and the returned mutated parameters.
	width	the width of the gaussian drift applied to each parameter

Definition at line 58 of file CKGeneticAlgorithm1.cpp.

References Array1D< T >::dim1(), Random::gasdev(), and ran.

Referenced by generateNewPopulation(), and initializePopulation().

Array1D< double > CKGeneticAlgorithm1::crossover	(	Array1D< double > &	parent1,
		Array1D< double > &	parent2
	)			`[private]`

Generates a child by breeding two parents.

The fraction of each parent is chosen with a uniform random distribution.

Parameters:

	parent1	first partent of the child.
	parent2	second parent of the child.

Definition at line 74 of file CKGeneticAlgorithm1.cpp.

References Array1D< T >::dim1(), ran, and Random::unidev().

Referenced by generateNewPopulation().

int CKGeneticAlgorithm1::selectParent ( ) [private]

Selects a parent for breeding.

The probability distribution of parent i being selected is a linear distribution with the first member having a weight of PopulationSize and the last member having a weight of 1.

$\rho(member_{i}) = 2\frac{PopulationSize-i}{PopulationSize^{2}}$

The details of this distriubution are worked out for the continuous case and used without modification here.

Returns:: index of the selected parent.

Definition at line 88 of file CKGeneticAlgorithm1.cpp.

References Population, ran, SortedParameterScorePairList::size(), and Random::unidev().

Referenced by generateNewPopulation().

void CKGeneticAlgorithm1::generateNewPopulation ( ) [private]

Breeds and mutates the current population to generate a new population.

Definition at line 102 of file CKGeneticAlgorithm1.cpp.

References SortedParameterScorePairList::add(), crossover(), QMCObjectiveFunction::evaluate(), SortedParameterScorePairList::get(), ParameterScorePair::getParameters(), InitialDistributionWidth, mutate(), MutationRate, OF, Population, PopulationSize, Stopwatch::reset(), SortedParameterScorePairList::resize(), selectParent(), Stopwatch::start(), Stopwatch::stop(), and sw.

Referenced by optimize().

void CKGeneticAlgorithm1::initializePopulation ( Array1D< double > & initialguess ) [private]

Create the initial population of points surrounding the initial guess.

The points are distributed with respect to an N-dimensional gaussian distribution with a standard deviation of InitialDistributionWidth.

Parameters:

initialguess

starting point for the optimization.

Definition at line 26 of file CKGeneticAlgorithm1.cpp.

References SortedParameterScorePairList::add(), SortedParameterScorePairList::clear(), Array1D< T >::dim1(), QMCObjectiveFunction::evaluate(), InitialDistributionWidth, mutate(), OF, Population, PopulationSize, Stopwatch::reset(), Stopwatch::start(), Stopwatch::stop(), and sw.

Referenced by optimize().

Member Data Documentation

Stopwatch CKGeneticAlgorithm1::sw [private]

Definition at line 64 of file CKGeneticAlgorithm1.h.

Referenced by generateNewPopulation(), initializePopulation(), and optimize().

QMCObjectiveFunction* CKGeneticAlgorithm1::OF [private]

Objective function to optimize.

Definition at line 69 of file CKGeneticAlgorithm1.h.

Referenced by CKGeneticAlgorithm1(), generateNewPopulation(), and initializePopulation().

double CKGeneticAlgorithm1::MutationRate [private]

Rate that there are mutations in the population.

Definition at line 74 of file CKGeneticAlgorithm1.h.

Referenced by CKGeneticAlgorithm1(), and generateNewPopulation().

int CKGeneticAlgorithm1::PopulationSize [private]

Number of members in the population.

Definition at line 79 of file CKGeneticAlgorithm1.h.

Referenced by CKGeneticAlgorithm1(), generateNewPopulation(), initializePopulation(), and optimize().

double CKGeneticAlgorithm1::InitialDistributionWidth [private]

Spread of the initial population around the initial guess.

Definition at line 84 of file CKGeneticAlgorithm1.h.

Referenced by CKGeneticAlgorithm1(), generateNewPopulation(), and initializePopulation().

SortedParameterScorePairList CKGeneticAlgorithm1::Population [private]

Population ordered so that the better parameter sets have smaller indices.

Definition at line 89 of file CKGeneticAlgorithm1.h.

Referenced by generateNewPopulation(), initializePopulation(), optimize(), and selectParent().

ParameterScorePair CKGeneticAlgorithm1::BestPopulationMember [private]

Best parameter set found.

Definition at line 94 of file CKGeneticAlgorithm1.h.

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


Public Member Functions
	CKGeneticAlgorithm1 (QMCObjectiveFunction *function, int populationsize, double mutationrate, double distributionwidth)
	Constructs and inializes this optimization algorithm.
Array1D< double >	optimize (Array1D< double > &initialGuess, QMCDerivativeProperties &dp, double, int)
	Optimize the function starting from the provided initial guess parameters.
Private Member Functions
void	mutate (Array1D< double > &parameters, double width)
	Mutates the input parameters by adding an N-dimensional gaussian random variable with a standard deviation of `MutationRate`.
Array1D< double >	crossover (Array1D< double > &parent1, Array1D< double > &parent2)
	Generates a child by breeding two parents.
int	selectParent ()
	Selects a parent for breeding.
void	generateNewPopulation ()
	Breeds and mutates the current population to generate a new population.
void	initializePopulation (Array1D< double > &initialguess)
	Create the initial population of points surrounding the initial guess.
Private Attributes
Stopwatch	sw
QMCObjectiveFunction *	OF
	Objective function to optimize.
double	MutationRate
	Rate that there are mutations in the population.
int	PopulationSize
	Number of members in the population.
double	InitialDistributionWidth
	Spread of the initial population around the initial guess.
SortedParameterScorePairList	Population
	Population ordered so that the better parameter sets have smaller indices.
ParameterScorePair	BestPopulationMember
	Best parameter set found.