Analysis of baseline evolutionary algorithms for the packing while travelling problem

DOI10.1145/3299904.3340313MaRDI QIDQ5215486zbMATH OpenOpenAlexFDO

Authors Vahid Roostapour, Mojgan Pourhassan, F. Neumann

Publication date 11 February 2020

Published in Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.04692

zbMATH Keywords

evolutionary algorithmsruntime analysis(1+1) EApacking-while-travelling problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27)

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(n^3)$ 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(n^{2}log(maxn,p_{max}))$, where $p_{max}$ 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.

Recommendations

• An evolutionary algorithm based hyper-heuristic framework for the set packing problem
• Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem
• Evolutionary algorithms for knapsack problems
• A hybrid evolutionary algorithm for the two-dimensional packing problem
• A hybrid evolutionary approach for set packing problem
• A hybrid evolutionary algorithm for the offline Bin Packing Problem
• Analysis of solution quality of a multiobjective optimization-based evolutionary algorithm for knapsack problem
• Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem
• Performance evaluation of evolutionary class of algorithms -- an application to 0-1 knapsack problem

Cited in

(2)

• A polynomial-time approximation scheme for thief orienteering on directed acyclic graphs
• Algorithms for the thief orienteering problem on directed acyclic graphs

This page was built for publication: Analysis of baseline evolutionary algorithms for the packing while travelling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215486)