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

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

СУРГУТАНОВ ВЛАДИМИР ВЛАДИМИРОВИЧ

РАЗВИТИЕ МЕТОДОВ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ ДЛЯ МОДЕЛИРОВАНИЯ САМООРГАНИЗАЦИИ В ДЕЦЕНТРАЛИЗОВАННЫХ СОЦИАЛЬНЫХ И ТЕХНИЧЕСКИХ СИСТЕМАХ

05.13.01 - Системный анализ, управление и обработка информации, (промышленность) по техническим наукам

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

Волгоград - 2005

Работа выполнена в Камышинском технологическом институте (филиал) Волгоградского государственного технического университета

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

научный сотрудник Крушель Елена Георгиевна.

Официальные оппоненты: ДОктор технических наук, профессор

Резчиков Александр Федорович.

доктор технических наук, доцент Заболеева-Зотова Алла Викторовна.

Ведущая организация Таганрогский радиотехнический университет.

Защита состоится «Я» дз^кхиЬМ 2005г. в |X часов на заседании диссертационного совета Д 212.628.04 'при Волгоградском государственном техническом университете по адресу: 400131 Волгоград, пр. Ленина, 28, ауд.

т

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

Автореферат разослан «X/ » 2005г.

Ученый секретарь диссертационного совета ~ -■ Водопьянов В.И.

2Ш-Ч

3

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

Актуальность темы. Современный э тап развития естественных наук в изучении явлений различной природы обнаруживает схожие проблемы, решение которых ведет к выработке общей методологии исследования мира сложных систем. Единую причинную модель мира предлагает синергетика, с ее нелинейными моделями, аппаратом исследования причин неустойчивости, структурных изменений и явлений самоорганизации. Благодаря взаимному проникновению идей открывается перспектива дальнейшего развития научных знаний. Успешно происходит трансляция науки о сложном из неживой природы в проблематику анализа технических систем и динамики социальных сред.

Тем не менее, исследование процессов самоорганизации, проявление которых в системах макромира отличается большим разнообразием, затруднено ввиду недостаточной изученности свойств объектов, образующих элементы систем в таких средах. В результате модели конкретных приложений, например, социальных процессов (К.П. Иванов, А.К. Гуц, Ю.Б. Бахтин, В.В. Коро-бицин, В.В. Ляхов),либо ограничены рассмотрением когерентной (групповой) самоорганизации и связаны в первую очередь с полевыми и принципиально нелинейными моделями, либо вовсе ее не учитывают. Таким образом, назрела необходимость построения базовых моделей континуальной самоорганизации, тесно связанной с прогрессивной эволюцией индивидуальных элементарных открытых систем.

Широкие возможности моделирования самоорганизации имеются в гибридных системах. Имитационные модели развития здесь производятся в рамках методологии многоагентных систем (далее MAC), а популярным инструментом, воспроизводящим эволюционные процессы, служат генетические алгоритмы (далее ГА, J.H. Н olland). П ривлекательность ГА обусловлена их сильно нелинейным поведением, функционированием на грани порядка и хаоса. Препятствием на пути использования ГА как базовой модели самоорганизации является эффект предварительной сходимости (как яркое проявление отсутствия самоорганизации), в то время как естественным процессам, напротив, присуща живучесть и постоянное развитие.

Достаточное число публикаций посвящено исследованию ГА как средства оптимизации, поиску его оптимальной структуры и параметров. Известны способы снижения риска предварительной сходимости (JI.A. Гладков, В.В. Курейчик), обеспечиваемые интеллектуальной надстройкой, гибридизацией. Такие меры адекватны задачам оптимизации, но не приемлемы для задач моделирования процессов самоорганизации в децентрализованных системах.

Актуальность темы работы для решения теоретических вопросов заключается:

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

— в потребности адаптации методов эволюционных вычислений для моделирования систем эволюционной природы;

— в необходимости изучения и в разработке средств снижения риска предварительной сходимости ГА.

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

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

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

1. Разработана методика оценки процесса сходимости ГА для выявления потенциала самоорганизации алгоритма («живучесть» в условиях риска предварительной сходимости, способность «выходить из локальных ям»). Создан программный комплекс для исследования влияния параметров и структуры типовых моделей ГА на показатели качества сходимости и найден ряд алгоритмических решений улучшения данных показателей в рамках простого ГА (далее ПГА).

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

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

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

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

Методы исследований. Решение поставленных задач сопряжено с применением методологии MAC, методов оптимизации, статистической обработки данных, имитационного моделирования, объектно-ориентированного анализа и проектирования программных средств.

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

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

1. В рамках параллельного ГА обнаружены механизмы самоорганизации.

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

3. Спроектированы модели ГА, обнаруживающие автоколебания генотипов с динамическими аттракторами в кодируемом генами пространстве решений. Найдены алгоритмические решения по улучшению сходимости ПГА.

Практическая значимость результатов:

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

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

На защиту выносятся:

1. Базовые модели самоорганизации ГА, обеспечиваемой двумя различными структурами параллельного ГА: с переменной интенсивностью отбора и с внутренней целевой функцией.

2. Подход к моделированию механизмов самоорганизации децентрализованных систем в рамках методологии MAC и эволюционных вычислений.

3. Решения по улучшению сходимости ПГА, программный комплекс оптимальной настройки параметров и структуры типовых моделей ГА.

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

Внедрение.

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

2. Программный комплекс компьютерного моделирования комплиментарного этнического контакта внедрен в учебный процесс на кафедре «Истории и археологии» Волгоградского государственного университета

Апробация работы.

