graphs/AntColony/Algorithm/ACO.cs

using System.Collections.Concurrent;

namespace AntColony.Algorithm;

/// <summary>
/// Алгоритм построения кратчайшего пути с помощью симуляции муравьиной колонии
/// </summary>
public class AntColonyOptimizer
{
    private readonly int numberOfCities;
    private double[][] distances;
    private double[][] pheromones;
    private readonly double evaporationRate;
    private readonly int numberOfAnts;

    private readonly List<IAnt> xants = [];
    private IAnt[] ants;

    /// <summary>
    /// Инициализировать алгоритм
    /// </summary>
    /// <param name="distances">Матрица расстояний</param>
    /// <param name="numberOfAnts">Количество муравьев</param>
    /// <param name="evaporationRate">Скорость испарения</param>
    /// <param name="Q">Значение Q</param>
    public AntColonyOptimizer(double[][] distances, double evaporationRate = 0.1)
    {
        numberOfCities = distances.GetLength(0);
        this.distances = distances;
        this.evaporationRate = evaporationRate;

        // Строим стартовую матрицу феромонов
        pheromones = new double[numberOfCities][];
        for (int i = 0; i < numberOfCities; i++)
        {
            var r = new double[numberOfCities];
            for (int j = 0; j < numberOfCities; j++)
            {
                if (i != j)
                    r[j] = 1.0; // Начальное значение
            }
            pheromones[i] = r;
        }
    }

    public AntColonyOptimizer AddAnts<T>(int count) where T : IAnt
    {
        for (int i = 0; i < count; i++)
        {
            xants.Add(Activator.CreateInstance<T>()!);
        }

        return this;
    }

    public AntColonyOptimizer ShuffleAnts()
    {
        ants = [.. xants];
        Random.Shared.Shuffle(ants);

        return this;
    }

    /// <summary>
    /// Обработчик ранней остановки работы алгоритма
    /// </summary>
    /// <returns>Лучший путь и его длину на текущий момент</returns>
    public (List<int> tour, double distance) EarlyExit() => (bestTourEver, bestDistanceEver);

    private List<int> bestTourEver = [];
    private double bestDistanceEver = double.PositiveInfinity;

    /// <summary>
    /// Решить задачу комивояжера (найти Гамильтонов цикл)
    /// </summary>
    /// <param name="maxIterations">Максимальное число итераций</param>
    /// <returns>Лучший путь и его расстояние</returns>
    public (List<int> bestTour, double bestDistance) Solve(int maxIterations)
    {
        // for (int iteration = 0; iteration < maxIterations; iteration++)
        for (int i = 0; i < maxIterations; i++)
        {
            ConcurrentBag<List<int>> antTours = [];
            ConcurrentBag<double> antDistances = [];

            Console.Write($"{i}/{maxIterations} - {bestDistanceEver}\r");

            // Каждый муравей строит путь
            var iterationTours = ants.AsParallel().Select(ant =>
            {
                var ct = ant.ConstructTour(ref distances, ref pheromones);
                if (!ct.HasValue) return ([], double.MaxValue);
                var (tour, distance) = ct.Value;
                antTours.Add(tour);
                antDistances.Add(distance);
                // Console.Write($"\r|- {i}/{numberOfAnts} - {distance}");

                return (tour, distance);
            });

            for (int j = 0; j < antTours.Count; j++)
            {
                ants[j].UpdatePheromones(ref pheromones);
            }

            // Console.Write(new string(' ', 20));

            // Console.CursorTop--;
            // Console.CursorLeft = 0;

            // Обновляем феромоны для всех путей
            EvaporatePheromones();
            // File.AppendAllText("./iteration-results", bestDistanceEver.ToString() + '\n');
            // }

            (List<int> Tour, double Distance) bestIterationTour = iterationTours.MinBy(x => x.distance);
            if (bestIterationTour.Distance < bestDistanceEver)
            {
                bestDistanceEver = bestIterationTour.Distance;
                bestTourEver = bestIterationTour.Tour;
                Console.WriteLine();
            }
        };

        return (bestTourEver, bestDistanceEver);
    }

    /// <summary>
    /// Обновить матрицу феромонов
    /// </summary>
    private void EvaporatePheromones()
    {
        // Испарение
        for (int i = 0; i < numberOfCities; i++)
        {
            for (int j = 0; j < numberOfCities; j++)
            {
                if (i != j)
                    pheromones[i][j] *= 1.0 - evaporationRate;
            }
        }
    }
}