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

Спрашивает Антон Анатольевич   13 мая 2008
объясните как он работает?
Ответ
Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов на графах. Подход предложен бельгийским исследователем Марко Дориго (Marco Dorigo). Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к пище.

В основе алгоритма лежит поведение муравьиной колонии — маркировка более удачных путей большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом, на основании формулы вида: ...... , где: Pi вероятность перехода по пути i, li длина i-ого перехода, fi количество феромона на i-ом переходе, q величина, определяющая «жадность» алгоритма, p величина, определяющая «стадность» алгоритма и q + p = 1

Решение не является точным и даже может быть одним из худших, однако, в силу вероятностности решения, повторение алгоритма может выдавать (достаточно) точный результат.
Источник: http://ru.wikipedia.org/wiki/Муравьиный_алгоритм
13 мая 2008 23:46
Другие ответы
1
Этот класс алгоритмов появился в результате исследований поведения живых муравьев. Муравей, двигаясь по определенному маршруту, оставляет за собой след пахнущего вещества (феромона). Такое вещество влияет на выбор маршрута: выбирается то направление ... Еще
13 мая 2008 23:51
2
Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также аналогичных задач поиска маршрутов ... Еще
13 мая 2008 23:51
3
В последние годы интенсивно разрабатывается научное направление Natural Computing — «Природные вычисления», объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. Это механизмы обеспечивают эффективную ... Еще
25 мая 2008 17:07
← Показать все ответы
Комментарии
  • 13 мая 2008 23:57

    А как же он работает? Отвечать на вопрос надо бы до конца! ! ! Софья Викторовна.

    • 14 мая 2008 10:12

      Вадим Петрович, Ваш ответ Вы взяли с того же сайта, что и я (и тоже его разместили!). Для Вас я размещаю информацию с другого сайта о том, как работает муравьиный алгоритмФ: муравьи умеют находить самый оптимальный путь между муравейником и внешними точками. Чем больше муравьев используют один и тот же путь, тем выше концентрация ферментов на этом пути. Чем ближе внешняя точка к муравейнику, тем больше раз к ней перемещались муравьи. Что касается более удаленной точки, то ее муравьи достигают реже, поэтому по дороге к ней они применяют более сильные ферменты. Чем выше концентрация ферментов на пути, тем предпочтительнее он для муравьев по сравнению с другими доступными. Так муравьиная "логика" позволяет выбирать более короткий путь между конечными точками.
      Алгоритмы муравья интересны, поскольку отражают ряд специфических свойств, присущих самим муравьям. Муравьи легко вступают в сотрудничество и работают вместе для достижения общей цели. Алгоритмы муравья работают так же, как муравьи. Это выражается в том, что смоделированные муравьи совместно решают проблему и помогают другим муравьям в дальнейшей оптимизации решения."