Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

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

Многоагентные системы были созданы для задач, которые нецелесообразно решать с помощью так называемых монолитных систем (представляющих собой целостный программный комплекс) ввиду сложности или высокой стоимости разработки таких систем. В отличие от них многоагентные системы – это совокупность интеллектуальных агентов, обладающих какими-либо свойствами, целями и способами взаимодействия с «окружающей средой» и между собой. Важно отметить, что агенты в системе не могут и не должны иметь полной информации о том, что происходит в ней. Если проводить аналогию с реальным миром, многоагентная система – это толпа людей или стадо животных, а монолитная система – это «бог из машины», обладающий исчерпывающей информацией об окружающем мире в любой момент времени. Следствием этого является видное невооружённым взглядом преимущество МАС перед монолитными системами в оптимизации: если второй нужна сложная система идентификации в целях принятия какого-либо решения [3], агенты МАС используют более простые алгоритмы.

Также из этих особенностей МАС следует то, что их агенты могут по-разному взаимодействовать с окружающей средой или, иначе говоря, использовать разные парадигмы. Это обязательно должно быть внесено в список рисков при анализе требований к программному проекту [1, 4], так как неверный выбор парадигмы может нанести существенный ущерб проекту. Тем не менее, в процессе выбора можно столкнуться с тем, что единого свода парадигм не существует. Данная статья посвящена их исследованию. Материалом для него выбрана наиболее известная группа многоагентных систем – биоинспирированные алгоритмы МАС. В качестве критерия классификации выбрано строение их агентов.

В процессе исследования нами были выявлены три парадигмы МАС. Первая из них была названа парадигмой индифферентных агентов. Её главная особенность – отсутствие какого-либо взаимодействия между агентами: они не имеют никакой информации о состоянии друг друга и не имеют средств коммуникации, равно как не могут влиять друг на друга. Мы считаем, что наглядным примером использования этой парадигмы послужит алгоритм искусственной иммунной системы.

В данном алгоритме агенты названы антителами, а условия решаемой задачи – антигеном. В основе алгоритма лежит цикл «воспроизведение-связывание-мутация», где связывание – это проверка решений-антител на пригодность, а мутация – изменение некоторых из свойств антитела. Количество итераций цикла может быть ограниченным. Другими условиями остановки работы алгоритма могут являться отсутствие улучшения решения на протяжении долгого времени или достижение порогового значения связывания. Значение связывания вычисляется по формуле:

(1)

где:

i - номер антитела;

- n-ое свойство антитела;

- коэффициент связывания n-го свойства антитела с n-ым участком антигена.

Отдельно стоит упомянуть процесс мутации. Перед тем, как пройти процесс клонирования и изменения свойств, антитела должны преодолеть барьер в виде определённого значения связывания: антитела, не прошедшие его, удаляются из цикла. Таким образом, обеспечивается отсеивание заведомо худших результатов и оптимизация процесса.

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

Вторая выявленная нами парадигма – парадигма гомогенных агентов. Система, реализованная через данную парадигму, населена полностью идентичными друг другу агентами, и, де-факто, стандартом их коммуникации являются различного рода «феромонные метки», оставляемые на пути следования агентов.

Алгоритм оптимизации подражанием муравьиной колонии или же муравьиный алгоритм – ярчайший пример подобной системы. Он применяется для поиска кратчайшего пути на некотором графе G (рисунок 1). Рассмотрим его работу.

Рисунок 1. Граф G

Выпустим в вершине А некоторое количество агентов (муравьёв), задав точкой назначения вершину Б. В пути они будут оставлять метки, чья привлекательность будет со временем уменьшаться. Несмотря на то, что маршрут выбирается случайным образом по формуле (2) и муравьи в начале работы могут массово использовать неоптимальный вариант, через большое количество итераций он устареет, и колония будет пользоваться маршрутом, близким к наиболее оптимальному.

, (2)

где:

- вероятность перехода по пути i,

- величина, обратная весу (длине) i-го перехода,

- количество “феромона” на i-м переходе,

q - величина, определяющая “жадность” алгоритма,

p - величина, определяющая “стадность” алгоритма и

q + p = 1.

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

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

В качестве примера нами была выбрана версия алгоритма пастушьей собаки (АПС) из работы [2]. АПС – алгоритм, основанный на адаптивной коммутации между сбором агентов, когда они слишком рассредоточены, и их перегоном к точке назначения, как только они агрегируют. Поведение агентов (овец) зависит от, условно говоря, функции страха F(a) перед управляющим агентом (собакой), чьё значение уменьшается, если овца скрылась за другой. Если же точка, в которой находится овца, является локальным максимумом функции F(a), т. е. овца находится в пределах досягаемости собаки-пастуха, её перемещение определяется следующим образом:

(3)

где:

– координаты овцы;

h – передвижение овцы за один шаг.

Если , где - пороговое значение страха, то решение считается найденным и овца меняет местоположение по формуле (3).

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

Объединим всё вышесказанное (таблица 1).

Таблица 1 - Сравнение парадигм МАС

Таким образом, мы изучили МАС и на примере биоинспирированных алгоритмов и выявили три их парадигмы. Учитывая существование иных способов классификации парадигм, например, по признаку организации агентов [8], мы считаем, что наша классификация будет полезна для малых проектов, в которых строение агентов важнее, чем способы их организации.