Compact Genetic Algorithms with R

Compact Genetic Algorithm (CGA) is a member of Genetic Algorithms (GAs) and also Estimation of Distribution Algorithms (EDAs). Since it is based on a single chromosome rather than a population of chromosomes, it is compact.

For detailed information, research papers [1] and [2] present a complete and a brief documentations, respectively.

In this blog post, we give an example of use of compact genetic algorithms on ONEMAX function. ONEMAX function takes n-bits as parameters and returns the number of ones as integer. Since it is only one local optimum when all of the bits equal to 1, it is called ONEMAX.

First of all, we load the R package eive which includes the wrapped C++ function cga.

> require("eive")

The other step is to define the ONEMAX function.

> ONEMAX <- function (x){
+     return(-sum(x))
+ }

Now we write the main part, optimization with cga:

> result <- cga(chsize = 10 , popsize = 100 , evalFunc = ONEMAX)

> result
 [1] 1 1 1 1 1 1 1 1 1 1

The result is a vector in which the bits are all equal to 1.

The most important issue in this example is speed, because the algorithm is implemented in C++ and wrapped using Rcpp to be called within R.

Here is the example of 1000 bits and the time consumed by the cga function call:

> system.time(
+     result <- cga(chsize = 1000,popsize = 100,evalFunc = ONEMAX)

+ )
   user  system elapsed 
  0.443   0.000   0.433 
> ONEMAX(result)
[1] -994

This result seems to be considerably fast and 994 of 1000 bits are found as 1 by the function in 0.433 seconds. Lets increase the population size from 100 to 200:

> system.time(
+     result <- cga(chsize = 1000,popsize = 200,evalFunc = ONEMAX)

+ )
   user  system elapsed 
  0.891   0.000   0.866 
> print (ONEMAX(result))
[1] -1000

Now, after setting the population size from 100 to 200, function doubles the time consumed to 0.866 seconds. But this time, 1000 of 1000 bits are 1, and the optimal solution is reached.

Have a nice read !



[1] Harik, Georges R., Fernando G. Lobo, and David E. Goldberg. "The compact genetic algorithm." Evolutionary Computation, IEEE Transactions on 3.4 (1999): 287-297.

[2] Satman, M. Hakan, and Erkin Diyarbakirlioglu. "Reducing errors-in-variables bias in linear regression using compact genetic algorithms." Journal of Statistical Computation and Simulation ahead-of-print (2014): 1-20.