автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка методов и алгоритмов мультиагентного поиска релевантной информации в информационных средах гипертекстовой организации

На правах рукописи

РГЗ ОД

2 1 ДЗГ 2303

КОНОНЕНКО Роман Николаевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ МУЛЬТИАГЕНТНОГО ПОИСКА РЕЛЕВАНТНОЙ ИНФОРМАЦИИ В ИНФОРМАЦИОННЫХ СРЕДАХ ГИПЕРТЕКСТОВОЙ ОРГАНИЗАЦИИ

Специальность: 05.13.16. - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Таганрог - 2000 г.

Работа выполнена в Таганрогском государственном радиотехническом университете.

Научный руководитель - доктор технических наук, профессор

Божич В. И.

Официальные оппоненты:

доктор технических наук, профессор Маргслов А. В. кандидат техническтгх паук, с.н.с. Тарасов В. Б.

Ведущая организация - НИИ Иснрокнбернетикн,

г. Ростов-на-Дону

Защита состоится "_"___2000 г. в____час.__мин.

на заседании диссертационного совета Д 063.13.02 при Таганрогском государственном радиотехническом университете (347928, г.Таганрог, ГСП-17 Л, пер. Некрасовский, 44 ).

С диссертацией можно ознакомиться в библиотеке университета.

Авторефера г разделан "_

2000 г.

Ученый секретарь диссертационного совета

к.т.н., доцент А.Н. Целых

ЬМОй.-М.С ЯМ.О

J

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Переход к постиндустриальному информационному обществу неразрывно связан с развитием глобальных информационных систем (ГИС), содержащих беспрецедентное количество информации. В настоящее время, наиболее известкой и быстроразвивающейся системой такого рода является возникшая на базе мировой компьютерной сети Internet гипертекстовая информационная система World Wide Web (WWW). По оценкам специалистов, на 1997 год система WWW насчитывала примерно 150-106 документов, при этом объем хранимых в системе данных удваивался каждые 4 месяца. Экспоненциальный рост WWW и сверхбольшой объем хранимой в данной системе информации породили новую проблему ее эффективного использования. В частности, актуальной стала проблема поиска полезной (релевантной) информации в ресурсах WWW. Каждый, кто работал с системой WWW, знает, что найти требуемую информацию в WWW без знания точного URL-адреса затруднительно, а подчас и просто невозможно. Для решения этой задачи в настоящее время применяются существующие поисковые системы (ПС), значительно облегчающие задачу поиска. Однако, результаты поиска с помощью классических ПС далеко не всегда являются удовлетворительными. В частности, существующие ПС имеют тенденцию возвращать по запросу слишком большой объем информации, лишь малая часть которой является действительно релевантной сделанному запросу, т.е. точность поиска является низкой. Низкая эффективность существующих ПС объясняется классическим подходом, принятым при их построении. Данный подход основан на механизме глобальной индексации содержимого WWW и унаследован от ПС, предназначенных для поиска в локализованных коллекциях данных сравнительно небольшого объема. Устранение недостатков существующих ПС требует разработки принципиально новых подходов к построению ПС и методов интеллектуального поиска релевантной информации в глобальной информационной среде, порожденной информационным содержимым ГИС WWW.

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

информации, являются мультиагентные системы (МА-системы). Их особенность заключается в децентрализованной обработке информации на основе относительно независимых информационных компонент — агентов, решающих общую задачу коллективных! образом. Как показал анализ, основные свойства МА-систем отвечают основным качествам глобальных информационных сред, что обуславливает перспективность их применения при построении ПС нового поколения.

Предлагаемая диссертационная работа посвящена проблеме построения эффективных систем поиска релевантной информации в глобальных гипертекстовых информационных средах на основе МА-систем как прогрессивного направления ИИ.

Целью работы является разработка методов и алгоритмов интеллектуального поиска релевантной информации в сложных информационных средах гипертекстовой организации (основная ориентация сделана на ГИС WWW как наиболее развитую информационную среду Internet).

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

- разработка метода интеллектуального поиска в информационных хранилищах гипертекстовой организации на основе одного из современных направлений искусственного интеллекта — мультиагентных систем;

- разработка комплекса математических и имитационных программных моделей гипертекстовой среды, алгоритмов мультиагентного поиска в гипертекстовой информационной среде;

- проведение имитационного программного моделирования, анализ полученных результатов, исследование эффективности построенных алгоритмов мультиагентного поиска релевантной информации;

- разработка общей архитектуры поискового агента и мультиагентнои поисковой системы для гипертекстовой информационной среды.

Предметом исследования являются:

- мультиагентные системы на основе бионического направления

ИИ;

- эволюционные алгоритмы оптимизации и адаптации интеллектуальных агентов; .

- эффективность применения нейронных сетей прямого распространения в качестве интеллектуального ядра поисковых агентов.

Методы исследования. В качестве основных методов

исследования использованы математические модели и имитационное компьютерное моделирование.

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

Практической ценностью диссертационной работы являются:

- разработанный метод интеллектуального поиска релевантной информации в гипертекстовой информационной среде, позволяющий существенно сократить объем просматриваемой при поиске информации за счет ориентации поиска в перспективных направлениях;

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

- разработанные варианты функциональных архитектур мультиагентной поисковой системы для одно- и многомашинной реализации (на основе мобильных агентов) могут служить основой при проектировании действующих поисковых систем на основе мультиагентного подхода;

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

На защиту выносятся следующие основные научные поло же н и я:

- метод интеллектуального мультиагентного поиска в

информационных хранилищах гипертекстовой организации;

- комплекс алгоритмов мультиагентного поиска информации в гипертекстовых информационных средах;

- архитектура поискового агента на основе нейронной сети прямого распространения;

- комбинированный алгоритм обучения нейросетевых поисковых агентов;

- варианты архитектуры интеллектуальной поисковой системы для гипертекстовых информационных сред на основе парадигмы бионической мультиагентной системы.

Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийской школе-семинаре "Современные проблемы математического моделирования" (Абрау-Дюрсо, 1995); Всероссийской научно-технической конференции "Нейроинформатика-99" (Москва, 1999); Второй научно-методической конференции "Internet и современное общество" (Санкт-Петербург, 1999); VI Всероссийской конференции "Нейрокомпьютеры и их применение" (Москва, 2000).

Публикации. Результаты, полученные в работе, нашли отражение в 10 печатных работах, одна из которых была опубликована за рубежом, две — в центральной печати. Семь работ были опубликованы в сборниках научных трудов конференций, в том числе одна работа была представлена на международной конференции, пять — на всероссийских конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, пяти разделов и заключения, изложенных на 202 страницах, содержит 61 рисунок, 105 наименований библиографии и 129 страниц приложения, всего 339 страниц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы цель и задачи исследований.

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

