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:

Population()

set_crossover_rate()

set_mutation_rate()

set_crossover_type()

set_select_type()

set_tournament_size()

set_elite_size()

set_preserve_best()

get_best()

get_best_score()

get_avg_score()

get_standard_deviation()

get_chromosome()

get_score()

get_generations()

has_converged()

run()

cycle()

save()

load()

migrate()


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:

PopulationMT()

set_crossover_rate()

set_mutation_rate()

set_crossover_type()

set_select_type()

set_tournament_size()

set_elite_size()

set_preserve_best()

get_best()

get_best_score()

get_avg_score()

get_standard_deviation()

get_chromosome()

get_score()

get_generations()

has_converged()

run()

cycle()

save()

load()

set_migration_interval()

set_migration_size()

set_topology()


Functions


Copy-constructors for classes Population and PopulationMT:


Population()

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:


PopulationMT()

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:


set_crossover_rate()

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);


set_mutation_rate()

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);


set_crossover_type()

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:


set_select_type()

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:


set_tournament_size()

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);


set_elite_size()

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);


set_preserve_best()

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);


get_best()

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:


get_best_score()

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();


get_avg_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();


get_standard_deviation()

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();


get_chromosome()

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:


get_score()

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);


get_generations()

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();


has_converged()

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:


The run() function can be called in a few different ways:


run()

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:


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:


cycle()

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:


Save/load procedures can be called either with a filename or with a fstream object:


save()

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);


load()

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:


migrate()

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:


The following functions that control migration policies are available only in the multi-threaded PopulationMT class:


set_migration_interval()

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);


set_migration_size()

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:


set_topology()

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:


Copyright © 2007 Alessandro Presta