Andreu Sancho Homepage

In the last post we acknowledged that competent GAs are those that automatically identify building blocks (BBs) and exchange these BBs without disrupting them. As a simple example, the compact genetic algorithm (cGA) was presented for competently solving the trap-n functions. In spite of the good results obtained by cGA in these environments, this algorithm is way too simple for truly tough problems : the m-concatenated trap-n problems, as depicted in Figure 1 . In these kinds of problems, deceptive trap-n functions are concatenated into a single, bigger problem.   cGA’s probability vector representation cannot detect the complicated combinations of BBs so, again, a new strategy to tackle this challenging environments is required: we need an order-n probabilistic optimization algorithm (in contrast cGA is of order-1). Figure 1: the 4-concatenated trap-3: It is composed of four trap-3 functions and the objective is to find  111111111111 , but the problem is deceptive and ...

Genetic Algorithms (GAs), are a search and optimization method inspired in the way nature works with living entities, using evolutionary-based operators. These operators exchange genetic information through different generations until an ending condition, typically the desired solution, is found. In this entry, the formalism of why GAs work is described as proposed by Holland in the middle seventies and later by Goldberg. To do so, we first need to introduce some key concepts, assuming the classical ternary representation {0, 1, *} , where * is the don't care symbol. A fundamental concept in GA theory is the one of schema . A schema is a particular subset among the set of all possible binary strings described by a template composed of the ternary alphabet {0, 1, *} . For instance, the schema 01**1 corresponds to the set of strings of length five (that is, strings composed of five symbols from the ternary alphabet) with a 0 in the first position, an 1 in the second position ...