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.

R Package: mcga

Machine coded genetic algorithm (MCGA) is a fast tool for real-valued optimization problems. It uses the byte representation of variables rather than real-values. It performs the classical crossover operations (uniform) on these byte representations. Mutation operator is also similar to classical mutation operator, which is to say, it changes a randomly selected byte value of a chromosome by +1 or -1 with probability 1/2. In MCGAs there is no need for encoding-decoding process and the classical operators are directly applicable on real-values. It is fast and can handle a wide range of a search space with high precision. Using a 256-unary alphabet is the main disadvantage of this algorithm but a moderate size population is convenient for many problems. Package also includes multi_mcga function for multi objective optimization problems. This function sorts the chromosomes using their ranks calculated from the non-dominated sorting algorithm.

Package Url:

http://cran.r-project.org/web/packages/mcga/index.html

R Installation:

  install.packages ("mcga")

For help and example type

  ?mcga

in R console.