A quick tour of GA

A quick tour of GA

This is my note for learning A quick tour of GA.

Genetic algorithms(GAs) are stochastic search algorithms inspired by the basic principles of biological evolution and natural selection. GAs simulate the evolution of living organisms, where the fittest individuals dominate over the weaker ones, by mimicking the biological mechanisms of evolution, such as selection, crossover and mutation.

The R Package GA provides a collection of general purpose functions for optimization using genetic algorithms. The package includes a flexible set of tools for implementing genetic algorithms search in both continuous and discrete case, whether constrained or not. Users can easily define their own objective function depending on the problem at hand. Several genetic operators are available and can be combined to explore the best setting for the current task. Furthermore, users can define new genetic operators and easily evaluate their performances. Local search using general-purpose optimisation algorithms can be applied stochastically to exploit interesting regions. GAs can be run sequentially or in parallel. using an explicit master-slave parallelisation (主从并行化) or a coarse-grain isolands approach(粗粒度孤岛方法).

R
1
2
library(GA)
library(basetheme)

Function optimisation in one dimension

R
1
2
3
4
5
6
f <- function(x){
(x^2 + x) * cos(x)
}
lbound <- -10; ubound <- 10
basetheme("brutal")
curve(f, from = lbound, to = ubound, n = 1000)

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
GA <- ga(type = "real-valued", 
fitness = f,
lower = c(th = lbound),
upper = c(ubound))
summary(GA)

#> ── Genetic Algorithm ───────────────────

#> GA settings:
#> Type = real-valued
#> Population size = 50
#> Number of generations = 100
#> Elitism = 2
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> th
#> lower -10
#> upper 10

#> GA results:
#> Iterations = 100
#> Fitness function value = 47.70562
#> Solution =
#> th
#> [1,] 6.560576
R
1
plot(GA)

R
1
2
3
curve(f, from = lbound, to = ubound, n = 1000)
points([email protected], [email protected],
col = 2, pch = 19)

Function optimisation in two dimensions

R
1
2
3
4
5
6
Rastrigin <- function(x1, x2){
20 + x1^2 + x2^2 - 10 * (cos(2 * pi * x1) + cos(2 * pi * x2))
}
x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)
f <- outer(x1, x2, Rastrigin)
persp3D(x1, x2, f, theta = 50, phi = 20, col.palette = bl2gr.colors)

R
1
filled.contour(x1, x2, f, color.palette = bl2gr.colors)

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
GA <- ga(type = "real-valued",
fitness = function(x) - Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12), upper = c(5.12, 5.12),
popSize = 50, maxiter = 1000, run = 100)
summary(GA)

#> ── Genetic Algorithm ───────────────────

#> GA settings:
#> Type = real-valued
#> Population size = 50
#> Number of generations = 1000
#> Elitism = 2
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> x1 x2
#> lower -5.12 -5.12
#> upper 5.12 5.12

#> GA results:
#> Iterations = 226
#> Fitness function value = -5.284561e-06
#> Solution =
#> x1 x2
#> [1,] 3.810227e-05 -0.0001586974

plot(GA)

R
1
2
3
4
5
6
7
filled.contour(
x1, x2, f,
color.palette = bl2gr.colors,
plot.axes = {axis(1); axis(2);
points([email protected][, 1], [email protected][, 2],
pch = 3, cex = 2, col = "white",
lwd = 2)})

The GA search process can be visualised by defining a monitoring function as follows:

R
1
2
3
4
5
6
7
8
9
10
11
12
13
monitor <- function(obj){
contour(x1, x2, f, drawlabels = F,
col = grey(0.5))
title(paste("iteration = ", [email protected]),
font.main = 1)
points([email protected], pch = 20, col = 2)
}
GA <- ga(type = "real-valued",
fitness = function(x) -Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12),
upper = c(5.12, 5.12),
popSize = 50, maxiter = 100,
monitor = monitor)

Setting some members of the initial population

The suggestions argument to ga() function call can be used to provide a matrix of solutions to be inclued in the initial population.

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
suggestedSol <- matrix(c(0.2, 1.5, -1.5, 0.5), nrow = 2, ncol = 2, byrow = TRUE)
GA1 <- ga(type = "real-valued",
fitness = function(x) -Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12), upper = c(5.12, 5.12),
suggestions = suggestedSol,
popSize = 50, maxiter = 1)
head([email protected])

#> [,1] [,2]
#> [1,] 0.200000 1.5000000
#> [2,] -1.500000 0.5000000
#> [3,] -4.953995 -0.1242975
#> [4,] 1.131681 -1.3110331
#> [5,] 2.092647 2.6630662
#> [6,] 1.664817 2.7611906

