 |
    |
GA-Hardness Revisited
Haipeng Guo and William H. Hsu
Department of Computing and Information Sciences
Kansas State University
Manhattan, KS 66502
{hpguo,bhsu}@cis.ksu.edu
Abstract. Ever since the invention of Genetic Algorithms (GAs), researchers have put a lot of efforts into understanding what makes a function or problem instance hard for GAs to optimize. Many measures have been proposed to distinguish so-called GA-hard from GA-easy problems. None of these, however, has yet achieved the goal of being a reliable predictive GA-hardness measure. In this paper, we first present a general, abstract theoretical framework of instance hardness and algorithm performance based on Kolmogorov complexity. We then list several major misconceptions of GA-hardness research in the context of this theory. Finally, we propose some future directions.
LNCS 2724, p. 1584 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003