The objective of this activity is to study the functioning of Ant Colony Optimization Algorithms (OCH). To do this, students will be required to implement different variants of these algorithms, corresponding to Ant System (SH), Elitist Ant System (SHE), and Ant Colony System (SCH), to solve the Traveling Salesman Problem. The behavior of the implemented ACO algorithms should be compared with a greedy algorithm.
The Traveling Salesman Problem (TSP) is one of the most well-known combinatorial optimization problems. In its most general formulation, given a set of cities, the objective is to find the minimum-cost circuit that starts from a specific city, visits all the other cities exactly once, and returns to the starting city.
In our case, we will work with three standard instances of the problem (two model datasets) obtained from the TSPLIB library, all of which correspond to the symmetric TSP. These are: • Ch130: Size of 130 cities. Optimal solution cost: 6,110. • A280: Size of 280 cities. Optimal solution cost: 2,579.