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

Leonardo Vanneschi

doi:10.1007/978-3-642-01129-0_74

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

Leonardo Vanneschi

NOVA Information Management School (NOVA IMS)

Research output: Chapter in Book/Report/Conference proceeding › Chapter

4 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 language	Unknown
Title of host publication	Applications of Evolutionary Computing, Proceedings
Editors	M 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 Publication	Berlin
Publisher	SPRINGER-VERLAG BERLIN
Pages	645-654
Volume	5484
ISBN (Print)	0302-9743 978-3-642-01128-3
DOIs	https://doi.org/10.1007/978-3-642-01129-0_74
Publication status	Published - 1 Jan 2009

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag Berlin

Access to Document

10.1007/978-3-642-01129-0_74

Cite this

Vanneschi, L. (2009). NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. In M. 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 (Eds.), Applications of Evolutionary Computing, Proceedings (Vol. 5484, pp. 645-654). (Lecture Notes in Computer Science). SPRINGER-VERLAG BERLIN. https://doi.org/10.1007/978-3-642-01129-0_74

Vanneschi, Leonardo. / NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. Applications of Evolutionary Computing, Proceedings. editor / M 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. Vol. 5484 Berlin : SPRINGER-VERLAG BERLIN, 2009. pp. 645-654 (Lecture Notes in Computer Science).

@inbook{6c4d4143ecd84b6c9efe8eec10cc7740,

title = "NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results",

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.",

keywords = "landscapes, fitness",

author = "Leonardo Vanneschi",

note = "ISI Document Delivery No.: BJH22 Times Cited: 0 Cited Reference Count: 13 Vanneschi, Leonardo Verel, Sebastien Tomassini, Marco Collard, Philippe Proceedings Paper EvoWorkshops 2009 Apr 15-17, 2009 Tubingen, GERMANY Eberhard Karls Univ Tubingen, German Res Fdn, Edinburgh Napier Univ, Ctr Emergent Comp, Natl Res Council Heidelberger platz 3, d-14197 berlin, germany",

year = "2009",

month = jan,

day = "1",

doi = "10.1007/978-3-642-01129-0_74",

language = "Unknown",

isbn = "0302-9743 978-3-642-01128-3",

volume = "5484",

series = "Lecture Notes in Computer Science",

publisher = "SPRINGER-VERLAG BERLIN",

pages = "645--654",

editor = "M Giacobini and A Brabazon and S Cagnoni and GA DiCaro and A Ekart and AI EsparciaAlcazar and M Farooq and A Fink and P Machado and J McCormack and M Oneill and F Neri and M Preuss and F Rothlauf and E Tarantino and S Yang",

booktitle = "Applications of Evolutionary Computing, Proceedings",

}

Vanneschi, L 2009, NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. in M 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 (eds), Applications of Evolutionary Computing, Proceedings. vol. 5484, Lecture Notes in Computer Science, SPRINGER-VERLAG BERLIN, Berlin, pp. 645-654. https://doi.org/10.1007/978-3-642-01129-0_74

NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. / Vanneschi, Leonardo.

Applications of Evolutionary Computing, Proceedings. ed. / M 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. Vol. 5484 Berlin : SPRINGER-VERLAG BERLIN, 2009. p. 645-654 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

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

AU - Vanneschi, Leonardo

N1 - ISI Document Delivery No.: BJH22 Times Cited: 0 Cited Reference Count: 13 Vanneschi, Leonardo Verel, Sebastien Tomassini, Marco Collard, Philippe Proceedings Paper EvoWorkshops 2009 Apr 15-17, 2009 Tubingen, GERMANY Eberhard Karls Univ Tubingen, German Res Fdn, Edinburgh Napier Univ, Ctr Emergent Comp, Natl Res Council Heidelberger platz 3, d-14197 berlin, germany

PY - 2009/1/1

Y1 - 2009/1/1

N2 - 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.

AB - 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.

KW - landscapes

KW - fitness

U2 - 10.1007/978-3-642-01129-0_74

DO - 10.1007/978-3-642-01129-0_74

M3 - Chapter

SN - 0302-9743 978-3-642-01128-3

VL - 5484

T3 - Lecture Notes in Computer Science

SP - 645

EP - 654

BT - Applications of Evolutionary Computing, Proceedings

A2 - Giacobini, M

A2 - Brabazon, A

A2 - Cagnoni, S

A2 - DiCaro, GA

A2 - Ekart, A

A2 - EsparciaAlcazar, AI

A2 - Farooq, M

A2 - Fink, A

A2 - Machado, P

A2 - McCormack, J

A2 - Oneill, M

A2 - Neri, F

A2 - Preuss, M

A2 - Rothlauf, F

A2 - Tarantino, E

A2 - Yang, S

PB - SPRINGER-VERLAG BERLIN

CY - Berlin

ER -

Vanneschi L. NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. In Giacobini M, Brabazon A, Cagnoni S, DiCaro GA, Ekart A, EsparciaAlcazar AI, Farooq M, Fink A, Machado P, McCormack J, Oneill M, Neri F, Preuss M, Rothlauf F, Tarantino E, Yang S, editors, Applications of Evolutionary Computing, Proceedings. Vol. 5484. Berlin: SPRINGER-VERLAG BERLIN. 2009. p. 645-654. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-01129-0_74