Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6858544 | Information Sciences | 2014 | 22 Pages |
Abstract
This paper presents rigorous theoretical and numerical analyses of the runtime of the (1Â +Â 1) EA and random search on several selected instance classes of this problem. The theoretical analysis shows firstly, that there are instance classes where the EA is efficient, while random testing fails completely. Secondly, an instance class that is difficult for both random testing and the EA is presented. Finally, a parametrised instance class with tunable difficulty is presented. The numerical study estimates the constants in the asymptotic expressions obtained in the theoretical analysis, and the variability of the runtime. The numerical results fit well with the theoretical results, even for small problem instance sizes. Together, these results provide a first theoretical characterisation of the potential and limitations of the (1Â +Â 1) EA on the problem of computing UIOs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Per Kristian Lehre, Xin Yao,