R: Genetic Algorithm

gena {gena}

R Documentation

Genetic Algorithm

Description

This function allows to use genetic algorithm for numeric global optimization of real-valued functions.

Usage

gena(
  fn,
  gr = NULL,
  lower,
  upper,
  pop.n = 100,
  pop.initial = NULL,
  pop.method = "uniform",
  mating.method = "rank",
  mating.par = NULL,
  mating.self = FALSE,
  crossover.method = "local",
  crossover.par = NULL,
  crossover.prob = 0.8,
  mutation.method = "constant",
  mutation.par = NULL,
  mutation.prob = 0.2,
  mutation.genes.prob = 1/length(lower),
  elite.n = min(10, 2 * round(pop.n/20)),
  elite.duplicates = FALSE,
  hybrid.method = "rank",
  hybrid.par = 2,
  hybrid.prob = 0,
  hybrid.opt.par = NULL,
  hybrid.n = 1,
  constr.method = NULL,
  constr.par = NULL,
  maxiter = 100,
  is.max = TRUE,
  info = TRUE,
  ...
)

Arguments

`fn`	function to be maximized i.e. fitness function.
`gr`	gradient of the `fn`.
`lower`	lower bound of the search space.
`upper`	upper bound of the search space.
`pop.n`	integer representing the size of the population.
`pop.initial`	numeric matrix which rows are chromosomes to be included into the initial population. Numeric vector will be coerced to single row matrix.
`pop.method`	the algorithm to be applied for a creation of the initial population. See 'Details' for additional information.
`mating.method`	the algorithm to be applied for a mating i.e. selection of parents. See 'Details' for additional information.
`mating.par`	parameters of the mating (selection) algorithm.
`mating.self`	logical; if `TRUE` then the chromosome may mate with itself i.e. both parents may be the same chromosome.
`crossover.method`	an algorithm to be applied for crossover i.e. creation of the children. See 'Details' for additional information.
`crossover.par`	parameters of the crossover algorithm.
`crossover.prob`	probability of the crossover for each pair of parents.
`mutation.method`	algorithm to be applied for mutation i.e. random change in some genes of the children. See 'Details' for additional information.
`mutation.par`	parameters of the mutation algorithm.
`mutation.prob`	mutation probability for the chromosomes.
`mutation.genes.prob`	mutation probability for the genes.
`elite.n`	number of the elite children i.e. those which have the highest function value and will be preserved for the next population.
`elite.duplicates`	logical; if `TRUE` then some elite children may have the same genes.
`hybrid.method`	hybrids selection algorithm i.e. mechanism determining which chromosomes should be subject to local optimization. See 'Details' for additional information.
`hybrid.par`	parameters of the hybridization algorithm.
`hybrid.prob`	probability of generating the hybrids each iteration.
`hybrid.opt.par`	parameters of the local optimization function to be used for hybridization algorithm (including `fn` and `gr`).
`hybrid.n`	number of hybrids that appear if hybridization should take place during the iteration.
`constr.method`	the algorithm to be applied for imposing constraints on the chromosomes. See 'Details' for additional information.
`constr.par`	parameters of the constraint algorithm.
`maxiter`	maximum number of iterations of the algorithm.
`is.max`	logical; if `TRUE` (default) then fitness function will be maximized. Otherwise it will be minimized.
`info`	logical; if `TRUE` (default) then some optimization related information will be printed each iteration.
`...`	additional parameters to be passed to `fn` and `gr` functions.

Details

To find information on particular methods available via pop.method, mating.method, crossover.method, mutation.method, hybrid.method and constr.method arguments please see 'Details' section of gena.population, gena.crossover, gena.mutation, gena.hybrid and gena.constr correspondingly. For example to find information on possible values of mutation.method and mutation.par arguments see description of method and par arguments of gena.mutation function.

It is possible to provide manually implemented functions for population initialization, mating, crossover, mutation and hybridization. For example manual mutation function may be provided through mutation.method argument. It should have the same signature (arguments) as gena.mutation function and return the same object i.e. the matrix of chromosomes of the appropriate size. Manually implemented functions for other operators (crossover, mating and so on) may be provided in a similar way.

