Session:

MOD - Modularity, regularity and hierarchy in open-ended evolutionary computation

Title:

No Free Lunch for Module Encapsulation

Authors:

Ozlem O. Garibay
Ivan I. Garibay
Annie S. Wu

Abstract:

The concept of modularity has been extensively studied in the evolutionary computation community. In contrast with fitness-driven modularity approach, we present an analysis where modules are simply strings of genomic symbols. Our contribution is two fold: we provide a theorem on the impact of the module encapsulation on the search space and, we offer a static mathematical analysis of the necessary conditions for the encapsulation to be beneficial. Under certain assumptions, we prove that encapsulating and replacing all lower level modules or primitives with the higher level counterparts does not affect the size of the search space or bias the search. Encapsulating primitives into modules has two effects on the search space: increase in the size of the search space and bias the search. The size of the search space increases when a new module is encapsulated, since it introduces a new element into the search space alphabet. However, encapsulating ``good'' modules bias the search towards the solution. We define ``good'' modules as modules that are present in the optimal solution and ``bad'' modules as modules that are not. Hence, there is a trade-off between the gains and losses of introducing a new module in terms of search space size and bias. In order for module encapsulation to benefit the search, the encapsulated module should enable the search algorithm to search a smaller space. We provide a closed form expression that determines whether the creation of module will be beneficial in terms of the size of the new search space. Using this expression, we can summarize the effects of encapsulating a module as follows: encapsulating bad modules is always detrimental; encapsulating good modules is advantageous only if the provided expression is satisfied.