10 минут, чтобы понять алгоритм муравьиной колонии

У муравьев практически нет зрения, но они способны находить пищу в темном мире и находить кратчайший путь из пещеры к еде. Как они это делают?

Процесс поиска муравьями пищи

Поведение одиночного муравья очень простое, а количество вариантов поведения меньше 10, но муравьиная колония, состоящая из тысяч муравьев, может обладать большим интеллектом, который неотделим от способа передачи ими информации - феромона.

Когда муравьи идут, они выделяют вещество под названием «феромон», которое используется для обозначения их пути. В процессе поиска пищи направление ходьбы выбирается в соответствии с концентрацией феромона и, наконец, достигает места, где находится пища.

Феромоны со временем постепенно испаряются.

Вначале, поскольку на земле нет феромонов, муравьи ходят случайным образом. В процессе ходьбы муравьи будут непрерывно выделять феромоны, чтобы отметить свой путь. Со временем пищу находят несколько муравьев, и из норы к еде ведет несколько путей. Поскольку поведенческие траектории муравьев распределены случайным образом, количество муравьев на коротком пути больше, чем количество муравьев на длинном пути в единицу времени, поэтому концентрация оставляемых муравьями феромонов выше. Это дает четкое указание направления для муравьев позади, и все больше и больше муравьев собираются на кратчайшем пути.

Что такое Алгоритм муравьиной колонии?

Алгоритм муравьиной колонии имитирует процесс поиска пищи муравьями, он может найти кратчайший путь, начинающийся от источника, проходящий через ряд заданных точек спроса и, наконец, возвращающийся к источнику. Это также известно как задача путешествующего продавца (TSP).

В этой статье алгоритм муравьиной колонии используется для решения задачи планирования балансировки нагрузки в распределенной среде.

Применение алгоритма Ant Colony — планирование балансировки нагрузки

Кластерный режим является широко используемой структурой развертывания в настоящее время, то есть, когда вычислительная мощность одной машины не может удовлетворить бизнес-требованиям, добавляются узлы обработки, а за планирование запросов отвечает балансировщик нагрузки. Однако для большой системы ситуация часто оказывается более сложной. Вычислительная мощность узлов в кластере часто разная, и сложность обработки разных задач тоже разная. Так как же балансировщик нагрузки распределяет задачи для оптимизации производительности кластера? Максимальная загрузка ресурсов? Это очень сложный и ценный вопрос.

В этой статье мы используем алгоритм муравьиной колонии для решения этой проблемы.

Математическое моделирование

Прежде чем начать, нам сначала нужно математически смоделировать проблему «планирования балансировки нагрузки», количественно оценить различные показатели и сопоставить их с алгоритмом муравьиной колонии.

описание проблемы

Найдите оптимальную стратегию распределения задач, при которой N задач разной длины можно выделить на M серверных узлов с разными вычислительными возможностями в соответствии с определенной стратегией, а время выполнения N задач будет кратчайшим.

В этой задаче мы используем время выполнения всех задач как меру качества стратегии распределения. Каждая стратегия распределения является допустимым решением этой проблемы. Тогда стратегия размещения с наименьшим временем выполнения является оптимальным решением этой задачи.

определение параметра

var tasks = [];
var taskNum = 100;

• tasks: массив задач, нижний индекс массива представляет номер задачи, а значение массива представляет длину задачи. Например: tasks[0]=10 означает, что длина первой задачи равна 10.
• taskNum: количество задач, то есть длина массива задач. Здесь, чтобы улучшить читаемость кода, используется taskNum для представления количества задач.

var nodes = [];
var nodeNum = 10;

• узлы: массив узлов обработки. Нижний индекс массива представляет номер узла обработки, а значение массива представляет скорость обработки узла. Например: nodes[0]=10 означает, что скорость обработки первого узла обработки равна 10.
• nodeNum: количество узлов обработки, то есть длина массива узлов. Здесь nodeNum используется для представления количества узлов, чтобы улучшить читаемость кода.

var iteratorNum;
var antNum;

• iteratorNum: общее количество итераций, требуемых алгоритмом муравьиной колонии, и каждая итерация имеет муравьев antNum для назначения задач.
• antNum: количество муравьев в каждой итерации. Каждый муравей является планировщиком задач, и каждый муравей в каждой итерации должен выполнить назначение всех задач, что является допустимым решением.

var timeMatrix = [];

