Analysis of baseline evolutionary algorithms for the packing while travelling problem

DOI10.1145/3299904.3340313zbMATH Open1433.68650arXiv1902.04692OpenAlexW2911580966MaRDI QIDQ5215486FDOQ5215486

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)

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.

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

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

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)

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)