Let’s get ready to rumble redux: Crossover versus mutation head to head on exponentially scaled problems
11 February 2007Sastry, K., Goldberg, D. E. (2007). IlliGAL Report No. 2007005. University of Illinois at Urbana-Champaign, Urbana IL. [Full paper - PDF] [Full paper - PS].
Abstract:
This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems with substructures of non-uniform salience. This study assumes that the recombination and mutation operators have the knowledge of the building blocks (BBs) and effectively exchange or search among competing BBs. Facetwise models of convergence time and population sizing have been used to determine the scalability of each algorithm. The analysis shows that for deterministic exponentially-scaled additively separable, problems, the BB-wise mutation is more efficient than crossover yielding a speedup of ?(l logl), where l is the problem size. For the noisy exponentially-scaled problems, the outcome depends on whether scaling on noise is dominant. When scaling dominates, mutation is more efficient than crossover yielding a speedup of ?(l logl). On the other hand, when noise dominates, crossover is more efficient than mutation yielding a speedup of ?(l).
Related Posts:
- Let’s get ready to rumble redux: Crossover versus mutation head to head on exponentially scaled problems
- Let’s get ready to rumble: Crossover versus mutation head to head
- Combining Competent Crossover and Mutation Operators: A Probabilistic Model Building Approach
- Hierarchical BOA on random decomposable problems
- Inducing sequentiality using grammatical genetic codes
No comments yet
