A Noise-Aware Multiobjective Genetic Algorithm for Probabilistic Traveling Salesperson Problem with Profits (pTSPP)

This thesis formulates a new multiobjective optimization problem (MOP), the Probabilistic Traveling Salesperson Problem with Profits (pTSPP), which contains inherent noise in its objective functions. As a variant of TSP, many real-world noisy MOPs can be reduced to pTSPP. In order to solve pTSPP, this thesis proposes an evolutionary multiobjective optimization algorithm (EMOA) that leverages a novel noise-aware dominance operator, called the alpha-dominance operator. The operator takes objective value samples of given two individuals (or solution candidates), estimates the impacts of noise on the samples and determines whether it is statistically confident enough to judge which individual is superior/inferior to the other. Unlike existing noise-aware dominance operator, the -dominance operator assumes no noise distributions a priori; it is well applicable to various real-world noisy MOPs, including pTSPP, whose objective functions follow unknown noise distributions. Experimental results demonstrate that the -dominance operator allows the proposed EMOA to eectively obtain quality solutions to pTSPP and it outperforms existing noise-aware dominance operators