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.4333

  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
  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
  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