As it can be seen, the first two solution considered are those provided, whereas the rest is filled randomly as usual. A full search can be obtained as follows:

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
GA <- ga(type = "real-valued",
fitness = function(x) -Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12), upper = c(5.12, 5.12),
suggestions = suggestedSol,
popSize = 50, maxiter = 100)
summary(GA)

#> ── Genetic Algorithm ───────────────────

#> GA settings:
#> Type = real-valued
#> Population size = 50
#> Number of generations = 100
#> Elitism = 2
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> x1 x2
#> lower -5.12 -5.12
#> upper 5.12 5.12
#> Suggestions =
#> x1 x2
#> 1 0.2 1.5
#> 2 -1.5 0.5

#> GA results:
#> Iterations = 100
#> Fitness function value = -3.862743e-06
#> Solution =
#> x1 x2
#> [1,] 0.0001220222 6.768184e-05

Constrained optimisation

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
f <- function(x){
100 * (x[1]^2 - x[2])^2 + (1 - x[1])^2
}
c1 <- function(x){
x[1] * x[2] + x[1] - x[2] + 1.5
}
c2 <- function(x){
10 - x[1] * x[2]
}
ngrid <- 250
x1 <- seq(0, 1, length = ngrid)
x2 <- seq(0, 13, length = ngrid)
x12 <- expand.grid(x1, x2)
col <- adjustcolor(bl2gr.colors(4)[2:3], alpha = 0.2)
plot(x1, x2, type = "n", xaxs = "i", yaxs = "i")
image(x1, x2, matrix(ifelse(apply(x12, 1, c1) <= 0, 0, NA), nrow = ngrid, ncol = ngrid),
col = col[1], add = TRUE)
image(x1, x2, matrix(ifelse(apply(x12, 1, c2) <= 0, 0, NA), nrow = ngrid, ncol = ngrid),
col = col[2], add = TRUE)
contour(x1, x2, matrix(apply(x12, 1, f), nrow = ngrid, ncol = ngrid),
nlevels = 21, add = TRUE)

A GA solution can be obtained by defining a penalised fitness function:

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
fitness <- function(x){
f <- f(x)
pen <- sqrt(.Machine$double.xmax)
# 大于 0 就给予一个无限大的惩罚
penalty1 <- max(c1(x), 0) * pen
penalty2 <- max(c2(x), 0) * pen
f - penalty1 - penalty2
}

GA <- ga("real-valued",
fitness = fitness,
lower = c(0, 0), upper = c(1, 13),
maxiter = 1000, run = 200, seed = 123)
summary(GA)

#> ── Genetic Algorithm ───────────────────
#>
#> GA settings:
#> Type = real-valued
#> Population size = 50
#> Number of generations = 1000
#> Elitism = 2
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> x1 x2
#> lower 0 0
#> upper 1 13
#>
#> GA results:
#> Iterations = 1000
#> Fitness function value = 15323.33
#> Solution =
#> x1 x2
#> [1,] 0.7728004 12.97594

fitness([email protected])
#> [1] 15323.33
f([email protected])
#> [1] 15323.33

c1([email protected])
#> [1] -0.6753282

c2([email protected])
#> [1] -0.02781433

A graph showing the the solution found is obtained as:

R
1
2
3
4
5
6
7
8
plot(x1, x2, type = "n", xaxs = "i", yaxs = "i")
image(x1, x2, matrix(ifelse(apply(x12, 1, c1) <= 0, 0, NA), ngrid, ngrid),
col = col[1], add = TRUE)
image(x1, x2, matrix(ifelse(apply(x12, 1, c2) <= 0, 0, NA), ngrid, ngrid),
col = col[2], add = TRUE)
contour(x1, x2, matrix(apply(x12, 1, f), ngrid, ngrid),
nlevels = 21, add = TRUE)
points([email protected][1], [email protected][2], col = "dodgerblue3", pch = 3) # GA solution

Hybrid GAs

Hybrid Genetic Algothrms (HGAs) incorporate efficient local search algorithms into GAs. In case of real-valued optimisation problems, the GA package provides a simple way to start local searchs from GA solutions after a certain number of iterations, so that, once a promising region is identified, the convergence to the local optimum can be speed up.

