Fitness switching genetic algorithm for solving combinatorial optimization problems with rare feasible solutions.

The goal of meta-heuristic algorithms such as genetic algorithm is to explore the search space of the combinatorial optimization problems efficiently to locate the optimal solutions, the feasible solutions with the best output values. However, typical meta-heuristic algorithms implicitly assume that the feasible solutions for the given problems can be generated easily, and they can fail to solve the problems with rare feasible solutions in effective manner. In this context, this paper aims to introduce the maze-type shortest path problem as an example of the combinatorial optimization problem with rare feasible solutions and to propose the fitness switching genetic algorithm for solving it. The maze-type shortest path problem is characterized by the maze-type network that contains many dead-ends, and the conventional genetic algorithms based on the population of feasible paths are not appropriate for finding the optimal path in such networks. On the contrary, this paper introduces the fitness switching and fitness leveling operations for maintaining the population of both feasible and infeasible paths during the search procedure. In addition, the infeasible paths are randomly modified by the simple local search of the proposed algorithm to find the feasible paths more quickly. The experiment results show that the proposed algorithm can address the issues in the combinatorial optimization problems with rare feasible solutions very effectively. [ABSTRACT FROM AUTHOR]