• Матрица времени обработки задачи.
  • Это двумерная матрица. Например: timeMatrix[i][j] представляет время обработки, необходимое для того, чтобы i-я задача была назначена j-му узлу.
  • Эта матрица вычисляется на основе массива задач и массива узлов. Например, task[i] представляет длину i-й задачи, а nodes[j] представляет скорость обработки j-го узла. Итак, timeMatrix[i][j]=task[i]/nodes[j].

var pheromoneMatrix = [];
var maxPheromoneMatrix = [];
var criticalPointMatrix = [];

• pheromoneMatrix: матрица феромонов
  • Это двумерная матрица, которая записывает концентрацию феромонов на пути, назначенном задачей i узлу j.
  • Например: pheromoneMatrix[i][j]=0,5 означает, что концентрация феромона на пути, назначенном задачей i к узлу j, равна 0,5
• maxPheromoneMatrix: индекс самого большого феромона в каждой строке матрицы pheromoneMatrix.
  • Например: maxPheromoneMatrix[0]=5 означает, что среди всех феромонов в строке 0 таблицы pheromoneMatrix индекс самого большого феромона равен 5.
• CriticalPointMatrix: В одной итерации критическое количество муравьев, использующих стратегию случайного распределения.
  • Например, если количество муравьев установлено равным 10, то на каждой итерации будет 10 муравьев, чтобы выполнить назначение всех задач. А процесс распределения осуществляется по порядку номеров муравьев от меньшего к большему (нумерация муравьев начинается с 0). Если CriticalPointMatrix[0]=5, это означает, что при назначении 0-й задачи муравьи с номерами от 0 до 5 назначают задачи в соответствии с концентрацией феромона (т.е.: назначают задачу с концентрацией феромона в строке Самая высокая обработка узла), муравьи 6–9 используют случайное распределение (т. е. случайным образом назначают задачи любому узлу для обработки).
  • почему ты хочешь сделать это?Если каждый муравей ставит задачу узлу с наибольшей концентрацией феромона, то происходит застой. То есть алгоритм преждевременно сходится к локальному оптимальному решению и не может найти глобальное оптимальное решение. Следовательно, некоторым муравьям необходимо следовать стратегии распределения с самым высоким феромоном, а некоторым муравьям необходимо следовать стратегии случайного распределения, чтобы находить новые локальные оптимальные решения.

var p = 0.5;
var q = 2;

• p: доля распада феромона после завершения каждой итерации. Мы знаем, что в настоящих муравьиных колониях феромоны, выделяемые муравьями, со временем постепенно распадаются. Затем в алгоритме мы делаем распад феромона после каждой итерации, но в течение одной итерации концентрация феромона остается неизменной.
• q: Доля феромона увеличивается каждый раз, когда муравьи проходят путь. Мы также знаем, что в настоящих муравьиных колониях муравьи выделяют феромоны во время путешествия. Затем в алгоритме делаем так, чтобы алгоритм увеличивал феромон q на пройденном муравьями пути после каждой итерации, но концентрация феромона не менялась в течение одной итерации.

Инициализация алгоритма

// 初始化任务集合
tasks = initRandomArray(_taskNum, taskLengthRange);

// 初始化节点集合
nodes = initRandomArray(_nodeNum, nodeSpeendRange);

Перед официальным запуском нам нужно инициализировать массив задач и массив узлов. Здесь используется метод случайного назначения, мы случайным образом создаем 100 задач для задач, а длина каждой задачи представляет собой случайное целое число от 10 до 100. Затем создайте 10 узлов случайным образом для узлов, а скорость обработки каждого узла представляет собой случайное целое число от 10 до 100.

Хорошо, подготовка завершена, давайте посмотрим на реализацию алгоритма муравьиной колонии.

Алгоритм муравьиной колонии

/**
 * 蚁群算法
 */
function aca() {
    // 初始化任务执行时间矩阵
    initTimeMatrix(tasks, nodes);

    // 初始化信息素矩阵
    initPheromoneMatrix(taskNum, nodeNum);

    // 迭代搜索
    acaSearch(iteratorNum, antNum);
}

Как видите, алгоритм муравьиной колонии не сложный, в общем это три части:

• Инициализировать матрицу времени выполнения задачи
• Инициализировать матрицу феромонов
• итеративный поиск

Конечно, первый и второй шаги относительно просты, а относительно сложный код находится в «итеративном поиске». Итак, давайте рассмотрим процесс реализации этих трех шагов по отдельности.

Инициализировать матрицу времени выполнения задачи

/**
 * 初始化任务处理时间矩阵
 * @param tasks 任务(长度)列表
 * @param nodes 节点(处理速度)列表
 */
function initTimeMatrix(tasks, nodes) {
    for (var i=0; i<tasks.length; i++) {
        // 分别计算任务i分配给所有节点的处理时间
        var timeMatrix_i = [];
        for (var j=0; j<nodes.length; j++) {
            timeMatrix_i.push(tasks[i] / nodes[j]);
        }
        timeMatrix.push(timeMatrix_i);
    }
}

Из приведенного выше исследования мы уже знаем, что, когда определены задачи массива длины задачи и узлы массива скорости обработки узлов, можно определить время выполнения всех задач.Используйте формулу tasks[i]/nodes[j] для расчета Да , то есть "время = длина/скорость", знание математики начальной школы. ОК, тогда расчет матрицы timeMatrix такой.

Вот еще одно введение в значение матрицы timeMatrix: timeMatrix[i][j] представляет время, необходимое для того, чтобы задача i была выделена узлу j для обработки, и ее формула расчета:

timeMatrix[i][j] = tasks[i]/nodes[j]

Инициализировать матрицу феромонов

/**
 * 初始化信息素矩阵(全为1)
 * @param taskNum 任务数量
 * @param nodeNum 节点数量
 */
function initPheromoneMatrix(taskNum, nodeNum) {
    for (var i=0; i<taskNum; i++) {
        var pheromoneMatrix_i = [];
        for (var j=0; j<nodeNum; j++) {
            pheromoneMatrix_i.push(1);
        }
        pheromoneMatrix.push(pheromoneMatrix_i);
    }
}

Инициализация матрицы феромонов означает установку всех элементов в матрице феромонов на 1.

Здесь снова повторяется значение матрицы феромонов: pheromoneMatrix[i][j] представляет концентрацию феромонов пути, который назначает задачу i узлу j.

Примечание. Мы рассматриваем назначение задачи в процессе планирования балансировки нагрузки как путь в алгоритме колонии муравьев. Например, мы принимаем действие «назначить задачу i узлу j» как путь для муравьев, чтобы перейти от задачи i к узлу j. Таким образом, pheromoneMatrix[i][j] эквивалентна концентрации феромона на пути i->j.

Итеративный процесс поиска

/**
 * 迭代搜索
 * @param iteratorNum 迭代次数
 * @param antNum 蚂蚁数量
 */
function acaSearch(iteratorNum, antNum) {
    for (var itCount=0; itCount<iteratorNum; itCount++) {
        // 本次迭代中，所有蚂蚁的路径
        var pathMatrix_allAnt = [];

        for (var antCount=0; antCount<antNum; antCount++) {
            // 第antCount只蚂蚁的分配策略(pathMatrix[i][j]表示第antCount只蚂蚁将i任务分配给j节点处理)
            var pathMatrix_oneAnt = initMatrix(taskNum, nodeNum, 0);
            for (var taskCount=0; taskCount<taskNum; taskCount++) {
                // 将第taskCount个任务分配给第nodeCount个节点处理
                var nodeCount = assignOneTask(antCount, taskCount, nodes, pheromoneMatrix);
                pathMatrix_oneAnt[taskCount][nodeCount] = 1;
            }
            // 将当前蚂蚁的路径加入pathMatrix_allAnt
            pathMatrix_allAnt.push(pathMatrix_oneAnt);
        }

        // 计算 本次迭代中 所有蚂蚁 的任务处理时间
        var timeArray_oneIt = calTime_oneIt(pathMatrix_allAnt);
        // 将本地迭代中 所有蚂蚁的 任务处理时间加入总结果集
        resultData.push(timeArray_oneIt);

        // 更新信息素
        updatePheromoneMatrix(pathMatrix_allAnt, pheromoneMatrix, timeArray_oneIt);
    }
}

Этот процесс немного сложен, но ничего страшного, позвольте мне пройти его по порядку.

Всего во всем алгоритме муравьиной колонии выполняется iteratorNum итераций. Каждая итерация будет генерировать текущую оптимальную стратегию распределения, которая является «локальным оптимальным решением». Чем больше итераций, тем ближе локальное оптимальное решение к глобальному оптимальному решению. Однако слишком большое количество итераций потребует больших затрат времени и производительности для балансировщика нагрузки, поэтому он не сможет справиться с планированием масштабных задач. Однако, если количество итераций слишком мало, глобальное оптимальное решение может быть не получено. Итак, как решить эту проблему? Есть два способа:

