FGA manual
Classes
In the FGA library there are two classes:
Population<GeneType>
Template class for a population of chromosomes. GeneType is the data type of genes (a chromosome is a sequence of genes); it can be a primitive data-type as well as a user-defined data structure.
Public methods:
PopulationMT<GeneType>
Template class for a multi-threaded population of chromosomes.
With this class it is possible to evolve multiple sub-populations in parallel.
Public methods:
Functions
Copy-constructors for classes Population and PopulationMT:
Population(int nc, int clength, float (*f)(GeneType *), GeneType (*mgene)(GeneType), GeneType (*rgene)(), void (*ccustom)(GeneType *, GeneType *), void (*mcustom)(GeneType *), void (*rcustom)(GeneType *), GeneType *(*scustom)(GeneType **))
What it does:
Creates and initializes the population.
Arguments:
Argument |
Meaning |
Default value |
nc |
number of chromosomes in population |
|
clength |
length of each chromosome (number of genes) |
|
f |
fitness function |
|
mgene |
gene mutation operator |
|
rgene |
random gene generator |
|
ccustom |
custom crossover operator |
|
mcustom |
chromosome-wide mutation operator |
|
rcustom |
random chromosome generator |
|
scustom |
custom selection operator |
|
Example usage:
1) Population<char> my_population(10, 5, my_fitness_function, my_mutate_gene, my_random_gene, NULL, NULL, NULL, NULL);
where the functions passed as pointers are of the following types:
float my_fitness_function(char *chromosome) { // return chromosome's fitness value } char my_mutate_gene(char gene) { // return mutated gene } char my_random_gene() { // return a random gene }
2) Population<char> my_population(10, 5, my_fitness_function, NULL, NULL, my_crossover_operator, my_mutate_chromosome, my_random_chromosome, my_select_chromosome);
where the new functions passed as pointers are of the following types:
void my_crossover_operator(char *chromosome1, char *chromosome2) { // operates crossing-over on the two chromosomes } void my_mutate_chromosome(char *chromosome) { // mutates the chromosome } void my_random_chromosome(char *chromosome) { // creates a random chromosome in the buffer passed as an argument } char *my_select_chromosome(char **chromosomes) { // return a pointer to the selected chromosome, chosen from the “chromosomes” array }
Notes:
Chromosome-wide operators overwrite gene-operators.
If a custom crossover operator is passed, crossover type is automatically set to CROSSOVER_CUSTOM, and so happens with all other custom functions.
PopulationMT(int nc, int clength, float (*f)(GeneType *), GeneType (*mgene)(GeneType), GeneType (*rgene)(), void (*ccustom)(GeneType *, GeneType *), void (*mcustom)(GeneType *), void (*rcustom)(GeneType *), GeneType *(*scustom)(GeneType **))
What it does:
Creates and initializes the multi-threaded population.
Arguments:
Argument |
Meaning |
Default value |
nt |
number of threads (corresponds to the number of sub-populations) |
|
nc |
number of chromosomes in population |
|
clength |
length of each chromosome (number of genes) |
|
f |
fitness function |
|
mgene |
gene mutation operator |
|
rgene |
random gene generator |
|
ccustom |
custom crossover operator |
|
mcustom |
chromosome-wide mutation operator |
|
rcustom |
random chromosome generator |
|
scustom |
custom selection operator |
|
Example usage:
It's used like Population, except that the number of threads must be passed as the first argument:
PopulationMT<char> my_population(2, 10, 5, my_fitness_function, my_mutate_gene, my_random_gene, NULL, NULL, NULL, NULL);
The following functions are the same for both Population and PopulationMT classes:
void set_crossover_rate(float crate)
What it does:
Sets the probability that two chromosomes will be crossed over.
Arguments:
Argument |
Meaning |
Default value |
crate |
probability that two chromosomes will be crossed over (a floating point number in [0, 1]) |
0.7 |
Example usage:
my_population.set_crossover_rate(0.5);
void set_mutation_rate(float mrate)
What it does:
Sets the probability that a gene will be mutated; if mutate type is set to MUTATE_CUSTOM, then it means the probability that a chromosome will be mutated (using the chromosome-wide operator).
Arguments:
Argument |
Meaning |
Default value |
mrate |
probability of mutation (a floating point number in [0, 1]) |
0.001 |
Example usage:
my_population.set_mutation_rate(0.1);
void set_crossover_type(int ctype)
What it does:
Sets the crossover operator.
Arguments:
Argument |
Meaning |
Default value |
ctype |
crossover operator to be used. Available options: CROSSOVER_1POINT, CROSSOVER_2POINT, CROSSOVER_UNIFORM, CROSSOVER_CUSTOM |
CROSSOVER_1POINT |
Example usage:
my_population.set_crossover_type(CROSSOVER_UNIFORM);
Notes:
CROSSOVER_1POINT is the standard cut-paste crossover operator.
CROSSOVER_2POINT is a variant that makes two cuts and swaps the internal sections of the two chromosomes.
CROSSOVER_UNIFORM means that each gene has ½ probability to be swapped between the two chromosomes.
CROSSOVER_CUSTOM refers to the custom crossover function that can be passed to the copy constructor of the class.
void set_select_type(int stype)
What it does:
Sets the selection operator (the operator that chooses chromosomes for the breeding stage).
Arguments:
Argument |
Meaning |
Default value |
stype |
selection operator to be used. Available options: SELECT_WEIGHTED, SELECT_UNIFORM, SELECT_TOURNAMENT, SELECT_ELITIST, SELECT_CUSTOM |
SELECT_WEIGHTED |
Example usage:
my_population.set_select_type(SELECT_TOURNAMENT);
Notes:
SELECT_TOURNAMENT is very fast if tournament size is not too large. It selects a random subset of candidates and chooses the fittest chromosome from the subset.
SELECT_UNIFORM is the fastest selection operator but it can loose good solutions. Each chromosome has the same probability to be chosen.
SELECT_ELITIST is the most conservative operator, and can sometimes lead to earlier convergence. It first chooses the fittest chromosomes and then, if needed, completes with SELECT_UNIFORM.
SELECT_WEIGHTED means that the probability to be chosen is proportional to fitness.
SELECT_CUSTOM falls back to the select function provided to the copy constructor.
void set_tournament_size(int tsize)
What it does:
Sets the size of the subset of candidates for the tournament crossover operator.
Arguments:
Argument |
Meaning |
Default value |
tsize |
size of tournament (it should be lesser or equal to the number of chromosomes in the population or sub-population) |
2 |
Example usage:
my_population.set_tournament_size(10);
void set_elite_size(int esize)
What it does:
Sets the size of the elite of chromosomes to be chosen by the elitist crossover operator.
Arguments:
Argument |
Meaning |
Default value |
esize |
size of elite (it should be lesser or equal to the number of chromosomes in the population or sub-population) |
nc / 10 |
Example usage:
my_population.set_elite_size(10);
void set_preserve_best(bool p)
What it does:
Sets whether the fittest individual in the population should be preserved across generations. If set to true, this means that if the best child chromosome is worse than the best parent chromosome, the latter is inserted in the new population, replacing a random chromosome of fitness below average.
Arguments:
Argument |
Meaning |
Default value |
p |
whether the fittest individual should be preserved or not |
true |
Example usage:
my_population.set_elite_size(10);
GeneType *get_best()
What it does:
Returns a pointer to the fittest chromosome in the population.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
char *best = my_population.get_best();
Notes:
The all-time best individual is guaranteed to be in the current population only if preserve_best is set to true.
float get_best_score()
What it does:
Returns the score of the fittest chromosome in the population.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
float best_score = my_population.get_best_score();
float get_avg_score()
What it does:
Returns the average fitness of chromosomes.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
float avg_score = my_population.get_avg_score();
float get_standard_deviation
What it does:
Returns the standard deviation of fitness values, calculated as the square root of the variance (i.e. the root mean square deviation of all fitness values from the average).
Arguments:
Argument |
Meaning |
Default value |
Example usage:
float deviation = my_population.get_standard_deviation();
GeneType *get_chromosome(int c)
What it does:
Returns a pointer to chromosome number c in the population.
Arguments:
Argument |
Meaning |
Default value |
c |
position of the chromosome in the population |
|
Example usage:
char *chr = my_population.get_chromosome(10);
Notes:
Multi-threaded populations are intended to have n * nthreads chromosomes (where n is the number of chromosomes in each sub-population, nthreads is the number of sub-populations).
float get_score(int c)
What it does:
Returns the score of chromosome number c in the population.
Arguments:
Argument |
Meaning |
Default value |
c |
position of the chromosome in the population |
|
Example usage:
float score = my_population.get_score(10);
int get_generations()
What it does:
Returns the number of generations evolved from the initial population.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
int generations = my_population.get_generations();
bool has_converged()
What it does:
Returns whether the population has converged. A gene is said to have converged when 95% of the chromosomes in the population share the same allele (value) for that gene. The population has converged if and only if all genes have converged.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
bool terminate = my_population.has_converged();
Notes:
In the multi-threaded version, the function returns true if and only if all sub-populations have separately converged.
The run() function can be called in a few different ways:
bool run(float min_tolerated_fitness, int max_generations)
What it does:
Evolves the population until at least a chromosome reaches the minimum fitness value, or generations exceed the maximum number.
Returns true if the first condition is reached before the second, false otherwise.
Arguments:
Argument |
Meaning |
Default value |
min_tolerated_fitness |
minimum tolerated fitness value |
|
max_generations |
maximum number of generations before stopping evolution |
|
Example usage:
bool success = my_population.run(20, 1000);
run()
bool run(int stable_generations)
What it does:
Evolves the population until the best fitness value is stable for the indicated number of generations.
Always returns true.
Arguments:
Argument |
Meaning |
Default value |
stable_generations |
number of generations to wait before returning the solution |
|
Example usage:
my_population.run(10);
Notes:
This version of run() is useful when it is not known what can be a “good” fitness value.
run()
bool run()
What it does:
Evolves the population until it converges.
Always returns true.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
my_population.run();
Notes:
If the fitness function isn't well-defined, it is possible that this version of run() will never return. That can also be caused by a bad choice of the selection operator (too randomized selectors like SELECT_UNIFORM are generally not suitable for convergence-based termination conditions).
This version of run() is generally slower than the others since its termination condition is more restrictive, but it assures that the population has reached stability and cannot evolve further.
void cycle()
What it does:
Executes one single step of evolution: selects chromosomes for breeding; breeds them; eventually mutates the new chromosomes.
Arguments:
Argument |
Meaning |
Default value |
Example usage:
while (some_condition) my_population.cycle();
Notes:
If preserve_best is set to true, the best individual is guaranteed to be preserved if evolution doesn't bring a fitter one.
Save/load procedures can be called either with a filename or with a fstream object:
void save(char *file)
What it does:
Saves the population on a plain text file (works for both single- and multi-threaded populations).
Arguments:
Argument |
Meaning |
Default value |
file |
path of the file to write to (if it doesn't exist, it will be created) |
|
Example usage:
my_population.save(“mypop.txt”);
save()
void save(ofstream& out)
What it does:
Saves the population on a plain text file.
Arguments:
Argument |
Meaning |
Default value |
out |
ofstream object to write to |
|
Example usage:
my_population.save(output_stream);
void load(char *file)
What it does:
Loads the population from a plain text file.
Arguments:
Argument |
Meaning |
Default value |
file |
path of the file to read from |
|
Example usage:
my_population.load(“mypop.txt”);
Notes:
- Custom functions like fitness and operators are NOT saved. The population object must still be created, then load() can be called to restore the progress of a past session of evolution (it basically loads all chromosomes and settings).
load()
void load(ifstream& in)
What it does:
Loads the population from a plain text file.
Arguments:
Argument |
Meaning |
Default value |
in |
ifstream object to read from |
|
Example usage:
my_population.load(input_stream);
The migrate() function that follows is available only in the single-threaded Population class, and it is used internally by PopulationMT to implement information exchange between sub-populations:
void migrate(GeneType *c)
What it does:
Migrates the given chromosome in the population, replacing a random element.
Arguments:
Argument |
Meaning |
Default value |
c |
chromosome to copy in population |
|
Example usage:
my_population.migrate(new_chromosome);
Notes:
Migration only replaces chromosomes with fitness below the average value in the target population.
The following functions that control migration policies are available only in the multi-threaded PopulationMT class:
void set_migration_interval(int mint)
What it does:
Sets the number of generations after which migration among sub-populations should be performed.
Arguments:
Argument |
Meaning |
Default value |
mint |
migration interval (number of generations) |
10 |
Example usage:
my_population.set_migration_interval(50);
void set_migration_size(int msize)
What it does:
Sets the maximum number of individuals to be migrated among each couple of populations.
Arguments:
Argument |
Meaning |
Default value |
msize |
number of individuals to be migrated |
n / (10 * (nthreads - 1)) |
Example usage:
my_population.set_migration_size(10);
Notes:
The default value means that, if the topology is a complete graph, after migration from all other sub-populations has been performed, 10% of the target sub-population will have been replaced.
void set_topology(int t)
What it does:
Sets the topology for migration (a graph representing connections among sub-populations).
Arguments:
Argument |
Meaning |
Default value |
t |
topology type. Available options: TOPOLOGY_COMPLETE, TOPOLOGY_RING, TOPOLOGY_BIDIRECTIONAL_RING, TOPOLOGY_ISOLATED |
TOPOLOGY_COMPLETE |
Example usage:
my_population.set_topology(TOPOLOGY_RING);
Notes:
TOPOLOGY_COMPLETE means that migration is performed between all ordered couples of sub-populations.
TOPOLOGY_RING creates a connection from each population i to population i + 1.
TOPOLOGY_BIDIRECTIONAL_RING connects populations i and i + 1 in both directions.
TOPOLOGY_ISOLATED prevents from any kind of migration, so that sub-populations evolve separately without exchanging information.
Copyright © 2007 Alessandro Presta