Подсказка

Для эффективного поиска ответа на Ваш вопрос, выберите вопросительное слово, например "Как" и соответственно этому вопросительному слову составьте свой вопрос. Если Ваш вопрос не содержит вопросительного слова, то выберите в списке -//- и просто напишите свой вопрос.

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

Спрашивает Антон Анатольевич   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

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