Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms

详细信息    查看全文

• 关键词：Traveling Thief Problem ; Traveling Salesman Problem ; Knapsack problem ; Interwoven systems ; Multi ; objective optimization ; Discrete optimization ; Combinatoric problems
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10173
• 期：1
• 页码：46-60
• 丛书名：Evolutionary Multi-Criterion Optimization
• ISBN：978-3-319-54157-0
• 卷排序：10173

文摘

This publication investigates characteristics of and algorithms for the quite new and complex Bi-Objective Traveling Thief Problem, where the well-known Traveling Salesman Problem and Binary Knapsack Problem interact. The interdependence of these two components builds an interwoven system where solving one subproblem separately does not solve the overall problem. The objective space of the Bi-Objective Traveling Thief Problem has through the interaction of two discrete subproblems some interesting properties which are investigated. We propose different kind of algorithms to solve the Bi-Objective Traveling Thief Problem. The first proposed deterministic algorithm picks items on tours calculated by a Traveling Salesman Problem Solver greedily. As an extension, the greedy strategy is substituted by a Knapsack Problem Solver and the resulting Pareto front is locally optimized. These methods serve as a references for the performance of multi-objective evolutionary algorithms. Additional experiments on evolutionary factory and recombination operators are presented. The obtained results provide insights into principles of an exemplary bi-objective interwoven system and new starting points for ongoing research.