Searching in Symmetric Solution Space for Permutation-Related Optimization Problems.

Abstract

Symmetry is a widespread phenomenon in nature. Recognizing symmetry can minimize redundancy to improve computing efficiency. In this paper, we take permutation-related combinatorial optimization problems as a starting point and explore the symmetric structure of its solution space through group theory. From a new perspective of group action, we discover that the meaningful symmetric feature within the solution space is subject to two conditions regarding the form of objective function and the number of objects to be permuted. To exploit the symmetric features, we design a half-solution-space search strategy for various search operators, which are commonly used for permutation-related combinatorial optimization problems. The half-solution-space search strategy can make these operators explore more promising regions without additional computational effort. When the condition of object number for symmetry is unsatisfied, we propose two dimension mapping approaches to construct the symmetric feature, making the half-solution-space search strategy applicable. We evaluate the proposed strategy on three classes of popular 68 benchmark instances, including the single row facility layout problem (SRFLP), traveling salesman problem (TSP), and multi-objective traveling salesman problem (MOTSP). Experimental results show that algorithms embedded with the half-solution-space search strategy can achieve a more competitive performance than those not exploiting the symmetric features.