Niching foundations: Basin identification on fixed-property generated landscapes

Preuss M., Stoean C., Stoean R.

Abstract
The performance of niching based or related evolutionary algorithms clearly depends on problem properties as e.g. the number of local optima of a problem. We assume there must be more such properties currently not taken into account and, following from practical experience, suggest two more, namely basin size contrast (BSC), the size relation of the largest and the smallest basin, and global to local optima contrast (GLC), the height relation of the global and an average local optimum. We investigate the effect of these problem properties on the performance of different basin identification methods (as subtasks of niching algorithms), namely nearest-better clustering, detect-multimodal, and Jarvis-Patrick clustering, individually, or in combinations. Employing an existing problem generator that enables complete control and knowledge of basins, instances are generated and validated according to predefined property values and the basin identification performance data is modeled in order to detect similarities that may be interpreted as effects of the stated properties. We also give recommendations concerning usage of basin identification methods in different situations. Our approach is strongly related to the recently suggested general idea of exploratory landscape analysis (ELA). Copyright 2011 ACM.

Keywords
Basin identification; Clustering; Exploratory landscape analysis; Global optimization; Niching