On the fitness landscapes of interdependency models in the travelling thief problem

Mohamed El Yafrani; Marcella Scoczynski; Myriam R.B.S. Delgado; Ricardo Lüders; Peter Nielsen; Markus Wagner

doi:10.1145/3520304.3528798

On the fitness landscapes of interdependency models in the travelling thief problem

Mohamed El Yafrani, Marcella Scoczynski, Myriam R.B.S. Delgado, Ricardo Lüders, Peter Nielsen, Markus Wagner

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

2 Citations (Scopus)

Abstract

Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling time of the "thief"to the weight of the knapsack. However, other forms of dependency as well as combinations of dependencies should be considered for investigation, as they are often found in complex real-world problems. Our goal is to study the impact of different forms of dependency in the TTP using a simple local search algorithm. To achieve this, we use Local Optima Networks, a technique for analysing the fitness landscape.

Original language	English
Title of host publication	Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion
Editors	Jonathan Fieldsend
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	188-191
Number of pages	4
ISBN (Electronic)	9781450392686
DOIs	https://doi.org/10.1145/3520304.3528798
Publication status	Published - 2022
Externally published	Yes
Event	The Genetic and Evolutionary Computation Conference 2022 - Online, Boston, United States of America Duration: 9 Jul 2022 → 13 Jul 2022 https://dl.acm.org/doi/proceedings/10.1145/3520304 (Proceedings) https://gecco-2022.sigevo.org/HomePage (Website)

Conference

Conference	The Genetic and Evolutionary Computation Conference 2022
Abbreviated title	GECCO 2022
Country/Territory	United States of America
City	Boston
Period	9/07/22 → 13/07/22
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3520304 (Proceedings) https://gecco-2022.sigevo.org/HomePage (Website)

Keywords

basins of attraction
interdependency models
local optima networks
travelling thief problem

Access to Document

10.1145/3520304.3528798

Cite this

Yafrani, M. E., Scoczynski, M., Delgado, M. R. B. S., Lüders, R., Nielsen, P., & Wagner, M. (2022). On the fitness landscapes of interdependency models in the travelling thief problem. In J. Fieldsend (Ed.), Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion (pp. 188-191). Association for Computing Machinery (ACM). https://doi.org/10.1145/3520304.3528798

@inproceedings{e159bebbb428491da18de2aebcd90f3b,

title = "On the fitness landscapes of interdependency models in the travelling thief problem",

abstract = "Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling time of the {"}thief{"}to the weight of the knapsack. However, other forms of dependency as well as combinations of dependencies should be considered for investigation, as they are often found in complex real-world problems. Our goal is to study the impact of different forms of dependency in the TTP using a simple local search algorithm. To achieve this, we use Local Optima Networks, a technique for analysing the fitness landscape.",

keywords = "basins of attraction, interdependency models, local optima networks, travelling thief problem",

author = "Yafrani, {Mohamed El} and Marcella Scoczynski and Delgado, {Myriam R.B.S.} and Ricardo L{\"u}ders and Peter Nielsen and Markus Wagner",

note = "Publisher Copyright: {\textcopyright} 2022 Owner/Author.; The Genetic and Evolutionary Computation Conference 2022, GECCO 2022 ; Conference date: 09-07-2022 Through 13-07-2022",

year = "2022",

doi = "10.1145/3520304.3528798",

language = "English",

pages = "188--191",

editor = "Jonathan Fieldsend",

booktitle = "Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

url = "https://dl.acm.org/doi/proceedings/10.1145/3520304, https://gecco-2022.sigevo.org/HomePage",

}

Yafrani, ME, Scoczynski, M, Delgado, MRBS, Lüders, R, Nielsen, P & Wagner, M 2022, On the fitness landscapes of interdependency models in the travelling thief problem. in J Fieldsend (ed.), Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery (ACM), New York NY USA, pp. 188-191, The Genetic and Evolutionary Computation Conference 2022, Boston, Massachusetts, United States of America, 9/07/22. https://doi.org/10.1145/3520304.3528798

On the fitness landscapes of interdependency models in the travelling thief problem. / Yafrani, Mohamed El; Scoczynski, Marcella; Delgado, Myriam R.B.S. et al.
Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion. ed. / Jonathan Fieldsend. New York NY USA: Association for Computing Machinery (ACM), 2022. p. 188-191.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - On the fitness landscapes of interdependency models in the travelling thief problem

AU - Yafrani, Mohamed El

AU - Scoczynski, Marcella

AU - Delgado, Myriam R.B.S.

AU - Lüders, Ricardo

AU - Nielsen, Peter

AU - Wagner, Markus

PY - 2022

Y1 - 2022

N2 - Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling time of the "thief"to the weight of the knapsack. However, other forms of dependency as well as combinations of dependencies should be considered for investigation, as they are often found in complex real-world problems. Our goal is to study the impact of different forms of dependency in the TTP using a simple local search algorithm. To achieve this, we use Local Optima Networks, a technique for analysing the fitness landscape.

AB - Since its inception in 2013, the Travelling Thief Problem (TTP) has been widely studied as an example of problems with multiple interconnected sub-problems. The dependency in this model arises when tying the travelling time of the "thief"to the weight of the knapsack. However, other forms of dependency as well as combinations of dependencies should be considered for investigation, as they are often found in complex real-world problems. Our goal is to study the impact of different forms of dependency in the TTP using a simple local search algorithm. To achieve this, we use Local Optima Networks, a technique for analysing the fitness landscape.

KW - basins of attraction

KW - interdependency models

KW - local optima networks

KW - travelling thief problem

UR - http://www.scopus.com/inward/record.url?scp=85136323751&partnerID=8YFLogxK

U2 - 10.1145/3520304.3528798

DO - 10.1145/3520304.3528798

M3 - Conference Paper

AN - SCOPUS:85136323751

SP - 188

EP - 191

BT - Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion

A2 - Fieldsend, Jonathan

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - The Genetic and Evolutionary Computation Conference 2022

Y2 - 9 July 2022 through 13 July 2022

ER -

On the fitness landscapes of interdependency models in the travelling thief problem

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this