By default function does not impose any constraints upon the parameters. If constr.method = "bounds" then lower and upper constraints will be imposed. Lower bounds should be strictly smaller then upper bounds.

Currently the only available termination condition is maxiter. We are going to provide some additional termination conditions during future updates.

Infinite values in lower and upper are substituted with -(.Machine$double.xmax * 0.9) and .Machine$double.xmax * 0.9 correspondingly.

By default if gr is provided then BFGS algorithm will be used inside optim during hybridization. Otherwise Nelder-Mead will be used. Manual values for optim arguments may be provided (as a list) through hybrid.opt.par argument.

Arguments pop.n and elite.n should be even integers and elite.n should be greater then 2. If these arguments are odd integers then they will be coerced to even integers by adding 1. Also pop.n should be greater then elite.n at least by 2.

For more information on the genetic algorithm please see Katoch et. al. (2020).

Value

This function returns an object of class gena that is a list containing the following elements:

par - chromosome (solution) with the highest fitness (objective function) value.
value - value of fn at par.
population - matrix of chromosomes (solutions) of the last iteration of the algorithm.
counts - a two-element integer vector giving the number of calls to fn and gr respectively.
is.max - identical to is.max input argument.
fitness.history - vector which i-th element is fitness of the best chromosome in i-th iteration.
iter - last iteration number.

References

S. Katoch, S. Chauhan, V. Kumar (2020). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80, 8091-8126. <doi:10.1007/s11042-020-10139-6>

Examples

## Consider Ackley function

fn <- function(par, a = 20, b = 0.2)
{
  val <- a * exp(-b * sqrt(0.5 * (par[1] ^ 2 + par[2] ^ 2))) +
         exp(0.5 * (cos(2 * pi * par[1]) + cos(2 * pi * par[2]))) -
         exp(1) - a
  return(val)
}

# Maximize this function using classical
# genetic algorithm setup
set.seed(123)
lower <- c(-5, -100)
upper <- c(100, 5)
opt <- gena(fn = fn, 
            lower = lower, upper = upper,
            hybrid.prob = 0,
            a = 20, b = 0.2)
print(opt$par)

# Replicate optimization using hybridization
opt <- gena(fn = fn, 
            lower = lower, upper = upper,
            hybrid.prob = 0.2,
            a = 20, b = 0.2)
print(opt$par)


## Consider Rosenbrock function
fn <- function(par, a = 100)
{
  val <- -(a * (par[2] - par[1] ^ 2) ^ 2 + (1 - par[1]) ^ 2 +
           a * (par[3] - par[2] ^ 2) ^ 2 + (1 - par[2]) ^ 2)
  return(val)
}

# Apply genetic algorithm
lower <- rep(-10, 3)
upper <- rep(10, 3)
set.seed(123)
opt <- gena(fn = fn,
            lower = lower, upper = upper,
            a = 100)
print(opt$par)


# Improve the results by hybridization
opt <- gena(fn = fn,
            lower = lower, upper = upper,
            hybrid.prob = 0.2,
            a = 100)
print(opt$par)


# Provide manually implemented mutation function
# which simply randomly sorts genes. 
# Note that this function should have the same 
# arguments as gena.mutation.
mutation.my <- function(children, lower, upper, 
                        prob, prob.genes, 
                        method, par, iter)
{
  # Get dimensional data
  children.n <- nrow(children)
  genes.n <- ncol(children)
  
  # Select chromosomes that should mutate
  random_values <- runif(children.n, 0, 1)
  mutation_ind <- which(random_values <= prob)
   
  # Mutate chromosomes by randomly sorting
  # their genes
  for (i in mutation_ind)
  {
    children[i, ] <- children[i, sample(1:genes.n)]
  }
  
  # Return mutated chromosomes
  return(children)
}

opt <- gena(fn = fn,
            lower = lower, upper = upper,
            mutation.method = mutation.my,
            a = 100)
print(opt$par)

[Package gena version 1.0.0 Index]