поисковых систем. Дается общее описание функций и требований к поисковой системе WWW, вводится общая терминология для рассматриваемой предметной области. Обзор существующих в настоящее время систем автоматического поиска включает восемь ПС с классической архитектурой. Архитектура всех рассматриваемых ПС базируется на механизмах индексации данных. При таком подходе к поиску информации в WWW исходная гипертекстовая модель конвертируется в индекс — сжатый высокорегулярный экстракт исходных данных, отражающий информационное содержимое исходной гипертекстовой среды. В рассматриваемых классических Г1С индекс представляет собой реляционную базу данных, методы работы с которой хорошо известны. Обработка запросов пользователей происходит на основе построенного глобального индекса исходных гипертекстовых данных. Индекс используется для обработки многих запросов от многих пользователей, содержимое запросов неизвестно на момент его составления. В силу этого, индекс должен обладать универсальностью и полнотой, т.е. отражать все аспекты информационого содержимого гипертекстовой коллекции данных. Для составления индекса в рассматриваемых системах применяются методы автоматической индексации, приведенные в приложении 2. Индекс составляется на основе полного сканирования содержимого WWW с помощью различных алгоритмов исчерпывающего поиска.

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

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

Второй раздел диссертационной работы посвящен разработке метода мультиагентного поиска (МА-поиска) в информационной среде гипертекстовой организации. Рассматривается понятие агента, приведена общая идеология мультиагентных систем, описываются основные свойства мультиагентного подхода к построению интеллектуальных систем как одного из новых направлений исследований в ИИ. Обосновывается возможность построения методов интеллектуального поиска и гипертекстовой среде WWW в виде следующих двух базовых допущений об ее организации.

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

2. Наличие связи между контекстом HTML-документа, в котором находится гиперссылка, и содержимым документа, адресуемого данной гиперссылкой.

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

Общий алгоритм МА-поиска, следующий из предложенного метода, выглядит следующим образом:

1. Создается начальная популяция, состоящая из п0 агентов. Каждому агенту присваивается начальное значение энергии, равномерно распределенное в интервале [0; Етах], где Етах —. максимальная энергия агента. Агенты размещаются на некоторых начальных документах.

2. Выбрать из популяции текущего агента а,. Предоставить агенту процессорное время для выполнения поиска. Используя предоставленное время, агент анализирует содержимое текущего HTML-документа d\ и устанавливает гиперссылку 1,к для перехода на следующий документ ¿4.

3. Извлечь из WWW-среды документ dk, URL которого определяется гнперссылкой ¡¡¡,. Определить энергетическую стоимость документа E[dk) с учетом степени релевантности документа и затрат ресурсов на его извлечение. Сообщить агенту а, изменение энергии А£, = E[dt), установить для агента текущий документ равным dk.

4. Анализ условия выживания агента. Если модифицированная энергия

агента Е, < 0, агент уничтожается (исключается из популяции), переход к п8.

5. Обучение. Агент а, использует локальную информацию (в общем случае, полученное изменение энергии ЛЕ,-) для адаптации на основе встроенного в него алгоритма обучения.

6. Репродукция. Если Е, > Е„юх , агент создает свою копию, которая помещается в популяцию агентов. Энергия агента-родителя и агента-потомка распределяется поровну, т.е. устанавливается равной Е,/ 2. Потомок стартует с документа, на котором находился родитель при репродукции.

7. "Выживший" агент а, возвращается в рабочую популяцию.

8. Если текущий размер популяции п, = 0 или получена команда остановки поиска, то завершение работы алгоритма, в противном случае — переход к п2.

В моделях функция энергетической стоимости документа определялась выражением:

Е(^) = Е,-р{ак)-с, (1)

где

Е5 — энергия поощрения агента;

— дискретная функция релевантности документа,

равная 1 для релевантных документов и 0 — в противном случае; с — постоянная стоимость извлечения документа из коллекции.

Для всех ранее извлекавшихся документов Е{с1к) равнялось 0.

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

- месторасположением агента в информационной среде (первое допущение);

- способностью агента выделять перспективные гиперссылки в тексте документа на основе встроенного алгоритма анализа текста (второе допущение).

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

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

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

где

¿) — множество вершин графа, соответствующих

документам гипертекстовой коллекции данных;

Ь — множество ребер графа, соответствующих гипсрссылкам в документах коллекции.

Множество вершин-документов графа Н разбивается на 2 подмножества релевантных и нерелевантных запросу пользователя документов коллекции:

(2)

£) = йи/,

КпТ = 0,

(3)

(4)

где

Я — подмножество релевантных документов в коллекции; / — подмножество нерелевантных документов в коллекции.

Основными параметрами гипертекстовой среды являются (в скобках указаны типовые значения, принятые при моделировании):

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

II — вероятность того, что гиперссылка, расположенная на релевантном документе, адресует релевантный документ;

Т— вероятность правильной оценки глперссылки (совпадения значения Л со значением р {df) адресуемого гиперссылкой документа); ..

A(l,j) — оценка перспективности гиперссылки при анализе ее контекста в содержащем ее документе.

Для существования сделанных выше допущений о свойствах гипертекста необходимо выполнение условий II > К (1-е допущение), Т > 0.5 (2-е допущение).

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

N (Ю4) — общее число документов в коллекции; К (0.1) — доля релевантных документов в коллекции; ¿,„„>.(20) — максимальное колтество гиперссылок в

гипертекстовом документе.

где

определяются степенью присутствия терминов из запроса пользователя в документе.

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

В разделе представлено 4 модели мультиагентных ПС, на основе которых исследуются различные аспекты алгоритма МА-поиска.

В первых 2-х моделях ПС на основе неадаптивных агентов исследуются возможности МА-поиска безотносительно к способу реализации встроенных в агентов механизмов анализа текста. Поисковые агенты в этих моделях определяют гиперссылку для дальнейшего поиска на основе равновероятного (1-я модель) и стохастического, основанного на значениях оценок Л (2-я модель) выбора. Обучение агентов в этих моделях не производится. Во 2-й модели, где исследуется эффективность поиска в зависимости от 2-го допущения, считается, что точность построения агентами оценок л для гиперссылок задается фиксированным параметром Т. Основным результатом первых двух моделей является зависимость эффективности МА-поиска от наличия и выраженности полезных особенностей организации гипертекста в WWW, определяемых параметрами //, Т гипертекстовой модели.

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

к Я 1-741-7" 1-Я

где

ц'0 — определяющая точность МА-поиска доля популяции поисковых агентов, расположенных на релевантных документах коллекции данных;

Я — точность ненаправленного поиска, совпадающая с долей релевантных документов в гипертекстовой коллекции.

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

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

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

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

начиная со средних значений параметра Т- 0.75 и низких значений //=0.25.

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

- нейронной сети (персептрона);

- стохастического селектора гиперссылок.

На входы персептрона подавался »-мерный (по числу терминов в запросе) вектор, характеризующий содержимое документа с учетом отношения терминов к анализируемой гиперссылке (матрицы степеней отношения терминов в документах к содержащимся гиперссылкам создавались при генерации модели гипертекста исходя из заданной максимальной точности прогнозирования Т). На единственном выходе сети формировалась оценка Я для текущей анализируемой гиперссылки. Полученные для каждой гиперсылки оценки передавались на вход селектора гиперссылки, выделявшего единственную гиперссылку из всего множества с вероятностью, пропорциональной где /? — адаптивный параметр агента, задающий баланс между стохастизмом и детерминизмом производимого агентом поиска.

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

