MEDAL Report 2011003
Advanced Neighborhoods and Problem Difficulty Measures
Mark Hauschild and Martin Pelikan  (2011)

Abstract. While different measures of problem difficulty of fitness landscapes have been proposed, recent studies have shown that many of the common ones do not closely correspond to the actual difficulty of problems when solved by evolutionary algorithms. One of the reasons for this is that most problem difficulty measures are based on neighborhood structures that are quite different from those used in most evolutionary algorithms. This paper examines several ways to increase the accuracy of problem difficulty measures by including linkage information in the measure to more accurately take into account the advanced neighborhoods explored by some evolutionary algorithms. The effects of these modifications of problem difficulty are examined in the context of several simple and advanced evolutionary algorithms. The results are then discussed and promising areas for future research are proposed.

Download PDF

Download PS

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan