Что такое феромон у муравья
Я, субъект персональных данных, в соответствии с Федеральным законом от 27 июля 2006 года № 152 «О персональных данных» предоставляю ООО НПИЦ Агрокон (далее — Оператор), расположенному по адресу 117545, г. Москва, ул. Дорожная, д.5, кор.1, согласие на обработку персональных данных, указанных мной в форме на сайте в сети «Интернет», владельцем которого является Оператор.
Под персональными данными субъекта персональных данных понимается нижеуказанная общая информация: ФИО, адрес электронной почты и номер телефона.
Принимая настоящее Соглашение, я выражаю свою заинтересованность и полное согласие, что обработка персональных данных может включать в себя следующие действия: сбор, систематизацию, накопление, хранение, уточнение (обновление, изменение), использование, передачу (предоставление, доступ), блокирование, удаление, уничтожение, осуществляемых как с использованием средств автоматизации (автоматизированная обработка), так и без использования таких средств (неавтоматизированная обработка).
Я понимаю и соглашаюсь с тем, что предоставленная информация, является полной, точной и достоверной; при предоставлении информации не нарушается действующее законодательство Российской Федерации, законные права и интересы третьих лиц; вся предоставленная информация заполнена мною в отношении себя лично; информация не относится к государственной, банковской и/или коммерческой тайне, информация не относится к информации о расовой и/или национальной принадлежности, политических взглядах, религиозных или философских убеждениях, не относится к информации о состоянии здоровья и интимной жизни.
Я понимаю и соглашаюсь с тем, что Оператор не проверяет достоверность персональных данных, предоставляемых мной, и не имеет возможности оценивать мою дееспособность и исходит из того, что я предоставляю достоверные персональные данные и поддерживаю такие данные в актуальном состоянии.
Я понимаю и соглашаюсь с тем, что Оператор имеет право направлять мне уведомления о новых продуктах и услугах, специальных предложениях и различных событиях, посредством отправки электронных писем, СМС сообщений, сообщений в мессенджерах и звонков.
Согласие действует по достижении целей обработки или в случае утраты необходимости в достижении этих целей, если иное не предусмотрено федеральным законом.
Согласие может быть отозвано мною в любое время на основании моего письменного заявления.
Источник
Алгоритмы муравьиной колонии
Содержание
Введение
Каждый, кто хоть раз в жизни наблюдал за муравьями, обязательно должен был заметить: вся деятельность этих насекомых имеет ярко выраженную групповую окраску. Работая вместе, группа муравьев способна затащить в муравейник кусок пищи или строительного материала, в 10 раз больше самих работников. Ученые давно знают об этом, но только в последнее время задумались о полезном применении муравьиного опыта в повседневной жизни.
Сам по себе муравей — достаточно примитивное существо. Все его действия, по сути, сводятся к элементарным инстинктивным реакциям на окружающую обстановку и своих собратьев. Однако несколько муравьев вместе образуют сложную систему, которую некоторые ученые называют «коллективным разумом». Поэтому алгоритмы муравьиных колоний часто называют алгоритмами роевого интеллекта.
Например, группа муравьев прекрасно умеет находить кратчайшую дорогу к пище. Если какое-нибудь препятствие — палка, камень, нога человека — встает на пути, бравые добытчики быстро находят новый оптимальный маршрут.
Муравьи решают проблемы поиска путей с помощью химической регуляции. Каждый муравей оставляет за собой на земле дорожку особых веществ — феромонов. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев — тем явнее след, а чем явнее след — тем большее «желание» пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к «кормушке», тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, и круг замыкается. Остальные пути — менее используемые — потихоньку пропадают.
Алгоритмы муравья, или оптимизация по принципу муравьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго), основаны на применении нескольких агентов и обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, в изменяющихся сетях.
В настоящей статье рассматривается общий случай алгоритма муравьиной колонии.
Идея алгоритма
Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного феромона, используя его в качестве маркера.
При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй — нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время 
. Первый муравей в этот момент пройдет только половину пути (рис. 2).
Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рис. 3).
При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.
Рис. 2. Рис. 3.
В этом и состоит базовая идея алгоритма муравья — оптимизация путем непрямой связи между автономными агентами.
Пошаговое описание общей схемы
Предположим, что окружающая среда для муравьев представляет собой полный неориентированный граф . Каждое ребро имеет вес, который обозначается как расстояние между двумя вершинами, соединенными им. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении (рис. 4).
Вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромонов на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьев двигается по локально-оптимальному маршруту. Избежать этого можно моделируя отрицательно обратную связь в виде испарения феромона. Причем, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарений может привести к получению устойчивого локального оптимального решения.
Муравей
Муравей — это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона , по имени математика сэра Уильяма Гамильтона.
Узлы в списке «текущего путешествия» располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.
Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи, так как для каждой задачи способ размещения муравьев является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
На этом же этапе задается начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
Движение муравья
Движение муравья основывается на одном и очень простом вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующего ребра пути используется уравнение
(1)
Здесь — интенсивность фермента на ребре между узлами и , — функция, которая представляет измерение обратного расстояния для грани, — вес фермента, a — коэффициент эвристики. Параметры и определяют относительную значимость двух параметров, а также их влияние на уравнение. Так как муравей путешествует только по узлам, которые еще не были посещены (как указано списком табу), вероятность рассчитывается только для ребер, которые ведут к еще не посещенным узлам. Переменная представляет эти ребра.
Путешествие муравья
Пройденный муравьем путь отображается, когда муравей посетит все узлы графа. Циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана — она равна сумме всех ребер, по которым путешествовал муравей. Уравнение (2) показывает количество феромона, который был оставлен на каждом ребре пути для муравья . Переменная является константой.
(2)
Результат уравнения является средством измерения пути, — короткий путь характеризуется высокой концентрацией феромонов, а более длинный путь — более низкой. Затем полученный результат используется в уравнении (3), чтобы увеличить количество феромона вдоль каждого ребра пройденного муравьем пути.
(3)
Важно, что данное уравнение применяется ко всему пути, при этом каждое ребро помечается феромоном пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни феромона, в противном случае истинная длина пути останется неизвестной. Константа — значение между 0 и 1.
Испарение феромонов
В начале пути у каждого ребра есть шанс быть выбранным. Чтобы постепенно удалить ребра, которые входят в худшие пути графа, ко всем ребрам применяется процедура испарения феромона. Используя константу из уравнения 3, мы получаем уравнение 4:
(4)
Поэтому для испарения феромона используется обратный коэффициент обновления пути.
Повторный запуск
После того как путь муравья завершен, ребра обновлены в соответствии с длиной пути и произошло испарение феромона на всех ребрах, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по графу, основывая выбор ребра на уравнении 1. Этот процесс может выполняться для постоянного количества путей или до момента, когда на протяжении нескольких запусков не было отмечено повторных изменений. Затем определяется лучший путь, который и является решением.
Демонстрационный пример
Разберем функционирование рассмотренного выше алгоритма на простом примере, чтобы увидеть, как работают уравнения. Возьмем простой сценарий с двумя муравьями из примера который рассмотрели в п. 1. На рис. 5 показан этот пример с двумя ребрами между двумя узлами ( и ). Каждое ребро инициализируется и имеет одинаковые шансы на то, чтобы быть выбранным.
Рис. 5. Рис. 6.
Два муравья находятся в узле помечаются как и . Так как вероятность выбора любого пути одинакова, в этом цикле мы проигнорируем уравнение выбора пути. Данные для задачи:
- число пройденных шагов: для
, для
- уровень феромона (Q/пройденное расстояние): для ,
На рис. 6 каждый муравей выбирает свой путь (муравей идет по верхнему пути, а муравей — по нижнему). Муравей сделал 20 шагов, а муравей , — только 10. По уравнению 2 мы рассчитываем количество феромонов, которое должно быть «нанесено».
Примечание: Работу алгоритма можно изменить, переопределив его параметры (например, , или ), например придав больший вес феромонам или расстоянию между узлами.
Далее по уравнению 3 рассчитывается количество феромона, которое будет применено. Для муравья результат составляет: Для муравья результат составляет: Далее с помощью уравнения 4 определяется, какая часть феромонов испарится и, соответственно, сколько останется. Результаты (для каждого пути соответственно) составляют:
Эти значения представляют новое количество феромонов для каждого пути (верхнего и нижнего, соответственно). Теперь переместим муравьев обратно в узел воспользуемся вероятностным уравнением выбора пути 1, чтобы определить, какой путь должны выбрать муравьи. Вероятность того, что муравей выберет верхний путь (представленный количеством феромона 0,16), составляет:
Вероятность того, что муравей выберет нижний путь (представленный количеством феромона 0,28) составляет:
При сопоставлении двух вероятностей оба муравья выберут нижний путь, который является наиболее оптимальным.
Характерные особенности
Для алгоритма муравьиной колонии необходимо указать:
- закон выделения феромона,
- закон испарения феромона,
- количество агентов,
- места размещения.
Все эти характеристики выбираются с учетом особенности задачи на основе экспериментальных исследований (эвристики).
- реализует поиск приближенных решений ,
- имеет полиномиальную сложность,
- является одним из видов вероятностных алгоритмов (законы выделения испарения – вероятностные законы).
Области применения
Алгоритм оптимизации муравьиной колонии может быть успешно применен для решения сложных комплексных задач оптимизации. Цель решения сложных комплексных задач оптимизации – поиск и определение наиболее подходящего решения для оптимизации (нахождения минимума или максимума) целевой функции (цены, точности, времени, расстояния и т.п.) из дискретного множества возможных решений. Типичный пример решения подобной задачи – квадратичная задача о назначениях, задача календарного планирования, задача маршрутизации транспорта, различных сетей (GPRS, телефонные, компьютерные и т.п.), распределение ресурсов и работ. Эти задачи возникают в бизнесе, инженерии, производстве и многих других областях. Исследования показали, что метод муравьиных колоний может давать результаты, даже лучшие чем при использовании генетических алгоритмов и нейронных сетей.
Заключение
Рассмотрены механизмы реализации эвристических алгоритмов муравьиной колонии. Они могут быть успешно применены для решения сложных комбинаторных задач оптимизации. Основная идея, лежащая в основе алгоритмов муравьиной колонии, заключается в использовании механизма положительной обратной связи, который помогает найти наилучшее приближенное решение в сложных задачах оптимизации. То есть, если в данном узле муравей должен выбрать между различными вариантами и если фактически выбранные результаты будут хорошими, то в будущем такой выбор будет более желателен, чем предыдущий. Этот подход является многообещающим из-за его общности и эффективности в обнаружении очень хороших решений сложных проблем.
Источник