Биологически обоснованный метод формирования поискового поведения

Размещено на http://www.allbest.ru/

Биологически обоснованный метод формирования поискового поведения

1. Тактики поискового поведения биологических организмов

тактика поисковый поведение робот

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

С этой целью была построена модель поискового агента, использующая две тактики. Одна из этих тактик заключается в том, что организм перемещается в определенном направлении на значительное расстояние. Вторая тактика представляет собой частые случайные изменения направления движения. Эта тактика приводит к тому, что организм остается на ограниченном участке. Эти тактики чередуются, причем переключение между ними инерционно: организм придерживается текущей тактики в течение некоторого времени, несмотря на вариации внешней стимуляции. Такое чередование тактик характерно для поискового поведения бактерий Korobkova et al., 2004], дрозофил Reynolds et al., 2007], тлей Mashanova et al., 2010], а также других организмов, в том числе позвоночных (см. обзоры: Kramer et al., 2001], Bartumeus et al., 2009]).

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

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

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

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

2. Поиск минимума функций нескольких переменных

Для определенности рассматриваем случай функции двух переменных. Минимум функции f(x,y) ищется следующим образом. Считается, что в пространстве x,y движется агент. Движение происходит в дискретном времени t. Величины смещения агента в такт времени t равны

Дx(t) = s cosц(t), Дy(t) = s sinц(t) , (2.1)

где угол ц(t) характеризует направление перемещения агента, s - величина перемещения. Вводится мотивация M(t) к сохранению направления поиска. Динамика мотивации определяется выражением:

M(t) = k₁ M(t-1) + о(t) + I(t) ,(2.2)

где время t дискретно, t = 1,2,…, 0 < k₁ < 1, 1-k₁ << 1, о(t) - нормально распределенная случайная величина с нулевым средним и дисперсией, равной у². Величина I(t) пропорциональна приращению функции f(x,y) (с обратным знаком) за последний такт времени:

I(t) = - k₂ f(t) - f(t-1)] , k₂ > 0 ,(2.3)

где f(t) и f(t-1) - значения f(x,y) в месте нахождения агента в такты времени t и t-1.

Первое слагаемое в правой части (2.2) характеризует медленную релаксацию мотивации, второе - случайные вариации мотивации, третье - направленное изменение мотивации.

Считаем, что при M(t) > 0 направление перемещения агента не меняется: ц(t) = ц(t-1), а при M(t) < 0 угол ц меняется на случайную величину w: ц(t) = ц(t-1) + w, где w - нормально распределенная случайная величина с нулевым средним и дисперсией, равной w₀².

Таким образом, аналогично изложенным выше биологическим примерам имеются две тактики поискового поведения:

1) движение в выбранном направлении (при M(t) > 0),

2) случайная вариация направления перемещения (при M(t) < 0).

Мотивация M(t) регулирует инерционное переключение между тактиками.

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

Метод минимизации функции f(x,y) был реализован в виде компьютерной программы. При расчетах полагалось s = 0.01, остальные параметры k₁, k₂, у, w₀ грубо подбирались эвристически таким образом, чтобы происходило достаточно быстрое нахождение минимума f(x,y).

Было продемонстрировано, что аналогично несколько более сложной методике, исследованной в работе Непомнящих, 2006], данный метод обеспечивает нахождение минимума

- для одноэкстремальной функции, например, для гауссовского распределения f(x,y);

- для функции, имеющей «плато», т.е. область в пространстве x,y, в которой значение f(x,y) не меняется;

- при наличии в пространстве x,y непреодолимого агентом барьера ограниченного размера.

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

Кроме того, в рамках рассматриваемого метода был построен аналог известного овражного метода минимизации функций Гельфанд и др., 1961]. Предполагалось, что минимизируемая функция имеет достаточно глубокий «овраг», в котором она слабо меняется.

Моделирование было проведено для следующего примера. Полагалось

f(x,y) = (с - с₀)² - бx ,

где с = (x² + y²)^Ѕ , с₀ = 1, б = 0.01. Так как б << 1, то «грубый» минимум, «овраг» соответствует окружности радиуса 1 с центром в начале координат (с = 1), а глобальный минимум соответствует координатам x_m = 1.005, y_m = 0. При этом f(x_m , y_m) = - 0.010025.

Рис. 1. Траектория движения агента при наличии «оврага». Исходные координаты агента составляли x = y = 0. Сначала за время t, примерно равное 100 тактам, находится овраг, т.е. единичная окружность. Затем происходит движение вдоль окружности, при t ? 800 фактически достигается глобальный минимум функции и происходят колебания в окрестности точки x_m , y_m

