MOGADOR revisited: Improving a genetic approach to multi-objective corridor search

摘要

The MOGADOR algorithm is a specialized heuristic approach to the shortest path problem, which employs genetic operators to the search for near optimal corridors within the context of multiple independent objectives. This article expands upon the work contained in the MOGADOR algorithm's debut publication by introducing a set of refined techniques for initializing the algorithm, which are responsive to the characteristics of the problem specification, the desired runtime, and the global quality of the output solution set. A core component of these techniques is the introduction of a novel process for constructing so-called pseudo-random walks that is based on the repetitive sampling of a dynamically parameterized bivariate-normal distribution. Guidance is provided regarding the appropriate parameterization of the proposed initialization procedure for a variety of problem contexts. The article concludes with a prospective treatment of different approaches to the parallelization of the algorithm's various components and references an open source library containing the source code for the various new algorithms introduced.