Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
- Бұл бет үшін навигация:
- Алгоритм роя частиц
| Муравьиный алгоритм
Эвристический метод, основанный на моделировании поведения муравьев, ищущих пути от своей колонии к источникам пищи. Этот метод позволяет относительно быстро найти хорошее, но не обязательно оптимальное решение. Муравьиный алгоритм моделирует мультиагентную систему. Её агентов можно называть муравьями. Как и настоящие муравьи, они довольно просто устроены: для выполнения своих обязанностей они требуют небольшое количество памяти, а на каждом шаге работы выполняют несложные вычисления. Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается. Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их. После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути. Алгоритм роя частиц Сокращенно называется PSO, его основная идея состоит в том, чтобы моделировать поведение хищных птиц. Все частицы имеют значение пригодности, определяемое оптимизированной функцией, а каждая частица также имеет скорость, которая определяет направление и расстояние, на которое они летят. Затем частицы следуют за текущей оптимальной частицей и ищут в пространстве решений. Клеточные автоматы: определение, элементарные клеточные автоматы, двумерные клеточные автоматы, типы окрестностей, игра "Жизнь", параллельная реализация. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|