1. ограниченное количество итераций Чтобы избежать слишком большого количества итераций, мы можем заранее установить количество итераций, чтобы после такого количества итераций текущее локальное оптимальное решение считалось глобальным оптимальным решением.
2. Установить допуск к ошибкам Мы также можем заранее установить допустимый диапазон ошибок. После итерации N текущее оптимальное время обработки задачи находится в пределах этого допустимого диапазона, после чего итерация останавливается.

Эти два метода имеют свои достоинства, и здесь мы выбираем первый — ограничение количества итераций. И ограничьте количество итераций до 1000.

Примечание. Скорость сходимости также является важным показателем качества алгоритма. Например, алгоритм 1 выполняет 10 итераций, чтобы найти глобальное оптимальное решение, а алгоритм 2 выполняет 1000 итераций, чтобы найти глобальное оптимальное решение. Следовательно, скорость сходимости алгоритма 1 лучше, чем у алгоритма 2.

Поток выполнения вышеуказанного алгоритма описан ниже.

Алгоритму муравьиной колонии требуется общее число итераций iteratorNum.В каждой итерации все муравьи должны выполнить назначение всех задач. Таким образом, в приведенном выше алгоритме используются три слоя циклов for.Первый слой используется для цикла количества итераций.В этом алгоритме всего используется 1000 циклов,второй слой используется для муравьиного цикла.Есть Всего в этом алгоритме 10 муравьев. 10 циклов; третий слой используется для зацикливания всех задач. Всего в этом алгоритме 100 задач, поэтому ему нужно зациклиться 100 раз. В каждом цикле текущая задача назначается узел по определенной стратегии, а pathMatrix_oneAnt Стратегия размещения муравьев записывается в матрицу.

pathMatrix_oneAnt — двумерная матрица, все элементы которой равны 0 или 1. Например: pathMatrix_oneAnt[i][j]=1 означает, что текущий муравей назначает задачу i узлу j для обработки, pathMatrix_oneAnt[i][j]= 0 Указывает, что задача i не назначена узлу j для обработки. Каждая строка этой матрицы имеет один и только один элемент, равный 1, все остальные элементы равны 0.

После того, как каждый муравей завершит распределение этих 100 задач, будет сгенерирована матрица pathMatrix_oneAnt для записи стратегии распределения муравья. Затем, когда все 10 муравьев выполнят задание, будет сгенерирована матрица pathMatrix. Это трехмерная матрица.Первое измерение записывает номер муравья, второе измерение представляет индекс задачи, а третье измерение представляет номер узла, поэтому pathMatrix[x][i][j] =1 означает число x Муравей назначает задачу i узлу j для обработки, pathMatrix[x][i][j]=0 означает, что муравей с номером x не назначает задачу i узлу j для обработки.

Назначение этих 10 муравьев для выполнения задачи также называется итерацией. После завершения каждой итерации функция calTime_oneIt используется для расчета времени обработки задачи всеми муравьями в этой итерации и записи его в матрицу timeArray_oneIt.

Перед завершением каждой итерации матрицу феромонов необходимо обновить с помощью функции updatePheromoneMatrix.

Три важные функции в процессе итеративного поиска подробно описаны ниже:

• Функция назначения задач: assignOneTask
• Функция расчета времени обработки задачи: calTime_oneIt
• Функция обновления феромона: updatePheromoneMatrix

функция назначения задач

/**
 * 将第taskCount个任务分配给某一个节点处理
 * @param antCount 蚂蚁编号
 * @param taskCount 任务编号
 * @param nodes 节点集合
 * @param pheromoneMatrix 信息素集合
 */
function assignOneTask(antCount, taskCount, nodes, pheromoneMatrix) {

    // 若当前蚂蚁编号在临界点之前，则采用最大信息素的分配方式
    if (antCount <= criticalPointMatrix[taskCount]) {
        return maxPheromoneMatrix[taskCount];
    }

    // 若当前蚂蚁编号在临界点之后，则采用随机分配方式
    return random(0, nodeNum-1);
}

Функция назначения задач отвечает за назначение указанной задачи узлу для обработки в соответствии с определенной стратегией. Существует две стратегии распределения:

1. Распределить по концентрации феромона То есть задача назначается узлу с наибольшей концентрацией феромона в строке для обработки. Например, если номер текущей задачи — taskCount, а текущая матрица концентрации феромонов — pheromoneMatrix, то задача будет назначена узлу с наибольшей концентрацией феромонов в строке pheromoneMatrix[taskCount].

