Evolutionary Computation

Structured Genetic Algorithms (st. GA)

The field of biological evolution brought a new age in adaptive computation (AC). Among different evolutionary computation approaches, Genetic Algorithms (GA) are receiving much attention both in academic and industries. Genetic algorithms are general-purpose search procedures based on the mechanisms of natural selection and population genetics. Genetic algorithm-based tools have started growing impact in companies - predicting financial market, in factories - job scheduling etc. with their power of search, optimization, adaptation and learning. For the users of diversified fields, genetic algorithms are appealing because of their simplicity, easy to interface and ease to extensibility.

Despite their generally robust character, as the application increases, there found many domains where formal GAs perform poorly. Several modifications have been suggested to alleviate the difficulties both in the manipulation of encoded information and the ways of representing problem spaces. A number of different models, namely, Messy GAs and Genetic Programmings developed recently which addressed the representation issue of GAs.

Dipankar Dasgupta has been involved in the investigation of a more biologically motivated genetic search model - called the Structured Genetic Algorithm (sGA). The model uses some complex mechanisms of biological systems for developing a more efficient genetic search technique. Specifically, this model incorporates redundant genetic material and a gene activation mechanism which utilizes multi-layered genomic structures for the chromosome. The additional genetic material has many advantages in search and optimization. It mainly serves two purposes: primarily, it can maintain genetic diversity at all time during the search process, where the expected variability largely depends on the amount of redundancy incorporated in the encoding.

The following paragraphs summarize some aspects and advantages of Structured Genetic Algorithms:

• A chromosome is represented by a set of substrings which act as different levels to establish a kind of switch, controlling the expression of down stream genes. These during reproduction are modified by the genetic operators - crossover and mutation etc. - exactly as in simple GAs.

• In decoding to the phenotype, a chromosome is interpreted as a hierarchical genomic structure of the genetic material. Only those genes currently {\em active} in the chromosome contribute to the fitness of the phenotype. The {\em passive} genes are apparently neutral and carried along as redundant genetic material during the evolutionary process.
• Genetic operations altering high-level genes result in changes to the active elements of the genomic structures. Particularly, the role of mutation is twofold: it changes the allele value of any gene, but when it occurs at a higher level it acts as a dominance operator and changes the expression of a set of gene values at the lower level.
• Even when a population converges to its phenotypic space, genotypic diversity still exists which is a unique characteristic of the model. In most other formal genetic models, phenotypic convergence implies genotypic convergence with consequent impoverishment of diversity within the population.
• It can maintain a balance between exploration and exploitation resulting in efficient searching of potential areas of the phenotypic space. Being trapped at a local optimum which causes premature convergence can be avoided.
• The sGA provides a long-term mechanism for preserving and retrieving alternative solutions or previously-expressed building blocks within the chromosomal structures. In non-stationary optimizations, a sGA provides a means of rapid long jump adaptation; whereas a simple GA with the dominance and diploidy used so far can store or retrieve one allele independently, and thus may provide only a short-term preservation.
• Co-evolution can also occur easily among species by simultaneously sampling and preserving different areas of search space in a multi-global fitness landscape. In effect, it can retain multiple optional solutions (or parameter spaces) in function optimization.
• It can achieve optimization of multi-stage problems by defining search spaces in its different layers and can explore and exploit them in a single evolutionary process.

One school of thought (Darwinian) believes that evolutionary changes are gradual; another (Punctuated Equilibria) postulates that evolutionary changes go in sudden bursts, punctuating long periods of stasis when very small evolutionary changes take place in a given lineage. The new model provides a good framework for carrying out studies that could bridge these two theories.

Structured GA's results to date are very encouraging, though there remain many issues for further investigation. It appears to an enhancement of the formal genetic model with a number of practical advantages. This approach has also received favorable attention in the field of evolutionary computation. However, the studies on structured GAs done so far are only the first step toward the broader goal of developing a more efficient genetic search. Further research to understand the behavior of the model and to determine its search properties is in progress.