Основные результаты работы докладывались на IX и X международных конференциях «Математика. Компьютер. Образование» (Дубна 2002, Пущине 2003), I, II и (II Всероссийских конференциях «Прогрессивные технологии в обучении и производстве» (Камышин 2002, 2004, 2005), научном семинаре НИИ Археологии (Волгоград, ВолГУ 2003), конференции молодых ученых ( Волгоград, ВолгГТУ 2001), научном семинаре кафедры САПР ТРТУ (Таганрог 20051.

Объем л структура работы.

Работа состой! из четырех глав и двух приложений. Общий объем работы- страниц - 120, иллюстраций - 41, таблиц - 4.

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

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

В главе 1 приводится аналитический обзор методов моделирования социальных систем и методов эволюционных вычислений. Обзор проведен по следующей схеме: вначале описывается понятие и виды самоорганизации систем: когерентная (А. Пригожин) и континуальная (А.П. Руденко), затем анализируются модели с постоянной структурой и подчеркивается, что в них возможности моделирования ограничиваются лишь эффектами когерентной самоорганизации (параграф 1). Далее рассматриваются возможности моделирования континуальной самоорганизации и прогрессивной эволюции в гибридных системах, посредством построения MAC с использованием ГА. Указывается общий недостаток методологии MAC, связанный с трудностями обнаружения причин самоорганизации на фоне многих факторов, обуславливающих взаимодействие агентов (параграф 2). Далее рассматриваются оптимизационные структуры эволюционных вычислений, спроектированные на базе ГА с использованием синергетических и эволюционных принципов адаптации. Отмечается отсутствие моделей ГА с децентрализованной самоорганизацией (параграф 3). Далее рассматриваются методы параметрической адаптации ГА (параграф 4). Более подробно:

В параграфе 1 описываются способы построения моделей социальных систем: полевые (в фазовых пространствах), статистические (в пространственно-временном поле), стохастические (с уравнениями Ланжевена и Фокке-ра-Планка) и модели динамических систем (с уравнениями баланса). Приводится краткое описание разработок по моделированию этнических процессов (модель этнической системы А.К. Гуца; полевая модель взаимодействия этнических полей В.В. Коробицина; модели К.П. Иванова, использующие подход математической генетики и строящиеся исходя из тезиса о существовании гена пассионарности; модель рассеяния энергии Т.А. Айзатулина и по-пуляционной биологии В.В. Ляхова).

В параграфе 2 излагаются основы методологии и приводятся основные архитектуры MAC по B.C. Субраманяну. Описываются способы взаимодействия и виды агентов. Приводятся аспекты самоорганизации MAC: агенты взаимодействуют, реагируя на действия других агентов или исходя из своих внутренних целей, в результате система агентов обнаруживает сложное поведение, генерацию целей, отсутствующих в логике отдельно взятого агента.

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

Далее раскрывается тематика направления «искусственная жизнь», представляющего интерес с точки зрения моделирования эффектов самоорганизации в среде неинтеллектуальных агентов. Попутно излагаются модели целенаправленного адаптивного поведения В.Г. Редько, «Полимир» Ягера и «Sexual swimmers» Д. Вентреллы. Обобщаются примеры автоколебаний и живучести искусственных биоценозов при использовании ГА в качестве инструмента моделирования MAC.

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

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

Рассматриваются архитектуры параллельного ГА. Среди новых выделяются архитектуры с интеллектуальными надстройками, включая базы знаний с обратными связями и синтезом различных эволюционных парадигм (Дарвина, Ламарка, Фризе и др.).

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

В параграфе 4 описываются методы параметрической адаптации ПГА. Рассматриваются способы повышения его «живучести». Приводятся работы Д.И. Батищева и С.А. Исаева по оптимизации многоэкстремальных функций. В работах описываются различные модификации структуры ГА, включая варианты выбора селективной стратегии. Приводится обзор алгоритмов с переменным размером популяции Ю.Р. Цоя, многовариантные алгоритмы В.В. Курейчика. Сравниваются различные модификации и модели ГА. Вскрывается проблема баланса исследования и использования. Поднимается проблема сложности теоретического исследования сходимости, связанной с нелинейностью и наличием параллелизма в работе ГА и с недостатками ис-

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

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

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

Указываются результаты оценки ВС одной генерации (одного поколения) моделей ГА:

- простой ГА: tGA «(lc +lm+lr)-t ,

-параллельный ГА: tlSLAND CA *m (lc +lm+lr)-7,

— перезапускаемый ГА: ¡сне GA ~ +1)- / ■ f ,

где lc,lm,lr - численности промежуточных пулов кроссинговера, мутации и репродукции, т - количество «островов» параллельного ГА, / - численность популяции, S - среднее количество генераций до перезапуска и Г -среднее время вычисления значения функции пригодности (далее ФП). Затем модели ГА сравниваются по показателю ВС одной генерации:

'ISLAND_GA " tGA ■та tCHC_GA ' т{2$ + Фс +lm +lr)/l ■

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

1. Оценка дисперсии (в пространстве локусов) решений, представленных в 1-й генерации

\н

где оj - j-я особь популяции (1 х п строка, содержащая п значений ге-j /

нов), а о' = - среднее (в пространстве локусов) решений.

1М

2.Критерий близости к оптимуму

А(Р') = rrunjjoy - o0/),|j/ w'min,

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

Ставится задача комплексного анализа влияния параметров ГА на сходимость в рамках разработанной методики ее оценки. Выделяются подлежащие оптимизации параметры:

1. Численность популяции /.

2. Соотношение участия операторов: мутации 1т, кроссинговера 1С и репродукции 1Г.

3. Особенности селективной стратегии.

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

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

Выдвигается тезис о недостатках использования ПГА как средства моделирования процессов самоорганизации ввиду «скатывания в локальные ямы» (предварительная сходимость). Поднимается проблема неэффективности мутаций в рамках вероятностного отбора (высокий уровень мутации ухудшает сходимость). Далее проводится анализ причин неэффективности мутаций в рамках вероятностного отбора, в котором вероятность попадания особи в новое поколение пропорциональна значению ФП ее генотипа.

Математически этот факт выражается заданием линейной зависимости вероятности отбора Р(о,) от значения ФП у, = f{o¡) особи о,:

f(y¡ = f(°i))- к-y,+b , где к - интенсивность отбора, b - нормировочный коэффициент.

Далее на качественном уровне моделируется ситуация вероятностного отбора одной особи популяции 0\,02,..,0¡, с учетом нелинейности, обеспечиваемой «оврагом» функции. В такой ситуации ГА приходится работать в условиях малых отличий пригодности особей: V¡j(y¡ ~ У¡) ■ Для достижения максимального контраста вероятностей отбора осо бей и соответственно ус-

корения сходимости необходимо увеличивать к, а Ь корректировать для

I

выполнения условия нормировки вероятностей: ^ =1.

/=1

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

В качестве тестовой функции используется нелинейная ФП целочисленного аргумента, определенная на отрезке [\\хор1]:

| «з,х, при х е |1,0.5хор, \

Х ~ [0.5а,хо/)( + а2{х-0.5дгор,)при (о ах » а2 (условие наличия «оврага»).

Рассматривается вариант нахождения в «локальной яме», когда П(Р') = 0, т.е. популяция Р' состоит из / одинаковых особей с некоторым генотипом хк.

Моделируется запуск оператора вероятностного отбора и составляется закон распределения случайной величины X: «в результате отбора одной особи, выбран генотип г», где ¡' е \,2,..,хор(:

каХ1 + Ь, при / е \},0.5хор11 к(о.5а[Хор, + а2(/ - 0.5хор1))+ Ь, при / е (о.5хор1,хк), к{0.5а]Хор, + а2[1- 0.5хор1 )&хор1 +1)+ Ь, при ¡ = хк, к(о.5аххор1 + а2(' - 0-5*ор,))+ Ь, при / е (хк^сор1]

Далее ставится задача максимизации скорости сходимости J = Р(Х > хк) -» шах, на множестве пар {к,Ь} с ограничениями (по смыслу термина вероятность)

Хрр!

У>(Х = 0 = 1. =

Р(Х = о =

Решение данной задачи при условии а\! а2,хор1 »1 дает следующую

оценку вероятности выбора лучшего решения:

Р(Х>хк) =

1-

хк

Хор1,

На основе анализа данного выражения делается вывод о неэффективности вероятностного («рулеточного») отбора, который при хк = 0.5хор1 дает

Р(Х > хк) « 1 /6, что совпадает с аналогичными расчетами для чисто случайного отбора. Причиной такого недостатка указывается ограниченность в выборе значений киЬ,т. к. «особи-мутанты» с низким значением ФП не позволяют уменьшать значение Ь, и ограничение Р(Х = 1) = 0 становится лимитирующим.

Предлагается улучшить показатель Р(Х > хк) за счет фильтрации мутаций. Предлагается использовать в отборе лишь тех «особей-мутантов», для которых мутация дала улучшение значения ФП. Такой подход позволяет избежать появления особей с очень низкой пригодностью. Именно такие особи нивелируют преимущество вероятностного отбора, т. к. не позволяют задавать большие отрицательные значения Ь, тем самым снижая контраст пргод-ностей особей.

Глава 3 посвящена развитию идей эволюционных вычислений для решения задач моделирования механизмов самоорганизации децентрализованных систем.

В параграфе 1 описывается идея построения адаптивного ГА.

Выдвигается тезис о решающем значении двух процессов в задаче «выхода из локальных ям»: поддержание генетического разнообразия и направленный пВ качестве средств управления данными процессами предлагается использовать два механизма: динамическое изменение интенсивности отбора и направленная (не случайная) мутация. Далее обосновывается невозможность оптимизации данных механизмов вне реального времени функционирования ГА и выдвигается тезис о необходимости их самоорганизации посредством выбора надлежащей архитектуры ГА.

В параграфе 2 предлагаются архитектуры децентрализованной самоорганизации ГА. В качестве архитектуры, обеспечивающей адаптивное определение интенсивности отбора, предлагается параллельный («островной») ГА, где г'-й «остров» функционирует с коэффициентом интенсивности отбора £(/). Работа ГА моделируется на «овражной» функции, в процессе оптимизации которой ГА переживает два этапа: первый, начальный этап предполагает оптимальную интенсивность отбора к -1, второй (в области «оврага») -большую интенсивность к = 1.5 (рис.1).

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

£ = 1.5 достигает «оврага» за время Т + аТ ( а < 1), в то время как автономная его работа позволила бы достичь второго этапа за время 2Т > (1 + а)Т. Далее лидер меняется - им становится «остров» с интенсивностью отбора А = 1.5.

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

Далее вводятся понятия, требуемые для описания второй архитектуры, обеспечивающей самостоятельный выбор направления поиска. Мутационной последовательностью (далее МП) назван ряд целенаправленных мутаций, возникающих в последовательных генерациях ГА, ведущий к изменению аттрактора сходимости всего генома популяции Далее вводится понятие внутренней целевой функции (далее ЦФ), а именно функция пригодности

вида /(о^) = ~{pJ - o\oJ - дУ, где о] - строка, кодирующая генотипу'-й особи, о - средний генотип популяции.

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

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

В качестве архитектуры, обеспечивающей адаптивный выбор МП, предлагается использовать параллельный ГА (рис. 2), т «островов» которого функционируют с внутренней ЦФ /т, и поставляют особей в пул миграции. Наряду с данными «островами» функционирует ГА с внешней ЦФ /ои,, который использует особей пула для направленной коррекции генома своей популяции.

«Острова» с внутренней ЦФ

/

Общий пул \ 21. п

Рис. 2. Архитектура параллельного ГА с варьированием направления поиска.

Далее описывается архитектура (рис. 3), имеющая комбинированную структуру. Основная идея состоит в использовании смешанной ФП в виде /(а) = а£ои( + (1 - а)_/)„, где а - весовой коэффициент, 0 < а < 1.

/(«О Д«2) /(«;) Я«т = 1) -——

Общий пул

Рис. 3. Архитектура параллельного ГА с самоорганизацией.

В процессе работы такого ГА происходит взаимная направленная коррекция геномов популяций-«островов» за счет обмена особями, при этом динамические аттракторы функционируют как с высоким уровнем степени сво-

боды (на грани порядка и хаоса) для малых а , так и с низким, для а, близких к единице.

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

Для моделирования социальных систем предлагается структура, полученная модификацией архитектуры параллельного ГА с самоорганизацией, когда в системе отсутствует внешняя ЦФ: для всех «островов» а = О.

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

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

В параграфе 1 описаны результаты построения модели этнической системы. Отмечается синергетическая природа пассионарной теории этногенеза Л.Н. Гумилева (далее ПТЭ). Вводятся основные моделируемые понятия: стереотип поведения (далее СП) как вектор, длина и направление которого определяется соответственно уровнем и типом пассионарности человека. Вводится векторное поле Р(xl,yj) - средний СП членов этноса в точке ландшафта с координатами (*,-,.Уу). Вводится вектор-функция 7, характеризующая СП, который требуется для максимальной адаптации членов этноса к ландшафту в точке , у^). Отмечается, что в гомеостазе

В модельном представлении векторное поле Р(х^у^ формируют популяции ГА . Таким образом, имеется л х £ прямоугольная сетка параллельно функционирующих ГА (/ е 1,2..г; у е 1,2.^), обменивающихся с соседними «островами» особями посредством оператора миграции.

Внутриэтнические факторы этногенеза моделируются кроссинговером и мутациями - составляющими ГА для популяции Р^. Составляющие вектора

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

Межэтнические факторы этногенеза моделируются посредством взаимодействия между популяциями, занимающими соседние точки ландшафта. Для этого популяции обмениваются своими членами («особями-мигрантами»), которые либо выживают в новых условиях, либо отторгаются по принципам, сходным с принципами естественного отбора. Перемешивание популяций отражается на динамике функции Р(xí,yJ) .

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

Р(х,у)

I --'Чиии^-' Цх.у) Рис.4. Взаимодействие популяций и ландшафтов.

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

пользователям } -й группы.

Целью агента является минимизация собственных затрат:

■А Го, При X: ; (/) > ,

I,(Ь,0 = а, (/) ■ * ■ У(О + а-О-*/(0)> где ог,(/) = И у "т -

[ ' р и(' 1™

признак выбира агентом альтернативы оплаты, х\т1 «пороговый трафик», определяет преимущество перехода либо на повременный режим, либо на режим абонентской платы: Х||т = а/Ь, Ь - стоимость минуты, а - фиксированная абонентская плата.

Взаимодействие агентов происходит сменой итерации матрицы инцидентности ] -> . Для этого для каждой пары агентов в; - а? вычисляется произведение потерь от полной взаимной переброски трафиков: В~щ,а2 = 0~а2 ■ Потери агента пары (например, а\) равны

г . , М

D~a, =

/

Ли- ^"^'З-*1!

где /(х,) функция субъективной пользы сброса единицы трафика, л - отклонение суммарной длительности трафика агента от . Далее для пары а[-а'2 с наименьшим значением произведения субъективного вреда 0~аьа2 вычисляется субъективная польза от передачи своего трафика вто-

рому агенту:

(

D+a; =

/

i'=l,iVa!

Ol

, аналогично для a2.

Агент (пусть a[) пары a\-a'2 с большим значением субъективной пользы D+ пытается перебросить трафик второму агенту, причем если превышено критическое значение вреда D~a'2 > f lim то трафик урезается = (0 < Coef < 1). Если же £Га; < D~\im, то тра-

фик перебрасывается [fs+i] = 0, = ха'г,а\ ['J + ха\,а'г{1Л ■

' Процесс итерирования продолжается до достижения стационарного состояния матрицы инцидентности трафика. Значение прибыли, полученной узлом связи рассчитывается суммой прибыли по итерациям J(b) = = F(X(ts)) и зависит от динамики F матрицы инцидентно-

сти.

Процесс оптимизации прибыли 1(Ь,() - ^1,(6, г) узла связи заключается

1=1

в установлении оптимального значения Ъ при фиксированном значении а. Решение задачи производится поисковым методом дихотомии.

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

ЗАКЛЮЧЕНИЕ

Основные результаты работы состоят в следующем:

1. На основании обзора выявлена потребность в моделировании самоорганизации в социальных и технических системах и предложено адаптировать методы эволюционных вычислений (ГА) для описания механизмов децентрализованной самоорганизации и прогрессивной эволюции.

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

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

- создать методику исследования эффективности ГА и влияния каждого из генетических операторов на их сходимость;

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

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

3. Предложены новые методы структурной адаптации в рамках параллельного ГА за счет самоорганизации алгоритма. Реализация данных методов позволила:

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

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

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

4. Созданные алгоритмы применены для решения прикладных задач моделирования:

- комплиментарного этнического контакта;

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

Основное содержание работы отражено в 6 публикациях:

1. Сургутанов В.В. Модель эволюции этносов и ее реализация на базе генетических алгоритмов [Текст] / Крушель Б.Г. Сургутанов В.В. // «Математика, Компьютер, Образование» сб. науч. тр. / МОО «Женщины в науке и образовании». - М-Ижевск, 2002. - Часть 1. - С. 308317.

2. Сургутанов В.В. Моделирование процессов этногенеза с учетом взаимодействий на основе фактора взаимной адаптации [Текст] / Сургутанов В.В. // «Математика. Компьютер. Образование» сб. науч. тр. / НИЦ «Регулярная и хаотическая динамика». - М.-Ижевск, 2003. - 10. -С.125-135.

3. Сургутанов В.В. Мультиагентный подход к моделированию процессов эволюционирования систем макроуровня [Текст] / Сургутанов В.В. // «Математика. Компьютер. Образование» тезисы XI международной конференции / МОО «Женщины в науке и образовании». -М.-Ижевск, 2004. - С.158.

4. Сургутанов В.В. Постановка задачи идентификации интегральных характеристик мультиагентных систем [Текст] / Сургутанов В.В. // Прогрессивные технологии в обучении и производстве. Материалы Всероссийской конференции / Камышинский технологический институт (филиал) ВолгГТУ. - Камышин, 2004. - С. 161-164.

5. Сургутанов В.В. Моделирование, анализ сходимости и оптимизация мутаций простого генетического алгоритма [Текст] / Сургутанов В.В. Ершов А.Я. // Инновационные технологии в обучении и производстве: Материалы III всероссийской конференции 1 КТИ ВолгГТУ. -Камышин, 2005. - т. 2. - С. 90-93.

6. Сургутанов В.В. Настройка параметров регуляторов с использованием генетических алгоритмов [Текст] / Сургутанов В.В. Ершов А.Я. // Материалы III всероссийской конференции / КТИ ВолгГТУ. - Камышин, 2005. - т. 2. - С. 93-97.

№ 2 4 5 7 в

РНБ Русский фонд

2006-4 24450

Сургутанов Владимир Владимирович

РАЗВИТИЕ МЕТОДОВ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ ДЛЯ МОДЕЛИРОВАНИЯ САМООРГАНИЗАЦИИ В ДЕЦЕНТРАЛИЗОВАННЫХ СОЦИАЛЬНЫХ И ТЕХНИЧЕСКИХ СИСТЕМАХ

Автореферат

Подписано в печать 18.11.2005

Тираж 110 экз. Заказ 5428

Отпечатано ООО «НТС», Волгоградская обл., г. Камышин ул. Феоктистова, 53

ВВЕДЕНИЕ.

1 АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ МОДЕЛИРОВАНИЯ САМООРГАНИЗУЮЩИХСЯ СИСТЕМ.

1.1 Проблема описания самоорганизации в рамках базовых моделей сложных систем.

1.1.1 Сущность явления и виды самоорганизации.

1.1.2 Недостатки имеющихся базовых моделей сложных систем.

1.2 Поиск базовых алгоритмов самоорганизации в имитационных моделях методологии многоагентных систем.

1.2.1 Принципы построения и механизмы самоорганизации в многоагентных системах.

1.2.2 «Искусственная жизнь» и генетические алгоритмы как средство моделирования эволюции.

1.3 Оптимизационные структуры эволюционных вычислений, основанные на принципах самоорганизации.

1.3.1 Неоднородные архитектуры генетического поиска.

1.3.2 Однородные архитектуры генетического поиска.

1.4 Параметрическая адаптация в генетических алгоритмах.

1.4.1 Управление уровнем генетического разнообразия.

1.4.2 Управление направленностью генетического разнообразия.

1.5 Выводы.

2 УЛУЧШЕНИЕ АДАПТАЦИОННЫХ СВОЙСТВ ПРОСТОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

2.1 Методика оценки эффективности генетического алгоритма. 31 2.1.1 Оценка вычислительной сложности моделей генетического алгоритма.

-32.1.2 Оценка процесса сходимости и качества решения, найденного генетическим алгоритмом.

2.1.3 Использование компьютерного моделирования для анализа свойств генетических алгоритмов.

2.2 Улучшения свойств простого генетического алгоритма как средства оптимизации.

2.2.1 Причины неэффективности вероятностного отбора.

2.2.2 Пути повышения эффективности мутаций для вероятностного отбора.

2.2.3 Анализ эффективности улучшенного оператора мутаций

2.3 Выводы.

3 РАЗВИТИЕ ИДЕЙ ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ ДЛЯ МОДЕЛИРОВАНИЯ МЕХАНИЗМОВ САМООРГАНИЗАЦИИ.

3.1 Идея адаптивного генетического алгоритма.

3.2 Невозможность оптимизации интенсивности отбора.

• 3.3 Невозможность оптимизации направления поиска.

3.4 Генетический алгоритм с внутренней целевой функцией.

3.5 Архитектуры самоорганизации генетического алгоритма.

3.6 Формализация алгоритма самоорганизации генома.

3.7 Выводы.

4 РЕШЕНИЕ ПРИКЛАДНЫХ ЗАДАЧ МОДЕЛИРОВАНИЯ.

4.1 Моделирование процессов этногенеза.

4.1.1 Формальное описание модели.

4.1.2 Уточнение математической модели.

4.1.3 Результаты моделирования.

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

4.2.1 Актуальность введения альтернативной тарификации.

4.2.2 Описание задачи в терминах иерархического управлення92 « 4.2.3 Сжатие данных о распределении трафика.

4.2.4 Многоагеитная система взаимодействия абонентов сети

4.2.5 Результаты оптимизации на модели.

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

Актуальность темы. Тем не менее, исследование процессов самоорганизации, проявление которых в системах макромира отличается большим разнообразием, затруднено ввиду недостаточной изученности свойств объектов, образующих элементы систем в таких средах. В результате модели конкретных приложений, например, социальных процессов [2, 19, 20, 22, 29, 40], либо ограничены рассмотрением когерентной (групповой) самоорганизации и связаны в первую очередь с полевыми и принципиально нелинейными моделями, либо вовсе ее не учитывают. Таким образом, назрела необходимость построения базовых моделей континуальной самоорганизации, тесно связанной с прогрессивной эволюцией индивидуальных элементарных открытых систем.

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

Достаточное число публикаций посвящено исследованию ГА как средства оптимизации, поиску его оптимальной структуры [12,13,32,38,44] и параметров [5,35,72]. Известны способы снижения риска предварительной сходимости, обеспечиваемые интеллектуальной надстройкой, гибридизацией. Такие меры адекватны задачам оптимизации, но не приемлемы для задач моделирования процессов самоорганизации в децентрализованных системах.

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

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

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

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

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

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

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

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

Методы исследований. Решение поставленных задач сопряжено с применением методологии MAC, методов оптимизации, статистической обработки данных, имитационного моделирования, объектно-ориентированного анализа и проектирования программных средств.

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

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

1. В рамках параллельного ГА обнаружены механизмы самоорганизации.

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

3. Спроектированы модели ГА, обнаруживающие автоколебания генотипов с динамическими аттракторами в кодируемом генами пространстве решений. Найдены алгоритмические решения по улучшению сходимости ПГА.

Практическая значимость результатов:

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

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

На защиту выносятся:

1. Базовые модели самоорганизации ГА, обеспечиваемой двумя различными структурами параллельного ГА: с переменной интенсивностью отбора и с внутренней целевой функцией.

2. Подход к моделированию механизмов самоорганизации децентрализованных систем в рамках методологии MAC и эволюционных вычислений.

3. Решения по улучшению сходимости ПГА, программный комплекс оптимальной настройки параметров и структуры типовых моделей ГА.

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

Внедрение.

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

2. Программный комплекс компьютерного моделирования комплиментарного этнического контакта внедрен в учебный процесс на кафедре «Истории и археологии» Волгоградского государственного университета.

Апробация работы.

Основные результаты работы докладывались на IX и X международных конференциях «Математика. Компьютер. Образование» (Дубна 2002, Пущино 2003), I, II и III Всероссийских конференциях «Прогрессивные технологии в обучении и производстве» (Камышин 2002, 2004, 2005), научном семинаре НИИ Археологии (Волгоград, ВолГУ 2003), конференции молодых ученых (Волгоград, ВолгГТУ 2001), научном семинаре кафедры САПР ТРТУ (Таганрог 2005).

Основное содержание работы отражено в четырех главах и трех приложениях. В первой главе приводится аналитический обзор методов моделирования самоорганизующихся систем. Вторая глава посвящена параметрической адаптации ГА к задачам моделирования эволюционных процессов. В третьей главе разрабатываются новые архитектуры ГА для описания процессов самоорганизации в децентрализованных системах. В четвертой главе приводится постановка прикладных задач моделирования социальной системы и технической задачи оптимизации с привлечением разработанных и стандартных алгоритмов эволюционных вычислений соответственно. В приложениях приводится материал, поясняющий устройство ГА, расчеты вычислительной сложности (ВС) генерации, обзор концепций ПТЭ и эксперименты комплексного анализа сходимости основных моделей ГА. к Результаты работы опубликованы в [54-59].

Автор считает своим приятным долгом выразить благодарность Елене Георгиевне Крушель за вклад в формирование научного мировоззрения, Валерию Анатольевичу Камаеву и Сергею Алексеевичу Фоменкову за обсуждение работы и ценные рекомендации по ее содержанию и представлению.

Основные результаты работы состоят в следующем:

1. На основании обзора выявлена потребность в моделировании самоорганизации в социальных и технических системах и предложено развить методы эволюционных вычислений (ГА) для описания механизмов децентрализованной самоорганизации и прогрессивной эволюции.

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

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

- создать методику исследования эффективности ГА и влияния каждого из ГО на их сходимость;

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

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

3. Предложены новые методы структурной адаптации в рамках параллельного ГА за счет самоорганизации алгоритма. Реализация данных методов позволила:

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

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

4. Созданные алгоритмы применены для решения прикладных задач моделирования: комплиментарного этнического контакта;

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

-102

- 100-ЗАКЛЮЧЕНИЕ

1. Айзатулин Т.А. Теория России. Геоподоснова и моделирование. / М. 1999. 70с.

2. Аниконов Ю. Е. Математическое моделирование этнических процессов // Математические проблемы экологии. / Новосибирск: Ин-т математики, 1994. С.3-6.

3. Ахромеева Т. С., Курдюмов С. П., Малинецкий Г. Г., Самарский А. А. Нестационарные структуры и диффузионный хаос. / М.: Наука. 1992.

4. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов // Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании". / Воронеж, ВГТУ, 1997. С.4-17.

5. Бромлей Ю.В. Этнос и этнография. / Наука. Москва, 1973. 280с.

6. Бурцев М.С., Гусарев Р.В., Редько В.Г. Модель эволюционного возникновения целенаправленного адаптивного поведения 1. Случай двух потребностей. / М.: Препринт ИПМ РАН, 2000, N 43.

7. Бурцев М.С., Гусарев Р.В., Редько В.Г. Модель эволюционного возникновения целенаправленного адаптивного поведения 2. Исследование развития иерархии целей. / М.: Препринт ИПМ РАН, 2000, N43.

8. Бюргер А., Гнатюк В.И., Литвиненко В.И., Ткачук А.А. Применение распределенного генетического алгоритма при решениизадачи об упаковке в контейнеры // Перспективные информационные технологии и интеллектуальные системы. / -С.11-15.

9. Валиев М.К., Дехтярь М.И., Диковский А .Я. О сложности верификации асинхронных многоагентных систем. // Труды П-го Межд. научно-практического семинара "Интегрированные модели и мягкие вычисления в искусственном интеллекте". / Коломна, 2003. С.69-75.

10. Гладков JI.A., Зинченко JI.A., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин С.Н. Методы генетического поиска. // Научное издание, под редакцией В.М. Курейчика. / Таганрог: Изд-во ТРТУ, 2002. 122с.

11. B.М. Курейчика. / Таганрог. Изд-во ТРТУ. 2003. -150с.

12. Голубин А.В. Определение параметров генетического алгоритма с помощью программного комплекса "gensearch" // // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2004, №3 (19). -С.42-47.

13. Гумилев Л.Н. От Руси до России. / С-Пб.: ACT 2003г. 415с.

14. Гумилев Л.Н. Этногенез и биосфера Земли. / Л., 1989. 496 с.

15. Гуц А. К. Математическая модель этногенеза // Ученый совет мат.фак. ОмГУ. / Деп. в ВИНИТИ 20.07.1994, N 1885-В94. 18с.

16. Гуц А.К., Коробицин В.В., Лаптев А.А., Паутова Л.А., Фролова Ю.В. Математические модели социальных систем: // Учебное пособие. / Омск: Омск. гос. ун-т, 2000. -256с.

17. Дегтерев А.С., Канашкин Ф.В., Сумароков А.Д. Обобщение генетических алгоритмов и алгоритмов схемы МИВЕР // Электронный журнал "Исследовано в России", /стр. 1658-1665, 2004. http://zhurnal.ape.relarn.ru/articles/2004/153.pdf.

18. Иванов К.П. Проблемы этнической географии / Под ред. А.И. Чистобаева. / СПб.: Изд. СПбГУ, 1998. 216с.

19. Каган М.С. Синергетическая парадигма диалектика общего и особенного в познании различных сфер бытия // Синергетическая парадигма. Нелинейное мышление в науке и искусстве. / М., 2002. С. 15-21.

20. Калашников Р.С. Повышение эффективности генетического поиска. // Сборник статей. Перспективные информационные технологии и интеллектуальные системы №4 / 2004. С. 43-45.

21. Капица С. П., Курдюмов С. П., Малинецкий Г. Г. Синергетика и прогнозы будущего. / М.: Наука, 1997.

22. Колесов Ю. Б., Сениченков Ю. Б. Компьютерное моделирование в научных исследованиях и образовании. // Электронный Интернет журнал Exponenta Pro Математика в приложениях. №1 (1) / 2003. С-4.

23. Колесов Ю. Б., Сениченков Ю. Б. Компьютерное моделирование динамических систем // Научнотехнические ведомости СПбГТУ. / 2002. -№ 3. С.93-102

24. Коробицин В.В. Модель территориального распределения пассионарной энергии этноса // Математические структуры и моделирование. / Омск, 2000. -№5. -С.44-53.

25. Косоруков А. Л. Разработка моделей, методов и алгоритмов синтеза структур обмена ресурсов. // Диссертация на соискание ученой степени кандидата технических наук. / 05.13.12. ИГЭУ. Иваново. 1995.

26. Курейчик В. В. Перспективные архитектуры генетического поиска // Программные продукты и системы, № 3., 1998, -С.47-48.

27. Курейчик В.В., Неупокоева Н.В. Перспективные технологии решения оптимизационных задач. // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2003, №2 (14). -С.79-82.

28. Курейчик В.В. Построение архитектуры комбинированного поиска для размещения элементов ЭВА. // Перспективные информационные технологии и интеллектуальные системы. / -С. 51.

29. Курейчик В.М. Генетические алгоритмы // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2000, №1(1).

30. Курейчик В.М., Зинченко Л.А. Многоальтернативные генетические алгоритмы поиска экстремума функции. // Известия академии наук. Теория и системы управления. // 2003. -№4.

31. Курейчик В.М., Зинченко Л.А. Эволюционное моделирование с использованием численно-аналитических моделей. // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2001, №2 . -С.30-39.

32. Курейчик В.М., Зинченко JI.A., Хабарова И.В. Исследование динамических операторов в эволюционном моделировании // Перспективные технологии С. 65.

33. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. // Монография. / Таганрог: Изд-во ТРТУ, 2000. -192с.

34. Лебедев О.Б. Глобальная трассировка на основе генетической эволюции// Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2000, №2.

35. Ляхов В.В. Этногенез как динамическая система. // Информационный бюллетень Ассоциации "История и компьютер", N 30, июнь 2002.

36. Минкин Ю.И. Построение, исследование и применение конкурентного самоорганизующегося генетического алгоритма // Автореферат диссертации на соискание ученой степени канд. техн. наук / 05.13.01.-М., 2000.-19с.

37. Мухлаева И.В. Решение задачи одномерной упаковки с помощью параллельного генетического алгоритма. // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2001, №4.

38. Наместников A.M. Эффективность генетических алгоритмов для задач автоматизированного проектирования // Известия РАН. Теория и системы управления. / 2002. N2. - С. 127-133.

39. Неупокоева Н.В. Об одной архитектуре генетического поиска // // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2002, №3 (15). -С.32-35.

40. Николис Г., Пригожин И. Самоорганизация в неравновесных системах. /М.: Мир, 1979. -512с.

41. Паклин Н.Б., Сенилов М.А., Тененев В.А. Интеллектуальные модели на основе гибридного генетического алгоритма с градиентнымобучением лидера // Искусственный интеллект. / Донецк: Наука i освгга. 2004. №4. - С.159-168.

42. Редько В.Г. Эволюционная кибернетика. /М.: Наука, 2001. -156с.

43. Руденко А.П. Самоорганизация и прогрессивная эволюция в природных процессах в аспекте концепции эволюционного катализа. // Росс. Хим. журн. / 1995. -Т.39. -N2. С.55-71.

44. Силютин Д.С. Применение многоагентных технологий в организации генетического поиска изоморфной подстановки. // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2003, №2(14). -С.48-54.

45. Соловьев С.А. Математическое моделирование динамики инвестиций вдали от насыщения рынка. / Препринт, институт прикладной математики РАН., Москва. 2001.

46. Сороколетов П.В. методы адаптации в задачах компоновки // Перспективные информационные технологии и интеллектуальные системы. / Таганрог: Изд-во ТРТУ, 2004, №1 (17). -С.27-30.

47. Сургутанов В.В. Модель эволюции этносов и ее реализация на базе генетических алгоритмов / Крушель Е.Г. Сургутанов В.В. // «Математика,

48. Компьютер, Образование» сб. науч. тр. / МОО «Женщины в науке и образовании». М-Ижевск, 2002. - Часть 1. - С. 308-317.

49. Сургутанов В.В. Настройка параметров регуляторов с использованием генетических алгоритмов / Сургутанов В.В. Ершов А.Я. // Материалы III всероссийской конференции / КТИ ВолгГТУ. Камышин, 2005.-т. 2.-С. 93-97.

50. Тарасов В.Б. Восходящее и нисходящее проектирование многоагентных систем. // Проблемы управления и моделирования в сложных системах. Труды международной конференции. / Самара, Самарский научный центр РАН. 1999. С.268-274.

51. Турчин В.Ф. Феномен науки. Кибернетический подход к эволюции. / М.: Наука, 1993. 295с. (1-е изд).

52. Хакен Г. Синергетика. / М.: Мир, 1980. -404с.

53. Чипига А.Ф., Воронкин Р.А. Оператор кроссинговера в мажоритарном генетическом алгоритме. // Вестник СевКавГТУ Серия «Физико-химическая», № 1 (8), 2004.

54. Эйген М. Самоорганизация материи и эволюция биологических макромолекул. /М.: Мир. 1973. -216с.

55. Ackley D., Littman М. Interactions between learning and evolution. // Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S. (Eds.) Artificial Life II. Reading, MA / Addison-Wesley, 1992, pp.487-509.

56. Adami C., Brown C.T. Evolutionary learning in the 2D Artificial Life system «Avida» // In Artificial Live IV Cambridge, MA / MIT Press. 1994. p.377.

57. Altenberg L. Genom growth and evolution of genotype-phenotype map, Institute of statistic and decision-making , / Duk University. Darhem. U.S.A.

58. Baker R. Genetic Algorithms in Search and Optimization. // Financial Engineering News. / July 1998.

59. T. Blickle, L. Thiele. A Comparison of Selection Schemes used in Genetic Algorithms (2nd Edition). TIK-Report No. 11, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, 1995.

60. Dawkins R. The Evolution of Evolvability. // Artificial Life Proceedings. / Addison-Wesley 1989 pp. 201-220.

61. Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning. / Addison-Wesley Pub. Co. 1989.

62. Goldberg D.E. Sizing populations for serial and parallel genetic algorithms. // In J.D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms. / 1989 pp. 70-79.

63. Goldberg D.E., Bridges C. L. An analysis of a reordering operator on a GA-hard problem. // Biological Cybernetics. / 62. pp. 397-405.

64. Goldberg D.E., Deb K. A comparative analysis of selection schemes used in genetic algorithms. // In G.J.E. Rawlins, editor, Foundations of Genetic Algorithms, / volume 1, pp. 69-93, San Mateo, CA, 1991.

65. Goldberg D.E., Smith R.E. Nonstationary function optimization using genetic algorithms with dominance and diploidy. // Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms. / pp. 59-68.

66. Holland J.H. Adaptation in Natural and Artificial Systems. // MIT Press. // Cambridge, MA, 2nd edition, 1992.

67. Holland J.H., Reitman J.S. Cognitive systems based on adaptive algorithms. // In D.A. Waterman F. Hayes-Roth (Eds.), Pattern-directed inference systems, /pp. 313-329. New York: Academic Press.

68. Koza J. Genetic Programming / Banzhaf W., Chellapilla K., Deb K., Dorigo M., Fogel D., Garzon M., Goldberg D., Iba H., Riolo R. / 1998.

69. Langton C.G. Artificial life, volume 1, Santa Fe Institute Studies in the Sciences of Complexity. / Addison-Wesley, Santa Fe, NM, 1989, pp. 1-47.

70. Mauldin M. L. Maintaining diversity in genetic search. // Proceedings of the National Conference on Artificial Intelligence. / pp. 247-250.

71. Skobelev P.O. Holonic Systems Simulation // Proc. of the 2nd International Conference "Complex Systems: Control and Modelling Problems". Samara, June 20-23. / 2000. p. 73-79.

72. Smith R.E. Adaptively resizing populations: An algorithm and analysis. // Proceedings of the Fifth International Conference on Genetic Algorithms. / p. 653.

73. Smith R.E. An investigation of diploid genetic algorithms for adaptive search of nonstationary functions (Masters thesis and TCGA Report No. 88001). // Tuscaloosa: University of Alabama, The Clearinghouse for Genetic Algorithms.

74. Subrahmanian V.S. Heterogeneous Agent Systems / Bonatti P., Dix J. et al. // MIT Press. / 2000.

75. Ventrella J. Sexual Swimmers (Emergent Morphology and Locomotion without a Fitness Function). From Animals to Animats. // MIT Press / 1996. pp. 484-493

76. Vittikh V.A., Skobelev P.O. Multi-Agent Systems for Modelling of Self-organisation and Co-operation Processes // Proceedings of XIII International Conference on Artificial Intelligence in Engineering. / Ireland, Galway, 1998. pp. 25-30.

77. Vlassis N. A Concise Introduction to Multiagent Systems and Distributed AI. / University of Amsterdam. 2003.

78. Yaeger L., Computational Genetics, Physiology, Learning, Vision, and Behavior or Poly Word: Life in a New Context. // Langton, C. G. (ed). Artificial Life III. / Addison-Wesley, 1994. pp. 263-298.

79. СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ

80. MAC многоагентная система,1. ГА генетический алгоритм,

81. ПГА простой генетический алгоритм,

82. ВС вычислительная сложность,

83. ПТЭ — пассионарная теория этногенеза,

84. ЭОС элементарная открытая система,1. ЦФ целевая функция,1. ГО генетический оператор,1. ФП функция пригодности,

85. ДСВ — дискретная случайная величина,1. ЛРУ линия равного уровня,1. СП стереотип поведения,1. РУС районный узел связи,1. СВ случайная величина.