извлекаемых агентом документов. В первой из моделей 2 группы проведено сравнение эффективностей обоих типов алгоритмов обучения. Результаты моделирования позволили сделать вывод о преимуществе архитектурно-зависимого метода. Результаты работы для 2-х методов показаны на рис.1, где приведено изменение точности поиска в зависимости от доли извлеченных релевантных документов гипертекстовой среды (достигнутой общности поиска). Для ненаправленного поиска соответствующая кривая, определяется уравнением Л = /? == 0.1.

-г

V

Ц —— 1 1 Т -а,

1 "Г"

у

— V

, 1,

зз' ■ I ■ . I ■ ■ ■ . . ■

00 01 02 СЗ 04 05 05 07 08 09 10 Ог

Рис 1. Кривые точности поиска для обучения на основе обратного распространения ошибки (сплошная линия) и мутации (пунктир), #=0.25, Т= 1.

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

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

В пятом разделе работы показаны варианты архитектурной реализации для разработанных алгоритмов МА-понска. Рассматриваются вариант с реализацией мультиагентной системы на одной вычислительной машине и вариант с многомашинной реализацией с использованием "мобильных" агентов. Одномашинная реализация мультиагентной ПС, как соответствующая современному уровню развития ¡Шетпе^технологий, рассмотрена наиболее подробно. На основе проведенного при проектировании имитационных программных моделей объектно-ориентированного анализа предметной области выделены основные блоки программной архитектуры ПС, определены функции этих блоков. Описан процесс работы мультиагентной Г1С при отработке запроса пользователя.

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

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

В приложении 1 содержится дополнительная информация по

истории развития гипертекстовой системы WWW, ее современному состоянию и архитектуре. Также рассматривается гипертекстовая модель данных и ее представление в виде ориентированного графа.

В приложении 2 представлены сведения по методам автоматической индексации и методам вычисления степени релевантности гипертекстовых документов.

В приложении 3 представлены дополнительные сведения по агентам и мультиагентным системам, приведены примеры мультиагентных систем, предназначенных для работы в различных информационных системах, в том числе в системе WWW.

В приложении 4 приведено описание программной реализации разработанных имитационных моделей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

Основные результаты диссертационной работы заключаются в следующем.

1. Разработан метод интеллектуального МА-поиска в информационных хранилищах гипертекстовой организации. Метод позволяет существенно повысить эффективность поиска в гипертекстовых информационных средах за счет ориентации поиска на наиболее перспективные области поискового информационного пространства на основе механизмов эволюционной адаптации.

2. Разработаны математические и программные модели

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

3. Разработан комплекс алгоритмов fvlA-поиска информации в гипертекстовых информационных средах. Для имитационного моделирования алгоритмов созданы их программные реализации.

4. Разработаны эволюционный и комбинированный методы и алгоритмы обучения/адаптации поисковых агентов в мультиагентной системе.

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

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

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Кононенко Р.Н., Лебедько O.A., Топчий А.П. Комбинированный эволюционный и градиентный поиск в обучении нейронных сетей //Математическое моделирование / Под ред. A.A. Самарского.— 1997. Том 9. № 2. — М.:Институт математического моделирования РАН. — С. 74-76.

2. Topchy А.P., Miagkih V.V., Kononenko R.N., Melihov A.N. Adaptive Genetic Search for Optimization of Fuzzy and Neuro-Fuzzy Systems // Proceedings of the Evolutionary Computations and Algorithms Conference (EvCA-96). — 1996. — P. 245-253.

3. Божич В.И. Кононенко Р.Н., Топчий А.П. Технологии агентов

в распределенных информационно-вычислительных сетях // Научно-техническая конференция ''Информационная безопасность автоматизированных систем", 16-17 июня 1998 г. — Воронеж, НИИСвязи: Истоки, 1998. — С.123-129.

4. Кононенко Р.Н. Модель поисковой системы на основе агентов для распределенных информационно-вычислительных сред // III Всероссийская научная конференция студентов и аспирантов. Тезисы докладов. Радиоэлектроника, микроэлектроника, системы связи и управления. 9-10 октября 1997. — Таганрог: Издательство ТРТУ, 1997. — С. 190.

5. Кононенко Р.Н., Лебедько O.A. Моделирование последовательных алгоритмов декодирования сверточных кодоз // IV Всероссийская научная конференция студентов и аспирантов. Тезисы докладов. 8-9 октября. — Таганрог: изд-во ТРТУ, 1998. — С. 340.

6. Кононенко Р. Н., Тоггчпй А.П., Абияка A.A., Божич В.И. Самоорганизующаяся коммуникация в мультиагентной системе автоматического разминирования // Анализ и моделирование адаптивных, интеллектуальных систем: Межвуз. сб. науч. трудов. — Ростов н/Д.: Издательство СКНЦ ВШ, 1998. — С. 12-18. '

7. Божич В.И., Кононенко Р.Н., Абияка A.A. Нейросетевое управление в мультиагентной системе с самоорганизующейся коммуникацией // Научная сессия МИФИ - 99. Всероссийская научно-техническая конференция "Нейроинформатика-99". Сборник научных трудов. В 3 частях. Ч.З. — М.: МИФИ,' 1999. — С. 239-246.

8. Абияка A.A., Божич В.И., Кононенко Р.Н. Самоорганизующаяся коммуникация в мультиагентной системе с нейросетевым управлением // Известия Академии Наук. Теория и системы управления. — 1999. — № 5. — С. 135-138.

9. Кононенко Р.Н., Божич В.И. Модель мультиагентной информационной поисковой системы WWW // Internet и современное общество: Тезисы Второй научно-методической конференции. Санкт-Петербург, 29 ноября - 3 декабря 1999. — Санкт-Петербург: Издательство С.-Петербургского университета, 1999. — С. 92-93.

10. Кононенко Р.Н. Божич В.И. Модель мультиагентной поисковой системы Internet на основе пенросетевых агентов // VI Всероссийская конференция "Нейрокомпьютеры и их применение" (НКП 2000), 16 -18 февраля 2000. Сборник научных трудов. — Москва, 2000,—С. 245-249.

В работах, написанных в соавторстве, личный вклад автора состоит в следующем: /1/ - проведен обзор эволюционных алгоритмов.

л