The use of HGAs is controlled by the optional argument optim = TRUE (by default is set to FALSE). Local searches are executed using the base R function optim(), which makes avaiable general-purpose optimisation methods, such as Nelder-Mead, quasi-Newton with and without box constraints, and conjugate-gradient algorithms. The local search method to be used and other parameters are controlled with the optional argument optimArgs, which must be a list with the following structure and defaults.

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
optimArgs <- list(
method = "L-BFGS-B",
poptim = 0.05,
pressel = 0.5,
control = list(fnscale = -1,
maxit = 100)
)
GA <- ga(type = "real-valued",
fitness = function(x) -Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12),
upper = c(5.12, 5.12),
popSize = 50, maxiter = 10000,
run = 100, optim = TRUE)
summary(GA)

#> ── Genetic Algorithm ───────────────────

#> GA settings:
#> Type = real-valued
#> Population size = 50
#> Number of generations = 10000
#> Elitism = 2
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> x1 x2
#> lower -5.12 -5.12
#> upper 5.12 5.12

#> GA results:
#> Iterations = 110
#> Fitness function value = 0
#> Solution =
#> x1 x2
#> [1,] 0 0

plot(GA)

Parallel computing

Consider the following simple example where a pause statement is introduced to simulate an expensive fitness function.

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
library(GA)
fitness <- function(x){
Sys.sleep(0.01)
x * runif(1)
}
library(rbenchmark)
out <- benchmark(
GA1 = ga(type = "real-valued",
fitness = fitness,
lower = 0,
upper = 1,
popSize = 50,
maxiter = 100,
monitor = FALSE,
seed = 12345),
GA2 = ga(type = "real-valued",
fitness = fitness,
lower = 0,
upper = 1,
popSize = 50,
maxiter = 100,
monitor = FALSE,
seed = 12345,
parallel = TRUE),
GA3 = ga(type = "real-valued",
fitness = fitness,
lower = 0,
upper = 1,
popSize = 50,
maxiter = 100,
monitor = FALSE,
seed = 12345,
parallel = 2),
GA4 = ga(type = "real-valued",
fitness = fitness,
lower = 0,
upper = 1,
popSize = 50,
maxiter = 100,
monitor = FALSE,
seed = 12345,
parallel = "snow"),
columns = c("test", "replications", "elapsed", "relative"),
order = "test",
replications = 10
)

out$average <- with(out, average <- elapsed / replications)
out[, c(1:3, 5, 4)]

#> test replications elapsed average relative
#> 1 GA1 10 514.516 51.4516 2.902
#> 2 GA2 10 177.274 17.7274 1.000
#> 3 GA3 10 296.982 29.6982 1.675
#> 4 GA4 10 262.092 26.2092 1.478

Island evolution

GAs can be designed to evolve using an Island evolution approach. Here the population is partitioned in a set of sub-populations (islands) in which isolated GAs are executed on separated processor runs. Occasionally, some individuals from an island migrate to another island, thus allowing sub-populations to share genetic material.

This approach is implemented in the gaisl() function, which has the same input arguments as the ga() function, with the addition of the following argument:

  1. numIslands: an integer value specifying the number of islands to use (by default is set to 4).
  2. migrationRate: a value in the range (0, 1) which gives the proportion of individuals that undergo migration between islands in every exchange (by default equal to 0.10).
  3. migrationInterval: an integer value specifying the number of interations at which exchange of individuals takes place (by default set at 10).

Parallel computing is used by default in the Island evolution approach. Hybridistion by local search is also availabel as discussed previously.

R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
GA <- gaisl(type = "real-valued",
fitness = function(x) -Rastrigin(x[1], x[2]),
lower = c(-5.12, -5.12),
upper = c(5.12, 5.12),
popSize = 100,
maxiter = 1000, run = 100,
numIslands = 4,
migrationRate = 0.2,
migrationInterval = 50)
summary(GA)

#> ── Islands Genetic Algorithm ───────────

#> GA settings:
#> Type = real-valued
#> Number of islands = 4
#> Islands pop. size = 25
#> Migration rate = 0.2
#> Migration interval = 50
#> Elitism = 1
#> Crossover probability = 0.8
#> Mutation probability = 0.1
#> Search domain =
#> x1 x2
#> lower -5.12 -5.12
#> upper 5.12 5.12

#> GA results:
#> Iterations = 600
#> Epochs = 12
#> Fitness function values = -3.403443e-08 -3.168482e-08 -3.168482e-08 -3.168482e-08
#> Solutions =
#> x1 x2
#> [1,] 5.226443e-06 -1.200981e-05
#> [2,] -5.908544e-06 -1.117127e-05
#> [3,] -5.908544e-06 -1.117127e-05
#> [4,] -5.908544e-06 -1.117127e-05

plot(GA)

# R

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×