Queued Pareto Local Search for Multi−objective Decision Making

Abstract

Many real-world optimisation problems involve balancing multiple objectives. When there is no solution that is best with respect to all objectives it is often desirable to compute the Pareto front. Firstly, we propose queued Pareto local search (QPLS), which improves on existing Pareto local search (PLS) methods by maintaining a queue of candidate solutions that prevents premature exclusion. Secondly, we propose Pareto local policy search (PLoPS), which improves upon QPLS in the context of multi-objective sequential decision problems known as multi-objective Markov decision processes (MOMDPs). PLoPS exploits the structure of MOMDPs by quickly identifying policies that are improvements without fully evaluating them, and intelligently initialising their values. We test the performance of QPLS and PLoPS on respectively multi-objective coordination graphs (MO-CoGs) and MOMDPs, and compare them to popular evolutionary and decision-theoretic alternatives. The results show that QPLS and PLoPS outperform these alternatives.