оптимизации и анализ возможностей их применения к обучению нейронных сетей; /2/ - разработана программная модель генетического обучения, нейро-нечеткой системы управления мобильным объектом, поставлены эксперименты, проведено моделирование; /3/ - проведен обзор существующих технологий на основе агентов и сделан анализ их применимости к построению информационных систем, действующих ь распределенных информационно-вычислительных средах; /5/ разработана программная реализация последовательного алгоритма Фано декодирования сверточных кодов и проведено исследование его корректирующей способности в зависимости от параметров моделируемых ошибок в канале связи; /6-8/ , - разработана мультиагентная система поиска мин на основе нейросетевых агентов, поставлены эксперименты и проанализированы результаты моделирования; /9,10/ - разработаны модели мультиагентной ПС для гипертекстовых информационных сред и графовые модели гипертекста, написана программная реализация для указанных моделей, проведен анализ результатов моделирования.

Типография Таганрогского государственного радиотехнического университета ЗАКАЗ № 189 . Тираж 130 экз.

«С»

ВВЕДЕНИЕ

1. АНАЛИЗ СУЩЕСТВУЮЩИХ СИСТЕМ ПОИСКА ИНФОРМАЦИИ В ГИПЕРТЕКСТОВЫХ ИНФОРМАЦИОННЫХ СРЕДАХ

1.1. Основные термины, общие показатели качества работы поисковых систем

1.2. Глобальная гипертекстовая информационная среда World Wide Web и ее основные свойства

1.3. Общее описание, задачи и основные требования к поисковым системам WWW

1.4. Общая характеристика классических поисковых систем WWW

1.5. Обзор существующих классических поисковых систем WWW

1.6. Обобщенная архитектура и недостатки классических поисковых систем

1.7. Проблемы построения поисковых систем WWW

1.8. Выводы

2. РАЗРАБОТКА МЕТОДА МУЛЬТИАГЕНТНОГО ПОИСКА И ОБЩЕГО АЛГОРИТМА РАБОТЫ МУЛЬТИАГЕНТНОЙ ПОИСКОВОЙ СИСТЕМЫ

2.1. Понятие агента, идеология мультиагентных систем

2.2. Применимость мультиагентного подхода для решения поставленной задачи

2.3. Базовые допущения об организации гипертекстовых сред при мультиагентном поиске информации

2.4. Метод мультиагентного поиска и общий алгоритм работы мультиагентной поисковой системы

2.5. Аналоги алгоритма мультиагентного поиска

2.6. Эволюционный и архитектурно-зависимый методы обучения агентов

2.7. Выводы

3. РАЗРАБОТКА МОДЕЛЕЙ ГИПЕРТЕКСТОВОЙ СРЕДЫ

3.1. Общие замечания

3.2. Классификация моделей гипертекста

3.3. Модель гипертекста с предустановленной степенью релевантности документов

3.4. Модель гипертекста с предустановленной степенью релевантности документов и прогнозированием релевантности гиперссылок

3.5. Модель гипертекста с имитацией распределения терминов в документах на основе функции релевантности

3.6. Модель гипертекста на основе распределения терминов в документах

3.7. Выводы

4. РАЗРАБОТКА АЛГОРИТМОВ МУЛЬТИАГЕНТНОГО ПОИСКА В ГИПЕРТЕКСТОВЫХ СРЕДАХ

4.1. Общие показатели эффективности поиска, классификация моделей поисковых систем

4.2. Особенности статистического анализа результатов моделирования

4.3. Модель мультиагентной поисковой системы на основе необучаемых агентов

4.3.1. Общие замечания, алгоритм работы поискового агента

4.3.2. Основные параметры моделирования

4.3.3. Анализ результатов имитационного моделирования

4.3.4. Выводы по модели

4.4. Модель мультиагентной поисковой системы с прогнозированием релевантности гиперссылок на основе необучаемых агентов

4.4.1. Общие замечания, алгоритм работы поискового агента

4.4.2. Основные параметры моделирования

4.4.3. Анализ результатов имитационного моделирования

4.4.4. Сравнение мультиагентного поиска с поиском на основе классических алгоритмов обхода графов

4.4.5. Выводы по модели

4.5. Модель мультиагентной поисковой системы на основе обучаемых нейросетевых агентов

4.5.1. Общие замечания

4.5.2. Описание архитектуры нейросетевого агента и алгоритма его работы

4.5.3. Алгоритмы обучения нейросетевых агентов

4.5.4. Анализ результатов имитационного моделирования

4.5.5. Выводы по модели

4.6. Модель мультиагентной поисковой системы с комбинированным алгоритмом обучения нейросетевых агентов

4.6.1. Общие замечания

4.6.2. Комбинированный метод обучения нейросетевого агента

4.6.3. Анализ результатов имитационного моделирования

4.6.4. Выводы по модели

4.7. Выводы

5. РАЗРАБОТКА АРХИТЕКТУРЫ МУЛЬТИАГЕНТНОЙ ПОИСКОВОЙ СИСТЕМЫ

5.1. Общие замечания

5.2. Архитектура мультиагентной поисковой системы для одномашинной реализации

5.3. Архитектура мультиагентной поисковой системы с использованием мобильных агентов

5.4. Выводы ЗАКЛЮЧЕНИЕ

Информация, становясь стратегическим ресурсом нового, высокотехнологичного общества, ставит перед человечеством задачу разработки принципиально новых методов своей обработки, хранения и контроля. В настоящее время не подлежит сомнению тот факт, что переход к постиндустриальному обществу 21 века неразрывно связан с развитием информационных инфраструктур, призванных эффективно решать проблемы обработки информации. В первую очередь сюда относятся компьютерные сети всех уровней и электронные хранилища данных, обеспечивающие хранение, быстрый доступ и контроль огромных массивов данных самой разнообразной природы: числовых данных, текстов, мультимедиа информации. В развитых странах практически вся актуальная служебная, технологическая и коммерческая информация уже переведена в электронную форму и хранится в бесчисленных базах данных и знаний, цифровых библиотеках различного масштаба. Из созданных к настоящему моменту хранилищ данных наиболее обширными и впечатляющими являются распределенные глобальные информационные системы (ГИС). Возникшие на базе мировой компьютерной сети Internet глобальные информационные ситемы, такие как Gopher и WWW, являют собой примеры информационных систем нового поколения. Их отличает, прежде всего, гигантский масштаб: объем хранимой в них информации огромен, содержащиеся данные включают сведения практически из всех развитых стран мира. Поистине планетарный масштаб указанных ГИС диктует некоторые принципиальные их свойства.

1. Сверхбольшой объем хранимой информации — самая популярная система Internet WWW к настоящему моменту содержит сотни миллионов единиц информации (гипертекстовых документов) /1-4/, что далеко не является пределом. Каждые 4 месяца количество информации, хранимой в этой ГИС, удваивается /1/.

2. "Спонтанный" характер возникновения — такие системы формируют свою структуру в результате действий миллионов пользователей, включающих в ГИС собственную информацию независимо друг от друга. Возникновение системы начинается, как правило, с создания небольшого ядра ограниченным количеством лиц /5,6/. Дальнейшее расширение производится независимыми пользователями, включающими в ГИС информацию по собственному усмотрению. При этом никто, в том числе и создатели ГИС, не в состоянии контролировать всю информацию, поступающую в систему. Масштабность ГИС делает невозможным полное согласование или контроль над всей хранимой в ней информации каким либо центром. Отдельные люди формируют мизерные, по сравнению со всей системой, части ГИС. Никто из них не способен 6 охватить всю систему в целом, но располагает некоторой ограниченной информацией, позволяющей локально согласовать данные с их окружением (например, директорией в Gopher или гиперссылками на ранее включенные в коллекцию документы для системы WWW). Можно сказать, что общая структура ГИС формируется как результат самоорганизации: отдельные индивидуумы-создатели ГИС создают нечто большее чем та "микроинформация", с которой они работают.

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

4. Децентрализованность и распределенность. Данное свойство вытекает из вышеописанного способа возникновения и развития ГИС, а так же из факта территориальной распределенности, в силу чего является невозможным существование единого центра, полностью контролирующего всю информацию в ГИС. Структуры ГИС во многом подобны структуре и организации сети Internet, на базе которой они существуют. Работа отдельных частей системы поддерживается заинтересованными в их существовании организациями, которые в совокупности осуществляют децентрализованное управление информационными ресурсами ГИС. Если бы существовал единый центр, через который бы проходили абсолютно все запросы, и где регистрировалась бы вся поступающая информация, на него легла бы непомерная нагрузка. Такой центр должен был бы обрабатывать количество информации, соизмеримое со всеми данными, накопленными человечеством и успевать обрабатывать количество запросов, соизмеримое с численностью населения всей планеты. Кроме того, даже если бы адекватная задаче сверхмощная вычислительная система была бы создана, любые запасы ее производительности были бы исчерпаны в считанные годы вследствие экспоненциального роста глобальной сети и общего объема хранимой в ней информации /1/. В силу сказанного, распределенная структура ГИС, позволяющая распределить растущую нагрузку на соразмерно увеличивающиеся вычислительные ресурсы базовой компьютерной сети, представляется единственно возможной.

5. Нестационарность — в ГИС постоянно происходят изменения, связанные со включением новых информационных ресурсов, изменением или исключением старых. Кроме того, изменяются такие параметры, как загруженность информационных ресурсов и каналов связи. Изменения могут быть как долговременными (например, вследствие изменения физической структуры базовой глобальной вычислительной сети), так и 7 кратковременными, например, связанными с суточным изменением активности пользователей.

Обладая вышеперечисленными свойствами, ГИС являют собой пример совершенно новой глобальной информационной среды, возникшей на базе мировой компьютерной сети и включившей в себя информационные ресурсы всей планеты. Тем не менее, несмотря на успехи созданных к настоящему моменту ГИС, в особенности, системы WWW, бесспорным является то, что это лишь первый шаг на пути создания высокоэффективных глобальных информационных сред. Существующие ГИС решили только самые насущные проблемы, возникшие при появлении глобальных компьютерных сетей: проблемы объединения сверхбольшого числа разнородных информационных ресурсов в единую систему, обеспечения к ним единообразного доступа и способов использования. Теоретически, каждый пользователь Internet может, воспользовавшись той или иной ГИС, получить доступ к любому открытому ресурсу сети. Однако, громадный объем и слабая упорядоченность информации, хранимой в ГИС, порождают новую проблему: "Как найти нужный ресурс или требуемую информацию?". Те, кто имел возможность работы с ГИС, знают, что поиск требуемых данных в поистине "мировом информационном океане" напоминает поиск иголки в стоге сена. Если неизвестен точный адрес ресурса, где располагаются данные, найти их крайне тяжело, а зачастую, просто невозможно. Таким образом, возникает своего рода парадокс: пользователь системы потенциально имеет в своем распоряжении все информационное богатство глобальной информационной среды, но использовать его эффективно он не в состоянии. Следует отметить, что некоторые ГИС изначально не были рассчитаны на столь глобальное применение, которое они получили в последствии: например, изобретенная Т.Б.Ли ГИС WWW была предназначена для повышения эффективности обмена научной информацией между относительно небольшим сообществом физиков-ядерщиков. Масштабы и тематическое содержание системы должны были быть ограниченными, нахождение требуемой информации при этих условиях не было затруднительным. Однако, весьма удачная, открытая для расширения архитектура WWW позволила ей буквально за несколько лет превратиться в основную ГИС сети Internet. В результате неконтролируемого роста как общего объема содержащейся информации, так и тематического содержания хранимых сведений, данная система перестала быть способной к эффективному использованию информации в масштабах, которых сама же достигла.

Резюмируя, можно сказать, что, решив проблему объединения и обеспечения 8 доступа к огромному числу ресурсов в рамках единой информационной среды, ГИС WWW породила новую проблему — проблему эффективного использования созданного информационного богатства. В настоящий момент актуальность данной проблемы очевидна. В развитых странах, где оперативное получение и слежение за информацией в Internet для многих уже стало жизненной необходимостью, появились фирмы, специализирующиеся на поставке из Internet необходимой информации. Кроме того, уже созданы и работают автоматические поисковые системы первого поколения, такие как Altavista, Rambler, Excite, Yahoo! и другие /1/. Однако, как будет показано в работе, архитектура этих систем основана на классическом подходе, разработанном для относительно простых, локализованных информационных хранилищ данных, и не способна полностью решить возникшую проблему /2,7,8/. Слишком большой объем поисковых данных и достаточно примитивный, неадаптивный поиск по ключевым словам, производимый подобными системами, зачастую не эффективен: в ответ на введенный запрос пользователю предлагаются сотни тысяч найденных документов, лишь малая часть которых оказывается действительно релевантной (соответствующей) запросу пользователя. Таким образом, проблема эффективного нахождения информации в глобальных информационных средах по прежнему остается открытой. В связи с этим, в зарубежных научных кругах проводятся исследования и разработки систем нового поколения, призванных вести эффективный поиск и контроль за изменением в Internet полезной информации. В ход пущены едва ли не все достижения искусственного интеллекта (ИИ): нечеткие экспертные системы, нейронные сети, системы автоматического планирования, генетические алгоритмы и.т.д. Технологический багаж ИИ, с той или иной степенью успешности разрабатываемый для робототехнических систем, работающих в реальном мире, по мнению ряда ученых /9,10/, идеально подходит для построения действительно интеллектуальных программ нового поколения, действующих в глобальных информационных средах. Одним из перспективных направлений ИИ, ориентированным на построение сложных систем обработки информации, являются мультиагентные системы. К их особенностям относится децентрализованная обработка информации на основе относительно независимых информационных компонент — агентов, решающих общую задачу коллективным образом. Как будет показано в работе, основные свойства мультиагентых систем отвечают свойсвам и требованиям глобальных информационных сред, что открывает возможность построения систем, в частности поисковых, способных эффективно работать в указанных средах. 9

Настоящая диссертационная работа посвящена проблеме построения эффективных систем поиска информации в глобальных информационных средах на основе мультиагентного подхода как одного из прогрессивных направлений ИИ.

Целью настоящей диссертационной работы является разработка методов и алгоритмов интеллектуального поиска релевантной информации в сложных информационных средах гипертекстовой организации (основная ориентация сделана на ГИС WWW как наиболее развитую информационную среду Internet).

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

- разработка метода интеллектуального поиска в информационных хранилищах гипертекстовой организации на основе одного из современных направлений искусственного интеллекта — мультиагентных систем;

- разработка комплекса математических и имитационных программных моделей гипертекстовой среды, алгоритмов мультиагентного поиска в гипертекстовой информационной среде;

- проведение имитационного программного моделирования, анализ полученных результатов, исследование эффективности построенных алгоритмов мультиагентного поиска релевантной информации;

- разработка общей архитектуры поискового агента и мультиагентной поисковой системы для гипертекстовой информационной среды.

Предметом исследования являются:

- мультиагентные системы на основе бионического направления ИИ;

- эволюционные алгоритмы оптимизации и адаптации интеллектуальных агентов;

- эффективность применения нейронных сетей прямого распространения в качестве интеллектуального ядра поисковых агентов.

Методы исследования.В качестве основных методов исследования использованы математические модели и имитационное компьютерное моделирование.

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

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

В процессе исследований и теоретических обобщений получены следующие новые научные результаты:

- разработан метод интеллектуального мультиагентного поиска в информационных хранилищах гипертекстовой организации;

- разработаны математические модели гипертекстовой информационной среды различного уровня детализации;

- разработан комплекс алгоритмов мультиагентного поиска информации в гипертекстовых информационных средах;

- разработаны эволюционный и комбинированный методы и алгоритмы обучения/адаптации поисковых агентов, работающие непосредственно в процессе поиска информации;

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

- разработаны варианты архитектур агентов и поисковой системы для гипертекстовых информационных сред на основе парадигмы бионической мультиагентной системы;

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

Положения, выносимые на защиту:

- метод интеллектуального мультиагентного поиска в информационных хранилищах гипертекстовой организации;

- комплекс алгоритмов мультиагентного поиска информации в гипертекстовых информационных средах;

- архитектура поискового агента на основе нейронной сети прямого распространения;

- комбинированный алгоритм обучения нейросетевых поисковых агентов;

- варианты архитектуры интеллектуальной поисковой системы для гипертекстовых информационных сред на основе парадигмы бионической

11 мультиагентной системы.

Практической ценностью диссертационной работы являются:

- разработанный метод интеллектуального поиска релевантной информации в гипертекстовой информационной среде, позволяющий существенно сократить объем просматриваемой при поиске информации за счет ориентации поиска в перспективных направлениях;

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

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на Всероссийской школе-семинаре "Современные проблемы математического моделирования" (Абрау-Дюрсо, 1995); Всероссийской научно-технической конференции "Нейроинформатика-99" (Москва, 1999); Второй научно-методической конференции "Internet и современное общество" (Санкт-Петербург, 1999); VI Всероссийской конференции "Нейрокомпьютеры и их применение" (Москва, 2000).

Публикации. Результаты, полученные в работе, нашли отражение в 10 печатных работах, одна из которых была опубликована за рубежом, две — в центральной печати. Семь работ были опубликованы в сборниках научных трудов конференций, в том числе одна работа была представлена на международной конференции, пять — на всероссийских конференциях.

Структура работы. Диссертационная работа состоит из введения, пяти разделов и заключения, изложенных на 202 страницах, содержит 61 рисунок, 105 наименований библиографии и 129 страниц приложения, всего 339 страниц.

Основные результаты диссертационной работы заключаются в следующем.

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

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

3. Разработан комплекс алгоритмов мультиагентного поиска информации в гипертекстовых информационных средах. Для имитационного моделирования алгоритмов созданы их программные реализации.

4. Разработаны эволюционный и комбинированный методы и алгоритмы обучения/адаптации поисковых агентов в мультиагентной системе.

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

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

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

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

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

203

ЗАКЛЮЧЕНИЕ

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

1. Gudivada V.N., Raghavan V.V. Information Retrieval on the World Wide Web //IEEE Internet Computing. — 1997. V.l. N. 5. P. 58-68.

2. Кононенко P.H. Божич В.И. Модель мультиагентной поисковой системы internet на основе нейросетевых агентов // VI Всероссийская конференция "Нейрокомпьютеры и их применение" (НКП 2000), 16 18 февраля 2000. Сборник научных трудов. — Москва, 2000.

3. Крол Эд: Все об Internet / Пер. с англ. — К.: Торгово-издательское бюро BHV,1995,— 592 е.: ил. — ISBN-5-87419-001-5.

4. Храмцов Б.П. Лабиринт Internet: Практическое руководство — М.: Электроинформ,1996. —256 с.

5. Шумский С.А., Яровой A.B., Зорин О.Л. Ассоциативный поиск текстовой информации // Научная сессия МИФИ 99. Всероссийская научно-техническая конференция "Нейроинформатика-99". Сборник научных трудов. В 3 частях. Ч.З. — М.: МИФИ, 1999. — С. 101-110.

6. O'Leary D.E. The Internet, Intranets, and the AI Renaissance // Computer. — 1997. V.30. N. 1. P. 71-78.

7. Hendler J.A, Guest Editors Introduction:Intelligent Agents:Where AI Meets Information Technology // IEEE Expert Intelligent Systems and Their Applications. :— 1996. V.U.2041. N. 6. P. 20-24.

8. Дейт К. Дж. Введение в системы баз данных / Пер. с англ.— 6-е изд.—К.: Диалектика, 1998. — 784 е.: ил.

9. Stone P. Veloso М. Multiagent Systems: A Survey from the Machine Learning Perspective // Under review for journal publication. — Pittsburgh (PA): Carnegie Mellon University. Computer Science Department, 1997. — 40 p.

10. Де Во Дебора. Распределенные агенты SRI обеспечивают гибкость // Международный компьютерный еженедельник Computerworld (Россия). — 1997. V.69. N. 4. Р. 43.

11. Kotz D., Gray R., Nog S., Rus D., Chawla S., Gubenko G. Agent TCL:Targeting the Needs of Mobile Computers // IEEE Internet Computing.— 1997. V.l, N. 4. P. 58-67.

12. Симкин С. Бартлет H., Алекс JI. Программирование на Java. Путеводитель / Пер. с англ. — К.: НИПФ "ДиаСофт Лтд.", 1996. — 736 с.

13. Watson М. Intelligent Java Applications for the Internet and Intranets — San Francisco (CA): Morgan Kaufman, 1997.

14. Lesser V. R. Multiagent Systems: An Emerging Subdiscipline of AI // ACM Computing Surveys. — 1995. V.27. September. P. 340-342

15. Трахтенгерц Э.А. Взаимодействие агентов в многоагентных средах // Автоматика и телемеханика. — 1998. N. 8. — М.: Наука, 1998. — С.3-52.

16. Городецкий В.И. Многоагентные системы: современное состояние исследований и перспективы // Новости искусственного интеллекта.— 1996. N.1.C.1-8.

