Agent model of information retrieval on the basis of beehive metaphor

A new approach to information retrieval that is based on a beehive metaphor is presented. A beehive model simulates several kinds of beehive typical behavior. It is a simple model that describes processes taking place in Web-search. The approach gives possibility of distributed PageRank calculation...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
1. Verfasser:	Remarovich, S.S.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 681.3
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/799
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-799
record_format	ojs
resource_txt_mv	ppisoftskievua/ed/6fa20ea87709da4ffda43103378530ed.pdf
spelling	pp_isofts_kiev_ua-article-7992025-09-02T15:47:58Z Agent model of information retrieval on the basis of beehive metaphor Агентна модель пошуку інформації на основі метафори бджолиного вулика Remarovich, S.S. UDC 681.3 УДК 681.3 A new approach to information retrieval that is based on a beehive metaphor is presented. A beehive model simulates several kinds of beehive typical behavior. It is a simple model that describes processes taking place in Web-search. The approach gives possibility of distributed PageRank calculation of Web pages.Prombles in programming 2011; 1: 70-77 Представлено новий підхід до пошуку інформації, який заснований на метафорі бджолиного вулика. Запропонована модель бджолиного вулика в тому значенні, що вона імітує окремі види типової поведінки бджіл. Це є проста модель, яка описує процеси, що мають місце у Веб-пошуку. Підхід надає можливість розподіленого обчислення PageRank Веб-сторінок.Prombles in programming 2011; 1: 70-77 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-28 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/799 PROBLEMS IN PROGRAMMING; No 1 (2011); 70-77 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2011); 70-77 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2011); 70-77 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/799/851 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-09-02T15:47:58Z
collection	OJS
language	Ukrainian
topic	UDC 681.3
spellingShingle	UDC 681.3 Remarovich, S.S. Agent model of information retrieval on the basis of beehive metaphor
topic_facet	UDC 681.3 УДК 681.3
format	Article
author	Remarovich, S.S.
author_facet	Remarovich, S.S.
author_sort	Remarovich, S.S.
title	Agent model of information retrieval on the basis of beehive metaphor
title_short	Agent model of information retrieval on the basis of beehive metaphor
title_full	Agent model of information retrieval on the basis of beehive metaphor
title_fullStr	Agent model of information retrieval on the basis of beehive metaphor
title_full_unstemmed	Agent model of information retrieval on the basis of beehive metaphor
title_sort	agent model of information retrieval on the basis of beehive metaphor
title_alt	Агентна модель пошуку інформації на основі метафори бджолиного вулика
description	A new approach to information retrieval that is based on a beehive metaphor is presented. A beehive model simulates several kinds of beehive typical behavior. It is a simple model that describes processes taking place in Web-search. The approach gives possibility of distributed PageRank calculation of Web pages.Prombles in programming 2011; 1: 70-77
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/799
work_keys_str_mv	AT remarovichss agentmodelofinformationretrievalonthebasisofbeehivemetaphor AT remarovichss agentnamodelʹpošukuínformacíínaosnovímetaforibdžolinogovulika
first_indexed	2025-09-17T09:23:12Z
last_indexed	2025-09-17T09:23:12Z
_version_	1843502506813947904
fulltext	Експертні та інтелектуальні інформаційні системи 70 УДК 681.3 С. Ремарович АГЕНТНА МОДЕЛЬ ПОШУКУ ІНФОРМАЦІЇ НА ОСНОВІ МЕТАФОРИ БДЖОЛИНОГО ВУЛИКА Представлено новий підхід до пошуку інформації, який заснований на метафорі бджолиного вулика. Запропонована модель бджолиного вулика в тому значенні, що вона імітує окремі види типової поведінки бджіл. Це є проста модель, яка описує процеси, що мають місце у Веб-пошуку. Підхід надає можливість розподіленого обчислення PageRank Веб-сторінок. Вступ Світова мережа містить великі обся- ги інформації, які використовуються різни- ми застосуваннями. Інформація представ- ляється багатьма джерелами Інтернет. Роль пошуку є важливим процесом у питанні отримання інформації з урахуван- ням великої кількості різнорідних джерел та значних обсягів [1, 2]. Різні підходи, що розкривають проблеми пошуку, представ- лені в [3–9]. Пропонується дослідити можливо- сті, які відкриває розгляд поведінки суспі- льних комах. Суспільні комахи (мурашки, медоносні бджоли, терміти, оси і т.п.) показують чудовий рівень суспільної пове- дінки. Зокрема, вони спілкуються, хоча в дуже елементарний спосіб, один з одним. Наприклад, вони можуть спілкуватися щодо розташування джерел їжі. Вони на- віть співробітничають у напрямку досяг- нення деякої мети. Зокрема, вони можуть співробітничати щодо принесеної їжі. Комахи відрізняються за своїм організа- ційним рівнем без будь-якого централізо- ваного контролю [10]. Взаємодія комах та їх поведінка організовані за певними пра- вилами. Гіпотеза полягає у тому, що пове- дінка суспільних комах сприяє розробці агентної моделі Веб-пошуку джерел інфор- мації. 1. Метафора бджолиного вулика Поведінка медоносних бджіл була широко вивчена вченими природничих наук. Одна з цілей їх дослідження полягала у відтворенні моделі поведінки бджіл, особливо їх колективного вибору джерела нектару. В роботі [11] розроблена математична модель поведінки бджоли- ного вулика і подальше удосконалення моделі пізніше представлено в [12]. Медоносні бджоли – це суспільні комахи, які живуть у колоніях. Бджоли збирають їжу (нектар) з джерел, розта- шованих на відстані до 10 км від вулика. Колонія використовує прості правила, щоб відіслати бджіл у напрямку до кращого доступного джерела нектару. В цьому процесі фуражирування, бджоли поверта- ються з нектаром і інформацією про джерело. Так як джерела не постійні, з'являються нові, існуючі джерела стають виснаженими, то інформація про джерела є актуальною. Колонія пристосовується до постійно змінної ситуації. Щоб підтриму- вати достатнє надходження їжі, необхідне розвідування сусідньої місцевості щодо нових джерел і експлуатації існуючих. Іншими словами, є бджоли, які виконують місію фуражирування, і є розвідники джерел. Бджоли фуражирування посилають інформацію про розташування джерел їжі, які вони відвідали, інші бджоли здатні отримувати цю інформацію. Ці дії можна розглядати як переговори бджіл. Важливу роль у процесі комунікації грає танець похитування. У роботі [13] досліджені механізм переговорів і інформація, якою спілкуються бджоли. Існує гіпотеза, що дистанція і напрямок, в якому знаходяться джерела їжі, кодуються в танці похитуван- ня, хоча вони не є єдиними видами інфор- мації, якими керуються бджоли. Ми при- пускаємо, що танець похитування являє собою засіб повідомлення про джерело їжі. Танцівник знає не тільки дистанцію і © С. Ремарович, 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 1 Експертні та інтелектуальні інформаційні системи 71 напрям джерела їжі, але й якість джерела їжі, оскільки тривалість танцю залежить від якості джерела. Теоретична модель бджолиного вулика вперше була запропонована в роботі [11]. Модель містить множину джерел інформації – S. Бджоли танцюють, рекламуючи джерело si, або продовжують фуражирування з джерела si, або спосте- рігають танцівників, що сприяють рекла- муванню джерел s1, s2, ..., або слідують до нового джерела з множини джерел s1, s2, ... після переговорів. Кожен вибір джерел характеризується за допомогою вірогідно- стей. У роботі [14] проведено експери- мент, спрямований на дослідження того, як бджоли вибирають джерела нектару. В оточенні колонії були розміщені два джерела нектару, один з них 400 миль на північ, інший 400 миль на південь. 12 бджіл тренувалося літати до північного джерела, інші 15 бджіл до південного джерела. Джерела були різної якості. Південне було краще (концентрація цукру 2.5 одиниць) ніж північне (1.0 одиниці). Опівдні, джерела були переставлені. На- ступного ранку джерела були переставлені знову й опівдні ще раз. Емпіричне спостереження показало, що число бджіл, що фуражирують кращі джерела, зростає з часом, тоді як число бджіл, що фура- жирують гірші джерела, зменшилось. Експерименти з імітаційною моделлю дали ступінь схожості з емпіричними спосте- реженнями. Пізніше в [12] представлена інша імітаційна модель, яка дала експеримен- тальні результати, подібні оригінальному емпіричному досвіду [14]. Був сформу- льований набір правил, вдосконалено поняття бджоли фуражира. Відповідно до моделі потенційна бджола фуражира спочатку “незайнята”. Вона не знає про зовнішні джерела нектару. Незабаром, вона літатиме до джерел нектару. Політ може здійснюва- тись у ролі розвідника, тобто немає інфор- мації про місце призначення. Бджола може відвідати танцпол, спостерігати виконавців танцю і ставати новобранцем, отримати інформацію про джерело фуражирування, запам'ятавши позиційну інформацію. Ця модель була успішною у деяких видах поведінки колективного фуражирування. 2. Агентна модель пошуку інформації Модель бджолиного вулика можли- во розглядати з точки зору вирішення проблеми пошуку [15–17]. Одне з най- раніших згадувань у цьому напрямку належить до 1986 р., коли в [18] запропо- нували в короткій формі модель бджоли- ного вулика для різнорідних знань в експертній системі. В роботах [19, 20] вив- чені методи мульти-агентного моделюван- ня, використовуючи моделі бджолиного вулика. Як базис для моделювання та іміта- ції поведінки бджоли використовується SeSAm (Shell for Simulated Agent Systems) [21] – поліпшена версія системи AL-OSIS, яка була спеціально розроблена для того, щоб моделювати поведінку мурашок [22]. Ця оболонка моделювання забезпечує універсальне середовище для моделюван- ня й експериментування з системами, які засновані на агенті, з метою підтримати конструювання складних моделей. Систе- ма забезпечує графічний інтерфейс, має інструментальні засоби для збору й аналізу даних протоколу і т. д. У SeSAm моделю- вання середовища засновано на двови- мірних картах. Третя розмірність може бути представлена як комбінація декількох двовимірних карт. Об'єкти системи можуть бути ресурсами або агентами. Агенти виконують дії, тоді як ресурси не впливають на світ. Щоб збагатити середовище, визначають події як зміни в середовищі без певного джерела. Під час експерименту моделювання ці події можуть трапитися у певний інтервал часу, з певною вірогідністю або в певній ситуації. Агент визначається за допомогою чотирьох фіксованих категорій: - сенсорних здібностей; - внутрішніх параметрів; - процедури вибору дії, включаючи всі внутрішні уявлення, які використову- ються для цього; Експертні та інтелектуальні інформаційні системи 72 - дій, які змінюють внутрішній і зовнішній світ. Система SeSAm забезпечує задані за умовчанням рішення для кожної з цих категорій. Стандартні примітиви сенсор- них і виконавчих здібностей можуть бути адаптовані за допомогою графічних редак- торів, залежно від предметної області. У кожного агента є поточна діяльність, яка визначає дії, які він виконує самостійно в середовищі в кожний момент часу. Ця діяльність може бути вибрана двома способами: або тому, що міститься в плані, якому слідує агент, або тому, що вона вибрана як реакція, застосовуючи правило з більш високим пріоритетом. Завершення поточної діяльності може управлятися певними цільовими ситуаціями або простими простоями. У будь-який час рефлексні правила, які визначають аварій- ні ситуації, можуть перервати нормальне виконання. Щоб підтримати моделювання, введені ролі поведінки; щоб структурувати сукупність видів діяльності, визначені скелетні плани і аварійні правила. Ці ролі відповідають стереотипам. На відміну від класу агента, який, наприклад, представляє змодельований різновид, агенти можуть перемикати свою роль. У роботі [23] фуражирування бджіл використано для того, щоб удосконалити спільний процес фільтрації інформації. Один з останніх проектів [17] використовує метафору бджолиного вули- ка в системі «case-based recommender». Ідея полягає у тому, щоб використати танець бджоли для отримання найбільш подібного випадку. Випадок відповідає джерела нектару. База випадків являє собою набір джерел нектару. Запит корис- тувача порівнюється зі всіма випадками у базі випадків. Найподібніший випадок повертається користувачу. Бджоли вирі- шують покидати або продовжувати відві- дувати джерело залежно від того, наскільки запит є подібним до відвіданого випадку. Вірогідність покидання джерела зменшується зі збільшенням схожості між запитом і джерелом. Бджоли починають фуражирування випадково і через деякий час з'являється джерело з найвищим чис- лом бджіл. Розглянемо можливості процесу пошуку та отримання інформації у зазна- чений спосіб. Є дві цілі щодо нашої моделі: перша полягає у тому, що вона має моделювати поведінку біологічного вули- ка, а друга – має моделювати пошук інфор- мації. Для досягнення першої цілі буде достатньо, якщо модель покаже ступінь схожості з поведінкою фуражирування. Початкові дослідження моделі проведені в [11] та [17]. Наша модель вулика включає наступні об’єкти, умовна назва яких відповідає метафорі: «танцпол», «ауди- торію» і «кімнату відправки» (диспет- черську). Призначення та функціонування об’єктів розглянемо далі. «Диспетчерська кімната» забезпе- чує додаткову гнучкість моделі. Це є відображенням гіпотези, що деякі бджоли в аудиторії можуть бути не готові сліду- вати до будь-якого джерела. Вони або не стають захопленими танцівником у межах деякого часу, або може не бути танців- ників. Таким чином, вони вирішують виконувати фуражирування без поперед- ньої розвідки. Це краще, ніж залишитися в аудиторії у небезпеці голодування. У поча- тковому стані бджоли вилітають з диспет- черської кімнати, коли прибуває новий запит. Модель є гнучкою завдяки певній кількості параметризованих атрибутів. Параметрами моделі є наступні: - повне число агентів N (BIOR + + BISB) в початковому стані, яке склада- ється з бджіл, що знаходяться в кімнаті спостереження (BIOR), і тих, які почали фуражирування (BISB); - початкове розподілення бджіл між спостерігачами (BIOR) і фуражирами (BISB); - максимальний час, що приділя- ється для танцю відповідного джерела (максимальний час танцю MDT); - максимальний час, який бджола може провести в стані спостереження. Слід зазначити, що час танцю залежить від якості джерела, він визначається як MDT*quality. Час спостереження є або максимальним, або меншим, якщо деякий танцівник привернув увагу бджоли. Експертні та інтелектуальні інформаційні системи 73 Процес пошуку найкращого джере- ла починається у момент, коли бджоли BISB вилітають з «диспетчерської кім- нати» до випадково вибраного джерела. Кожна бджола, відвідавши джерело, оцінює його якість. Повернувшись до вулика, бджола вирішує, чи покидає вона джерело, яке відвідала. У моделі визначається вірогід- ність PP si X (Psi P X = 1 – Qi, де Qi – якість джерела) того, що бджола покидає джере- ло si. Відповідно, вірогідність того, що бджола не покидає джерела si дорівнює очевидно 1 – PP si X. Якщо бджола вирішує покинути джерело, вона відвідує ауди- торію з метою зміни джерела. Якщо бджола залишається з джере- лом, вона знову має два варіанти. Вона намагається привернути бджіл до джерела si, або вона може полетіти до іншого джерела si. Визначається вірогідність PP si D (Psi P D = 1 – PP si X) того, що бджола йде танцювати для джерела s . Вірогідність не танцювати дорівнює відповідно 1 – Psi i P D. У такому разі вона летить до джерела si. Якщо бджола вирішує танцювати для джерела, вона негайно входить до танцполу. Чим краще якість джерела, тим довше вона танцює для цього джерела. Проте, час танцювання не може бути довшим, ніж MDT. Після того, як бджола завершила танець, вона летить до джерела, яке вона рекламувала. Бджоли в аудиторії спостерігають танцюючих бджіл. Вони намагаються прийняти рішення, за яким танцівником необхідно слідувати до відповідного джерела. Спостерігаюча бджола вибирає джерело шляхом випадкового вибору танцівника. Припустимо, що танцівник рекламує джерело sj (j ∈ { 1, ..., M} ). Вона полетить до цього джерела з вірогідністю PP sj F. У моделі визначається вірогідність Psj P F як число бджіл, які танцюють для джерела sj, поділене на число всіх танцівників. Вірогідність, з якою бджола не полетить до джерела sj , відповідає значенню 1 – PP sj F. У такому разі, бджола випадково вибирає іншого танцівника або танцівників. Якщо бджола не вибирає джерело в межах виділеного часу, вона перемі- щується з аудиторії до кімнати відправки. Звідси вона летить до випадково призна- ченого джерела. Далі весь процес повто- рюється. Метафора бджолиного вулика є корисною для створення методів інформа- ційного пошуку у Веб-мережі. Документи в мережі мають декілька атрибутів. Деякі з них мають значення в інтервалі дійсних чисел. Це загальне припущення не охоплює всі можливі випадки. Для простоти припустимо, що атрибути можуть приймати значення 0, або 1. Значення 1 відповідає запиту користу- вача. Далі припустимо, що дійсні атрибути можуть мати значення в інтервалі [0,1]. Верхнє значення найкраще відповідає запиту користувача. Джерела мають три властивості. Дві з них двозначні і одна дійсна. В першому випадку бджола була здатна оцінити джерело, наскільки близько воно знаходиться до запиту користувача. В другому випадку створена ситуація, коли деякі бджоли будуть використовувати тільки першу властивість, а деякі – другу властивість, а інші використовують тільки третю властивість. Бджоли знаходять краще джерело та більш впевнені в рекомендації кращого джерела, якщо там є більше фуражирування. Результати експе- рименту підтверджують, що на початку бджоли ходять до різних джерел і пізніше об’єднуються на кращому. 3. Модель розподіленої оцінки рангу Веб-сторінок Релевантність мережної сторінки є суб'єктивною з точки зору користувача. Кожний користувач має різні інтереси і знання для її оцінки. Є алгоритми, які знаходять важливість Веб-сторінки згідно її розташування в графі мережі і взаємо- зв'язків в ньому. Вершини графа представ- ляють Веб-сторінки, а ребра – взаємо- зв'язки між цими сторінками. Алгоритм PageRank [24] представляє імітацію уяв- лення користувача, який випадково виби- рає різні зв'язки в мережі. Після кожного кліка користувач вирішує, чи він продовжує пошук, наприклад, якщо він клікає за зв'язками на сторінці. Вірогід- ність іншої випадкової сторінки назива- Експертні та інтелектуальні інформаційні системи 74 ється коефіцієнтом затухання d (damping factor). Багато досліджень спрямовано на визначення проблеми відповідних значень коефіцієнта затухання. Загалом, цей коефі- цієнт приймає значення приблизно 0.85 [24]. Кожна мережна сторінка має унікаль- ний PageRank, який не залежить від вимоги користувача. Це означає, що PageRank не виражає релевантність сторін- ки, враховуючи запит. Алгоритм викорис- товується Google, щоб визначити критерії для сортування пошукових результатів запита користувача. Алгоритм використовує структуру зв'язків гіпертексту як “рекомендації” сторінки. Оцінка сторінки визначається не лише числом зв'язків, що ведуть до цієї сторінки, але і базується також на оцінці тих сторінок. Згідно алгоритму PageRank оцінка сторінки може досягти максималь- ного значення 10. Припустимо, що сторінки B, C, D зв'язані з сторінкою А. Якщо L(X) є числом зв'язків, які виходять зі сторінки X, то формула для обчислення PageRank, з коефіцієнтом затухання d, буде відпо- відати: ). )( )( )( )( )( )((1)( DL DPR CL CPR BL BPRddAPR +++−= Версії цього алгоритму визначає формула ), )( )( )( )( )( )((1)( DL DPR CL CPR BL BPRd N dAPR +++ − = де N є числом всіх документів усіх сторінок у колекції, пов’язаних з даною сторінкою. Розглядаючи ці формули ми бачимо, що обчислення PageRank певної сторінки виводиться з PageRank решти сторінок. Загальна формула для обчислення PageRank сторінки pi є: ∑ ∈ +−= )( )( )( 1)( ij pMp j j i pL pPR ddpPR , де pi – сторінка, для якої обчислюється PageRank, М(pi ) – набір сторінок, які “зв'язані” зі сторінкою pi і L(pj ) є числом вихідних зв'язків сторінки pj. Щоб отримати значення PageRank, яке має бути точним, слід виконати ряд ітерацій. У кожній ітерації перераховується PageRank кожної сторінки в колекції. Число повто- рень залежить від числа сторінок і склад- ності взаємозв'язку суміжних сторінок. Ітеративний підхід до обчислення PageRank не враховує “важливість” вершин графа. Використовуючи ітеративний підхід обчислення PR сторінки А здійснюється після завершення обчислення PR сторінок B,C...,M. Найвигіднішим є підхід, у якому ми обчислюємо PR сторінок, від яких залежить решта сторінок. Проте, це не- можливо у разі, якщо залежність сторінок циклічна. Ітеративний підхід обробляє одну вершину після іншої незалежно від їх взаємного зв'язку. Для обчислення PageRank викорис- таємо агентну модель бджолиного вулика. Бджола має летіти до джерела E (вершина E), і має вирахувати PR(E), але водночас вона має знати, що попередньо необхідно вирахувати значення PR(D), PR(B), PR(F) і PR(H). Якщо джерело E матиме високу якість, бджола має летіти в танцпол і танцювати. Проте, вона не має танцювати для джерела E, а танцювати для одного із джерел D, B, F або H. Вибір джерела має бути випадковим з призначенням вірогід- ності для кожного з них. У цьому випадку бджола має привернути увагу інших бджіл до джерела, для якого їй слід вирахувати PR. Після закінчення танцю бджола має летіти назад до джерела E, щоб привер- нути бджіл летіти до джерела D, B, F або H. У разі ж, якщо якість джерела є досить високою, то бджола полетить до танцполу і буде танцювати там для одного із джерел D, B, F або H. Цикл повторюється, поки досягається значення PR(E). Після відвідування джерела sі бджола обчислює PR(sі) і послідовно визначає якість джерела sі за формулою Qi = PR(sі)/MaxPR, де MaxPR є найвищим відомим значенням PR вершини графа. По- дальші дії бджоли залежать тільки від роз- рахованого значення якості Qi. Бджола залишає джерело sі з вірогідністю PP si X =1 – – Q і летить до аудиторії. У випадку, коли бджола не залишає джерело, вона в залежності від Q вирішує, чи летіти їй до танцполу, чи продовжуватиме приносити i Si Експертні та інтелектуальні інформаційні системи 75 їжу з джерела s . Якщо вона летить до танцполу, то вона танцюватиме для одного з джерел, які зв'язані з джерелом s . Вибір цього джерела випадковий, наприклад s . Бджола таким чином сприятиме рекламу- ванню джерела s . Бджоли в аудиторії завжди випадково вибирають джерело і слідують за бджолою з вірогідністю Psj і і j j P F, яка дорівнює якості джерела, яке рекламу- ється бджолою Qj = PR(sj)/PR(sі). У разі , якщо бджола в аудиторії не вибере будь-яку бджолу для того, щоб слідувати за нею, за даний ліміт часу, вона летить до диспетчерської кімнати, звідки вона буде відправлена до випадкового джерела. Цикл оцінки вершин графа може описуватися наступним чином. Спочатку значення кожної вершини графа дорівнює PR = 1. Число бджіл випадково почне летіти до вершини. Кожна бджола після відвідування вершини поводиться згідно описаним правилам. Цей цикл ітеративно повторюють, поки всі вершини графа не будуть оцінені або поки не буде досягнуте за дане число повторень. Кінцевий стан оцінки графа показано на рисунку. Рисунок. Обчислення PageRank графа Хороші результати досягаються при використанні достатнього числа бджіл. Коли використовують 100 бджіл, то для цього обчислення потрібно тільки 13 ітерацій. Результати експериментів пока- зують, що коли число бджіл більше, ніж число вершин у графі, то цей метод дає кращі результати, ніж стандартний ітера- тивний метод. Але, якщо ми зменшуємо число бджіл, то число повторень, яке потрібно для обчислення PR, дуже швидко зростає. Більше число бджіл має позитивний вплив на пошукові результати – це збіль- шує можливість відвідування відповідних джерел. З точки зору ефективності, підхід забезпечує кращі результати, ніж інші методи, які припускають, що число бджіл більше, ніж число вершин у графі. Висновки Представлено підхід до мережного пошуку, який заснований на метафорі бджолиного вулика. Перевага цього підходу полягає у можливості розподіле- ного обчислення PageRank у випадку великого графа. Метод не потребує додаткового ускладнення, щоб бути поширеним на велику кількість комп'юте- рів, які мають спілкуватися один з одним. У цьому випадку бджоли повинні бути здатні здійснювати обчислення PageRank величезних графів. Потрібні подальші до- слідження в напрямку проблеми масшта- бованості підходу. Перевагою підходу є можливість безперервного обчислення PageRank графа в режимі on-line. Наприклад, Google перераховує PageRanks всіх індексованих оброблених сторінок один раз у певний період часу. Якщо ми використовуємо запропонований підхід, то має бути відносно легко перерахувати PageRanks безперервно – тобто бджоли мають по- стійно літати над графом і відновлювати PageRank вершин графа. Щоб досягти реальної моделі мережного пошуку, необхідно було враху- вати додаткові параметри, як наприклад, початкове розповсюдження напрямів фу- ражирування. Альтернативою до випад- кової генерації початкового напряму може бути деякий вид пам'яті (індивідуальний або колективний). Метафора вулика використовується як основа для агентної моделі пошуку інформації множини джерел, які представ- лені у Веб. Окрім такого автономного застосування, як пошук “фіксованої” час- тини Веб, вона може бути результативною щодо пошуку в динамічному Веб. Такий динамічний пошук, який виконується E H B D F A C I G H H F F 0,150,15 0,38236970,38236975 0,40 0,15 0,15 0,15 0,40 0,150,38236975 0,38236975 1,0935 Експертні та інтелектуальні інформаційні системи 76 безперервно, міг би забезпечити можли- вість адаптивного пошуку згідно зі змінами на Веб – зникнення старих доку- ментів і поява нових тощо. 1. Андон П.І., Дерецкий В.О. Проблеми побудови сервіс-орієнтованих прикладних інформаційних систем в Semantic web середовищі на основі агентного підходу // Проблеми програмування. – 2006. – № 2-3. – С. 493–502. 2. Дерецкий В.О., Богданова М.М., Ремарович С.С. Підхід до організації пошуку інформації в різнорідних джерелах // Проблеми програмування. – 2008. – № 2-3. – С. 395–402. 3. R. Koval and P. Navrat. Intelligent support for information retrieval of web documents, Computing and Informatics. – 2002. – 21(5). – Р. 509–528. 4. S. Ye, T. Chua, and J. Kei. Clustering web pages about persons and organizations, Web Intelligence and Agent Systems. – 2005. – 3(4). – Р. 203–216. 5. H. Lei and V. Govindaraju. Matching and retrieving sequential patterns using regression, Web Intelligence and Agent Systems. – 2005. – 3(4). – Р. 261–270. 6. X. Zhang, V. Lesser, and T. Wagner. A Layered Approach to Complex Negotiations, Web Intelligence and Agent Systems. – 2004. – 2(2). – Р. 91–104. 7. L. Hluchy, M. Laclavik, Z. Balogh, and M. Babik. AgentOWL: Semantic knowledge model and agent architecture, Computing and Informatics. – 2006. – 25(5). – Р. 421– 439. 8. K. Matusikova and M. Bielikova. Social navigation for semantic web applications using space maps, Computing and Informatics. – 2007. – 26(3). – Р. 281–299. 9. Ремарович С.С. Агентний підхід до тематичного пошуку інформації з використанням онтологій // Проблеми програмування.–2008.–№ 2-3.– С. 411–416. 10. D. Gordon. The organization of work in social insect colonies, Nature 380.– 1996. – Р. 12 1–124. 11. S. Camazine and J. Sneyd. A model of collective nectar source selection by honey bees: Self organization through simple rules, Journal of Theoretical Biology. – 1991. – 149(4). – Р. 547–571. 12. H. de Vries and J.C. Biesmeijer. Modelling collective foraging by means of individual behaviour rules in honey-bees, Behav. Ecol. Sociobiol. – 1998. – Р. 109–124. 13. http://www.polarization.com/bees/bees.html 14. T.D. Seeley, S. Camazine, and J. Sneyd. Collective decision-making in honey bees: how colonies choose among nectar sources, Behav Ecol Sociobiol.–1991.–28.–Р.277–290. 15. C.A. Tovey. The honey bee algorithm. A biologically inspired approach to internet server optimization, Engineering Enterprise. – Spring 2004. – Р. 13–15. 16. F. Lorenzi, D. Scherer dos Santos, and A.L.C. Bazzan. Case-Based Recommender System-Inspired by Social Insects, in: Proc. XXV Congresso da Sociedade Braseilera de Computacao, Sao Leopoldo. – 2005. – Р. 752–760. 17. F. Lorenzi, D. Scherer dos Santos, and A.L.C. Bazzan. Negotiation for task allocation among agents in case/base recommender systems: a swarm intelligence approach, in: Proc. IJCAI 2005 Conference, Workshop. – 2005. – Р. 23–27. 18. H.E. Bullock, P. Dey, and K.D. Reill. A “Bee Hive” model for heterogeneous knowledge in expert systems, ACM. – 1986. – Р. 417– 417. 19. A. Dornhaus, F. Klugl, F. Puppe, and J. Tautz. Task selection in honeybees – experiments using multi-agent simulation, in: 3rd German Workshop on Artificial Life. – 1998. – Р. 171–183. 20. F. Kluegl, C. Oechslain, F. Puppe, and A. Dornhaus. Multi-agent modelling in comparison to standard modelling, in: Proc. AIS2002 Artificial Intelligence, Simpulation and Planning in High Autonomy Systems, F.J. Barros, N. Giambasi, eds, SCS Publ. House. – 2002. – Р. 105–110. 21. F. Klügl and F. Puppe. The multi-agent simulation environment SeSAm. In. Proceedings of the Workshop „Simulation and knowledge-based systems”, H. Kleine Büning (ed.). (= Report tr-ri-98-194, Reihe Informatik, University Paderborn). – 1998. 22. F. Klügl, F. Puppe, U. Raub and J. Tautz. Simulating Multiple Emergent Behaviors – exemplified in an Ant Colony. In Proc. of Artificial Life VI, Los Angeles, June 26-29, 1998. 23. S.J. Schultze. A collaborative foraging approach to web browsing enrichment, in: Proc. CHI 2002, ACM. – 2002. – P. 860–861. 24. S. Brin and L. Page. The anatomy of a large- scale hypertextual web search engine, Computer Science Department, Stanford University, Stanford, http://www- db.stanford.edu/˜backrub/google.html. Отримано 20.04.2010 http://www.polarization.com/bees/bees.html Експертні та інтелектуальні інформаційні системи 77 Про автора: Ремарович Світлана Станіславівна, науковий співробітник. Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, Проспект Академіка Глушкова, 40. Тел.: 38 044 526 6249. e-mail: rem@isofts.kiev.ua Висновки

Agent model of information retrieval on the basis of beehive metaphor

Institution

Ähnliche Einträge