optimEA {CEGO}

Evolutionary Algorithm for Combinatorial Optimization

Description

A basic implementation of a simple Evolutionary Algorithm for Combinatorial Optimization. Default evolutionary operators aim at permutation optimization problems.

Usage

optimEA(x = NULL, fun, control = list())

Arguments

x

Optional start individual(s) as a list. If NULL (default), creationFunction (in control list) is used to create initial design. If x has less individuals than the population size, creationFunction will fill up the rest.

fun

target function to be minimized

control

(list), with the options:

budget

The limit on number of target function evaluations (stopping criterion) (default: 1000).

popsize

Population size (default: 100).

generations

Number of generations (stopping criterion) (default: Inf).

targetY

Target function value (stopping criterion) (default: -Inf).

vectorized

Boolean. Defines whether target function is vectorized (takes a list of solutions as argument) or not (takes single solution as argument). Default: FALSE.

verbosity

Level of text output during run. Defaults to 0, no output.

plotting

Plot optimization progress during run (TRUE) or not (FALSE). Default is FALSE.

archive

Whether to keep all candidate solutions and their fitness in an archive (TRUE) or not (FALSE). Default is TRUE. New solutions that are identical to an archived one, will not be evaluated. Instead, their fitness is taken from the archive.

recombinationFunction

Function that performs recombination, default: recombinationPermutationCycleCrossover, which is cycle crossover for permutations.

recombinationRate

Number of offspring, defined by the fraction of the population (popsize) that will be recombined.

mutationFunction

Function that performs mutation, default: mutationPermutationSwap, which is swap mutation for permutations.

parameters

Default parameter list for the algorithm, e.g., mutation rate, etc.

selection

Survival selection process: "tournament" (default) or "truncation".

tournamentSize

Tournament size (default: 2).

tournamentProbability

Tournament probability (default: 0.9).

localSearchFunction

If specified, this function is used for a local search step. Default is NULL.

localSearchRate

Specifies on what fraction of the population local search is applied. Default is zero. Maximum is 1 (100 percent).

localSearchSettings

List of settings passed to the local search function control parameter.

stoppingCriterionFunction

Custom additional stopping criterion. Function evaluated on the population, receiving all individuals (list) and their fitness (vector). If the result is FALSE, the algorithm stops.

verbosity

>0 for text output.

creationFunction

Function to create individuals/solutions in search space. Default is a function that creates random permutations of length 6.

selfAdaption

An optional ParamHelpers object, that describes parameters of the optimization (see parameters) which are subject to self-adaption. An example is given in mutationSelfAdapt.

selfAdaptTau

Positive numeric value, that controls the learning rate of numerical/integer self-adaptive parameters.

selfAdaptP

Value in [0,1]. A probability of mutation for all categorical, self-adaptive parameters.

Value

a list:

xbest

best solution found.

ybest

fitness of the best solution.

x

history of all evaluated solutions.

y

corresponding target function values f(x).

count

number of performed target function evaluations.

message

Termination message: Which stopping criterion was reached.

population

Last population.

fitness

Fitness of last population.

See Also

optimCEGO, optimRS, optim2Opt, optimMaxMinDist

Examples

#First example: permutation optimization
seed=0
#distance
dF <- distancePermutationHamming
#mutation
mF <- mutationPermutationSwap
#recombination
rF <-  recombinationPermutationCycleCrossover 
#creation
cF <- function()sample(5)
#objective function
lF <- landscapeGeneratorUNI(1:5,dF)
#start optimization
set.seed(seed)
res <- optimEA(,lF,list(creationFunction=cF,mutationFunction=mF,recombinationFunction=rF,
	popsize=6,budget=60,targetY=0,verbosity=1,
	vectorized=TRUE)) ##target function is "vectorized", expects list as input
res$xbest 
#Second example: binary string optimization
#number of bits
N <- 50
#target function (simple example)
f <- function(x){
 sum(x)
}
#function to create random Individuals
cf <- function(){
		sample(c(FALSE,TRUE),N,replace=TRUE)
}
#control list
cntrl <- list(
	budget = 100,
	popsize = 5,
	creationFunction = cf,
	vectorized = FALSE, #set to TRUE if f evaluates a list of individuals
	recombinationFunction = recombinationBinary2Point,
	recombinationRate = 0.1,
	mutationFunction = mutationBinaryBitFlip,
	parameters=list(mutationRate = 1/N),
	archive=FALSE #recommended for larger budgets. do not change.
)
#start algorithm
set.seed(1)
res <- optimEA(fun=f,control=cntrl)
res$xbest
res$ybest