NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Citations (Scopus)

Abstract

Negative Slope Coefficient is an indicator of problem hardness that has been introduced in 2004 and that has returned promising results on a large set of problems. It is based oil the concept of fitness cloud and works by partitioning the cloud into a number of bills representing as many different regions of the fitness landscape. The measure is calculated by joining the bills centroids by segments and summing all their negative slopes. In this paper, for the first time, we point out it potential problem of the Negative Slope Coefficient: We Study its value for different instances of the well known NK-landscapes and we show how this indicator is dramatically influenced by the minimum number of points contained in a bill. Successively, we formally justify this behavior of the Negative Slope Coefficient and we discuss pros and cons of this measure.
Original languageUnknown
Title of host publicationApplications of Evolutionary Computing, Proceedings
EditorsM Giacobini, A Brabazon, S Cagnoni, GA DiCaro, A Ekart, AI EsparciaAlcazar, M Farooq, A Fink, P Machado, J McCormack, M Oneill, F Neri, M Preuss, F Rothlauf, E Tarantino, S Yang
Place of PublicationBerlin
PublisherSPRINGER-VERLAG BERLIN
Pages645-654
Volume5484
ISBN (Print)0302-9743 978-3-642-01128-3
DOIs
Publication statusPublished - 1 Jan 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag Berlin

Cite this