Линейная алгебра и мат. Статистика



бет24/49
Дата09.01.2023
өлшемі294.26 Kb.
#468247
1   ...   20   21   22   23   24   25   26   27   ...   49
Вопросы Big Data

Муравьиный алгоритм

Эвристический метод, основанный на моделировании поведения муравьев, ищущих пути от своей колонии к источникам пищи. Этот метод позволяет относительно быстро найти хорошее, но не обязательно оптимальное решение.
Муравьиный алгоритм моделирует мультиагентную систему. Её агентов можно называть муравьями. Как и настоящие муравьи, они довольно просто устроены: для выполнения своих обязанностей они требуют небольшое количество памяти, а на каждом шаге работы выполняют несложные вычисления.
Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается.
Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их.
После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути.

  • Алгоритм роя частиц

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

  1. Клеточные автоматы: определение, элементарные клеточные автоматы, двумерные клеточные автоматы, типы окрестностей, игра "Жизнь", параллельная реализация.



Достарыңызбен бөлісу:
1   ...   20   21   22   23   24   25   26   27   ...   49




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет