"Муравьиная логика"

Муравьиная «логика».

Оглавление

1.Введение.....................................................................................................2

2. Литературный обзор……………………………………….....................3

3. Алгоритмы муравья…...............................................................................5

3.1. Естественная мотивация…………………………………....................5

3.2. Алгоритм муравья……………………...................................................6

3.3. Начальная популяция.............................................................................7

4. Исследовательская работа……………………………………….............8

5. Заключение……………………………………………………………….9

6. Литература …………………………………………................................10

7. Приложение.I-II........................................................................................11-12

Введение

Объектом исследования в моей работе являются «Природные вычисления», а предметом исследования математические методы, в которых заложены принципы природных механизмов принятия решений.

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

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

Цель моей работы: показать роль и место математических вариаций с муравьями в природе, доказать существование непрерывной связи между математикой и природой.

Я поставил перед собой следующие задачи:

1. Совершенствовать свои возможности  в области проектной деятельности.
2. Знакомство с историей возникновения вопроса «математические вариации с насекомыми», углубление знаний в области математики  и ее связи с другими науками.
3. Доказать, что отношение высоты муравейника к диаметру, подчинено всеобщему закону гармонии Природы - золотому сечению. 
4. Разработка и выполнение творческого проекта.

Использованные методы – сбор материала, его анализ и обобщение.

Литературный обзор

I

Математические способности муравьёв, в соответствии с потребностями сложного муравьиного сообщества, простираются далеко. Например, на одном кормовом участке живут семьи нескольких видов, из которых один может быть главным, доминирующим над несколькими другими. "Хозяевам" ничего не стоит прогнать или даже полностью уничтожить неугодных соседей, конкурирующих с основным видом. Но они этого не делают, сохраняя численность чужого вида на каком-то оптимальном уровне. Как они ведут такой учет?

И кто знает, может быть когда-либо и у насекомых будет обнаружен какой-то собственный банк данных? Нам пока неизвестно, каким образом ведут свою "бухгалтерию" муравьи, пчелы и прочие животные. Но важно то, что все они изначально знают, сколько и каких особей должно быть в семье, в стае или табуне. Откуда-то им всем ведомо, в частности, какая территория необходима для прокорма каждой семьи, то есть, на каком расстоянии друг от друга должны располагаться гнезда муравьев и птиц, так же, как и норы мышей или лис, берлоги у медведей и т.д. Другими словами, все эти наши соседи по планете пользуются числом и мерой. Не составляют исключения в этом смысле и муравьи. В этом нетрудно убедиться каждому любознательному человеку: измерьте хотя бы приблизительно, шагами расстояния между муравейниками в густо заселенном рыжими лесными муравьями лесу - и увидите, что для данного городища большинство муравьиных домов находятся примерно на одинаковом расстоянии друг от друга. И зависят эти расстояния, как и другие размеры муравьиной "архитектуры", от вида и состояния кормовой базы урочища, а также от густоты леса и сомкнутости крон деревьев (близости их вершин).    При этом вы заметите и то, что в одном городище высоты зрелых куполов тоже примерно одинаковы, отличаясь лишь на 20-30 процентов от средней величины. Более или менее выдержаны и диаметры куполов, а также их объёмы, крутизна склонов и другие показатели.

А отношение высоты к диаметру, в большинстве случаев, в среднем подчинено всеобщему закону гармонии Природы - золотому сечению или золотой пропорции, то есть пропорциональны. Правда, все это справедливо лишь для тех случаев, когда купола не повреждены человеком или медведем. И их должно быть достаточно много для статистического сравнения, хотя бы с десяток или более.

Муравьи-строители точно знают, чувствуют, какими должны быть параметры их сооружений - размеры купола, расстояния между входами и началами (устьями) подземных выработок-ходов и т. п. И они знают это не вообще, а применительно к конкретным экологическим условиям каждого места их обитания. Так, например, южноафриканский муравей-листорез умеет вырезать из листьев совершенно правильные круги, имеющие стандартные, почти одинаковые размеры. И пользуется он при этом лишь зазубренными краями своих асимметричных челюстей.

Необыкновенные "математические" способности насекомых исследовались учеными с помощью очень несложных и вместе с тем остроумных экспериментов. Муравьев поместили перед лабиринтом, устроенным прямо на лабораторном столе. В одном из ходов лабиринта, за вторым поворотом, клали приманку, например, кусочек сахара. Муравей-разведчик быстро находил его, быстро возвращался в гнездо, сообщал об этом своим товарищам, - и вскоре к его находке тянулась цепочка рабочих муравьев-фуражиров.    Потом приманку помещали за третий поворот, затем за четвертый, пятый и так далее. И каждый раз муравей, возвращаясь, шел прямо к приманке, не путаясь в поворотах сложного извилистого хода. Лабиринт тщательно чистили, протирали и промывали, уничтожая возможные пахучие следы и малейшие признаки запаха. Затем даже меняли его материал, оставляя неизменной конфигурацию. Но муравей всегда находил кратчайший путь, не прибегая к известному "методу проб и ошибок". Он не тыкался попусту даже несколько дней спустя, после недельного "перерыва в работе"...

Однако так продолжалось только до 15-16 поворота. Дальше муравей отыскать сахар без новых пробных "тыков" уже не мог...

Значит ли это, что муравей умеет считать только до 15 и запоминает результат лишь этого счета? Или это указывает на то, что его способности ограничиваются объёмом информации в 30 бит (15 поворотов при двухвариантном выборе дальнейшего пути на каждом из них)? Это человеку предстоит еще когда-либо узнать. Но, во всяком случае, ни приматы, ни птицы, ни другие живые существа этому пока еще не научились. И подумайте: кто из нас сможет запомнить путь в лабиринте из 15 поворотов после первой же попытки? Кто сможет сохранить эту важную информацию на столь длительный период? Без знаменитой нити Ариадны нам никак не обойтись... Но кто же дал ее муравьям?

Исследуя память животных, экспериментаторы используют специальные методики обучения. В настольных комнатных муравейниках - сравнительно легко и быстро вырабатываются у муравьев условные рефлексы на свет, вибрацию или какие-то иные сигналы. Обучаемые насекомые надолго запоминают дорогу к многократно увиденной в конце пути метке, к геометрической фигуре определенного цвета, формы и даже яркости.

Муравьи способны запоминать путь не только в лабораторном лабиринте. Они хорошо ориентируются и на дневной поверхности, и в трехмерном (объемном) пространстве, то есть и глубоко под землей, и на высоких деревьях. Это умение им необходимо так же, как путешественникам, конструкторам и архитекторам. Иначе они просто не смогли бы уверенно находить дорогу к пище и воде, к источникам лесных стройматериалов.

А в начале 2005 года на Интернете прошла заметка о том, что сотрудник Дрезденского университета Дирк Геблинг, изучая муравьиные колонии с целью выяснения способности насекомых регулировать свои напряженные "грузопотоки", установил, что муравьи поступают в точности так же, как жители больших городов, которые пытаются избежать транспортных пробок. Оказалось, что использование математической модели "муравьиного алгоритма" может помочь не только отладить движение разных видов транспорта, но и даст возможность правильно регулировать информационные потоки во Всемирной сети.

Вот какой неожиданный результат, имеющий важное прикладное значение, может дать наблюдение за жизнью муравьев!

Примечательно, что стройной геометрической системе подчинены не только параметры единичного гнезда, начиная от отдельных строительных деталей, но и всего городища, с размерами, измеряемыми иногда сотнями метров.

Алгоритмы муравья

II

В этой главе рассматривается интересный алгоритм, основанный на применении нескольких агентов, с помощью которого можно решать самые разнообразные задачи. Алгоритмы муравья (Ant algorithms), или оптимизация по принципу муравьиной колонии это название было придумано изобретателем алгоритма, Марко Дориго, обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения различных задач, в том числе, проблем маршрутизации в меняющихся сетях.

Естественная мотивация

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

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

Рассмотрим пример. Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного фермента, используя его в качестве маркера. (см.Приложение I).
При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время T1. Первый муравей в этот момент пройдет только половину пути (см.Приложение I).

Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время T2 второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (см.Приложение I). При перемещении каждого муравья на пути остается немного фермента. Для первого муравья за время T0T2 путь был покрыт ферментом только один раз. В то же самое время второй муравей покрыл путь ферментом дважды. За время T4 первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация фермента на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация фермента выше.

В этом и состоит базовая идея алгоритма муравья - оптимизация путем непрямой связи между автономными агентами.
Алгоритм муравья

Подробно рассмотрим алгоритм муравья, чтобы понять, как он работает при решении конкретной проблемы.

Предположим, что окружающая среда для муравьев представляет собой полный неориентированный граф. Каждое ребро имеет вес, который обозначается как расстояние между двумя вершинами, соединенными им. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении (см.Приложение I). Вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромонов на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в выбор собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьев двигается по локально-оптимальному маршруту. Избежать этого можно моделируя отрицательно обратную связь в виде испарения феромона. Причем, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарений может привести к получению устойчивого локального оптимального решения.

Начальная популяция 

После создания популяция муравьев поровну распределяется по узлам сети. Необходимо равное разделение муравьев между узлами, чтобы все узлы имели одинаковые шансы стать отправной точкой. Если все муравьи начнут движение из одной точки, это будет означать, что данная точка является оптимальной для старта, а на самом деле мы этого не знаем.

Каждый, кто хоть раз в жизни наблюдал за муравьями, обязательно должен был заметить: вся деятельность этих насекомых имеет ярко выраженную групповую окраску. Работая вместе, группа муравьев способна затащить в муравейник кусок пищи или строительного материала, в 10 раз больше самих работников. Ученые давно знают об этом, но только в последнее время задумались о полезном применении муравьиного опыта в повседневной жизни. Сам по себе муравей - достаточно примитивное существо. Все его действия, по сути, сводятся к элементарным инстинктивным реакциям на окружающую обстановку и своих собратьев. Однако несколько муравьев вместе образуют сложную систему, которую некоторые ученые называют «коллективным разумом». Поэтому алгоритмы муравьиных колоний часто называют алгоритмами роевого интеллекта.  Например, группа муравьев прекрасно умеет находить кратчайшую дорогу к пище. Если какое-нибудь препятствие - палка, камень, нога человека - встает на пути, бравые добытчики быстро находят новый оптимальный маршрут. Муравьи решают проблемы поиска путей с помощью химической регуляции. Каждый муравей оставляет за собой на земле дорожку особых веществ - феромонов. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев - тем явнее след, а чем явнее след - тем большее «желание» пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к «кормушке», тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, и круг замыкается. Остальные пути - менее используемые - потихоньку пропадают. Алгоритмы муравья, или оптимизация по принципу муравьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго), основаны на применении нескольких агентов и обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения различных задач.

Исследовательская работа.

Мною была проведена исследовательская работа (см. Приложение II).

1. Я измерил шагами расстояния между семью муравейниками в нашем лесу, где живут   рыжие муравьями.
2. Я измерил высоту семи муравейников.
3. Я измерил диаметр семи муравейников.
4. Подсчитал отношение высоты муравейника к диаметру.

Заключение

Мною были сделаны выводы:

1. Большинство муравьиных домов находятся примерно на одинаковом расстоянии друг от друга. В данном случае где-то 80-95 шагов. И зависят эти расстояния, как и другие размеры муравьиной "архитектуры", от вида и состояния кормовой базы урочища, а также от густоты леса и сомкнутости крон деревьев (близости их вершин).    
2. Высоты куполов муравейников  тоже примерно одинаковы, отличаясь лишь на 20-30 процентов от средней величины. Более или менее выдержаны и диаметры.
3. Отношение высоты к диаметру, в среднем подчинено всеобщему закону гармонии Природы - золотому сечению или золотой пропорции, то есть пропорциональны.
4. Мною были подобраны и решены комбинаторные задачи с помощью граф, которые я рекомендую использовать при проведении факультативных занятий в школе и подготовке к олимпиадам.
5. Выполнив свою работу и изучив описанные выше природные закономерности, я пришел к выводу, что совершенство природы не перестает удивлять человека, и ему есть чему учиться у насекомых. А математика – это уникальное средство познания красоты природы.

Список литературы

1. Азевич А.И.  Двадцать уроков гармонии. М., 1998.
2. Виленкин Н.Я., Шибасов Л.П., Шибасова З.Ф. За страницами учебника математики. М., 1996.
3. Гросман С., Тернер Джо. Математика для биологов. М, 1983.
4. Штовба С. Д. Муравьиные алгоритмы. Exponenta Pro. Математика в приложениях, 2003, №4, стр. 70-75.

http://vuz.exponenta.ru/PDF/book/mur.html

http://www.machinelearning.ru/wiki/

Приложение I

Начальная конфигурация

Прошёл один период времени

  Граф.

Прошло два периода времени

Приложение II