In this Python program, the objective was to develop an AI solution using ACO (Ant Colony Optimization) to efficiently solve the TSP (Traveling Salesman Problem). By simulating the behavior of ants and the pheromone trails they create, the program aims to iteratively construct and refine tours until an optimal or near-optimal route is obtained. The ants select nodes based on certain criteria and deposit pheromone on the edges, which influences the decision-making process of subsequent ants. Through the process of pheromone updates, the ACO algorithm explores the solution space and converges towards an optimal solution to the TSP.
- init (Edge Class): represents a connection between two cities in the TSP. It stores the indices of the cities, the weight (distance) of the edge, and the amount of pheromone on the edge.
- init(Ant Class): represents an ant agent in the ACO algorithm. It stores the parameters alpha and beta, which control the importance of pheromone and heuristic information in the ant's decision-making process. It also keeps track of the number of nodes, the edges connecting them, the ant's tour, and the distance traveled.
- _select_node: used by an “ant” to choose the next node to visit in the TSP. It calculates a roulette wheel selection based on the pheromone levels and heuristic information of the unvisited nodes. The alpha and beta parameters influence the probabilities of node selection, favoring higher pheromone levels and lower distances.
- find_tour: used by an “ant” to construct a tour by iteratively selecting the next node based on the _select_node function until all nodes are visited. It returns the completed tour.
- get_distance: calculates the total distance traveled by an ant in its tour by summing the weights (distances) of the edges between consecutive nodes. It returns the calculated distance.
- init(SolveTSPUsingACO Class): sets up various parameters and data structures, including the generation_distances list to store the best distance at each generation, the colony size, the scaling factor for pheromone, the evaporation rate, the weight of pheromone deposit, the number of steps (generations), the number of nodes, the nodes' coordinates, and the labels for the nodes. It also creates the edges between nodes, initializes the ants with the specified parameters, and sets initial values for the global best tour, global best distance, and initial tour.
- _add_pheromone: “deposits” pheromones on the edges of the tour based on the distance traveled by the “ant”. It calculates the amount of pheromone to add and updates the pheromone levels accordingly.
- _max_min: implements the Max-Min Ant System (MMAS) strategy for ACO. It performs iterations for the specified number of steps and updates the pheromone trails accordingly. It tracks the best tour found in each iteration and updates the global best tour and distance if necessary. The function also maintains a record of the best distance at each generation and plots the best tour, the generational change in distance, and the initial path.
- plot: generates a visual representation of the ACO algorithm's results. It creates a figure with three subplots, each displaying different information such as the best tour found, generational change in distance, and the initial path. The function utilizes Matplotlib to plot the tour, distances, and paths with customizable line widths, point radii, and annotation sizes.
- userSettings: prompts the user to enter parameters for the ACO algorithm, such as the number of cities, population size, and number of generations. It then creates an instance of the SolveTSPUsingACO class with the specified parameters, runs the ACO algorithm using the _max_min method, and plots the results using the plot method. It also includes input validation functions to ensure the user provides valid numerical inputs.
- checkUserInputInt: takes input from user and ensures the value is an integer, if not returns false.
- checkUserInputFloat: takes input from user and ensures the value is a float, if not returns false.
- name (Main): serves as the entry point of the program.