17. Larson R Bibliometrics of the World Wide Web: An Exploratory Analysis of the Intellectual Structure of Cyberspace // Proceedings 1996 Annual ASIS Meeting, 1996.

18. Ray T. S. Artificial Life II // Proc. of the Santa Fe Institute Studies in the Sciences of Complexity V. X., / C.Langton et al. eds.: Addison-Wesley, 1992,— 331 p.

19. Menczer F., Belew R.K. Latent Energy Environments // Adapting Individuals in Evolving Populations: Models and Algorithms / ed. by R.K. Belew, M. Mitchell. — Reading (MA): Addison Wesley, 1996. — (SFI Studies in the Sciences of Complexity; V. ХХ1П).

20. Menczer F., Belew R.K. Latent Energy Environments: A Tool for Artificial Life Simulations : Technical Report. — CS93-301. —- San Diego (CA): University of California, 1993. — 13 p.

21. Brown C.T. An Introduction to Avida, an Auto-Adaptive Genetic System : SURF105technical report. — Caltech, 1993.

22. Back T. et al. A Survey of Evolution Strategies // Proc. Int. Conf. Genetic Algorithms, San Diego: Morgan Kaufmann Publishers, 1991. — P. 2-9.

23. Back Т., Fogel D.B. and Michalewuz Z. Handbook of Evolutionary Computation — New York: Oxford University Press, 1997.

24. Fogel D. B. An Introduction to Simulated Evolutionary Optimization // IEEE Transactions on Neural Networks. — 1994. V. 5. N. 1.

25. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductionary Analysis With Application to Biology, Control and Artificial Intelligence. University of Michigan, 1975, —211 p.

26. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. —1. Addison Wesley, 1989.

27. Топчий А.П. Применение моделирования генетической эволюции для обучения искусственных нейронных сетей. // Математическое моделирование / Под.ред. А.А.Самарского. — 1997. Том 9. N.2. — М.:Институт математического моделирования РАН. — С. 85-87.

28. Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. — Cambridge (Mass.): MIT Press, 1992.

29. Starkweather Т., Whitley D., Mathias K. Optimization using Distributed Genetic Algorithms // Parallel Problem Solving from Nature / H.-P Schwefel., R. Manner — Berlin: Springer-Verlag Berlin, 1990. — P. 176-185.

30. Muhlenbein H., Schomisch M. Born J. The Parallel Genetic Algorithm as Function Optimizer// Parallel Computing. — 1991. V. 17. P. 498-516.

31. Soft Computing: Fuzzy Logic Neural Networks, and Distributed Artificial Intelligence / Eds. F. Aminzadeh, M. Jamshildi. — Englewood Cliffs: PTR Prentice Hall,1994 — 3011. P

32. Заде Л. Понятие лингвистической переменной и ее применения к принятию приближенных решений / Пер. с англ.; Под ред. Н.Н. Моисеева, С.А. Орловского1. М.:Мир, 1976. —166 с.206

33. Frakes W.B., Baeza-Yates R. Information Retrieval: Data Structures and Algorithms. — EngleWood Cliffs, N.J.: Prentice Hall, 1992.

34. Raghavan V., Wong S.K.M. A Critical Analysis of Vector Space Model for Information Retrieval // J. Am. Soc. Information Science. — 1986. V. 37. N.5. P. 279-287.

35. Harman D. Relevance Feedback Revisited // Proc. 15-th Ann. Int'l ACM SIGIR Conf. — New York: ACM Press, 1992. — P. 1-10.

36. Gloub G., Van Loan C. Matrix Computations. — 2d ed. — Baltimore, Maryland: Jouhn Hopkings, 1989.

37. Deerwester S., Dumais S., Furnas G., Landauer Т., Harsman R. Indexing by Latent Semantic Analysis // Journal of the American Society for Information Science. — 1990. V. 41. N. 6. P.391- 407.

38. Dumais S. Improving the Retrieval of Information from External Sources // Behavior Research Methods, Instruments and Computers. — 1991. V. 23. N. 2. P. 229-236.

39. Тюрин Ю.Н., Макаров А.А. Статистический анализ данных на компьютере / Под ред. В.Э. Фигурнова. — М.:ИНФРА-М, 1998.— 528 е.: ил.

40. Вентцель Е.С. Теория вероятностей. — М.: Наука, 1964. — 576 е.: ил.

41. Курейчик В.М. Методы генетического поиска: Учебное пособие, часть 1. — Таганрог: ТРТУ, 1988. — 118 с.

42. Joze L. Filho R., Treleaven P. Genetic-Algorithm Programming Environments // Proceedings of IEEE. — 1994. N. 1.

43. Unemi Т., Nagayoshi M. Evolution of Learning Robot Team via Local Mathing Strategy // In Proc. of Fourth European Conference on Artificial Life, Poster Session. — Brighton, UK, 1997.

44. Абияка А.А., Божич В.И., Кононенко Р.Н. Самоорганизующаяся коммуникация в мультиагентной системе с нейросетевым управлением // Известия Академии Наук.201

45. Теория и системы управления. — 1999. — N. 5. — С.135-138.

46. McLurkin J. Using Cooperative Robots for Explosive Ordnance Disposal / MIT Artificial Intelligence laboratory.— Cambridge (MA), 1997.

47. Касами Т., Такура H., Иварди Е. Теория кодирования. — М.:Мир, 1978.

48. Кононенко Р.Н., Лебедько О.А. Моделирование последовательных алгоритмов декодирования сверточных кодов // IV Всероссийская научная конференция студентов и аспирантов. Тезисы докладов. 8-9 октября. — Таганрог: изд-во ТРТУ, 1998. —С. 340.

49. Нильсон Н. Принципы искусственного интеллекта / Пер.с анг.— М.:Радио и связь,1985. — 376 е.: ил.

50. Лорьер Ж.-Л.Системы искусственного интеллекта / Пер. с франц. — М.:Мир, 1991.—568 с.: ил.

51. Чернухин Ю.В. Искусственный интеллект и нейрокомпьютеры. — Таганрог: изд-во ТРТУ, 1997. — 273 с.

52. Ежов А.А. Шумский С.А. Нейрокомпьютинг и его применение в экономике и бизнесе,— М.: МИФИ, 1998. — 224с.

53. Zadeh L.A. Fuzzy Sets // Information and Control. — 1965. V. 8. P. 338-353.

54. К.Асаи, Д.Ватада, С.Иваи и др. Прикладные нечеткие системы / Пер. с япон.; Под. Ред. Т. Тэрано, К.Асаи, М.Сугэно. — М.:Мир, 1993.—368 е.: ил.

55. Minsky М., Papert S. Perceptrons. — Cambridge (MA): MIT Press, 1969.

56. Вассерман Ф. Нейрокомпьютерная техника. — M.: Мир, 1992.

57. А.Н.Горбань. Обучение нейронных сетей. — М.: СП Параграф, 1990.

