AGH; An Ant Genetic Hybrid Solution to Solve the Multi-model Traveling Salesmen Problem

Abstract

The concept of multi-model optimization brings the idea of finding all or most of the existing high quality solutions. Recent research on multi-model optimization (MMO) seemed to be using nature inspired algorithms in solving such interesting problems. Multi-model traveling salesman problem is an important but rarely addressed discrete MMO problem. This paper proposes a hybrid algorithm combining the Ant Colony Systems algorithm (ACS) with a modified genetic algorithm (MODGA) to solve multi-model traveling salesman problems (MMTSPs). The concept of the hybrid algorithm divides the solution into two parts where ACS is used to find an average quality solution which is then provided as a threshold to the MODGA to find other quality solutions as much as possible. Benchmark multi-model TSP problems have been used on the new algorithm to test its capability. 70% of the success PR and 0.6% of success SR values indicates the capability of the method solving MMTSPs. The results compared with several state of the art multi-model optimization algorithms showed that the proposed hybrid algorithm performs competitively with these algorithms. As the first approach to solve MMTSPs without niching strategies, improvements will lead the current algorithm to a greater place.