2. Случайно назначен Назначайте задачи узлу по желанию.

Итак, как выбрать эти две стратегии распределения? Ответ - по текущему номеру муравья antCount.

Из вышеизложенного видно, что для записи критических точек номеров муравьев с использованием различных стратегий распределения в этой итерации используется матрица CriticalPointMatrix. Например: CriticalPointMatrix[i]=5 означает, что муравьи с номерами от 0 до 5 используют метод «по концентрации феромонов» при назначении i-й задачи (т. е. назначают i-ю задачу на узел с наибольшей концентрацией феромонов для обработки); Муравьи с номерами от 6 до 9 используют стратегию случайного распределения при назначении задачи i.

Рассчитать время обработки задачи

/**
 * 计算一次迭代中，所有蚂蚁的任务处理时间
 * @param pathMatrix_allAnt 所有蚂蚁的路径
 */
function calTime_oneIt(pathMatrix_allAnt) {
    var time_allAnt = [];
    for (var antIndex=0; antIndex<pathMatrix_allAnt.length; antIndex++) {
        // 获取第antIndex只蚂蚁的行走路径
        var pathMatrix = pathMatrix_allAnt[antIndex];

        // 获取处理时间最长的节点 对应的处理时间
        var maxTime = -1;
        for (var nodeIndex=0; nodeIndex<nodeNum; nodeIndex++) {
            // 计算节点taskIndex的任务处理时间
            var time = 0;
            for (var taskIndex=0; taskIndex<taskNum; taskIndex++) {
                if (pathMatrix[taskIndex][nodeIndex] == 1) {
                    time += timeMatrix[taskIndex][nodeIndex];
                }
            }
            // 更新maxTime
            if (time > maxTime) {
                maxTime = time;
            }
        }

        time_allAnt.push(maxTime);
    }
    return time_allAnt;
}

Каждый раз, когда итерация завершается, пути прохождения всех муравьев в этой итерации (т. е. между задачами всех муравьев) должны быть рассчитаны и записаны в матрицу time_allAnt.

При фактическом планировании балансировки нагрузки обработка задач каждого узла рассчитывается параллельно, поэтому время выполнения всех задач должно быть максимальным значением времени выполнения задачи всех узлов, а не суммой времени выполнения всех задач.

Каждый раз, когда завершается итерация, генерируется матрица time_allAnt, которая добавляется к матрице resultData. Когда алгоритм завершает все итерации, все времена обработки задач всех муравьев записываются в матрицу resultData, которая представляет собой двумерную матрицу. Например: resultData[x][y]=10 означает, что время обработки задачи y-го муравья на x-й итерации равно 10.

обновить феромон

/**
 * 更新信息素
 * @param pathMatrix_allAnt 本次迭代中所有蚂蚁的行走路径
 * @param pheromoneMatrix 信息素矩阵
 * @param timeArray_oneIt 本次迭代的任务处理时间的结果集
 */
function updatePheromoneMatrix(pathMatrix_allAnt, pheromoneMatrix, timeArray_oneIt) {
    // 所有信息素均衰减p%
    for (var i=0; i<taskNum; i++) {
        for (var j=0; j<nodeNum; j++) {
            pheromoneMatrix[i][j] *= p;
        }
    }

    // 找出任务处理时间最短的蚂蚁编号
    var minTime = Number.MAX_VALUE;
    var minIndex = -1;
    for (var antIndex=0; antIndex<antNum; antIndex++) {
        if (timeArray_oneIt[antIndex] < minTime) {
            minTime = timeArray_oneIt[antIndex];
            minIndex = antIndex;
        }
    }

    // 将本次迭代中最优路径的信息素增加q%
    for (var taskIndex=0; taskIndex<taskNum; taskIndex++) {
        for (var nodeIndex=0; nodeIndex<nodeNum; nodeIndex++) {
            if (pathMatrix_allAnt[minIndex][taskIndex][nodeIndex] == 1) {
                pheromoneMatrix[taskIndex][nodeIndex] *= q;
            }
        }
    }

    maxPheromoneMatrix = [];
    criticalPointMatrix = [];
    for (var taskIndex=0; taskIndex<taskNum; taskIndex++) {
        var maxPheromone = pheromoneMatrix[taskIndex][0];
        var maxIndex = 0;
        var sumPheromone = pheromoneMatrix[taskIndex][0];
        var isAllSame = true;

        for (var nodeIndex=1; nodeIndex<nodeNum; nodeIndex++) {
            if (pheromoneMatrix[taskIndex][nodeIndex] > maxPheromone) {
                maxPheromone = pheromoneMatrix[taskIndex][nodeIndex];
                maxIndex = nodeIndex;
            }

            if (pheromoneMatrix[taskIndex][nodeIndex] != pheromoneMatrix[taskIndex][nodeIndex-1]){
                isAllSame = false;
            }

            sumPheromone += pheromoneMatrix[taskIndex][nodeIndex];
        }

        // 若本行信息素全都相等，则随机选择一个作为最大信息素
        if (isAllSame==true) {
            maxIndex = random(0, nodeNum-1);
            maxPheromone = pheromoneMatrix[taskIndex][maxIndex];
        }

        // 将本行最大信息素的下标加入maxPheromoneMatrix
        maxPheromoneMatrix.push(maxIndex);

        // 将本次迭代的蚂蚁临界编号加入criticalPointMatrix(该临界点之前的蚂蚁的任务分配根据最大信息素原则，而该临界点之后的蚂蚁采用随机分配策略)
        criticalPointMatrix.push(Math.round(antNum * (maxPheromone/sumPheromone)));
    }
}

