Solving the Traveling Thief Problem using Orchestration in Optimization Networks
Sprache des Titels:
Lecture Notes in Computer Science
Optimization problems can sometimes be divided into multiple
subproblems. Working on these subproblems instead of the actual
master problem can have some advantages, e.g. if they are standard
problems, it is possible to use already existing algorithms, whereas specialized
algorithms would have to be implemented for the master problem.
In this paper we approach the NP-hard Traveling Thief Problem by
implementing different cooperative approaches using optimization networks.
Orchestration is used to guide the algorithms that solve the respective
subproblems. We conduct experiments on some instances of a
larger benchmark set to compare the different network approaches to
best known results, as well as a sophisticated, monolithic approach. Using
optimization networks, we are able to find new best solutions for all
of the selected problem instances.