The modular genetic algorithm: Exploiting regularities in the problem space

    Authors

    O. O. Garibay; Garibay, II;A. S. Wu

    Keywords

    Computer Science, Artificial Intelligence; Computer Science, Information; Systems; Computer Science, Software Engineering; Computer Science, ; Theory & Methods

    Abstract

    We introduce the modular genetic algorithm (MGA). The modular genetic algorithm is a search algorithm designed for a class of problems pervasive throughout nature and engineering: problems with modularity and regularity in their solutions. We hypothesize that genetic search algorithms with explicit mechanisms to exploit regularity and modularity on the problem space would not only outperform conventional genetic search, but also scale better for this problem class. In this paper we present experimental evidence in support of our hypothesis. In our experiments, we compare a limited version of the modular genetic algorithm with a canonical genetic algorithm (CA) applied to the checkerboard-pattern discovery problem for search spaces of sizes 2(32), 2(128), and 2(512). We observe that the MGA significantly outperforms the CA for high complexities. More importantly, while the performance of the CA drops 22.50% when the complexity of the problem increases, the MGA performance drops only 11.38%. These results indicate that the MGA has a strong scalability property for problems with regularity and modularity in their solutions.

    Journal Title

    Computer and Information Sciences - Iscis 2003

    Volume

    2869

    Publication Date

    1-1-2003

    Document Type

    Article

    Language

    English

    First Page

    584

    Last Page

    591

    WOS Identifier

    WOS:000188096800073

    ISSN

    0302-9743; 3-540-20409-1

    Share

    COinS