 |
    |
On Algorithm-Dependent Boundary Case Identification for Problem Classes
Chao Qian, Yang Yu, and Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210046, Chinaqianc@lamda.nju.edu.cn
yuy@lamda.nju.edu.cn
zhouzh@lamda.nju.edu.cn
Abstract. Running time analysis of metaheuristic search algorithms has attracted a lot of attention. When studying a metaheuristic algorithm over a problem class, a natural question is what are the easiest and the hardest cases of the problem class. The answer can be helpful for simplifying the analysis of an algorithm over a problem class as well as understanding the strength and weakness of an algorithm. This algorithm-dependent boundary case identification problem is investigated in this paper. We derive a general theorem for the identification, and apply it to a case that the (1+1)-EA with mutation probability less than 0.5 is used over the problem class of pseudo-Boolean functions with a unique global optimum.
LNCS 7491, p. 62 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012