Introduction
This project aims to solve a classical combinatoric problem, the Traveling Salesman Problem (TSP), in which one should visit all the n cities, only once, minimizing the traveling cost as much as possible. To do so, single and multi-objective optimization evolutionary algorithms will be imple- mented.
2 Single-Objective Optimization Problem
Table 1: Single-Objective Optimization Results
CityDistCar CityDistPlane Mean STD Mean STD 20 4282.27 155.55 5078.27 41.27 30 5054.13 246.11 7266.07 66.20 50 7770.27 420.68 11938.80 95.91
CityCostCar CityCostPlane Mean STD Mean STD 857.03 36.62 3428.13 146.47 1001.53 42.74 4006.13 170.95 1541.33 89.55 6165.33 358.21
#Cities
Objective Function 20
CityDistCar
CityDistPlane
CityCostCar
CityCostPlane
Table 2: Convergence Curve of Single-Objective Optimization
30 50
1
Table 3: Single-Objective Optimization Results using Heuristics
CityDistCar CityDistPlane CityCostCar CityCostPlane Mean STD Mean STD Mean STD Mean STD 20 4372.33 113.50 5100.37 32.60 874.57 23.42 3498.27 93.68
#Cities
30 5084.00 160.62 7273.50 42.91 1018.57 34.38 4074.27 137.51
50 7070.87 325.46 11802.53 66.18 1417.50 58.34 5670.00 233.35 Table 4: Convergence Curve of Single-Objective Optimization using Heuristics
Objective Function 20 30 50
CityDistCar
CityDistPlane
CityCostCar
CityCostPlane
2.1 Problem Formulation and EA Set Up
The candidate solution for the single-objective optimization problem is represented by a list that contains the order of the cities to be visited.
The evolutionary operators considered are partially mapped crossover (PMX) and inversion for mutation. Also, the probabilities for crossing and mutation were chosen iteratively through tests.
The selection of the individuals to βbreedβ the next generation is done with Tournament Selection.
2
3
Multi-Objective Optimization Problem
Table 5: Multi-Objective Optimization Results (Pareto Front)
#Cities 20
30 50
MinCost Dist (Time)
MinDist Dist (Time)
842.00
999.00 1462.00
Cost
4365.00 5024.00 7337.00
4006.00 4668.00 7079.00
Cost
1130.00 1285.00 1660.00
Table 6: Pareto Curve and Hypervolume of Multi-Objective Optimization
20 30 50
Pareto Curve
Hypervolume
3.1 Problem Formulation and EA Set Up
The candidate solution for the multi-objective optimization problem is represented by a list that, at each index, contains another list. In the latter, the first index indicates the city where the salesman is and the second index specifies the means of transportation to be used from the current city to the next one (0 represents travelling by car and 1 by plane).
The evolutionary operators used are the same as the single-objective optimization problem, but applied to the order of the cities list and means of transportation from one city to another, separately. The selection of the individuals is done by using the Non Dominated Sorting Genetic Algorithm
(NSGA-II).
4 Conclusions
From Table 2, it is possible to verify that the relation cost/distance converges in every case tested, although it takes longer to converge if the number of the cities is greater.
Comparing the graphics obtained in Table 2 and 4, we can conclude that, for 20 cities, even though the algorithm converges to the approximate same value, it converges faster with the heuristic method, since it only needs 25 generations versus the 50 generations needed without it. For 30 and 50 cities, it is possible to observe that the heuristic allows the algorithm to find better paths, that converge to lower costs.
3
By comparing the Tables 1 and 3, one verifies that the standard deviation decreases for all cases when the heuristics is applied. Thus, the heuristics helps to limit the search space.
For the multi-objective problem, it is also confirmed the convergence of the individuals to the pareto front, as well as the stabilization of the hypervolume. However it takes longer with the increase of the number of cities.
4
