GA, AS, ACS AND MMAS ALGORITHMS PERFORMANCE EVALUATION ON TRAVELING SALESMAN PROBLEM SOLVING

35882

Travelling Salesman Problem (TSP) is an important optimization method that have been applied to various areas. In this study, TSP is solved by using several heuristic algorithms like Genetic Algorithm (GA), Ant System (AS/ANT), Ant Colony System (ACS) and Max-Min Ant System (MMAS), performances of these algorithms are then measured. Applied algorithms are implemented inside an interface. Using this interface, maps can be generated with as much as required random points (cities) or loaded from dataset. Performance criterion of the measurement may be seen as the cost (path length) and the number repetitions. Performance measurements of these algorithms are tested on 5 different maps consisting of 36, 56, 76, 101 and 150 points. At each test for solving TSP for each map, the least cost is observed for MMAS and the highest cost is observed for GA. Ascending sort of these algorithms based on their cost is observed as MMAS (least), AS, ACS and GA (highest). The performance of the algorithms for the ch150 dataset in the TSPLIB library was found to be lower in GA, AS and MMAS compared to the literature.

50

Genetic Algorithm , Ant Colony Optimization , Travel Salesman Problem

Sdu International Technologic Science

60

Sdu International Technologic Science