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 List<IAnt> xants = [];
    private IAnt[]? ants;

    /// <summary>
    /// Инициализировать алгоритм
    /// </summary>
    /// <param name="distances">Матрица расстояний</param>
    /// <param name="evaporationRate">Скорость испарения</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;
        }
    }

    /// <summary>
    /// Добавить определенное количество муравьев заданного типа
    /// </summary>
    /// <typeparam name="T">Тип муравьев</typeparam>
    /// <param name="count">Количество муравьев</param>
    /// <param name="args">Аргументы конструктора муравья</param>
    public AntColonyOptimizer AddAnts<T>(int count, params object[] args) where T : IAnt
    {
        for (int i = 0; i < count; i++)
        {
            // Создаем нового муравья заданного типа
            xants.Add((T)Activator.CreateInstance(typeof(T), args)!);
        }

        return this;
    }

    /// <summary>
    /// Расположить всех муравьев в случайном порядке
    /// </summary>
    /// <param name="shuffle">Расположить муравьев в случайном порядке</param>
    public AntColonyOptimizer CompileAnts(bool shuffle = false)
    {
        ants = [.. xants];
        // Если нужно, располагаем муравьев в случайном порядке
        if (shuffle) 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)
    {
        // Если колония муравьев пуста
        if (ants is null) throw new MissingMemberException("Колония пуста. Забыли вызвать AntColonyOptimizer.CompileAnts()?");

        Console.WriteLine($"Поиск кратчайшего Гамильтонова цикла с {ants.Length} муравьев и {maxIterations} итераций");

        for (int i = 0; i < maxIterations; i++)
        {
            ConcurrentBag<List<int>> antTours = [];
            ConcurrentBag<double> antDistances = [];

            // Каждый муравей строит путь
            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);

                return (tour, distance);
            });

            // После того, как все муравьи построили маршруты, они последовательно (не параллельно) обновляют феромоны
            for (int j = 0; j < antTours.Count; j++)
            {
                ants[j].UpdatePheromones(ref pheromones);
            }

            // Испаряем феромоны после итерации
            EvaporatePheromones();

            // Находим лучший путь
            (List<int> Tour, double Distance) bestIterationTour = iterationTours.MinBy(x => x.distance);
            if (bestIterationTour.Distance < bestDistanceEver)  // Если лучше текущего - обновляем текущий
            {
                bestDistanceEver = bestIterationTour.Distance;
                bestTourEver = bestIterationTour.Tour;
                Console.WriteLine($"{i} - {bestDistanceEver,20}");
            }

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

        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;
            }
        }
    }
}