`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Методики дрессировки "цифровых муравьев"

0 
 

Муравьи относятся к тем немногим живым существам, которые не только сами приспосабливаются к среде обитания, но и активно перестраивают окружающий мир применительно к своим нуждам, своим задачам. Муравьи -- вечные строители. Гнезда многих видов поражают своими размерами, сложной и рациональной архитектоникой. Дороги, тоннели, разбросанные по территории убежища для тлей и червецов, грибные сады... Разнообразные способы запасания и хранения пищи, фактическое приручение ряда видов насекомых. И все это при почти абсолютном доминировании инстинктов. А. Захаров. Муравей, семья, колония
Моделирование природных явлений, началом которого можно считать создание клеточного автомата Джоном фон Нейманом и Артуром Брэксом в конце 40-х годов XX-го века, прошло с тех пор огромный путь. Нейронные сети, эмитирующие работу головного мозга, генетические алгоритмы, использующие принципы эволюции, оптимизация, эмулирующая поведение стаи птиц или рыб... Этот ряд можно продолжать достаточно долго.

Методики дрессировки "цифровых муравьев"
Пример реализации классического алгоритма оптимизации пути к источнику пищи (программа Алексея Васильева, Рига)
Одно из направлений, о котором пойдет речь, -- роевой (коллективный) интеллект (Swarm Intelligence). Его выбор вызван тем, что программы, основанные на данном принципе, уже перешагнули грань чисто теоретических и приносят реальную пользу во многих областях. AT&T и British Telecom используют ПО, разработанное с учетом данного подхода, для маршрутизации трафика, General Motors вводит систему контроля потока запчастей, построенную с применением роевой логики. Это только крупные корпорации, а если учесть небольшие, начинающие фирмы, то примеров использования алгоритмов роевого интеллекта можно найти огромное множество. В короткой статье сложно раскрыть столь объемную тему, и автор не претендует на полноту и безупречность изложения.

Основателями данного направления можно считать Эрика Бонабо (Eric Bonabeau), Марко Дориго (Marco Dorigo) и Гая Тераулаза (Guy Theraulaz). То, что система, состоящая из множества агентов, действующих по простым правилам, может иногда решать проблемы, несоизмеримые по своему масштабу и сложности с самими агентами, стало настоящим открытием. Появился другой, неклассический, способ построения сложных систем, когда не выстраивается жесткая, заранее определенная структура, и все ее компоненты подчиняются главному "центру управления". Системы, основанные на роевом интеллекте, являются эмпирическими, т. е. их действия с трудом объясняются теоретически, но на практике могут дать очень хорошие результаты. В этом сила и одновременно слабость подобных систем. В четких, хорошо структурированных задачах они вряд ли получат преимущество над системами, построенными на стройном математическом аппарате. Их возможности раскрываются там, где нет полной ясности. Именно здесь их способность к самоорганизации и адаптации может принести практическую пользу. Ведь можно попытаться смоделировать любые существующие системы, состоящие из множества самостоятельных объектов, начиная от финансовых рынков и заканчивая популяцией горилл в заповеднике Серенгети.

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

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

Рассмотрим подробнее один из алгоритмов, использующихся в сетях передачи данных. Для работы системы на основе этого алгоритма создаются два набора мобильных агентов (программ небольшого объема, способных перемещаться между узлами сети и выполнять на этих узлах определенные действия) -- так называемые "обычные муравьи" (forward ants) и "возвращающиеся муравьи" (backward ants). Эти агенты не связаны друг с другом напрямую и могут передавать свой опыт только через две информационные структуры, расположенные на каждом узле:

Методики дрессировки "цифровых муравьев"
Феромоновые дорожки
1. Массив Мk, представляющий собой статистическую модель распределения трафика для каждого пункта назначения d, такой, какой эта модель видится из узла k.

2. Таблица маршрутизации, которая содержит вероятностное значение Pdn для каждой пары узлов (d, n). Это значение характеризует оптимальность выбора (по времени прохождения маршрута) следующего узла n при условии, что пункт назначения -- это узел d.

Сначала в каждом узле сети s создается обычный "муравей" Fs>d со случайно выбранным узлом назначения d. Каждый "муравей" выбирает следующий пункт своего назначения, используя информацию в таблице маршрутизации. Каждый следующий узел выбирается по случайной схеме с вероятностью Pdn, зависящей от оптимальности маршрута к соседнему, еще не посещенному узлу n. Если "муравей" уже побывал на всех соседних узлах, то следующий определяется случайным образом. Если выбранный маршрут на данный момент не доступен, "муравей" ожидает доступа к линии связи в очереди с другими пакетами данных. Идентификатор каждого посещенного узла k и время, затраченное на перемещение к этому узлу Ts>k, заносится в память "муравья". Если происходит циклическое перемещение, т. е. если "муравей" попадает на уже посещенный им узел, все данные об узлах внутри цикла обнуляются.

Когда "муравей" Fs>d достигает узла назначения d, он создает "возвращающегося муравья" Bd>s, передает ему свою память и погибает. "Возвращающийся муравей" проделывает тот же самый путь, но в обратном направлении. Прибыв на узел k с предыдущего узла f, "муравей" обновляет массив Мk значениями времени Tk>i, затраченного на путешествие с узла k на каждый посещенный узел i по пути k>d. Он также вносит изменения в таблицу маршрутизации, повышая вероятность Pif, относящуюся к каждой паре узлов i и f , и понижая для нормализации вероятности Pin остальных соседних узлов n. Время Tk>i (указано выше), затраченное на прохождение маршрута "муравьем" Fs>d, используется для определения коэффициента повышения.

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

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

Методики дрессировки "цифровых муравьев"
Примеры приложений, выполненных в среде разработки SDG
Методики дрессировки "цифровых муравьев"
Следующая особенность -- сортировка личинок в муравейнике. Основоположником исследования и использования этого явления считается французская компания Eurobios, одна из ведущих компаний в разработке приложений, базирующихся на роевой логике. С многочисленными применениями основанных на данном явлении алгоритмов можно ознакомиться на Web-сайте этой компании. Они используются для анализа финансовых рисков, предсказания курса валют и акций, грузоперевозок, статистики. В муравейнике личинки рассортированы строго по группам без какого-либо центрального плана, указывающего муравьям, куда переносить данный тип личинок и корм для них. Простая модель на основе агентов объясняет этот феномен. Когда агент, "несущий" какой-либо объект, ощущает вокруг множество подобных объектов, он оставляет его в данном месте, агент, "нашедший" объект, отличающийся от своего окружения, переносит его в другое место. Применение данного алгоритма сортировки к распределенным базам данных может дать очень интересные результаты. Уже существуют попытки применить этот вид сортировки в поисковых системах в WWW и локальных сетях.

Одно из наиболее впечатляющих достижений общественных насекомых -- это сложная архитектура их гнезд, построенных без всяких инженерных познаний. Объяснить такое строительство можно сводом микроправил, по которым действует каждый из строителей. Конфигурация кирпичей, окружающих "строителя", несущего кирпич в настоящий момент, определяет согласно микроправилам, уложит он этот кирпич в данном месте или пронесет его дальше. Перспективность применения подобных алгоритмов в робототехнике и построении сложных систем очевидна даже на первый взгляд. Они дают возможность создать самовоспроизводящиеся и самонастраивающиеся системы. А к этой цели, т. е. возможности самостоятельного приспособления системы к меняющимся внешним условиям, стремятся практически все производители программного и аппаратного обеспечения, робототехники. Существуют программы, в том числе и свободно распространяемые, например Wasp Nest Building Simulator Доминика Снаерса (Dominique Snyers), в которых, меняя микроправила, можно наглядно увидеть, какой эффект произведет данное изменение и как это отразится на всей системе.

Итак, мир моделирования поведения общественных насекомых широк и разнообразен. Он часто пересекается с другими перспективными направлениями разработки программного обеспечения. Например, создатели таких модных на сегодняшний день направлений, как мобильные агенты или равноправные вычисления (peer-to-peer), вплотную заинтересовались исследованиями в области роевого интеллекта. Те же мобильные агенты при минимальном размере должны выполнять поставленные задачи, координировать свои действия с другими агентами, иметь защиту от атак извне. Минимизация размера заставляет максимально упрощать код мобильного агента и применять наиболее эффективные схемы взаимодействия между ними. Подробнее о применении роевой логики к работе мобильных агентов можно прочитать в работах Минтона (R. Minton), Марка Фабиунке (Mark Fabiunke) и других исследователей. В Internet имеется масса программ для любых платформ, действующих на этих принципах, многие из которых бесплатны и распространяются с исходными кодами. Для изучения подобных систем доступно множество примеров и библиотек, в том числе и целые программные среды разработки, например SDG (Swarm Development Group). Эта система, написанная на Objective C и занимающая со всеми библиотеками, примерами, шаблонами и описанием около 50 MB, распространяется бесплатно с открытыми исходными кодами. Другой пример -- это система ECHO, созданная специально для изучения взаимодействия между агентами и поведения сложных адаптирующихся систем. Можно также упомянуть о языке NAML Multi-Agent Modelling Language, служащем для построения мультиагентных систем. Ну, а о количестве приложений по данной теме говорит хотя бы тот факт, что при наборе в поисковом поле Google словосочетания "Swarm Intelligence" выдается более 32 тыс. ссылок, среди которых можно выбрать область, удовлетворяющую вашим вкусам, начиная от написания картин с помощью подобных алгоритмов и заканчивая маршрутизацией пакетов в IP-сетях.
0 
 

Напечатать Отправить другу

Читайте также

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT