Exploitation and Exploration Analysis of Elitist Evolutionary Algorithms: A Case Study
This work provides incremental theoretical insights for researchers in evolutionary computation by analyzing specific algorithms on benchmark functions.
The paper tackled the problem of evaluating exploitation and exploration in elitist evolutionary algorithms by proposing metrics based on success probability and one-step improvement rate, and demonstrated through case studies that these capabilities degenerate exponentially with problem dimension while optimization is possible by tuning mutation parameters.
Known as two cornerstones of problem solving by search, exploitation and exploration are extensively discussed for implementation and application of evolutionary algorithms (EAs). However, only a few researches focus on evaluation and theoretical estimation of exploitation and exploration. Considering that exploitation and exploration are two issues regarding global search and local search, this paper proposes to evaluate them via the success probability and the one-step improvement rate computed in different domains of integration. Then, case studies are performed by analyzing performances of (1+1) random univariate search and (1+1) evolutionary programming on the sphere function and the cheating problem. By rigorous theoretical analysis, we demonstrate that both exploitation and exploration of the investigated elitist EAs degenerate exponentially with the problem dimension $n$. Meanwhile, it is also shown that maximization of exploitation and exploration can be achieved by setting an appropriate value for the standard deviation $σ$ of Gaussian mutation, which is positively related to the distance from the present solution to the center of the promising region.