Глоссарий ИИ
Полный словарь искусственного интеллекта
Алгоритм муравьиной колонии (ACO)
Метаэвристика, вдохновленная поведением настоящих муравьев, использующая искусственные феромоны для поиска оптимальных решений в задачах комбинаторной оптимизации. Алгоритм имитирует отложение и испарение феромонов, чтобы направить поиск к лучшим решениям.
Испарение феромонов
Механизм экспоненциального убывания концентраций феромонов, позволяющий избежать преждевременной сходимости и способствовать исследованию новых решений. Этот процесс имитирует естественное испарение феромонов в колониях настоящих муравьев.
Вероятность перехода
Вероятностное правило, определяющее выбор следующего элемента, который муравей добавляет к частичному решению, основанное на уровнях феромонов и локальной эвристической информации. Эта вероятность объединяет коллективное обучение и априорную информацию для направления поиска.
Построение решения
Итерационный процесс, в котором каждый муравей строит полное решение, последовательно добавляя компоненты в соответствии с вероятностями перехода. Построение является вероятностным, но смещенным следами феромонов, оставленными предыдущими решениями.
Локальное обновление феромонов
Механизм изменения следов феромонов, выполняемый каждым муравьем сразу после добавления компонента к его частичному решению. Это локальное обновление снижает вероятность того, что другие муравьи выберут тот же путь в течение той же итерации.
Глобальное обновление феромонов
Процесс, применяемый после построения всех решений в одной итерации, при котором только лучшие решения откладывают феромоны для усиления перспективных компонентов. Этот механизм фокусирует поиск на наиболее перспективных областях пространства решений.
Комбинаторная оптимизация
Класс математических задач, состоящих в поиске лучшей конфигурации среди конечного, но очень большого множества возможных решений. Муравьиные алгоритмы особенно эффективны для решения этих NP-трудных задач.
Задача коммивояжера (TSP)
Классическая задача комбинаторной оптимизации, цель которой — найти кратчайший маршрут, проходящий через каждый город ровно один раз перед возвращением в исходную точку. Задача коммивояжера часто используется в качестве теста для оценки производительности муравьиных алгоритмов.
Параметр альфа (α)
Коэффициент, контролирующий влияние следов феромонов при расчете вероятностей перехода в алгоритмах муравьиных колоний (ACO). Высокое значение альфа способствует использованию ранее найденных решений.
Параметр бета (β)
Параметр, регулирующий важность эвристической информации при выборе переходов, обычно представляющий видимость или локальную желательность хода. Этот параметр балансирует коллективное обучение с априорной информацией о проблеме.
Параметр ро (ρ)
Скорость испарения феромонов, коэффициент в диапазоне от 0 до 1, определяющий скорость уменьшения следов феромонов между итерациями. Этот параметр контролирует сохранность накопленной в системе информации.
Параметр Q
Константа, используемая для определения количества феромонов, откладываемых муравьями, часто пропорциональная качеству найденного решения. Этот параметр влияет на интенсивность подкрепления хороших решений в системе.
Список кандидатов
Механизм оптимизации, ограничивающий выбор следующих ходов подмножеством наиболее перспективных вариантов на основе локальной эвристики. Эта техника ускоряет сходимость, фокусируясь на потенциально лучших решениях.
Эвристика видимости
Статическая или динамическая информация о локальной желательности хода, обычно основанная на свойствах задачи, таких как расстояние в задаче коммивояжера (TSP). Эта эвристика направляет муравьев независимо от накопленных феромонов.
Диверсификация поиска
Стратегия, направленная на поддержание исследования различных областей пространства решений во избежание застревания в локальных оптимумах. В ACO она контролируется в основном скоростью испарения и параметрами перехода.
Интенсификация поиска
Процесс концентрации поисковых усилий вокруг наиболее перспективных решений, выявленных на данный момент. Эта стратегия использует информацию, накопленную с помощью феромонов, для улучшения существующих решений.