Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics
Created by W.Langdon from
gp-bibliography.bib Revision:1.7954
- @Article{vanLon:2017:GPEM,
-
author = "Rinde R. S. {van Lon} and Juergen Branke and
Tom Holvoet",
-
title = "Optimizing agents with genetic programming: an
evaluation of hyper-heuristics in dynamic real-time
logistics",
-
journal = "Genetic Programming and Evolvable Machines",
-
year = "2018",
-
volume = "19",
-
number = "1-2",
-
pages = "93--120",
-
month = jun,
-
note = "Special Issue on Automated Design and Adaptation of
Heuristics for Scheduling and Combinatorial
Optimisation",
-
keywords = "genetic algorithms, genetic programming,
Hyper-heuristics, Multi-agent systems Logistics,
Decentralized, Centralized, Operational research,
Optimization, Real-time",
-
ISSN = "1389-2576",
-
DOI = "doi:10.1007/s10710-017-9300-5",
-
size = "28 pages",
-
abstract = "Dynamic pickup and delivery problems (PDPs) require
online algorithms for managing a fleet of vehicles.
Generally, vehicles can be managed either centrally or
decentrally. A common way to coordinate agents
de-centrally is to use the contract-net protocol (CNET)
that uses auctions to allocate tasks among agents. To
participate in an auction, agents require a method that
estimates the value of a task. Typically, this method
involves an optimization algorithm, e.g. to calculate
the cost to insert a customer. Recently,
hyper-heuristics have been proposed for automated
design of heuristics. Two properties of automatically
designed heuristics are particularly promising: (1) a
generated heuristic computes quickly, it is expected
therefore that hyper-heuristics perform especially well
for urgent problems, and (2) by using simulation-based
evaluation, hyper-heuristics can create a rule of thumb
that anticipates situations in the future. In the
present paper we empirically evaluate whether
hyper-heuristics, more specifically genetic programming
(GP), can be used to improve agents decentrally
coordinated via CNET. We compare several GP settings
and compare the resulting heuristic with existing
centralized and decentralized algorithms based on the
OptaPlanner optimization library. The tests are
conducted in real-time on a dynamic PDP dataset with
varying levels of dynamism, urgency, and scale. The
results indicate that the evolved heuristic always
outperforms the optimization algorithm in the
decentralized multi-agent system (MAS) and often
outperforms the centralized optimization algorithm. Our
paper demonstrates that designing MASs using genetic
programming is an effective way to obtain competitive
performance compared to traditional operational
research approaches. These results strengthen the
relevance of decentralized agent based approaches in
dynamic logistics.",
- }
Genetic Programming entries for
Rinde van Lon
Jurgen Branke
Tom Holvoet
Citations