A genetic algorithm class. More...

#include <GeneticAlgorithm.hpp>

Public Member Functions
	GeneticAlgorithm (const std::vector< Gene > &candidates, bool unique, double mutationRate=0.015, size_t tournament=10)
	Construct from parameters of Genetic Algorithm. More...

	GeneticAlgorithm (bool unique, double mutationRate=0.015, size_t tournament=10)
	Construct from parameters of Genetic Algorithm. More...

auto	evolveGeneArray (std::shared_ptr< GeneArray > geneArray, size_t population, size_t generation) const -> std::shared_ptr< GeneArray >
	Evolve a GeneArray. More...

auto	evolvePopulation (std::shared_ptr< Population > population) const -> std::shared_ptr< Population >
	Evolve population, a mass of GeneArray(es) More...

Protected Member Functions
virtual void	mutate (std::shared_ptr< GeneArray > geneArray) const
	Cause a mutation on the GeneArray. More...

Private Member Functions
auto	selection (std::shared_ptr< Population > population) const -> std::shared_ptr< GeneArray >
	Select the best GeneArray in population from tournament. More...

auto	crossover (std::shared_ptr< GeneArray > &parent1, std::shared_ptr< GeneArray > &parent2) const -> std::shared_ptr< GeneArray >
	Create a new GeneArray by crossing over two GeneArray(s) More...

Private Attributes
bool	unique
	Whether each element (Gene) is unique in their GeneArray. More...

double	mutationRate
	Rate of mutate ocurrence. More...

size_t	tournament
	Size of tournament in selection. More...

Detailed Description

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>
class samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >

A genetic algorithm class.

Template Parameters

GeneArray An array(std::vector) containing genes as elments; sequnce listing.

The GeneArray must be a type of std::vector.

Compare

A comparison class (or struct) returns whether left gene is more optimal.

Default template parameter of Compare is std::less<GeneArray>. It means to compare two std::vector (GeneArray must be a std::vector). Thus, you've to keep follwing rules.

If you don't want to follow the rules or want a custom comparison class, you have to realize a comparison class. The following code is an example realizing the comparison class.

- GeneArray is inherited from <i>std::vector</i>
- GeneArray has custom <i>auto operator<(const GeneArray &) const -> bool</i>

template <typename _Ty>
struct MyCompare
{
auto operator()(const _Ty &newObj, const _Ty &prevObj) const -> bool;
};

In the field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection. This heuristic (also sometimes called a metaheuristic) is routinely used to generate useful solutions to optimization and search problems.

Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

Referenced Wikipedia: https://en.wikipedia.org/wiki/Genetic_algorithm

Example Sources

example::tsp

Warning

Be careful for the mistakes of direction or position of Compare.

Most of logical errors failed to access optimal solution are occured by those mistakens.

See also: library::GAPopulation; samchon::library; example::tsp

Author: Jeongho Nam http://samchon.org

Definition at line 66 of file GeneticAlgorithm.hpp.

Constructor & Destructor Documentation

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::GeneticAlgorithm	(	const std::vector< Gene > &	candidates,
		bool	unique,
		double	mutationRate = `0.015`,
		size_t	tournament = `10`
	)

inline

Construct from parameters of Genetic Algorithm.

candidates Candidate genes used for mutation.

Parameters

unique	Whether each Gene is unique in their GeneArray
mutationRate	Rate of mutation
tournament	Size of tournament in selection
elitism	Whether to keep the elitest GeneArray

Definition at line 107 of file GeneticAlgorithm.hpp.

References samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutationRate, samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::tournament, and samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::unique.

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::GeneticAlgorithm	(	bool	unique,
		double	mutationRate = `0.015`,
		size_t	tournament = `10`
	)

inline

Construct from parameters of Genetic Algorithm.

Parameters

unique	Whether each Gene is unique in their GeneArray
mutationRate	Rate of mutation
tournament	Size of tournament in selection
elitism	Whether to keep the elitest GeneArray

Definition at line 124 of file GeneticAlgorithm.hpp.

References samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutationRate, samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::tournament, and samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::unique.

Member Function Documentation

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

auto samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolveGeneArray	(	std::shared_ptr< GeneArray >	geneArray,
		size_t	population,
		size_t	generation
	)		const -> std::shared_ptr<GeneArray>

inline

Evolve a GeneArray.

Convinient method accessing to evolvePopulation().

Parameters

geneArray	An initial set of genes; sequence listing
population	Size of population in a generation
generation	Size of generation in evolution

Returns: A evolved GeneArray optimally

