GeneticAlg.int {gramEvol}

Genetic Algorithm with Integer Chromosomes

Description

Uses genetic algorithm to find the minima of a given cost function. It evolves chromosomes with limited-range integers as codons.

Usage

GeneticAlg.int(genomeLen, codonMin, codonMax, 
    genomeMin = rep.int(codonMin, genomeLen), 
    genomeMax = rep.int(codonMax, genomeLen), 
    suggestions = NULL, popSize = 50, 
    iterations = 100, terminationCost = NA, 
    mutationChance = 1/(genomeLen+1), elitism = floor(popSize/10), 
    geneCrossoverPoints = NULL,
    monitorFunc = NULL, evalFunc, allowrepeat = TRUE, 
    showSettings = FALSE, verbose = FALSE, plapply = lapply)

Arguments

genomeLen

Number of integers (i.e, codons) in chromosome.

codonMin

Minimum integer value range for all codons.

codonMax

Maximum integer value range for all codons.

genomeMin

A vector of length genomeLen containing fine-grained control over each codon's minimum. Overrides codonMin.

genomeMax

A vector of length genomeLen containing fine-grained control over each codon's maximum. Overrides codonMax.

suggestions

A list of suggested chromosomes to be used in the initial population. Alternatively, an m-by-n matrix, where m is the number of suggestions and n is the chromosome length.

popSize

Size of the population.

iterations

Number of generations to evolve the population.

terminationCost

Target cost. If the best chromosome's cost reaches this value the algorithm terminates.

mutationChance

The chance of a codon being mutated. It must be between 0 and 1.

geneCrossoverPoints

Codon groupings (genes) to be considered while crossover occurs. If given, odd and even codon groups are exchanged between parents. Otherwise random points are selected and a classic single-point crossover is performed.

elitism

Number of top ranking chromosomes that are directly transfered to next generation without going through evolutionary operations.

monitorFunc

A function that is called at each generation. Can be used to monitor evolution of population.

evalFunc

The cost function.

allowrepeat

Allows or forbids repeated integers in the chromosome.

showSettings

Enables printing GA settings.

verbose

Enables verbose debugging info.

plapply

lapply function used for mapping chromosomes to cost function. See details for parallelization tips.

Details

GeneticAlg.int implements evolutionary algorithms with chromosomes created from integer values in the range of codonMin to codonMax. genomeMin and genomeMax allow fine-grained control of range for individual codons. It first creates an initial population, using suggested inputs suggestions and randomly generated chromosomes. Cost of each chromosome is evaluated using the cost function evalFunc. If one of the chromosomes reaches terminationCost, the algorithm terminates; Otherwise evolutionary operators including selection, cross-over and mutation are applied to the population to create a new generation. This iteration is continued until the required cost is reached or the number of generations exceeds iterations.

At each generation, the supplied monitorFunc is called with a list similar to GeneticAlg.int returning value as its argument.

The evalFunc receives integer sequences and must return a numeric value. The goal of optimization would be to find a chromosome which minimizes this value.

To parallelize cost function evaluation, set plapply to a parallelized lapply, such as mclapply from package parallel. In functions that do not handle data dependencies such as parLapply, variables and functions required for correct execution of evalFunc must be exported to worker nodes before invoking GeneticAlg.int.

Value

A list containing information about settings, population, and the best chromosome.

settings$genomeMin

Minimum of each codon.

Settings$genomeMax

Maximum of each codon.

settings$popSize

Size of the population.

settings$elitism

Number of elite individuals.

settings$iterations

Number of maximum generations.

settings$suggestions

Suggested chromosomes.

settings$mutationChance

Mutation chance.

settings$geneCrossoverPoints

Cross-over points.

population$population

The genomic data of the current population.

population$evaluations

Cost of the latest generation.

population$best

Historical cost of the best chromosomes.

population$mean

Historical mean cost of population.

population$currentIteration

Number of generations evolved until now.

best$genome

The best chromosome.

best$cost

The cost of the best chromosome.

References

This function is partially inspired by genalg package by Egon Willighagen. See https://cran.r-project.org/package=genalg.

See Also

GrammaticalEvolution, EvolutionStrategy.int

Examples

# define the evaluate function
evalfunc <- function(l) {
    # maximize the odd indices and minimize the even indices
    # no repeated values are allowed
    odd <- seq(1, 20, 2)
    even <- seq(2, 20, 2)
    err <- sum(l[even]) - sum(l[odd]);

    stopifnot(!any(duplicated(l))) # no duplication allowed

    return (err)
}

monitorFunc <- function(result) {
    cat("Best of gen: ", min(result$best$cost), "\n")
}

x <- GeneticAlg.int(genomeLen = 20, codonMin = 0, codonMax = 20,
                allowrepeat = FALSE, terminationCost = -110,
                monitorFunc = monitorFunc, evalFunc = evalfunc)

print(x)

best.result <- x$best$genome
print("Odds:")
print(sort(best.result[seq(1, 20, 2)]))
print("Evens:")
print(sort(best.result[seq(2, 20, 2)]))