Действительно ли муравьи находят кратчайший путь к источнику пищи?

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

Я не могу относиться к этому. Я видел, как муравьи проделывают очень длинный путь к еде. Это не всегда делается из соображений безопасности. Что говорят об этом биологи?

Посмотрите в Википедии «муравьиную мельницу» или на YouTube «спираль смерти муравья», и вы обнаружите, что они создают пути, которые не только неоптимальны, но и вообще недействительны.

Ответы (1)

Короткий ответ

Действительно ли муравьи находят кратчайший путь к источнику пищи?

Нет! Но они могут найти достойный путь

Более длинный ответ

Алгоритмы оптимизации используются для поиска в пространстве возможностей, которое слишком велико для изучения каждой отдельной возможности. Такие алгоритмы пытаются найти достаточно хорошее решение, часто не обязательно зная, насколько «хорошо» найденное решение по сравнению с наилучшим возможным решением. Таким образом, алгоритмы оптимизации не всегда находят лучшее решение. На самом деле, в большинстве случаев они находят не лучший путь, а достаточно хороший за разумное время.

То же самое относится и к муравьям. По аналогии, муравьиная колония представляет собой алгоритм, основанный на агентах, в котором агенты оставляют следы феромонов. Концентрация феромона зависит от длины следа. Следуя по следам, которые пахнут сильнее всего, и регулярно делая небольшие ошибки (чтобы они могли продолжать исследовать другие пути), они в конечном итоге находят достойное решение. Для получения дополнительной информации просто погуглите Как муравьи находят свой путь? .

