Genetic Algorithm

In this document we will be descause about GA algo. and function root finding.
First of all GA library must be installed from CRAN.

suppressWarnings({
if(!require(GA))
  install.packages("GA")})
## Loading required package: GA
## Loading required package: foreach
## Loading required package: iterators
## Package 'GA' version 3.2.1
## Type 'citation("GA")' for citing this R package in publications.
## 
## Attaching package: 'GA'
## The following object is masked from 'package:utils':
## 
##     de

Description of function \(ga()\)

Maximization of a fitness function using genetic algorithms (GAs). Local search using general-purpose optimisation algorithms can be applied stochastically to exploit interesting regions. The algorithm can be run sequentially or in parallel using an explicit master-slave parallelisation.

Arguments

fitness

the fitness function, any allowable R function which takes as input an individual string representing a potential solution, and returns a numerical value describing its “fitness”.

lower

a vector of length equal to the decision variables providing the lower bounds of the search space in case of real-valued or permutation encoded optimizations. Formerly this argument was named min; its usage is allowed but deprecated.

upper

a vector of length equal to the decision variables providing the upper bounds of the search space in case of real-valued or permutation encoded optimizations. Formerly this argument was named max; its usage is allowed but deprecated.

pcrossover

the probability of crossover between pairs of chromosomes. Typically this is a large value and by default is set to 0.8.

pmutation

the probability of mutation in a parent chromosome. Usually mutation occurs with a small probability, and by default is set to 0.1.

maxiter

the maximum number of iterations to run before the GA search is halted.

monitor

a logical or an R function which takes as input the current state of the ga-class object and show the evolution of the search. By default, for interactive sessions the function gaMonitor prints the average and best fitness values at each iteration. If set to plot these information are plotted on a graphical device. Other functions can be written by the user and supplied as argument. In non interactive sessions, by default monitor = FALSE so any output is suppressed.

Simple example

First of all lets define a mathematical function in order to find its zeros with ga algo. This function has an argument x, and its returns \(x^2+x-10\).

func <- function(x){
  return(x^2+x-10)
}

curve(func, from = -5, to = 5)
abline(h=0, lty=2, col="red")

To define a fitness function, it must be considered that the \(ga\) algo. tries to maximize the fitness value. Thus we need to return larger values for those inputs which are close to roots and vice versa. This can be done simply by taking the absolute of the function and multiplying it to -1.

fitness <- function(x){
  return(abs(func(x))*-1)
}
curve(fitness, from = -5, to = 5)
abline(h=0, lty=2, col="red")

We are now ready to use the \(ga\) function!

Root seaching in boundary [-5, 0]

model <- ga(type = "real-valued", fitness = fitness, lower = -5, upper = 0, popSize = 20)
summary(model)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  real-valued 
## Population size       =  20 
## Number of generations =  100 
## Elitism               =  1 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## Search domain = 
##       x1
## lower -5
## upper  0
## 
## GA results: 
## Iterations             = 100 
## Fitness function value = -3.139623e-05 
## Solution = 
##             x1
## [1,] -3.701567
plot(model)

x1 <- model@solution

As we got the result now. Lets plot it.

curve(func, from = -5, to = 5)
abline(h=0, lty=2, col="red")

abline(v=x1, lty=2, col="blue")

Root seaching in boundary [0, 5]

model <- ga(type = "real-valued", fitness = fitness, lower = 0, upper = 5, popSize = 20)
summary(model)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  real-valued 
## Population size       =  20 
## Number of generations =  100 
## Elitism               =  1 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## Search domain = 
##       x1
## lower  0
## upper  5
## 
## GA results: 
## Iterations             = 100 
## Fitness function value = -9.315632e-07 
## Solution = 
##            x1
## [1,] 2.701562
plot(model)

x2 <- model@solution

Lets have both roots at the same plot.

curve(func, from = -5, to = 5)
abline(h=0, lty=2, col="red")

abline(v=x1, lty=2, col="blue")
abline(v=x2, lty=2, col="blue")

An other example

Lets define the function bellow:

func <- function(x){
  return(log(x) - x^2 +1)
}
curve(func, from = 0.4, to=1.4)
abline(h = 0, lwd=1.5, lty=2, col="red")

Also the fitness function will be automatically changed to coresponding function.

curve(fitness, from = 0, to = 2)
abline(h=0, lty=2, col="red")

Root seaching in boundary [0.2, 0.6]

model <- ga(type = "real-valued", fitness = fitness, lower = 0.2, upper = 0.6, popSize = 20)
summary(model)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  real-valued 
## Population size       =  20 
## Number of generations =  100 
## Elitism               =  1 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## Search domain = 
##        x1
## lower 0.2
## upper 0.6
## 
## GA results: 
## Iterations             = 100 
## Fitness function value = -3.275431e-06 
## Solution = 
##             x1
## [1,] 0.4507661
plot(model)

x1 <- model@solution
curve(func, from = 0.2, to = 0.6)
abline(h=0, lty=2, col="red")
abline(v=x1, lty=2, col="blue")

x1
##             x1
## [1,] 0.4507661

Root seaching in boundary [0.6, 1.2]

model <- ga(type = "real-valued", fitness = fitness, lower = 0.6, upper = 1.2, popSize = 20)
summary(model)
## -- Genetic Algorithm ------------------- 
## 
## GA settings: 
## Type                  =  real-valued 
## Population size       =  20 
## Number of generations =  100 
## Elitism               =  1 
## Crossover probability =  0.8 
## Mutation probability  =  0.1 
## Search domain = 
##        x1
## lower 0.6
## upper 1.2
## 
## GA results: 
## Iterations             = 100 
## Fitness function value = -2.510046e-07 
## Solution = 
##             x1
## [1,] 0.9999997
plot(model)

x2 <- model@solution
curve(func, from = 0, to = 2)
abline(h=0, lty=2, col="red")
x2
##             x1
## [1,] 0.9999997
abline(v=x1, lty=2, col="blue")
abline(v=x2, lty=2, col="blue")