Каждый раз, когда итерация завершена, необходимо обновить матрицу феромонов.Эта функция включает следующие четыре шага:

1. Уменьшить все концентрации феромонов на p% Этот процесс используется для имитации улетучивания феромонов.

2. Найдите кратчайший путь в этой итерации и увеличьте концентрацию феромонов этого пути на q% В каждой итерации 10 муравьев будут генерировать 10 путей (то есть 10 стратегий назначения задач), нам нужно найти кратчайший путь и увеличить концентрацию феромонов этого пути.

3. Обновить матрицу maxPheromononeMatrix После выполнения шагов 1 и 2 матрица феромонов была обновлена. Далее необходимо вычислить индекс, соответствующий самому большому феромону в каждой строке на основе этой последней матрицы феромонов, а именно: матрица maxPheromoneMatrix. Как видно из вышеизложенного, эта матрица используется функцией assignOneTask при постановке задач.

4. Обновить матрицу CriticalPointMatrix Затем необходимо обновить матрицу CriticalPointMatrix, чтобы записать критическое число муравьев, для которого принята стратегия распределения задач. Например: элемент в 0-й строке матрицы феромонов равен pheromoneMatrix[0]={1,3,1,1,1,1,1,1,1,1}, тогда метод расчета CriticalPointMatrix[ 0] выглядит следующим образом:

   • Рассчитайте вероятность самого большого феромона: самый большой феромон / сумма всех феромонов в строке
     • 3/(1+3+1+1+1+1+1+1+1+1)=0.25
   • Рассчитайте критический индекс муравьев: количество муравьев * вероятность максимального феромона
     • 10*0,25=3 (с округлением вверх)
   • Таким образом, критическая точкаMatrix[0]=3
     • Это означает, что в следующем итерационном процессе при назначении задачи 0 муравьи 0-3 назначают задачу узлу с наибольшей концентрацией феромонов, а муравьи 4-9 используют стратегию случайного назначения.

Анализ результатов

Результат работы алгоритма показан на следующем рисунке:

По оси абсцисс — количество итераций, по оси ординат — время обработки задачи. Каждая точка представляет собой время обработки задачи одним муравьем. Количество итераций алгоритма на рисунке выше равно 100, а количество муравьев равно 1000, поэтому каждая итерация будет генерировать 1000 схем распределения задач, и после завершения каждой итерации будет выбрана текущая оптимальная схема и концентрация феромона схемы будет увеличено, чтобы вероятность выбора этой схемы была выше на следующей итерации. А также использовать определенную вероятность того, что муравьи примут стратегию случайного распределения, чтобы найти лучшее решение.

Из рисунка видно, что глобальное оптимальное решение появляется примерно через 30 итераций.

напиши в конце

Весь код я выложил на свой Github, вы можете скачать его по желанию. https://github.com/bz51/AntColonyAlgorithm

Выше два вопроса:

• aca.html
• aca.js

Реализация алгоритма муравьиной колонии находится в aca.js. После загрузки кода вы можете напрямую открыть aca.html в браузере, чтобы просмотреть его. Приветствую всех звезд. Также приглашаю вас обратить внимание на мой публичный аккаунт, где я регулярно делюсь технической галантереей~