Рис. 2. Зависимость функции f(x,y) от времени t. На врезке показана эта зависимость в увеличенном масштабе

Результаты типичного расчета показаны на Рис. 1, 2. Параметры расчета составляли k₁ = 0.5, k₂ = 1.0, у = 0.0001, w₀ = 2.0. В начале поиска агент находился в точке x = y = 0. Видно, что сначала происходит «грубая» минимизация функции f(x,y), при этом находится овраг, а затем происходит движение вдоль оврага и постепенное уменьшение величины f(x,y).

Заключение

Итак, построен метод поиска экстремума функции f(x,y), основанный на использовании мотивации M(t) к сохранению выбранного направления движения. Динамика мотивации определяется простыми уравнениями (2.2), (2.3). Данный метод легко обобщается на случай поиска оптимума функции многих переменных.

Необходимо подчеркнуть, что методы поиска экстремума функций, близкие к изложенному, разрабатывались рядом авторов (Цыпкин Я.З., Растригин Л.А., Неймарк Ю.И.), см. например, Растригин, 1981]. Однако изложенный метод в наиболее явном и четком виде использует свойства инерционности, стохастичности и влияние изменения оптимизируемой функции. В принципе, возможны модификации метода с применением схем адаптации, исследованных в 1960-80 гг. Например, можно учесть инерционность с помощью автоматов, аналогичных автоматам М.Л. Цетлина Цетлин, 1969], и такая модель была нами разработана Мосалов и др., 2003]; изучение модели показало, что она также достаточно эффективно обеспечивает поиск экстремума функций, хотя сама модель более громоздкая, чем представленная выше схема минимизации f(x,y). В метод можно вводить дальнейшие естественные усовершенствования, например, уменьшение шага s при приближении к экстремуму, постепенное уменьшение интенсивности стохастичности (подобно известному методу отжига Kirkpatrick et al, 1983]) и т.п. Однако, так как наша задача - охарактеризовать общие закономерности биологически инспирированного метода поиска, то мы ограничились наиболее простой формой метода.

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

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00129).

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

1.Гельфанд и др., 1961 Гельфанд И.М., Цетлин М.Л. Принцип нелокального поиска в задачах автоматической оптимизации // ДАН СССР. 1961. Т. 137. № 2.

2.Мосалов и др., 2003 Мосалов О.П., Редько В.Г., Непомнящих В.А. Модель поискового поведения анимата // Препринт Института прикладной математики им. М.В. Келдыша РАН. 2003. № 19.

3.Непомнящих, 2006 Непомнящих В.А. Модели автономного поискового поведения // От моделей поведения к искусственному интеллекту / Под ред. В.Г. Редько. М.: Изд-во УРСС, серия «Науки об искусственном», 2006.

4.Непомнящих и др., 2008 Непомнящих В.А., Попов Е.Е., Редько В.Г. Бионическая модель адаптивного поискового поведения // Известия РАН. Теория и системы управления, 2008. № 1.

5.Растригин, 1981 Растригин Л.А. Адаптация сложных систем. Рига: Зинатне, 1981.

6.Цетлин, 1969 Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем. М.: Наука, 1969.

7.Bartumeus et al., 2009] Bartumeus F., Catalan J. Optimal search behavior and classic foraging theory // Journal of Physics A: Mathematical and Theoretical. 2009. V.42. № 43. 434002, stacks.iop.org/JPhysA/42/434002

8.Kirkpatrick et al, 1983 Kirkpatrick S., Gelatt C.D.Jr., Vecchi M.P. Optimization by simulated annealing // Science. 1983. V. 220. № 4598.

9.Korobkova et al., 2004 Korobkova E., Emonet T., Vilar J. M. G., Shimizu T. S., Cluzel. P. From molecular noise to behavioural variability in a single bacterium // Nature. 2004. V. 428. № 6982.

10.Kramer et al., 2001 Kramer D.L., McLaughlin R.L. The behavioral ecology of intermittent locomotion // American Zoologist. 2001. V. 41. № 2.

11.Mashanova et al., 2010 Mashanova A., Oliver T.H., Jansen V.A.A. Evidence for intermittency and a truncated power law from highly resolved aphid movement data // Journal of Royal Society Interface. 2010. V.7. № 42.

Размещено на Allbest.ru