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

Mohamed El Yafrani; Marcella Martins; Myriam Delgado; Ricardo Luders; 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 Martins, Myriam Delgado, Ricardo Luders, Peter Nielsen, Markus Wagner

^*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

3 Citations (Scopus)

69 Downloads (Pure)

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	GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
Number of pages	4
Publisher	Association for Computing Machinery (ACM)
Publication date	9 Jul 2022
Pages	188-191
ISBN (Electronic)	9781450392686
DOIs	https://doi.org/10.1145/3520304.3528798
Publication status	Published - 9 Jul 2022
Event	2022 Genetic and Evolutionary Computation Conference, GECCO 2022 - Virtual, Online, United States Duration: 9 Jul 2022 → 13 Jul 2022

Conference

Conference	2022 Genetic and Evolutionary Computation Conference, GECCO 2022
Country/Territory	United States
City	Virtual, Online
Period	09/07/2022 → 13/07/2022
Sponsor	ACM SIGEVO

Series	GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

Bibliographical note

Publisher Copyright:
© 2022 Owner/Author.

Keywords

basins of attraction
interdependency models
local optima networks
travelling thief problem

Access to Document

10.1145/3520304.3528798

TTP_Gecco2022Submitted manuscript, 1 MBLicence: CC BY 4.0

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

El Yafrani, Mohamed ; Martins, Marcella ; Delgado, Myriam et al. / On the fitness landscapes of interdependency models in the travelling thief problem. GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), 2022. pp. 188-191 (GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference).

@inproceedings{62fc278331ed4e67ac26e7428049d59d,

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 = "{El Yafrani}, Mohamed and Marcella Martins and Myriam Delgado and Ricardo Luders and Peter Nielsen and Markus Wagner",

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

year = "2022",

month = jul,

day = "9",

doi = "10.1145/3520304.3528798",

language = "English",

series = "GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference",

pages = "188--191",

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

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

address = "United States",

}

El Yafrani, M, Martins, M, Delgado, M, Luders, R, Nielsen, P & Wagner, M 2022, On the fitness landscapes of interdependency models in the travelling thief problem. in GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference, pp. 188-191, 2022 Genetic and Evolutionary Computation Conference, GECCO 2022, Virtual, Online, United States, 09/07/2022. https://doi.org/10.1145/3520304.3528798

On the fitness landscapes of interdependency models in the travelling thief problem. / El Yafrani, Mohamed; Martins, Marcella; Delgado, Myriam et al.
GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), 2022. p. 188-191 (GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

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

AU - El Yafrani, Mohamed

AU - Martins, Marcella

AU - Delgado, Myriam

AU - Luders, Ricardo

AU - Nielsen, Peter

AU - Wagner, Markus

PY - 2022/7/9

Y1 - 2022/7/9

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 - Article in proceeding

AN - SCOPUS:85136323751

T3 - GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

SP - 188

EP - 191

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

PB - Association for Computing Machinery (ACM)

T2 - 2022 Genetic and Evolutionary Computation Conference, GECCO 2022

Y2 - 9 July 2022 through 13 July 2022

ER -

El Yafrani M, Martins M, Delgado M, Luders R, Nielsen P, Wagner M. On the fitness landscapes of interdependency models in the travelling thief problem. In GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM). 2022. p. 188-191. (GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference). doi: 10.1145/3520304.3528798

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

Abstract

Conference

Bibliographical note

Keywords

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this