Genetic Local Search(GLS) : Traveling Salesman Problem (TSP) Solver

A Traveling Salesman Problem (TSP) is one of optimization problem. TSP as a problem which “easy” to understand but hard to solve, becoming to standard problem for new optimization algorithms. For more close to the reality, the kind of TSP that has been chosen in this research is a TSP that contain a penalties for calculation of it tours. Together with increasing of city number that been used, it is more difficult to find the optimal solution. Because of that, a computer program is needed to do that task. Graph representations and heuristic solutions to this optimization are often found using algorithms that are based on what we called “iterative global optimization". As promising approach, combination of local search and genetic algorithm is used to find the near optimum solutions of TSP, which local search doing it task to find the local optima and genetic algorithm is to find the global optimum (with population-based search).
Unlike the traditional genetic algorithms, which use a single population, in this research for maximizing of optimal solution searching process, the multi population has been used. By using multi population, the search process can go on parallel processing on computer which multi-processor support. To perform multi-population, these research using an approach that based on Genetic Local Search (GLS) with two populations (called subpopulation). In first phase, both subpopulations separately regenerated as like as process on single population. After both regeneration processes completely finish, the process continues with information exchange of that both subpopulations. That process is performed by mate process of two chromosomes from different subpopulation (using crossover only). Although this approach in this research is used only small scale TSP, it can be used for large scale TSP. In this research, the software base on this approach is developing by using object-oriented concept (object-oriented analysis, object-oriented design, object-oriented programming dan object-oriented testing).
Based on experiment result, although the cost of tour can be better by performing that approach but entirely time needed to completely process can be extremely increase. However, with object-oriented concept that has been used, maintenance and development of object and class can be easier and helpful not for TSP purpose only, but it can be applying to other graph problems too (just like minimum spanning tree or shortest path).

You can download my GLS program to solve TSP problem right here.