Title

On The Performance Effects Of Unbiased Module Encapsulation

Keywords

Module encapsulation; Runtime analysis; Search space bias

Abstract

A recent theoretical investigation of modular representations shows that certain modularizations can introduce a distance bias into a landscape. This was a static analysis, and empirical investigations were used to connect formal results to performance. Here we replace this experimentation with an introductory runtime analysis of performance. We study a base-line, unbiased modularization that makes use of a complete module set (CMS), with special focus on strings that grow logarithmically with the problem size. We learn that even unbiased modularizations can have profound effects on problem performance. Our (1+1) CMS-EA optimizes a generalized OneMax problem in Ω(n2) time, provably worse than a (1+1) EA. More generally, our (1+1) CMS-EA optimizes a particular class of concatenated functions in O(2lm k n) time, where lm is the length of module strings and k is the number of module positions, when the modularization is aligned with the problem separability. We compare our results to known results for traditional EAs, and develop new intuition about modular encapsulation. We observe that search in the CMS-EA is essentially conducted at two levels (intra- and extra-module) and use this observation to construct a module trap, requiring super-polynomial time for our CMS-EA and O(n ln n) for the analogous EA. Copyright 2009 ACM.

Publication Date

12-31-2009

Publication Title

Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

Number of Pages

1729-1736

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/1569901.1570133

Socpus ID

72749099506 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/72749099506

This document is currently not available here.

Share

COinS