Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Analysis of baseline evolutionary algorithms for the packing while travelling problem
Author: Roostapour, V.
Pourhassan, M.
Neumann, F.
Citation: FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2019 / vol.abs/1902.04692, pp.124-132
Publisher: Association for Computing Machinery
Publisher Place: online
Issue Date: 2019
ISBN: 9781450362542
Conference Name: Foundations of Genetic Algorithms (FOGA) (27 Aug 2019 - 29 Aug 2019 : Potsdam, Germany)
Statement of
Vahid Roostapour, Mojgan Pourhassan, Frank Neumann
Abstract: The performance of base-line Evolutionary Algorithms (EAs) on combinatorial problems has been studied rigorously. From the theoretical viewpoint, the literature extensively investigates the linear problems, while the theoretical analysis of the non-linear problems is still far behind. In this paper, variations of the Packing While Travelling (PWT) - also known as the non-linear knapsack problem - are studied as an attempt to analyse the behaviour of EAs on non-linear problems from theoretical perspective. We investigate PWT for two cities and n items with correlated weights and profits, using single-objective and multi-objective algorithms. Our results show that RLS_swap, which differs from the classical RLS by having the ability to swap two bits in one iteration, finds the optimal solution in O(n3) expected time. We also study an enhanced version of GSEMO, which a specific selection operator to deal with exponential population size, and prove that it finds the Pareto front in the same asymptotic expected time. In the case of uniform weights, (1 + 1) EA is able to find the optimal solution in expected time O(n2 log (max{n,pmax})), where pmax is the largest profit of the given items. We also perform an experimental analysis to complement our theoretical investigations and provide additional insights into the runtime behavior.
Rights: © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
RMID: 1000011301
DOI: 10.1145/3299904.3340313
Grant ID:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.