Если мы не знаем, насколько хорошее найденное решение сравнивается с лучшим, то как мы узнаем, что оно достаточно хорошее?
@Ooker Как вы судите, по какому пути идти? Я думаю, вы обнаружите, что связываете это не с «лучшим» путем (о котором вы могли не знать), а вместо этого с ситуацией, например «можно ли тратить столько времени».
Точно так же, когда вы берете машину, чтобы отправиться в какое-то место, путь, который вы выбираете, обычно «достаточно хорош», а не самый лучший. Этого достаточно, потому что путь до места назначения занимает разумное время...
@ Remi.b «Такие алгоритмы пытаются найти достаточно хорошее решение, как правило, даже не зная, насколько «хорошо» найденное решение по сравнению с наилучшим возможным решением». - Задачи оптимизации на самом деле (как правило) знают, каково истинное решение, однако не всегда могут достичь его с помощью вычислений . При реализации функции оптимизации обычно определяется некоторый эпсилон, где, если ошибка вычисленного решения меньше, чем эпсилон, то решение алгоритма оптимизации будет принято как «достаточно близкое».
@ Remi.b Если алгоритм оптимизации не знает об истинном решении, которое он пытается получить, он не может проверить потенциальное решение. Я признаю, что определенно есть много случаев, когда истинное решение неизвестно, однако это гораздо более распространено в теоретической работе, чем в гораздо более практичных, прикладных вычислительных подходах.
@Charles Спасибо, я внес небольшую модификацию, чтобы не заявлять, что алгоритм оптимизации никогда не знает, какое решение является лучшим.
@ Чарльз, я не согласен. Вы можете проверить силу решения по сравнению с другими возможными решениями. Вам не нужно знать расстояние от наилучшего возможного маршрута до места, если вы проработаете 1000 возможных маршрутов, а затем выберете самый короткий из них.
@ Tom.Bowen89 Если у вас есть набор решений, и вы просто тестируете одно решение по сравнению с другими, как вы можете быть уверены, что любое из этих решений близко к требуемому результату? Должен быть определен тип «наиболее желаемого результата», иначе вы «не сможете увидеть лес из-за деревьев». Другими словами, необходимо определить идеальное решение или минимальную допустимую ошибку . Если нет, то нельзя быть уверенным в том, насколько точен ваш алгоритм и какие результаты он дает.
@ Tom.Bowen89 Я также добавлю, что во многих задачах оптимизации используется вероятностный подход, поэтому необходимо иметь несколько экземпляров (наборов решений, вытекающих из разных начальных условий) алгоритма. То есть каждый экземпляр работающего алгоритма будет создавать совершенно разные наборы решений. При этом, опять же, необходимо определить какой-то желаемый результат, чтобы оценить точность этих решений.
@ Tom.Bowen89 Итак, если отвлечься от вашего примера кратчайшего пути ... что, если истинный кратчайший путь составляет 10 миль, однако лучшее решение, которое дает ваш алгоритм, составляет 50 миль? Как вы сможете оценить точность, если у вас нет представления об истинном кратчайшем пути? Это важно, потому что, как сказано в моем предыдущем комментарии, если лучшее решение все еще очень далеко от истинного решения, алгоритм нужно будет запустить снова, чтобы получить другие потенциальные решения. Должна быть какая-то «внешняя» оценка производительности и точности вашего алгоритма.
@ Tom.Bowen89 Tom.Bowen89 Я рекомендую вам изучить алгоритмы имитации отжига, так как это обычная платформа в информатике для представления динамики алгоритмов оптимизации и аппроксимации. en.wikipedia.org/wiki/Simulated_annealing
@Charles, есть ли способ рассчитать уверенность в точности рассчитанного пути? Поправьте меня, если я ошибаюсь, но разве в статистике достоверность предположения не может быть вычислена самостоятельно с правильным значением?
@ooker Вы не можете рассчитать уверенность в том, что у вас есть лучший путь, просто сэмплируя (попробовав решения и увидев, какие из них работают), если вы не можете переборщить все пространство состояний. Однако, если вы что-то знаете о своем пространстве состояний, вы можете использовать эту специфичную для проблемы информацию, чтобы определить, насколько хорошо ваше решение. Например, если вы знаете, что пространство дифференцируемо, вы можете использовать любую известную вам информацию о максимальных производных для создания верхней/нижней границы.
@Charles: «Если алгоритм оптимизации не знает об истинном решении, которого он пытается достичь, то он не может проверить потенциальное решение». - Это не так - очень часто в реальной жизни критерием является "Решение должно стоить меньше Х". Если найдено решение, стоимость которого меньше X, оно является «достаточно хорошим» и, следовательно, действительным. Если это намного меньше, чем X, тем лучше. Нет необходимости знать абсолютное наилучшее достижимое значение. Значение X зависит от (внешних) ограничений проекта, а не от параметров самой задачи оптимизации.
Это именно то, что я сказал в предыдущем комментарии, лол. Пожалуйста, прочитайте все комментарии, прежде чем пытаться исправить кого-то. «При реализации функции оптимизации обычно определяется некоторый эпсилон, где, если ошибка вычисленного решения меньше, чем эпсилон, то решение алгоритма оптимизации будет принято как «достаточно близкое».
@Charles: я прочитал этот комментарий, и он отличается от того, что я говорю. Я не говорю, что вы определяете эпсилон, который дает приемлемую (пропорциональную или абсолютную) разницу между истинным оптимальным значением и лучшим из найденных - для этого все еще требуется априорное знание оптимального значения. Вместо этого я говорю, что вы определяете пороговое значение X, которое не зависит от оптимального значения, т. е. вас совершенно не заботит, насколько вы близки к истинному оптимуму, а только то, найдете ли вы решение, которое «работает» в любом контексте, в котором вы находитесь. оперируем.
@psmears То, как вы определяете эвристику, не всегда последовательно, и ее слишком сложно обобщить, поэтому ваши утверждения недействительны. Это отличается от алгоритма к алгоритму, который в конечном итоге основан на информации, которую вы уже получили при разработке алгоритма.
Комментарии не для продолжительных дискуссий. Пожалуйста, следите за этим в чате (и, возможно, на каком-нибудь сайте CS SE).
@Charles: Вы путаете алгоритм с проблемной областью и, в частности, с критерием приемлемости проблемы (возможно, для муравьев: превышает ли энергия в еде в конце этого пути энергию, затраченную на путь, достаточно, чтобы обеспечить выживание?) с критерием остановки/эвристикой конкретного алгоритма («Хорошо, мы потратили достаточно времени и энергии на проверку путей, теперь давайте приступим и поедим».). Первое, скорее всего, повлияет на выбор второго, но важно знать о различиях. Удачи в учебе, твой протеиновый проект звучит круто :)
@Pimgdxkcd.com/ 85
Действительно ли муравьи находят кратчайший путь к источнику пищи?
СпросиСетьПолитика конфиденциальности1y, 0v