Skip to main content

Toward Competent Genetic Algorithms: Linkage Learning

We endorse the term Competent Genetic Algorithms to those GAs that solve hard problems quickly, accurately and reliably [1]. We already know that GAs process building blocks (BB): low order---few specific bits---and low length---small distance between specific bits---schema with above average fitness. However, crossover may disturb these BB. Ideally, crossover should identify the fundamental BB of the problem at hand and mix them well, but in the real world this phenomenon scarcely happens. In order to tackle this issue a radical approach is required: remove the classic selecto-recombinative operators out of the GA loop and develop strategies that automatically identify BBs ensuring that these are not disrupted. Researchers call this strategy as Linkage Learning [2].

Estimation of Distribution Algorithms (EDAs) use probabilistic models that perform the task. They learn a probabilistic model and then build new solutions by sampling candidates from the model.

One of the simplest forms of EDA is the so-called compact genetic algorithm (cGA, [2]). CGA uses a probability vector to represent populations of strings. Furthermore, population is completely replaced by this probability vector---i.e., no explicit population is stored in memory, hence its name. At each iteration cGA generates two solutions out of the probability vector. Then it evaluates these two solutions and finally it updates the probability vector according to the fitness computation.


I coded a simple cGA in R solving the trap-n function: a simple boolean function that is deceptive---i.e., it is misleading toward local optima [1].  The situation is the following: for n = 5, the learner has to reach the chromosome 11111, but the fitness computation misleads the search towards 00000 (a local optima!). Figure 1 depicts this situation in the trap-5 function. This problem is hard for a traditional GA (specially for the simple GA), but cGA solves it quickly and accurately.



In the following I provide the code for the cGA in R. 


1:  #Class definition.  
2:  setClass( "Individual", representation( chromosome="array", fitness="numeric", size="numeric" ) )  
3:  #Constructor.  
4:  Individual <- function( indSize, p ) {  
5:      ind <- array( 0 , indSize )  
6:      for( i in 1:indSize ) {  
7:          if( rbinom( 1, 1, 0.5 ) < p[i] ) {  
8:              ind[i] = 1  
9:          }  
10:      }  
11:      #Trap-5 function fitness computation.  
12:      fit <- 0  
13:      no <- sum( ind )  
14:      if( no <= (indSize - 1) ) {  
15:          fit <- (indSize - 1 ) - no  
16:      } else {  
17:          fit <- indSize  
18:      }  
19:        
20:      new( "Individual", chromosome = as.array( ind ), fitness = fit, size = indSize )  
21:  }  
22:  #Accesor Methods.  
23:  getFitness <- function( obj ) obj@fitness  
24:  getSize <- function( obj ) obj@size  
25:  getChromosome <- function( obj ) obj@chromosome  
26:    
27:  #It updates the probability vector.  
28:  updatePVector <- function( x, y, p, indSize, popSize ) {  
29:      d <- 1 / popSize  
30:      for( i in 1:indSize ) {  
31:          if( x@chromosome[i] > y@chromosome[i] ) {  
32:              p[i] <- p[i] + d  
33:              if( p[i] > 1.0 ) {  
34:                  p[i] = 1.0  
35:              }  
36:          } else if( x@chromosome[i] > y@chromosome[i] ) {  
37:              p[i] <- p[i] - d  
38:              if( p[i] < 0.0 ) {  
39:                  p[i] = 0.0  
40:              }  
41:          }  
42:      }  
43:      return( p )  
44:  }  
45:    
46:  #The main cGA algorithm.  
47:  cGA <- function( indSize, popSize, iterations ) {  
48:      p <- array( 0.5, indSize ) #Vector of probabilities  
49:      t <- 0 #Time stamp.  
50:      while( t != iterations ) {  
51:          x <- Individual( indSize, p )  
52:          y <- Individual( indSize, p )  
53:          if( getFitness( x ) > getFitness( y ) ) {  
54:              p <- updatePVector( x, y, p, indSize, popSize )  
55:          } else {  
56:              p <- updatePVector( y, x, p, indSize, popSize )  
57:          }  
58:          t <- t + 1  
59:      }  
60:      return( p )  
61:  }  
62:  #Usage: cGA( 5, 4, 30 )  
63:    


References

[1] Goldberg, D.E. "The Design of Innovation: Lessons from and for Competent Genetic Algorithms." Kluwer Academic Publishers, Norwell, MA, USA, 2002

[2] Harik, G.R.; Lobo, F.G.; Goldberg, D.E., "The compact genetic algorithm," Evolutionary Computation, IEEE Transactions on, vol. 3, no. 4, pp.287, 297, 1999

Edit: notice that Figure 1 depicted a distinct trap-5 function---in the picture version of the function I forgot to count 0 as a valid solution. Also notice that the fitness function leads the system toward 00000 and not 00001.

Comments

Popular posts from this blog

Toward ensemble methods: A primer with Random Forest

The Kaggle-Higgs competition has attracted my attention very much lately. In this particular challenge, the goal is to generate a predictive model out of a bunch of data taken from distinct LHC’s detectors. The numbers are the following: 250000 properly labeled instances, 30 real-valued features (containing missing values), and two classes, namely background {b} and signal {s}. Also, the site provides a test set consisting of 550000 unlabeled instances. There are nearly 1300 participants while I am writing this post, and a lot of distinct methods are put to the test to win the challenge. Very interestingly, ensemble methods are all in the head of the leaderboard, and the surprise is XGBoost, a gradient boosting method that makes use of binary trees.
After checking the computational horsepower of the XGBoost algorithm by myself, I decided to take a closer look at ensemble methods. To start with, I implemented a Random Forest, an algorithm that consists of many independent binary trees…

High Performance Computing, yet another brief installation tutorial

Today’s mid- and high-end computers come with a tremendous hardware, mostly used in video games and other media software, that can be exploited for advanced computation, that is: High Performance Computing (HPC). This is a hot topic in Deep Learning as modern graphic cards come with huge streaming process power and large and quick memory. The most successful example is in Nvidia’s CUDA platform. In summary, CUDA significantly speeds up the fitting of large neural nets (for instance: from several hours to just a few minutes!).
However, the drawbacks come when setting up the scenario: it is non-trivial to install the requirements and set it running, and personally I had a little trouble the first time as many packages need to be manually compiled and installed in a specific order. The purpose of this entry is to reflect what I did for setting up Theano and Keras with HPC using an Nvidia’s graphic card (in my case a GT730) using GNU/Linux. To do so, I will start assuming a clean Debian …

A conceptual machine for cloning a human driver

If anything else, a Machine Learning practitioner has to get a global view and think on how far our conceptual machines can go. This is a little tale of my recent experience with Deep Learning. To start with, say that I am enrolled in the Udacity’s nanodegree inSelf Driving Car Engineer. Here we are learning the techniques needed for building a car controller capable of driving at the human level. The interesting part of the course (to be read as where one truly learns) is in the so called projects: these are nothing but assignments in which the student has to solve a challenging task, mainly by using Convolutional Neural Networks (convnets), the most well-known Deep Learning models. So far, the most mind-blowing task and the focus of this entry is project 3, were we have to record our driving behavior in a car simulator and let a convnet to clone it and successfully generalize the act of driving. It is remarkable that a convnet learns to control the car from raw color images jointly…