close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Программные продукты и системы
октября 2011 г.) по проекту «Программный комплекс и облачный сервис для автоматизации
обобщения и анализа финансово-экономической
информации о деятельности предприятий и обеспечения принятия управленческий решений» ЗАО
«МБК Груп» совместно с ОАО «МХК «ЕвроХим»
при финансовой поддержке Министерства образования и науки Российской Федерации.
Литература
1. Стариков А. Ядро OLAP-системы. Лаборатория
BaseGroup. URL: http://www.basegroup.ru/ (дата обращения:
7.08.2013).
2. Барсегян А., Куприянов М., Степаненко В., Холод И.
Технологии анализа данных. Data Mining, Text Mining, Visual
Mining, OLAP. СПб: БХВ-Петербург, 2007. С. 19–58.
3. Niemi T., Nummenmaa J., Thanisch P. Proceeding
DOLAP'01. Proc. 4th ACM intern. workshop on Data warehousing
and OLAP, NY, 2001, pp. 9–15.
4. Арустамов А. Применение OLAP-технологий при извлечении данных. Лаборатория BaseGroup. URL: http://www.basegroup.ru/ (дата обращения: 7.08.2013).
5. Щавелев Л.В. Способы аналитической обработки данных для поддержки принятия решений // Системы управления
базами данных. 1998. № 04–05.
6. Титоренко Г.А. Информационные технологии управления. М., 2003. С. 88–98.
7. Ильина О.П. Информационные технологии бухгалтерского учета. СПб: Питер, 2001. С. 57–60.
8. Назаров М.Г. Курс социально-экономической статистики. М., 2000. 771 с.
9. Карпов Ю.Г. Теория и технология программирования.
Основы построения трансляторов. СПб: БХВ-Петербург, 2012.
10. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов.
СПб: Корона-Принт, 2000.
11. Легалов А.И. Основы разработки трансляторов: учеб.
пособие. Красноярск: Сибирский федер. ун-т, 2008.
12. Коробова И.Л., Дьяков И.А., Литовка Ю.В. Основы
разработки трансляторов в САПР. ТГТУ, 2007.
13. Фридл Д. Регулярные выражения. СПб: Символ-Плюс,
2008.
14. Гойвертс Я., Левитан С. Регулярные выражения.
Сборник рецептов. СПб: Символ-Плюс, 2010.
№ 4, 2013 г.
References
1. Starikov A. The core of OLAP system, BaseGroup, 2003,
available at: http://www.basegroup.ru/ (accessed 26 August 2013)
(in Russ.).
2. Barsegyan A., Kupriyanov M., Stepanenko V., Holod I.
Tekhnologii analiza dannykh. Data Mining, Text Mining, Visual
Mining, OLAP [Data analysis technologies. Data Mining, Text
Mining, Visual Mining, OLAP]. St. Petersburg, BHV-Petersburg
Publ., 2007, pp. 19–58 (in Russ.).
3. Niemi T., Nummenmaa J., Thanisch P. Proc. of the 4th
ACM int. workshop on Data warehousing and OLAP. 2001,
pp. 9–15.
4. Arustamov A. Primenenye OLAP tekhnologiy pri izvlechenii dannykh [OLAP technologies application when data retrieval].
BaseGroup, 2003, available at: http://www.basegroup.ru/ (accessed
26 August 2013) (in Russ.).
5. Shchavelev L.V. Sistemy upravleniya bazami dannykh
[Databases management systems]. 1998, no. 04-05, p. 26 (in Russ.).
6. Titorenko G.A. Informatsionnye tekhnologii upravleniya
[Information technologies of management]. 2nd ed., Moscow,
2003, pp. 88–98 (in Russ.).
7. Ilina O.P. Informatsionnye tekhnologii bukhgalterskogo
uchyota [Information technologies of accounting]. St. Petersburg,
Piter Publ., 2001, pp. 57–60 (in Russ.).
8. Nazarov M.G. Kurs sotsialno-ekonomicheskoy statistiki
[Social-economic statistics course]. Moscow, 2000, 771 p.
(in Russ.).
9. Karpov Yu.G. Teoriya i tekhnologiya programmirovaniya.
Osnovy postroeniya translyatorov [Programming theory and technology. Fundamentals of translators]. BHV-Peterburg Publ., 2012
(in Russ.).
10. Kompaniets R.I., Mankov E.V., Filatov N.E. Sistemnoe
programmirovanie. Osnovy postroeniya translyatorov [System programming. Fundamentals of translators]. St. Petersburg, KoronaPrint Publ., 2000 (in Russ.).
11. Legalov A.I. Osnovy razrabotki translyatorov [Development basics of translators]. Textbook, Krasnoyarsk, Siberian Federal Univ. Publ., 2008 (in Russ.).
12. Korobova I.L., Dyakov I.A., Litovka Yu.V. Osnovy razrabotki translyatorov v SAPR [Development basics of translators in
CAD system]. Tver State Tech. Univ. Publ., 2007 (in Russ.).
13. Friedl J. Mastering Regular Expressions. O'Reilly Media
Publ., 2006.
14. Goyvaerts J., Levithan S. Regular Expressions Cookbook.
O'Reilly Media Publ., 2009.
УДК 519.68
ВЕРИФИКАЦИЯ МУЛЬТИАГЕНТНЫХ СИСТЕМ
С ПОМОЩЬЮ ЦЕПЕЙ МАРКОВА: ОЦЕНКА ВЕРОЯТНОСТИ
НАХОЖДЕНИЯ АГЕНТАМИ ОПТИМАЛЬНОГО РЕШЕНИЯ
И.Д. Зайцев, аспирант
(Институт систем информатики им. А.П. Ершова СО РАН,
просп. Лаврентьева, 6, г. Новосибирск, 630090, Россия, zaycev.ivan@gmail.com)
Предлагаются общее описание алгоритма работы определенного семейства мультиагентных систем и некоторые
следующие из этого описания оценки свойств систем. В последнее время мультиагентный подход к построению
сложных вычислительных систем обретает все большую популярность. Однако связанная с ним теория все еще недостаточно развита. Остаются неясными или недостаточно обоснованными вопросы о том, какого вида системы
лучше применять в тех или иных случаях и в чем их преимущество перед другими методами. Отчасти это связано с
тем, что в разных областях исследования под мультиагентной системой могут подразумеваться разные понятия. В
данной работе выделяется и формализуется отдельное семейство мультиагентных систем, для полученной формализации проводится аналогия с марковскими цепями. Далее с помощью известных свойств марковских цепей исследуются свойства выделенного семейства систем. Для систем, построенных с помощью функции особого вида, доказы-
96
Программные продукты и системы
№ 4, 2013 г.
вается, что вероятность нахождения агентами того или иного допустимого решения тем больше, чем больше значение функции полезности для этого решения.
Ключевые слова: мультиагентные системы, методы Монте-Карло, генетические алгоритмы, случайные процессы, цепи Маркова.
MULTIAGENT SYSTEMS VERIFICATION WITH MARKOV CHAINS:
PROBABILITY ESTIMATION OF OPTIMAL SOLUTION FINDING BY AGENTS
Zaytsev I.D., postgraduate student (A.P. Ershov Institute of Informatics Systems, Siberian Branch of RAS,
Lavrenteva Av, 6, г. Novosibirsk, 630090, Russian Federation, zaycev.ivan@gmail.com)
Аbstract. The paper presents general description of meta-algorithm, used by some class of multiagent systems.
Nowadays multiagent approach for complex systems building gains more and more popularity. But the theory, connected
with it, still remains not developed enough. It’s still unclear or not well-founded, which kind of systems should be used in
particular cases, and what advantages these systems have. Partly it’s because multiagent systems may have different
meanings in different research areas. In this work one particular class of multiagent systems is considered. Formalization of
this class is connected with Markov chains, so we can estimate some properties of these systems using that mathematical
instrument. Then, for systems built with some functions, statement is proved that probability of finding allowable solution by
agent is higher when fitness function meaning for this solution is higher.
Keywords: multiagent systems, Monte Carlo methods, genetic algorithms, stochastic processes, Markov chains.
В последние десятилетия мультиагентные системы (МАС) завоевывают все большую популярность. Высокопроизводительные вычислительные
системы строятся изначально как распределенные
системы с множеством потоков управления и
распределенными данными. Даже в пользовательском аппаратном обеспечении используются многоядерные и векторные процессоры. Все это делает востребованной концепцию МАС, в рамках
которой вычислительная система представляется
как набор принимающих решения и обменивающихся информацией агентов, в достаточной мере
не зависящих друг от друга.
Однако необходимо отметить, что теория МАС
недостаточно проработана. Отчасти это объясняется тем, что понятие МАС довольно размыто,
поскольку в разных областях исследования и применения под ним понимаются довольно разные
вещи. Все это усложняет не только поиск и определение свойств, верификацию МАС в общем
случае, но и саму формализацию понятий агента,
системы, программы и т.п. Закономерными в данном случае являются предварительное выделение
некоторого семейства МАС, устроенных схожим
образом, обоснование их значимости, формализация и исследование их свойств с помощью уже
существующего математического аппарата с возможной корректировкой этого аппарата с учетом
специфики задачи.
Например, в рамках работы [1] было выделено
семейство МАС, использующих парадигмы логического программирования, и предположено, что
процесс обмена информацией между объектами
подвержен случайным задержкам с заданным распределением вероятности. В данном случае представляют интерес МАС, используемые в имитационном моделировании в области экономики,
общественных наук и биологии. В предлагаемой
работе выделено такое семейство МАС, показано,
что в него входят также МАС, используемые при
решении оптимизационных задач, в частности,
реализующие эволюционные алгоритмы.
Семейство синхронных стохастических
мультиагентных моделей
В различных МАС требования к тому, что считать интеллектуальным агентом, существенно
разнятся. Агент может иметь сложное внутреннее
устройство, обладать довольно развитым искусственным интеллектом, а также действовать реактивно по фиксированному простому алгоритму.
Как правило, количество используемых агентов обратно пропорционально сложности их внутренней организации. В крайних случаях имеются
следующие типы систем.
МАС, состоящая из 2-3 высокоинтеллектуальных агентов (включающих в себя, как правило,
другие системы искусственного интеллекта, например экспертные), со сложным, продуманным
протоколом для общения, установления слаженности действий.
МАС, состоящая из большого числа (до нескольких тысяч или даже десятков тысяч) простых
агентов, взаимодействующих главным образом со
средой, а не друг с другом, с простым, но не строго детерминированным поведением. Такие системы, как известно, способны демонстрировать роевой интеллект (swarm intelligence), приспосабливаться к меняющимся условиям, находить ниши с
оптимальным значением тех или иных показателей. На этом, в частности, основываются методы
муравьиной колонии, роя частиц, другие эвристические методы [2, 3].
В экономике и общественных науках создать
продуманную и сложную модель действующего
субъекта (то есть построить высокоинтеллектуального агента) подчас бывает довольно сложно,
поскольку это требует наличия высокоразвитой
теории психологии субъектов, четкого знания алгоритмов, используемых ими для принятия тех
или иных решений. Эффективнее принять простую схему действий агента, а отклонения от нее
считать случайной величиной с заданным распределением. Таким образом, получаются модели,
97
Программные продукты и системы
более близкие ко второму крайнему случаю. При
этом полезно рассматривать агентное моделирование вместе с другими методами имитационного
моделирования [4].
Конечная цель агента в таких системах (и направленная к ее достижению деятельность) определяется поиском более или менее удачного приближения к наилучшему решению какой-то определенной задачи. Например, поиск глобального
максимума некоторой функции max(f) с помощью
приближенных методов или эвристик, характерных для задач искусственного интеллекта. Решение задачи производится поэтапно. Сначала
агенты ищут это приближение (каждый по собственному представлению о функции и своему алгоритму с использованием доступных сведений из
среды). Затем устанавливают некоторые значения
среды согласно найденному решению. После этого снова ищут приближение, исходя из уже изменившихся значений переменных среды. В последовательном повторении этих двух этапов и
заключается имитационное моделирование.
Для введения математического описания этого
процесса конкретизируем рассматриваемое семейство МАС и используемые понятия так, чтобы не
потерялась их ценность. Для этого рассмотрим
МАС сходного с описанным устройства, применяемые в задачах оптимизации (а также методы
оптимизации, реализовать которые можно с помощью таких МАС).
Пошаговый случайный поиск
Вероятностные методы решения задач (методы
Монте-Карло) занимают особое место среди методов поиска решений. С одной стороны, их использование, как правило, оказывается оправданным в
том случае, если свойства искомого решения и его
место среди допустимых решений (например,
максимизируемой функции в случае задачи поиска максимума) недостаточно изучены или вообще
трудно поддаются установлению, например, в
численном интегрировании сложных функций
в пространствах большой размерности.
С другой стороны, многие случайные вычисления могут быть осуществлены независимо друг
от друга, что делает довольно удобным процесс их
распараллеливания и обеспечивает рост скорости
вычислений с увеличением числа независимых
вычислителей. Например, метод иглы Бюффона
для определения значения числа Пи при последовательной генерации случайных чисел существенно проигрывает по времени другим численным
методам. Однако, поскольку генерация нескольких случайных чисел может быть проведена независимо, то, располагая произвольно большим количеством вычислителей, можно произвести генерацию сколь угодно большого набора случайных
чисел за время, ограниченное константой.
98
№ 4, 2013 г.
В реальности же вычислительные системы
имеют ограниченное количество вычислителей.
В связи с этим может быть случайно сгенерировано лишь определенное число решений. Однако зачастую обмен информацией о полученных решениях помогает сузить область поиска или задать
направления для дальнейшего поиска, в общем,
сохраняя вероятностный характер найденного
решения, увеличить вероятность нахождения оптимума. На этом принципе построены многие эвристические методы поиска оптимального решения [5].
Итак, представляется интересной следующая
математическая модель работы МАС. Пусть даны
n агентов (A1, …, An). Целью каждого агента является нахождение максимума заданной функции
f(x) (назовем ее целевой) на заданной области D.
Действия агентов определяются следующим алгоритмом. Изначально каждый агент получает начальное решение x0,j (j=1, …, n). Для краткости
обозначим совокупность значений переменной x у
всего набора агентов как X=<x1, …, xn>. Таким образом, агенты получают (или находят случайным
образом) начальный набор X0 и начинают пошагово искать максимум целевой функции. Опишем
алгоритм их действий (в общем виде) на i-м шаге.
У каждого агента имеется значение xi,j (то есть
задан набор Xi). Сначала каждый агент вычисляет
значение целевой функции на данном ему значении x (f(xi,j) обозначим для краткости fi,j, а набор
значений f у всех агентов – Fi). Затем агенты обмениваются информацией о найденных решениях
(каждый агент сообщает каждому или передает в
общую память значения xi,j, fi,j). Исходя из полученных решений, каждый агент определяет следующее значение xi+1,j=gi,j(Xi, Fi). Обозначим его
кратко как Xi+1=Gi(Xi, Fi), где функция Gi(Xi, Fi)
определяет набор <gi,1(Xi, Fi), …, gi,n(Xi,Fi)>. Функции gi,j(Xi, Fi) в общем случае могут не быть строго детерминированы, и для многих мультиагентных моделей это действительно так.
Поскольку вычисление значений функций f и g
осуществляется агентами независимо, можно
ожидать пропорционального количеству агентов
прироста производительности работы системы в
случае, если деятельность каждого агента реализуется отдельным вычислителем (например, процессором или одним ядром многоядерного процессора), а обращение вычислителей к общей памяти происходит за пренебрежимо малое время
(в сравнении со временем, необходимым на вычисление значений функций f и g).
Представление генетических алгоритмов в
рамках полученной модели. Деятельность довольно большого круга МАС можно представить в
предложенном общем виде. Интересным примером является мультиагентная реализация генетического алгоритма (ГА). Возьмем за основу описание ГА, данное в [6]. Предположим, что агенты
Программные продукты и системы
– это селекционеры, выращивающие, отбирающие
и скрещивающие лучших особей. Количество селекционеров равно количеству особей в одной популяции. Сначала селекционеры получают начальную популяцию X0. Затем каждый для своей
особи вычисляет значение функции полезности
(F(X0)=<f(x0,1), …, f(x0,n)>). Потом каждый агентселекционер выбирает сообразно значениям
функции полезности случайным образом две особи-решения и скрещивает их (алгоритм выбора и
алгоритм скрещивания могут быть разными в разных реализациях ГА). Таким образом определяется значение функции gi,j(Xi,Fi). Формально функцию g можно определить через умножение случайным образом составленных матриц на векторы,
что, например, проделано в [7].
ГА применяются в основном для задач, в которых функция полезности имеет достаточно сложный вид, что препятствует решению ее точными
методами. Это означает, что зачастую вычисление
функции полезности представляет собой весьма
трудную задачу и основное время в реализации
ГА занимает вычисление функции полезности для
одной особи.
Представление ГА в виде МАС, где каждому
агенту соответствует особь в популяции, позволяет существенно сократить время работы ГА. Кроме того, подобное представление дает возможность применить математические методы для
оценки свойств описываемой им МАС.
Исследование свойств полученной модели
МАС с помощью цепей Маркова
Формализуем и сузим полученное представление МАС. Предположим, что область D является
конечным множеством (что верно для многих систем), а функция g и начальные значения X0 – это
случайные величины с заданным распределением.
В начальный момент времени имеется набор
X0. На каждом следующем шаге получаем новый
набор Xi+1=Gi(Xi,Fi). Поскольку Fi=F(Xi), а функция F задана изначально, то получается, что
Gi зависит только от Xi. Выразим это кратко:
Xi+1=Gi(Xi). Нетрудно заметить, что это описание
марковского процесса с дискретным временем и
пространством – последовательность случайных
чисел Xi, где i обозначает момент времени и каждое следующее значение зависит только от настоящего.
Для многих МАС (в частности, представляющих ГА) Gi(Xi) не зависит от i. В таком случае полученная марковская цепь (МЦ) является также
однородной.
Множеством состояний S будет множество наборов X=<x1, …, xn> | xjD. Обозначим m=|S|= |D|n,
S={s1, …, sm}. Допустим, что a, b, c – произвольные элементы множества S. Начальным распределением будет вектор p=(p1, …, pm)T. Для удобства
№ 4, 2013 г.
в качестве индексов используем элементы множества S. Тогда получим, что вектор p состоит из
элементов pa=p(X0=a).
Матрица переходных вероятностей на i-м шаге
P(i) в таком случае состоит из элементов Pab(i)=
=p(Gi(a)=b). В дальнейшем будем рассматривать
однородные МЦ, иными словами, Pab(i)=Pab и не
зависит от i. Элемент P(i)ab будет обозначать вероятность попадания цепи из состояния a в состояния b по прошествии i шагов.
Такое описание позволит воспользоваться изученными свойствами МЦ для оценки эффективности и определения свойств МАС, подпадающих
под описанную модель. В частности, в работах
[1, 8] проводится оценка сложности верификации
МАС (хотя и другого вида), представленных в виде МЦ.
Небезынтересным также является поведение
систем после довольно значительного числа шагов. Как известно, для особого семейства МЦ, называемых эргодичными, по прошествии длительного периода времени вероятность попадания
случайной величины в то или иное состояние перестает зависеть от начального состояния цепи.
Иными словами, при i→∞ P(i)ab=P(i)b. Условия эргодичности и ее математическое определение даны, например, в [9]. Для данного случая это условие можно выразить так: возведенная в некоторую
степень матрица перехода не содержит нулевых
элементов. Иными словами, у МЦ есть вероятность через определенное число шагов перейти из
любого состояния в какое-либо другое. Полезно
было бы оценить вероятность получения того или
иного состояния в зависимости от значения максимизируемой функции f в нем. Высокое значение
вероятности для состояний с более высоким значением функций в данном случае гарантировало
бы большую вероятность нахождения максимума
(вне зависимости от начального решения).
Введем для оценки полезности состояния МЦ
функцию h(Xi)=max(f(xi,1), …, f(xi,n)), где Xi=<xi,1,
…, xi,n>.
Проведем сначала грубую и простую оценку
вероятности, взяв довольно сильное условие.
Предположим, что h(b)≥h(c)Pab≥Pac aS. Докажем, что также P(i)ab≥P(i)ac для любого i. Имеем
( i 1)
(i )
(i )
( i 1)
P a,b   P a, s P s ,b   P a , s P s ,c  P a ,c (поскольку
sS
sS
Ps,b≥Ps,c sS).
Из теоремы эргодичности [9] получаем, что
при количестве пройденных шагов, стремящемся
к бесконечности, вероятность попадания в то или
иное состояние не зависит от начального набора
X0. А из принятого здесь условия получаем, что
вероятность попадания в то или иное состояние
тем выше, чем выше соответствующее ему значение функции полезности h(X).
Однако полученной оценкой сложно воспользоваться, поскольку трудно построить такую
99
Программные продукты и системы
№ 4, 2013 г.
функцию G, которая удовлетворяла бы поставленным условиям. В связи с этим может быть предложено более мягкое начальное условие, которое
не ослабляет следствие.
Предположим, что изначально разрешены переходы не из каждого в каждое состояние, а только в некоторые из них и лишь для них выполняется сформулированное выше условие. Иными словами, h(b)≥h(c); Pab, Pac≠0Pab≥Pac aS. К
сожалению, для такого общего случая следствие
может и не выполняться.
Для выполнения следствия необходимо поставить вероятность перехода в определенное соответствие со значением функции полезности в искомом состоянии.
Пусть для каждого состояния a определено
множество соседних состояний S(a)={b | Pab≠0}.
Определим P ab  k ae h(b)  h( a ), bS(a). Коэффициент ka подбирается специально таким образом,
чтобы сумма вероятностей перехода из состояния
a в другие состояния равнялась 1. Для остальных
состояний вероятность перехода из состояния a
будет нулевой. Докажем, что для такой матрицы
перехода конечное условие будет выполняться.
Действительно,
(i ) h ( s )  h ( a )
h(b)  h( s )
( i 1)
(i )

