Since GA package does’nt provides integer type, its impossible to work with short positif natural numbers. This paper explains how to use binary type of GA package to solve somes mathematical problems like this mathematical equality: a + 2b + 3c + 4d = n

The GA R package

According to the manual, GA package can work with 3 types of genetic algorithms.

Type Description
“binary” for binary representations of decision variables.
“real-valued” for optimization problems where the decision variables are floating-point representations of real numbers.
“permutation” for problems that involves reordering of a list.

As you can see, we have not the “integer” type needed in somes computations. Despict the fact that we can work with real numbers, these are not suitable for certain calculations, whether in computation time or the fact that we need to work with positive integers.

In any case, the only possibility would be to use the “binary” type. When “binary” type is defined, the chromosome passed as argument to your fitness function is a vector of binary digits, for example:

c(1,0,0,1,1,1,0,1,1,0,1,0,0)

An integer value can be represented in binary, for instance the binary 101010 is 42 in base 10.

So, let’s work with this type

Working with positif integer with GA package

First, we have to choose how many integer variables we need. Say nbvars = 3 for instance.

We choose how many bits we needs to code these variables. The max value in decimal stored in a binary variable is defined as \(Vmax_{10} = 2^n - 1\)

Here we can see the maximum according to the number of bits for some values of n

n \(2^n - 1\)
2 3
3 7
4 15
5 31
6 63
8 255
10 1 023
12 4 095
16 65 535
24 16 777 215
32 4 294 967 295

So, if you choose 8 bits for your variables, you need to set the nBits argument of function ga() to 8 * nbvars so \(nBits = 3 * nbvars = 8 * 3 = 24\).

“bin2int” a function to retrieve them all

As seen above, the binary chromosome is passed as argument to your fitness function as a vector, so we have to retrieve our variables from this one.

The “bin2int” function is able to transform a binary vector to an integer vector. It needs two arguments, the binary vector and the number of bits of your variables.

Function definition

bin2int <- function(x, len) {
  Bin <- paste(x, collapse="")
  V <- stri_sub(Bin, seq(1, stri_length(Bin),by=len), length=len)
  ret <- strtoi(V, base=2)
  ret
}

Test

bin2int(rep(0:1, length=16), 4)
## [1] 5 5 5 5
bin2int(rep(0:1, length=24), 8)
## [1] 85 85 85
bin2int(rep(0:1, length=32), 32)
## [1] 1431655765

Our Simple mathematical equality problem

We want to solve the equality : \(a + 2b + 3c + 4d = 30\)

Where \(a, b, c, d \neq 0\)

One of the solutions is:

7 + (2 x 5) + (3 x 3) + (4 x 1) = 30

Other solutions have been found by the algorithm:

The fitness function

Our fitness function needs to retrieve 4 variables of 4 bits (range values is [0, 15] for each variables, that is \(15^4 = 50625\) possible combinations), nBits argument of the ga() function will be 4 * 4 = 16.

NB: our fitness function has to resolve the equation \(f = a +2b + 3c + 4d - 30 = 0\) where \(a,b,c,d \neq 0\)

solver <- function(x) {
  
  V <- bin2int(x, 4)
  a <- V[1]
  b <- V[2]
  c <- V[3]
  d <- V[4]
  
  R <- abs(((a+2*b+3*c+4*d)-30))
  
  if (a == 0 | b == 0 | c == 0 | d == 0) {
    return(100)
  } else {
    return(R)
  }
}

Running the rules

fitness <- function(x) -solver(x)
system.time({
GA <- ga(type = "binary", nBits=16,
         fitness =  fitness, elitism = 4,
         pcrossover = 0.20, pmutation = 0.1,
         popSize = 32, maxiter = 600, run = 100)

})
##    user  system elapsed 
##   0.179   0.000   0.179
summary(GA)
## +-----------------------------------+
## |         Genetic Algorithm         |
## +-----------------------------------+
## 
## GA settings: 
## Type                  =  binary 
## Population size       =  32 
## Number of generations =  600 
## Elitism               =  4 
## Crossover probability =  0.2 
## Mutation probability  =  0.1 
## 
## GA results: 
## Iterations             = 102 
## Fitness function value = 0 
## Solutions = 
##      x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16
## [1,]  0  0  1  1  0  1  1  0  0   0   0   1   0   0   1   1
## [2,]  0  1  1  1  0  1  1  0  0   0   0   1   0   0   1   0
## [3,]  1  1  1  1  0  0  1  0  0   0   0   1   0   0   1   0
## [4,]  0  1  1  1  0  0  1  1  0   0   1   1   0   0   1   0

Printing well formated result(s)

solution <- GA@solution
for (i in 1:nrow(solution)) {
  S <- bin2int(solution[i,], 4)
  To <- S[1]+2*S[2]+3*S[3]+4*S[4]
  res <-sprintf("Total = %d, a = %d, b = %d, c = %d, d = %d", To, S[1], S[2], S[3], S[4])
  print(res)
}
## [1] "Total = 30, a = 3, b = 6, c = 1, d = 3"
## [1] "Total = 30, a = 7, b = 6, c = 1, d = 2"
## [1] "Total = 30, a = 15, b = 2, c = 1, d = 2"
## [1] "Total = 30, a = 7, b = 3, c = 3, d = 2"

Monitoring

plot(GA)