MATLAB Source Code for Simple Ant Colony Optimization Algorithm Solving TSP

This is a simple Ant Colony Optimization algorithm implementation for solving the Traveling Salesman Problem (TSP). Below is the MATLAB source code with enhanced technical descriptions. The algorithm begins with parameter initialization including 50 ants, 100 iterations, pheromone decay coefficient of 0.5, pheromone enhancement coefficient of 2, and influence parameters alpha=1 (pheromone importance) and beta=5 (distance importance). City coordinates are initialized as a 5x2 matrix representing 5 cities with their spatial positions. The distance matrix is calculated using pdist2 function to compute pairwise Euclidean distances between all cities. The core algorithm operates through iterative cycles where: - Each ant constructs a path using probabilistic selection based on pheromone levels and distance heuristics - Path selection employs a roulette wheel selection mechanism that balances exploration and exploitation - Pheromone matrix updates incorporate both evaporation (global update) and reinforcement based on path quality (local update) MATLAB code implementation: % Initialize algorithm parameters num_ants = 50; max_iterations = 100; pheromone_decay = 0.5; pheromone_enhance = 2; alpha = 1; beta = 5; % Initialize city coordinates (5 cities example) city_coordinates = [1, 1; 2, 3; 4, 5; 6, 7; 8, 9]; % Calculate distance matrix using Euclidean distance distance_matrix = pdist2(city_coordinates, city_coordinates); % Initialize pheromone matrix with uniform distribution pheromone_matrix = ones(size(distance_matrix)); % Main optimization loop for iteration = 1:max_iterations % Initialize ant paths matrix ant_paths = zeros(num_ants, size(distance_matrix, 1)); % Construct paths for each ant for ant = 1:num_ants current_city = randi(size(distance_matrix, 1)); ant_paths(ant, 1) = current_city; % Build complete path for each ant for step = 2:size(distance_matrix, 1) available_cities = setdiff(1:size(distance_matrix, 1), ant_paths(ant, 1:step-1)); % Calculate transition probabilities combining pheromone and heuristic information probabilities = (pheromone_matrix(current_city, available_cities).^alpha) .* (distance_matrix(current_city, available_cities).^(-beta)); probabilities = probabilities / sum(probabilities); next_city_index = roulette_wheel_selection(probabilities); ant_paths(ant, step) = available_cities(next_city_index); current_city = available_cities(next_city_index); end end % Calculate path lengths for all ants path_lengths = zeros(num_ants, 1); for ant = 1:num_ants for step = 2:size(distance_matrix, 1) path_lengths(ant) = path_lengths(ant) + distance_matrix(ant_paths(ant, step-1), ant_paths(ant, step)); end % Add return to starting city (closed tour) path_lengths(ant) = path_lengths(ant) + distance_matrix(ant_paths(ant, end), ant_paths(ant, 1)); end % Update pheromone matrix with evaporation and reinforcement pheromone_matrix = (1 - pheromone_decay) .* pheromone_matrix; for ant = 1:num_ants for step = 2:size(distance_matrix, 1) pheromone_matrix(ant_paths(ant, step-1), ant_paths(ant, step)) = pheromone_matrix(ant_paths(ant, step-1), ant_paths(ant, step)) + pheromone_enhance / path_lengths(ant); end pheromone_matrix(ant_paths(ant, end), ant_paths(ant, 1)) = pheromone_matrix(ant_paths(ant, end), ant_paths(ant, 1)) + pheromone_enhance / path_lengths(ant); end end % Roulette wheel selection function for probabilistic city selection function index = roulette_wheel_selection(probabilities) cumulative_prob = cumsum(probabilities); random_value = rand(); for index = 1:length(probabilities) if random_value <= cumulative_prob(index) break; end end end This simple Ant Colony Optimization source code provides a fundamental implementation for solving TSP problems, demonstrating key ACO concepts including positive feedback through pheromone trails and heuristic information utilization for combinatorial optimization.