Title: Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees

Authors: Matej Crepinsek, Marjan Mernik, Shih-Hsi Liu

Addresses: Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia. ' Faculty of Electrical Engineering and Computer Science, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia. ' Department of Computer Science, California State University, 2576 E. San Ramon, Fresno, USA

Abstract: This paper introduces an ancestry tree-based approach for exploration and exploitation analysis. The approach introduces a data structure to record the evolution history of a population and a number of exploration and exploitation metrics. Such an approach not only provides insight of how and when the exploration and exploitation influence an evolution process, but also how the genetic structure of an individual is affected. It can be used to better understand inner working of an evolutionary algorithm or in evolutionary algorithm designing phase to develop suitable variation operators with good balance between exploration and exploitation. The approach is applied to the multi-objective 0/1 knapsack problem.

Keywords: exploitation; exploration; multi-objective 0-1 knapsack problem; evolutionary algorithms; ancestry trees; evolution process; genetic structure.

DOI: 10.1504/IJICA.2011.037947

International Journal of Innovative Computing and Applications, 2011 Vol.3 No.1, pp.11 - 19

Received: 22 Jul 2010
Accepted: 26 Jul 2010
Published online: 21 Mar 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article