Definition at line 141 of file GeneticAlgorithm.hpp.

References samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolvePopulation().

Referenced by samchon::example::tsp::Scheduler::optimize().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

auto samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolvePopulation ( std::shared_ptr< Population > population ) const -> std::shared_ptr<Population>

inline

Evolve population, a mass of GeneArray(es)

Parameters

population An initial population

Definition at line 157 of file GeneticAlgorithm.hpp.

References samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::crossover(), samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutate(), and samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::selection().

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolveGeneArray().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

auto samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::selection ( std::shared_ptr< Population > population ) const -> std::shared_ptr<GeneArray>

inlineprivate

Select the best GeneArray in population from tournament.

Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (using crossover operator). A generic selection procedure may be implemented as follows:

The fitness function is evaluated for each individual, providing fitness values, which are then normalized. Normalization means dividing the fitness value of each individual by the sum of all fitness values, so that the sum of all resulting fitness values equals 1.
The population is sorted by descending fitness values.
Accumulated normalized fitness values are computed (the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals). The accumulated fitness of the last individual should be 1 (otherwise something went wrong in the normalization step).
A random number R between 0 and 1 is chosen.
The selected individual is the first one whose accumulated normalized value is greater than R.

Referenced Wekipedia: https://en.wikipedia.org/wiki/Selection_(genetic_algorithm)

Parameters

population The target of tournament

Returns: The best genes derived by the tournament

Definition at line 215 of file GeneticAlgorithm.hpp.

References samchon::library::GAPopulation< GeneArray, Compare >::children, samchon::library::GAPopulation< GeneArray, Compare >::fitTest(), and samchon::library::Math::random().

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolvePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

auto samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::crossover	(	std::shared_ptr< GeneArray > &	parent1,
		std::shared_ptr< GeneArray > &	parent2
	)		const -> std::shared_ptr<GeneArray>

inlineprivate

Create a new GeneArray by crossing over two GeneArray(s)

crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based.

Cross over is a process of taking more than one parent solutions and producing a child solution from them. There are methods for selection of the chromosomes.

Referenced Wikipedia: https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)

Parameters

parent1	A parent sequence listing
parent2	A parent sequence listing

Definition at line 247 of file GeneticAlgorithm.hpp.

References samchon::library::Math::random().

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolvePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

virtual void samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutate ( std::shared_ptr< GeneArray > geneArray ) const

inlineprotectedvirtual

Cause a mutation on the GeneArray.

Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. It is analogous to biological mutation.

Mutation alters one or more gene values in a chromosome from its initial state. In mutation, the solution may change entirely from the previous solution. Hence GA can come to better solution by using mutation.

Mutation occurs during evolution according to a user-definable mutation probability. This probability should be set low. If it is set too high, the search will turn into a primitive random search.

Referenced Wikipedia: https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)

Note

Muttion is pursuing diversity. Mutation is useful for avoiding the following problem.

When initial set of genes(GeneArray) is far away from optimail, without mutation (only with selection and crossover), the genetic algorithm has a tend to wandering outside of the optimal.

Genes in the GeneArray will be swapped following percentage of the mutationRate.

Parameters

geneArray A container of genes to mutate

See also: mutationRate;

Definition at line 318 of file GeneticAlgorithm.hpp.

References samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutationRate, and samchon::library::Math::random().

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::evolvePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

bool samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::unique

private

Whether each element (Gene) is unique in their GeneArray.

Definition at line 77 of file GeneticAlgorithm.hpp.

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::GeneticAlgorithm().

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

double samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutationRate

private

Rate of mutate ocurrence.

The mutationRate determines the percentage of occurence of mutation in a GeneArray.

Note

When mutationRate is too high, it is hard to ancitipate studying on genetic algorithm.
When mutationRate is too low and initial set of genes(GeneArray) is far away from optimal, the evolution tends to wandering outside of he optimal.

Definition at line 90 of file GeneticAlgorithm.hpp.

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::GeneticAlgorithm(), and samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::mutate().

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>

size_t samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::tournament

private

Size of tournament in selection.

Definition at line 95 of file GeneticAlgorithm.hpp.

Referenced by samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >::GeneticAlgorithm().

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

D:/OneDrive/Project/Samchon/framework/cpp/samchon/library/GeneticAlgorithm.hpp

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type> class samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename GeneArray, typename Compare = std::less<GeneArray>, typename Gene = GeneArray::value_type>
class samchon::library::GeneticAlgorithm< GeneArray, Compare, Gene >