58. Topchy А.Р., Miagkih V.V., Kononenko R.N., Melihov A.N. Adaptive Genetic Search for Optimization of Fuzzy and Neuro-Fuzzy Systems // Proceedings of the Evolutionary Computations and Algorithms Conference (EvCA-96). — 1996. — P. 245-253.208

59. Jang J.-S., Sun C.-T. Neuro-Fuzzy Modeling and Control // In Proc. of the IEEE. — 1995. V. 83. N. 3. P. 378-406.

60. Mamdani E.H., Assilian S. An Experiment in Linguistic Synthesis With a Fuzzy Logic Controller // Int. J. Man-Machine Studies. — 1975. V. 7. N. 1. P. 11-13.

61. Varsek A., Urbancic Т., Filipic B. Genetic Algorithms in Controller Design and Tuning // IEEE Trans, on SMC. — 1993. V. 23. N. 5.

62. Thrif P., Fuzzy Logic Synthesis with Genetic Algorithms // In Proc. of the 4-th Int. Conf. on Genetic Algorithms. — San Diego. USA., 1991.

63. Karr C.L., Stanley D.A. Fuzzy Logic and Genetic Algorithms in Time-Varying Control Problems // In Proc. of the NAPFIS-91. — 1991. — P. 285-290.

64. IEEE Internet Computing.— 1998. V.2.N.I.

65. Kiniry J., Zimmelman D. Special Feature: A Hands-On Look at Java Mobil Agents // IEEE Internet Computing. — 1997, V. 1. N. 4. P. 21-33.

66. Гульев И. Создаем вирус и антивирус / Гульев И. — М.: ДМК, 1999. — 304 с.:ил.

67. Армстронг Т. Active X: создание Web приложений / Пер.с англ.—К.: Издательская группа BHV, 1998. — 592 с.

68. Salton G. Automatic Text Processing. — Reading (MA): Addison-Wesley, 1989.

69. Jung.G.S., Raghavan Y.V. Connectionist Learning in Constructing Thesaurus-like Knowledge Structure // Working Notes of AAAI Symp. on Text-Based Intelligence Systems, March 1990. — Palo Alto (CA),1990.— P. 123 127.

70. Мелихов A.H., Берштейн JI.C. Конечные четкие и расплывчатые множества. 42. Учебное пособие. — Таганрог: ТРТИ, 1981.

71. Shannon С.Е. Prediction and Entropy in Printed English // Bell Systems J. — 1951. V. 30. N. l.P. 50-65.

72. Robertson S.E. Spark-Jones K. Relevance Weighting of Search Terms // J. Am. Soc. of Information Sciences. — 1976. — P.129 146.

73. Хант Э. Искусственный интеллект / Пер. с англ. — М.: Мир, 1978. — 558 с.

74. Виннер Н. Кибернетика, или управление и связь в животном и машине. — 2-е. изд.1. М.: Наука, 1983. — 338 с.

75. Реальность и прогнозы искусственного интеллекта / Пер. с англ. — М.:Мир, 1987.247 с.

76. McCalloh W.S., Pitts W. A Logical Calculus of the Ideas Immanent in Nervous Activity // Bulletin of Math. Bio. — 1943. V.5. P. 115-133.20?

77. Bishop C.M. Neural Networks and Pattern Recognition. — Oxford Press, 1988.

78. Hunt K.J., Sbarbao D., Zbikovski R., Gawthrop P.J. Neural Networks for Control Systems: A Survey // Automatica. — 1992. V.28. P. 1083 1112.

79. Ожегов С.И. Словарь русского языка — изд. 9-е, исправ. и допол. /Под ред. Шведовой. — М.: "Советская энциклопедия", 1972.

80. Petrie С. Agent-Based Engineering, the Web and Intelligence // IEEE Expert Intelligent Systems and Their Applications. — 1996. V.l 1. N. 6. P. 24-30.

81. Maes P. Agents That Reduce Work and Information Overload // Comm. ACM. — 1994. V.37. N. 7.

82. Maes P. Modeling Adaptive Autonomous Agents // Artificial Life J. / ed. by N.Langton. — 1994. V.l, N. 1,2. —New York : MIT Press, 1994. — P. 135-162.

83. Minsky M. The Society of Mind. — New York: Simon and Schuster, 1986.

84. Interview with Pattie Maes:Humanizng the Global Computer // IEEE Internet Computing. —1997. V. 1. N.4.P.10-20.

85. Sen S., Secaran M., Hale J. Learning to Coordinate Without Sharing Information // Proc. of National Conference on Artificial Intelligence. —1994. — P. 426 431.

86. Bond A. H., Gasser L. Readings in Distributed Artificial Intelligence. — San Mateo (CA): Morgan Kaufmann, 1988.

87. Genesereth M., Fikes R. et. al. Knowledge Interchange Format, Version 3.0 reference manual : Technical report / Stanford University. Computer Science Department. — Stanford, 1992.

88. Labrou Y. and Finin Т., A Semantics Approach For KQML — A General Purpose Communication Language for Software Agents // In Proc. of 3d Int. Conf. on Information and Knowledge Management, Nov. 1994. — 1994.

89. Crites R:H. Large Scale Dynamic Optimization Using Teams of Reinforcement Learning Agents: PhD Thesis. — University of Amherst. Comp. Sc. Department, 1996. — 104 p.

90. Поспелов Д.А. Вероятностные автоматы. — M.: Энергия, 1970. — 88с. :ил.

91. Etzioni О. Moving up the Information Food Chain:Deploing Softbots on the World Wide Web //AI Magazine. — 1997. V. 18. N. 2. P. 11-18.

92. Seiberg E., Etzioni O. The METACRAWLER Architecture for Resource Aggregation on the Web // IEEE Expert. — 1997. V. 1. N. 12. P. 8 14.

93. Etzioni O., Henks O., Weld D., Draper D., Lesh N., Williamson M. An Approach to Planning with Incomplete Information // In Proceedings of The Third International210

94. Conference on Principles of Knowledge Representation and Reasoning. — San Francisco (CA): Morgan Kaufmann, 1992. — P.l 15 -125.

95. Shakes J., Langheinrich M., Etzioni O. AHOY! The Home Page Finder // In Proceedings of the Sixth International World Wide Web Conference,?-11 April. — Santa Clara (CA), 1997.

96. Doorenbos R., Etzioni O., Weld D. A Scaleable Comparison-Shopping Agent for the World Wide Web // In Proceedings of Autonomous Agents. —New York: Association of Computing Machinery, 1997.— P.39 -48.

97. Hove A.E., Dreilinger D., A Description of Metasearch Engine That Learns Which Engine to Query // AI Magazine. — 1997. V. 18. N. 2. P. 11 -18.

98. Hedberg S. Agents for Sale: First Wave of Intelligent Agents go commercial // IEEE Expert Intelligent Systems and Their Applications. — 1996. V. 11. N. 6. P. 16 19.

99. Shardan U., Maes P. Social Information Filtering: Algorithms for Automating 'Word of Mouth' // Proc. CHI-95 Conf. — New York: ACM Press, May 1995.211