Journal
APPLIED SOFT COMPUTING
Volume 13, Issue 1, Pages 9-26Publisher
ELSEVIER
DOI: 10.1016/j.asoc.2012.08.046
Keywords
Diversity measures; Evolutionary algorithms; Exploration/exploitation balance; Premature convergence
Ask authors/readers for more resources
Practitioners often rely on search results to learn about the performance of a particular optimizer as applied to a real-world problem. However, even the best fitness measure is often not precise enough to reveal the behavior of the optimizer's added features or the nature of the interactions among its parameters. This makes customization of an efficient search method a rather difficult task. The aim of this paper is to propose a diagnostic tool to help determine the impact of parameter setting by monitoring the exploration/exploitation balance (EEB) of the search process, as this constitutes a key characteristic of any population-based optimizer. It is common practice to evaluate the EEB through a diversity measure. For any diagnostic tool developed to perform this function, it will be critical to be able to certify its reliability. To achieve this, the performance of the selected measure needs to be assessed, and the EEB framework must be able to accommodate any landscape structure. We show that to devise a diagnostic tool, the EEB must be viewed from an orthogonal perspective, which means that two diversity measures need to be involved: one for the exploration axis, and one for the exploitation axis. Exploration is best described by a genotypic diversity measure (GDM), while exploitation is better represented by a phenotypic convergence measure (PCM). Our paper includes a complete review of PCM formulations, and compares nearly all the published PCMs over a validation framework involving six test cases that offer controlled fitness distribution. This simple framework makes it possible to portray the underlying behavior of phenotypic formulations based on three established requirements: monotonicity in fitness varieties, twinning, and monotonicity in distance. We prove that these requirements are sufficient to identify phenotypic formulation weaknesses, and, from this conclusion, we propose a new PCM, which, once validated, is shown to comply with all the above-mentioned requirements. We then compare these phenotypic formulations over three specially designed fitness landscapes, and, finally, the new phenotypic formulation is combined with a genotypic formulation to form the foundation of the EEB diagnostic tool. The value of such a tool is substantiated through a comparison of the behaviors of various genetic operators and parameters. Crown Copyright (C) 2012 Published by Elsevier B. V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available