k be
P a ,b  i 
P a , s P s ,b   k a e
sS ( a )|bS ( s )

 k
(i )
a
k be
Optimisation Problems. Proc. of IPROMS 2006 Conf., 2006,
pp. 454–461.
3. Raudenska L. Swarm-based optimization. Kvalita Inovacia
Prosperita. Quality Innovation Prosperity XIII/1 – 2009, no. 1,
pp. 45–51.
4. Замятина Е.Б. Современные теории имитационного
моделирования: спец. курс. Пермь: ПГУ, 2007. 119 с.
5. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения: сб. лекций молодеж. и науч. школ по
дискрет. матем. и ее приложениям. М.: МГУ, 2001. С. 87–117.
6. Богатырев М.Ю. Инварианты и симметрии в генетических алгоритмах // Искусственный интеллект: тр. XI национальн. конф. по искусствен. интеллекту с междунар. участием
«КИИ-2008». М.: Ленанд, 2008. Т. 1. Сек. 3.
7. Курейчик В.М., Лебедев Б.К. Определения и основные
понятия генетических алгоритмов // III Всерос. межвуз. конф.
молодых ученых СПбГУ ИТМО. URL: http://faculty.ifmo.ru/
csd/files/kureichik_v_m_lebedev_b_k_internet_lecture.pdf (дата
обращения: 13.12.2012).
8. Бурмистров М.Ю., Валиев М.К., Дехтярь М.И., Диковский А.Я. О верификации динамических свойств систем взаимодействующих агентов: тр. X национальн. конф. по искусствен. интеллекту с междунар. участием. М.: Физматлит, 2006.
9. Булинский А.В., Ширяев А.Н. Теория случайных процессов. М.: Физматлит, 2005. 408 с.
References
1. Valiyev M.K., Dekhtyar M.I. Vestnik Tver State Univ.
Seriya “Prikladnaya matematika” [The bulletin of TvSU. “Applied
Mathematics” Series]. 2008, no. 35 (95), pp. 9–22.
2. Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S.,
Zaidi M. Proc. of IPROMS 2006 Conf. 2006, pp. 454–461.
3. Raudenska L. Quality Innovation Prosperity XIII/1 – 2009,
pp. 45–51.
4. Zamyatina E.B. Sovremennyye teorii imitatsionnogo modelirovaniya: spetsialny kurs [Modern theories of imitation modeling: special course]. Perm, Perm State Univ. Publ., 2007 (in Russ.).
5. Kochetov Yu.A. Diskretnaya matematika i eyo prilozheniya. Sbornik lektsiy molodyozhnykh i nauchnykh shkol po diskretnoy matematike i eyo prilozheniyam [Discrete math and its applications. Lectures of youth and scientific schools on discrete math
and its applications]. Moscow, MSU Publ., 2001, pp. 87–117
(in Russ.).
6. Bogatyrev M.Yu. Trudy 11 nats. konf. po iskusstvennomu
intellektu s mezhdunar. uchastiem (KII-2008) [Proc. of 11th
national conf. on artificial intelligence with int. participation
(CAI-2008)]. 2008, Dubna, vol. 1, section 3.
7. Kureychik V.M., Lebedev B.K. 3 Vseross. mezhvuz. konf.
molodykh uchyonyh SPbGU ITMO [3rd all-Russian conf. of young
scientists SPbSu IFMO]. Available at: http://faculty.ifmo.ru/csd/files/kureichik_v_m_lebedev_b_k_internet_lecture.pdf (accessed 13
December 2012).
8. Burmistrov M.Yu., Valiev M.K., Dekhtyar M.I., Dikovskiy A.Ya. Trudy 10 nats. konf. po iskusstvennomu intellektu s
mezhdunar. uchastiem [Proc. of 10th national conf. on artificial
intelligence with int. participation]. Moscow, Fizmatlit Publ., 2006.
9. Bulinskiy A.V., Shiryaev A.N. Teoriya sluchaynykh protsessov [The stochastic processes theory]. Moscow, Fizmatlit Publ.,
2005 (in Russ.).
h (b )  h ( a )
.
Выделенная в скобках сумма представляет собой нормировочную константу. Таким образом,
для матрицы перехода после i шагов верно то же
представление элементов, что и для начальной
матрицы перехода. Из условий эргодичности получаем, что в возведенной в некоторую степень
матрицы перехода все элементы будут ненулевыми. Но из формулы для элементов матрицы перехода, возведенной в произвольную степень, получаем искомое условие h(b)≥h(c)Pab≥Pac aS.
Таким образом, для заданной функции g получаем
верность того следствия, что вероятность нахождения решения тем больше, чем больше значение
целевой функции.
Литература
1. Валиев М.К., Дехтярь М.И. Вероятностные мультиагентные системы: семантика и верификация // Вестн. ТГУ: сер.
Прикладная математика. 2008. № 35 (95). С. 9–22.
2. Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S.,
and Zaidi M. The Bees Algorithm – Novel Tool for Complex

Вниманию авторов!
Редакция журнала «Программные продукты и системы» руководствуется «Кодексом этики научных публикаций», разработанным и утвержденным Комитетом по этике научных публикаций.
Все поступающие в редакцию статьи проходят экспертизу. При выявлении плагиата публикация отклоняется без права доработки материалов, автор статьи заносится в черный список.
100
1/--страниц
Пожаловаться на содержимое документа