Содержание к диссертации
Введение
1 Аналитический обзор методов моделирования самоорганизующихся систем 11
1.1 Проблема описания самоорганизации в рамках базовых моделей сложных систем 12
1.1.1 Сущность явления и виды самоорганизации 13
1.1.2 Недостатки имеющихся базовых моделей сложных систем 14
1.2 Поиск базовых алгоритмов самоорганизации в имитационных моделях методологии многоагентных систем 17
1.2.1 Принципы построения и механизмы самоорганизации в многоагентных системах 17
1.2.2 «Искусственная жизнь» и генетические алгоритмы как средство моделирования эволюции 19
1.3 Оптимизационные структуры эволюционных вычислений, основанные на принципах самоорганизации 21
1.3.1 Неоднородные архитектуры генетического поиска 23
1.3.2 Однородные архитектуры генетического поиска 24
1.4 Параметрическая адаптация в генетических алгоритмах 25
1.4.1 Управление уровнем генетического разнообразия 26
1.4.2 Управление направленностью генетического разнообразия 28
1.5 Выводы 29
2 Улучшение адаптационных свойств простого генетического алгоритма 31
2.1 Методика оценки эффективности генетического алгоритма ... 31
2.1.1 Оценка вычислительной сложности моделей генетического алгоритма 32
2.1.2 Оценка процесса сходимости и качества решения, найденного генетическим алгоритмом 33
2.1.3 Использование компьютерного моделирования для анализа свойств генетических алгоритмов 36
2.2 Улучшения свойств простого генетического алгоритма как средства оптимизации 38
2.2.1 Причины неэффективности вероятностного отбора 38
2.2.2 Пути повышения эффективности мутаций для вероятностного отбора 46
2.2.3 Анализ эффективности улучшенного оператора мутаций 46
2.3 Выводы 48
3 Развитие идей эволюционных вычислений для моделирования механизмов самоорганизации 49
3.1 Идея адаптивного генетического алгоритма 49
3.2 Невозможность оптимизации интенсивности отбора 52
3.3 Невозможность оптимизации направления поиска 53
3.4 Генетический алгоритм с внутренней целевой функцией 54
3.5 Архитектуры самоорганизации генетического алгоритма 59
3.6 Формализация алгоритма самоорганизации генома 63
3.7 Выводы 79
4 Решение прикладных задач моделирования 80
4.1 Моделирование процессов этногенеза 80
4.1.1 Формальное описание модели 81
4.1.2 Уточнение математической модели 83
4.1.3 Результаты моделирования 86
4.2 Моделирование поведения абонентов телефонной сети в
условиях альтернативной тарификации 91
4.2.1 Актуальность введения альтернативной тарификаиии... 91
4.2.2 Описание задачи в терминах иерархического управления92
4.2.3 Сжатие данных о распределении трафика 94
4.2.4 Многоагеїітная система взаимодействия абонентов сети 96
4.2.5 Результаты оптимизаиии на модели 98
Заключение 100
Библиографический список 102
Список использованных сокращений 112
Приложение 1 113
Приложение 2 121
Приложение 3 131
- Проблема описания самоорганизации в рамках базовых моделей сложных систем
- Методика оценки эффективности генетического алгоритма
- Идея адаптивного генетического алгоритма
- Моделирование процессов этногенеза
Введение к работе
Актуальность темы. Современный э тап развития естественных наук в изучении явлений различной природы обнаруживает схожие проблемы, решение которых ведет к выработке общей методологии исследования мира сложных систем. Единую причинную модель мира предлагает синергетика, с ее нелинейными моделями, аппаратом исследования причин неустойчивости, структурных изменений и явлений самоорганизации. Благодаря взаимному проникновению идей открывается перспектива дальнейшего развития научных знаний. Успешно происходит трансляция науки о сложном из неживой природы в проблематику анализа технических систем и динамики социальных сред.
Тем не менее, исследование процессов самоорганизации, проявление которых в системах макромира отличается большим разнообразием, затруднено ввиду недостаточной изученности свойств объектов, образующих элементы систем в таких средах. В результате модели конкретных приложений, например, социальных процессов (К.П. Иванов, А.К. Гуц, Ю.Б. Бахтин, В.В. Коро-бицин, В.В. Ляхов),либо ограничены рассмотрением когерентной (групповой) самоорганизации и связаны в первую очередь с полевыми и принципиально нелинейными моделями, либо вовсе ее не учитывают. Таким образом, назрела необходимость построения базовых моделей континуальной самоорганизации, тесно связанной с прогрессивной эволюцией индивидуальных элементарных открытых систем.
Широкие возможности моделирования самоорганизации имеются в гибридных системах. Имитационные модели развития здесь производятся в рамках методологии многоагентных систем (далее MAC), а популярным инструментом, воспроизводящим эволюционные процессы, служат генетические алгоритмы (далее ГА, J.H. Н olland). П ривлекательность ГА обусловлена их сильно нелинейным поведением, функционированием на грани порядка и хаоса. Препятствием на пути использования ГА как базовой модели самоорганизации является эффект предварительной сходимости (как яркое проявление отсутствия самоорганизации), в то время как естественным процессам, напротив, присуща живучесть и постоянное развитие.
Достаточное число публикаций посвящено исследованию ГА как средства оптимизации, поиску его оптимальной структуры и параметров. Известны способы снижения риска предварительной сходимости (Л.А. Гладков, В.В. Курейчик), обеспечиваемые интеллектуальной надстройкой, гибридизацией. Такие меры адекватны задачам оптимизации, но не приемлемы для задач моделирования процессов самоорганизации в децентрализованных системах.
Актуальность темы работы для решения теоретических вопросов заключается:
в необходимости моделирования механизмов континуальной самоорганизации элементарных открытых систем;
в потребности адаптации методов эволюционных вычислений для моделирования систем эволюционной природы;
в необходимости изучения и в разработке средств снижения риска предварительной сходимости ГА.
Актуальность темы для решения прикладных задач подтверждается потребностью в моделировании открытых динамических социальных и технических сред.
Целью диссертационной работы я вляется развитие методов эволюционных вычислений для эффективного решения задач моделирования самоорганизации децентрализованных систем эволюционной природы.
Для достижения цели в работе решены следующие задачи:
-
Разработана методика оценки процесса сходимости ГА для выявления потенциала самоорганизации алгоритма («живучесть» в условиях риска предварительной сходимости, способность «выходить из локальных ям»). Создан программный комплекс для исследования влияния параметров и структуры типовых моделей ГА на показатели качества сходимости и найден ряд алгоритмических решений улучшения данных показателей в рамках простого ГА (далее ПГА).
-
Определены понятия внутренней целевой функции и мутационных последовательностей и базовые алгоритмы самоорганизации ГА, обеспечиваемой двумя различными структурами параллельного ГА: с переменной интенсивностью отбора и с внутренней целевой функцией.
3.Разработан подход к моделированию децентрализованных самоорганизующихся систем посредством синтеза методологии MAC и эволюционных вычислений.
4. В рамках подхода и с использованием алгоритма самоорганизации ГА с внутренней целевой функцией построена модель, иллюстрирующая поведение, типичное для систем агентов социальной среды (на примере комплиментарного этнического контакта). Для оценки работоспособности модели реализован программный комплекс и проведено компьютерное моделирование.
5.На базе стандартных алгоритмических средств эволюционных вычислений разработана модель и программный комплекс для решения прикладной задачи моделирования поведения агентов (абонентов телефонной сети) в условиях введения в действие двух альтернатив тарификации.
Методы исследований. Решение поставленных задач сопряжено с применением методологии MAC, методов оптимизации, статистической обработки данных, имитационного моделирования, объектно-ориентированного анализа и проектирования программных средств.
Достоверность и обоснованность результатов в части алгоритмических решений по улучшению сходимости ПГА подтверждается сравнением алгоритмов как по общепринятым, так и по предлагаемым в работе показателям качества. Верификация предлагаемых моделей производится сопоставлением качественных результатов компьютерного моделирования с имеющимися статистическими данными и экспертными заключениями, озвученными в научной литературе.
Научная новизна. Впервые оптимизационные структуры эволюционных вычислений применены для моделирования процессов самоорганизации децентрализованных систем. В результате впервые удалось создать модель комплиментарного этнического контакта в отличие от известных работ по некомплиментарному взаимодействию социальных подсистем. При этом:
-
В рамках параллельного ГА обнаружены механизмы самоорганизации.
-
Определены понятия внутренней целевой функции и мутационных последовательностей как факторов снижения риска предварительной сходимости и обеспечения самоорганизации ГА.
-
Спроектированы модели ГА, обнаруживающие автоколебания генотипов с динамическими аттракторами в кодируемом генами пространстве решений. Найдены алгоритмические решения по улучшению сходимости ПГА.
Практическая значимость результатов:
-
Предлагаемые в работе алгоритмы и подход к моделированию процессов самоорганизации в открытых динамических системах могут быть использованы для формализации прикладных моделей социальных систем с комплиментарным взаимодействием агентов.
-
Разработанные алгоритмические решения по улучшению сходимости ПГА позволят решать задачи поиска экстремума большой размерности с меньшими временными затратами.
На защиту выносятся:
-
Базовые модели самоорганизации ГА, обеспечиваемой двумя различными структурами параллельного ГА: с переменной интенсивностью отбора и с внутренней целевой функцией.
-
Подход к моделированию механизмов самоорганизации децентрализованных систем в рамках методологии MAC и эволюционных вычислений.
-
Решения по улучшению сходимости ПГА, программный комплекс оптимальной настройки параметров и структуры типовых моделей ГА.
4. Приложения алгоритмов самоорганизации к решению задач моделирования социальной системы с комплиментарным взаимодействием агентов и технической системы динамического распределения ресурса: модель поведения агентов в условиях введения в действие двух альтернатив тарификации.
Внедрение.
-
Расчеты эффективности от введения повременной оплаты за телефонные переговоры, проведенные с учетом результатов имитационного моделирования поведения агентов в условиях введения в действие двух альтернатив тарификации, предоставлены управлению телефонных сетей г. Камышина.
-
Программный комплекс компьютерного моделирования комплиментарного этнического контакта внедрен в учебный процесс на кафедре «Истории и археологии» Волгоградского государственного университета
Апробация работы.
Основные результаты работы докладывались на IX и X международных конференциях «Математика. Компьютер. Образование» (Дубна 2002, Пущи-но 2003), I, II и (И Всероссийских конференциях «Прогрессивные технологии в обучении и производстве» (Камышин 2002, 2004, 2005), научном семинаре НИИ Археологии (Волгоград, ВолГУ 2003), конференции молодых ученых ( Волгоград, ВолгГТУ 2001), научном семинаре кафедры САПР ТРТУ (Таганрог 2005).
Объем л структура работы.
Работа состоит из четырех глав и двух приложений. Общий объем работы- страниц - 120, иллюстраций - 41, таблиц - 4.
Проблема описания самоорганизации в рамках базовых моделей сложных систем
Толчком к проведению исследований послужила постановка двух прикладных задач.
Первая задача - моделирование социальной системы на уровне этнических процессов. Наиболее близким к естественнонаучному здесь является подход Л.Н. Гумилева, выражаемый в рамках пассионарной теории этногенеза (ПТЭ), где этнос представляется как система эволюции взаимодействующих элементов [22, С.5].
Вторая задача - оптимизация тарифов телефонной связи. Предметом исследования здесь является поведение абонентов в условиях введения в действие двух альтернатив: а) повременная оплата услуг телефонной связи, б) выплата абонентской платы. Действие управляющих параметров: размер абонентской платы и стоимость исходящих вызовов приводит к эволюции трафика сети. При этом происходит взаимодействие абонентов с целью минимизации собственных затрат.
При детальном анализе прикладные задачи обнаруживают сходные черты:
1. Взаимодействие однотипных элементов. В случае этнических систем элементарными взаимодействующими элементами (агентами) являются члены этноса. В оптимизационной задаче — абоненты телефонной сети.
2. Эволюционная природа. Изменение структуры этнической системы в первой задаче и эволюция поведения абонентов и динамика размера и структуры внутрисетевого трафика - во второй.
Данные признаки позволяют отнести рассматриваемые прикладные задачи к классу задач моделирования самоорганизации систем.Сущность явления и виды самоорганизации
В физическом смысле такие процессы происходят вследствие того, что поток рассеиваемой свободной энергии системы , направленной к равновесию, трансформируется во внутреннюю полезную работу 0, направленную против равновесия, и поток бесполезно рассеиваемой энергии Q. Мерой самоорганизации является коэффициент полезного использования энергии г = 0/Е, а мерой необратимости — коэффициент t} = QIЕ. Согласно подходу И. Пригожина [45], оперирующего понятием энтропии S = Q/T, условием устойчивости неравновесной открытой системы является dS = dSe+dSj, где dS — изменение энтропии системы за время dt\ dSe — поток энтропии, обусловленный обменом веществ и энергии с внешней средой; dSj — производство энтропии внутри системы за счет необратимых процессов. В стационарном состоянии системы dS - О а при самоорганизации dS 0 т. е. необходим приток «отрицательной энтропии» dSe из внешней среды, перекрывающий производство энтропии dSj внутри системы.
Теория самоорганизации тесно связана с синергетикой [25], которая согласно современным представлениям является обобщением системного подхода. Синергетический подход применим к классу систем, само существование которых есть эволюция, развитие, история, исходя из того, что мир сложных систем подчиняется единым законам и может быть понят на основе единой объяснительной модели [23]. К свойствам таких систем относят открытость, неравновесность, динамизм, нелинейность математического описания, иерархическую сложность, фрактальность, способность к образованию странных аттракторов и т. д.
Развитием синергетического подхода является концепция эволюционного катализа А.П. Руденко, где различают два типа самоорганизации. Континуальная (видовая) самоорганизация микроскопических элементарных открытых систем (ЭОС) и когерентная (коллективная) самоорганизация макроскопических множеств ЭОС [49, С. 58]. При этом подчеркивается зависимость проявлений когерентной самоорганизации от наличия определенной континуальной самоорганизации индивидуальных объектов, составляющих множество [49, С.65].
По мнению А.П. Руденко определение синергетики Г. Хакена [62] покрывает лишь процессы когерентной самоорганизации, проявляющейся в кооперативном поведении множества микроскопических ЭОС. Континуальная же самоорганизация появляется вследствие эволюции самих элементов. При этом направленность эволюции, ее причины, движущие силы и механизм естественного отбора эволюционных изменений определяется основным законом прогрессивной эволюции.
Согласно этому закону, с наибольшей вероятностью осуществляются те цепи эволюционных изменений, которые приводят к возрастанию абсолютной энергетической мощности обменного процесса. Другими словами, прогрессивная эволюция приводит ко все более неравновесным состояниям, связанным с ростом коэффициента полезного использования энергии Е на внутреннюю полезную работу .
Определим, насколько известные методы моделирования систем учитывают процессы когерентной и континуальной самоорганизации.
1.1,2 Недостатки имеющихся базовых моделей сложных систем
Среди существующих моделей сложных динамических систем выделяют базовые, имитационные и модели статистического анализа. Недостатком моделей статистического анализа является невозможность обоснования результатов в терминах явлений предметной области.
-15-Имитационные модели часто перегружены деталями. Базовые модели, дают качественную картину и помогают понять существо происходящих процессов [52].
Классификацию моделей по внутреннему описанию предлагает А.К. Гуц [20, С.25]:
1. Модель динамической системы. Исходная система представляется в виде п подсистем Sj, динамика каждой из которых выписывается в виде дифференциального уравнения баланса dS; = fi{Sy,..Si,..Sn).
2. Статистическая модель. Элементы системы представляют статистический ансамбль Q: qs ,..qs.,..qs , позиции которого определяют степень принадлежности элемента соответствующей подсистеме S\,..Si,..Sn. Динамику системы описывают уравнениями для плотности распределения статистических ансамблей в пространстве подсистем.
3. Полевая модель. Величины, характеризующие выходные характеристики поведения системы, используют в качестве осей фазового пространства F. Поле задается функцией Р: F - R . Процессы, происходящие в системе, описываются уравнением поля А(Р) = f.
4. Стохастическая модель. Поведение системы описывается как процесс изменения во времени характеристики поля P(t) под действием случайной силы g{t): dPt dt = -кР + д.
Из приведенной классификации видно, что внутреннее описание моделей может предполагать как фиксированную структуру системы, так и изменяющуюся во времени.
Методика оценки эффективности генетического алгоритма
Для оценки возможностей самоорганизации создаваемых ГА в части борьбы с предварительной сходимостью, способности «выхода из локальных ям» и адаптации к изменениям внешних условий необходимо иметь методику анализа таких возможностей на основе количественных оценок эффективности процесса сходимости.
Оценка эффективности любого алгоритма базируется на комплексе мероприятий по определению: 1) ВС, 2) показателей качества найденного решения и процесса сходимости.
Оценка процесса сходимости и качества решения, найденного генетическим алгоритмом
Ранее оценка эффективности ГА проводилась для задач, где существует явный признак остановки алгоритма. К таким задачам относятся задачи оптимизации с критериями, построенными на минимизации ошибок (регрессия, идентификация), где присутствие в популяции особи со значением ФП, близким к нулю, ведет к остановке алгоритма и выдаче решения в виде генотипа данной особи. В таких задачах необходим лишь поиск оптимального генотипа х = хор . Анализируя разрабатываемые ГА на тестовых функциях, исследователи (среди прочих в [5]) сравнивали алгоритмы по числу генераций до обнаружения в популяции особи с оптимальным генотипом xopt = ycpt ,X2Pt ,.-xpt , где п — количество генов особи. Очевидно, что данный критерий не позволяет оценивать способности ГА к нахождению решения задач, в которых идеальное значение критерия неизвестно [69]. К числу таких задач, наряду с задачами самоорганизации, относятся также и классические оптимизационные задачи, в которых имеется информация только о форме оптимизируемой функции, а ее уравнение не задано (такие задачи изучаются, например, в теории экстремальных систем управления). Иные критерии нужны также и для исследования возможностей ГА в задачах с динамическими критериями (исследования ГА в условиях адаптации к изменяющейся среде проводятся в частности в [71,77,84,78]).
Необходимо создать критерии оценки процесса сходимости, как для оценки адаптационных свойств ГА, так и для оценки эффективности ГА в задачах классической оптимизации, где допускается лишь некоторая информация о форме оптимизируемой функции, само же оптимальное значение считается неизвестным.
Использование компьютерного моделирования для анализа свойств генетических алгоритмов
Теоретическое исследование эффективности ГА затруднено сложностью, нелинейностью и наличием параллелизма в работе ГА, поэтому основные результаты известны лишь для граничных простых случаев, когда часть механизмов алгоритма опускают и пытаются анализировать эффекты раздельно. Так появилась фундаментальная теорема ГА [34], теория строящих блоков, концепция квазивидов [48,С.13].
В предлагаемой работе анализируется комплексное влияние параметров ГА на сходимость, что стало возможным благодаря созданию автором программного комплекса как средства моделирования ГА и усовершенствования методики оценки сходимости.
Созданный программный комплекс позволяет получать различные оценки процесса смены поколений ГА с возможностью варьирования основных параметров ГО, что позволяет локализовать «узкие места» ГА.
Задача оценки сходимости ГА затруднена обилием параметров, присутствующих в выражениях ВС. Однако можно выявить группу несущественных и группу внешних к ГА параметров (не подлежащих оптимизации). Так, длительность машинных операций к„ и кс, скорость вычисления с и разрядность значений wj- ФП оказывают равное влияние на все модели ГА. Внешними являются параметры исходных данных ГА, а именно: п, wx (размерность пространства кодировки) и / (форма ФП).
Поэтому анализу и оптимизации подлежат только следующие параметры простого ГА: 1) / - численность популяции, 2) lm,lrJc — соотношения участия трех основных ГО, 3) р— число точек деления кроссинговером и мутирующих генов, 4) особенности селективной стратегии.
Отмечу ряд условий объективности экспериментов по анализу эффективности моделей
Во-первых, учитывая вероятностно-детерминированный характер исследуемых алгоритмов, получаемые в программном комплексе характеристики работы ГА необходимо усреднять по большому числу испытаний алгоритма. Для интегральных статистик (вычисляемых усреднением по популяции) достаточное число испытаний определено порядка 100 (размер популяции / = 40), при этом относительные отклонения получаемых интегральных статистик ГА (на примере л/0(х )) не превосходят 0.05. Достоверность получаемых характеристик растет с увеличением размера популяции. Для статистик пиковых величин (наибольшее значение ФП внутри популяции, близость лучшей особи к оптимуму и др.) достаточное количество испытаний для усреднения статистики порядка 2000 и мало зависит от размера популяции.
Причины неэффективности вероятностного отбора
В аналитическом обзоре было отмечено, что при приближении к оптимуму мутация становится вредной. Данный факт легко объясняется для ГА, где отсутствует промежуточный пул отбора, и порождаемые особи занимают места породивших (другими словами, где существует ограничение lm=l -{lc+lr))- Такое положение характерно для канонического ГА Дж. Холланда, именно для него предложен термин «порог мутаций» и стоит проблема нехватки репродуктивной памяти при увеличении процента мутантов [73].
Однако на практике применяют более эффективные алгоритмы, ослабляющие проблему нахождения баланса между исследованием 1т и использованием lr,lc посредством промежуточного пула. Тем не менее, эксперименты автора (представленные в Приложении 2) показывают, что модель с промежуточным пулом отбора не лишена недостатка, связанного с неэффективностью мутаций.
Автором предлагается тезис о взаимосвязи проблемы порога мутаций с неэффективным устройством оператора вероятностного отбора.
Проведем качественный анализ причин неэффективности мутаций в рамках вероятностного отбора, к которому принадлежат как пропорциональный, так и рулеточный отбор. Основная особенность этих видов отбора состоит в том, что вероятность попадания особи в новое поколение пропорциональна значению ФП генотипа данной особи.
Идея адаптивного генетического алгоритма
Компьютерные эксперименты комплексного анализа сходимости, описанные в Приложении 2, выявили следующие проблемы:
для оператора мутации: проблема порога мутаций, проблема взаимного уничтожения преимуществ в многомерном поиске,
для оператора репродукции: проблема кратковременности памяти, которую отбор делает почти марковской, вследствие экспоненциального роста одних строительных блоков и уничтожения других,
для оператора кроссинговера: проблема исследования и использования, когда кроссинговер оказывается практически неэффективным (на поздних стадиях процесса сходимости оптимизация идет исключительно за счет оператора мутаций).
Но если проблема порога мутаций и кратковременной памяти может быть устранена простыми техническими улучшениями структуры ГА (проблема порога мутаций решена в предыдущей главе), то проблема исследования и использования не имеет простых путей решения.
Анализируя процесс сходимости совместно с процессом потери степени свободы, можно выявить первый этап процесса сходимости. На этом этапе наблюдается быстрая сходимость, на основании чего сделан вывод о том, что это следствие не только участия оператора мутации, но и высокой степени свободы генома. То есть эффект использования заложен, возможно, и не в кроссинговере, а в самом геноме в виде высокой степени свободы.
Сужение пространства поиска ведет к наступлению второго этапа процесса сходимости, на котором потерянную скорость сходимости и свободу генома уже не может восстановить даже обширное исследование пространства поиска посредством мутаций (будь то обычные гипермутации, или улучшенный оператор, предложенный автором и описанный в предыдущей главе). Аналогично не имеет простого решения и проблема взаимного уничтожения преимуществ в разных генах.
Одним словом, оператор мутации неинтеллектуален, нельзя заложить правила, которые заставляли бы случайную мутацию расширять степень свободы в нужном направлении, требуемом для получения хороших результатов сходимости. Оператор кроссинговера оказывается еще менее пригодным, ведь он должен динамично реагировать на изменение ситуации в процессе поиска, по необходимости усиливать или ослаблять свое влияние на содержимое генома по отношению к оператору мутации.
Таким образом, представляется необходимым создание адаптивного ГА, с адаптивными операторами формирования пула и динамичной стратегией отбора. Решение данной задачи позволило бы продлевать первый этап процесса сходимости, обеспечивая нужный уровень степени свободы генома (за счет варьирования интенсивности отбора к и репродукции) и направленность внутривидового разнообразия (за счет выбора направленности мутаций и кроссинговера).
Автором видится несколько путей создания такого алгоритма. Первый путь в наделении ГО искусственным интеллектом, как, например, в случае вероятностных ГА [50]. Другой путь тесно связан с теорией сложных систем и синергетикой. Согласно данному методу ГО остаются вычислительно простыми, неинтеллектуальными, а адаптивное поведение достигается за счет выбора оптимальной, сложной, живучей структуры ГА, что иллюстрируют многочисленные архитектуры в [13]. Для реализации второго пути необходимо проектировать структуру ГА до обнаружения эффектов самоорганизации, способных породить внутренние цели, сопутствующие внешней цели — оптимизации.
В данной работе предлагаются решения, следующие второму из возможных путей в рамках децентрализованных архитектур ГА. При этом в качестве внутренней цели разрабатываемого ГА самоорганизации генома предлагается использовать цель поддержания нужного уровня степени свободы и направления изменения генофонда. Факторами, способствующими достижению данной цели, выбраны варьирование интенсивности естественного отбора и коррекция генофонда так называемыми мутационными последовательностями. В качестве обоснования выбора данных факторов выдвигается тезис об их значимости наряду со стандартными параметрами ГА и элементами его структуры (кроссинговер, мутация) в процессе оптимизации. В отличие от стандартных параметров алгоритм оптимизации данных факторов отсутствует, что демонстрируют нижеследующие факты.
Невозможность оптимизации интенсивности отбора
По аналогии с биологической эволюцией следует называть отбор интенсивным, если вероятности попадания в новую популяцию особей с низкой пригодностыо ничтожно малы. Для вероятностного отбора такая ситуация моделируется введением большого коэффициента к в выражении для вероятности селекции (1), и, возможно, даже переходом к нелинейной зависимости. Как было показано, большие значения к необходимы в случае попадания в овраг, где значения пригодности примерно равны и уравнивают достоинства и недостатки особей.
С другой стороны, большие значения к ведут к ослаблению репродуктивной функции, что препятствует попаданию особей с низкой пригодностыо в новое поколение, где они могли бы дать хорошее потомство, скрещиваясь или мутируя (проявляется эффект снижения степени свободы).
Таким образом, изменение коэффициента интенсивности отбора к позволяет варьировать соотношение исследования и использования, оптимальная динамика которого неизвестна. Эксперимент 7 Приложения 2, где варьирование интенсивности отбора дает непредсказуемые результаты на разных участках процесса сходимости подтверждает данный тезис.
Невозможность оптимизации направления поиска
Одна из проблем ГА — отсутствие возможности одновременной полезной мутации в нескольких генах. Именно этим обусловлена плохая сходимость для овражных функций многих переменных. В предыдущей главе уже было показано, как гипер-мутация портит преимущества, а медленная мутация грозит предварительной сходимостью. Низкая вероятность «хорошей» мутации в стандартной ее реализации может быть обоснована по двум схемам. Либо это одновременная мутация в т генах, либо это последовательная мутация одного нужного гена от поколения к поколению. Наступление второго варианта можно понимать как рождение последовательности мутаций, каждая из которых приносит выгодное изменение хромосомы. Такую последовательность и будем называть мутационной последовательностью. Вероятность ее возникновения в случае использования пула, заполняемого мутантами по стандартной методике (случайное распределение), крайне мала. Для наблюдения такой последовательности необходимо, чтобы мутации не являлись чисто случайной последовательностью, из которой селекция выбирает нужную, а приобретали бы в критические моменты некоторое инерционное, последовательное движение к необходимой оптимальной хромосоме. Для ГА же важно, чтобы в момент, когда получены мутанты нужного направления, совпадающего с изменением генофонда в сторону движения к оптимуму, такие особи появлялись бы вновь и вновь, чтобы преодолеть нелинейность ГА и обеспечить направленность поиска.
Аналитический обзор показал, что верную направленность поиска не удается произвести для задач общего вида, каждый метод применим лишь в узкой области задач.
Моделирование процессов этногенеза
Разработанная математическая модель основана на гипотезах ПТЭ, предложенной Л.Н. Гумилевым для объяснения стадий развития этносов [16,17,18]. ПТЭ позволяет рассматривать сложный нелинейный процесс исторического развития с позиций автомодельных систем. О самоорганизации этносов говорит тот факт, что до сих пор существующие на земле этнические системы не достигли стационарного состояния (гомеостаза). С точки зрения моделирования и последующего прогнозирования биологические факторы, в отличие от социально-психологических (выражаемых в [6]), оказались легко поддающимися формализации.
Обзор концепций ПТЭ произведен в Приложении 3. Основная идея подхода Л.Н. Гумилева выражается следующей цитатой [18]: «.. .реальная этническая целостность есть динамическая система, включающая в себя не только людей, но и элементы ландшафта, культурную традицию и взаимосвязи с соседями...».
Формальное описание модели
В разработанной модели, согласно включены все три цитируемых вида взаимодействий элементов этнической системы. Первый вид — традиция, передающаяся по наследству. Традиция моделируется ГА с внутренней ЦФ усреднения особей. Второй вид — взаимодействие с соседями, реализуется архитектурой параллельного ГА где каждый остров представляет собой популяцию соседей, а взаимодействие происходит за счет миграции с последующей адаптацией к традиции соседей. Третий вид взаимодействий - взаимная адаптация с ландшафтом — моделируется введением второго параллельного ГА, представляющего изменения внешней среды этноса во взаимодействии с ним. Острова ГА этносов взаимодействуют с островами ГА ландшафта посредством миграций, тем самым адаптируя ландшафт под собственный стереотип поведения.
Для кодировки генотипов особей использованы полевые представления организации социальных систем. В качестве проявлений этнической принадлежности выбран стереотип поведения (СП) - вектор р, длина и направление которого определяется соответственно уровнем и типом пассионарности человека (термин ПТЭ, определяющий неординарность и высокую энергию индивидуума). Учитывая, что члены этноса занимают определенный ареал, можно говорить о распределении векторов СП этноса по точкам ландшафта. Другими словами, имеется функция поля (х,у) - СП этноса в точке ландшафта с координатами х,у. Этносы взаимодействуют с ландшафтами различных типов. Каждый тип предполагает адекватный ландшафту СП гармоничного сосуществования. Таким образом, можно говорить о функции L(x,y), характеризующей СП, который требуется для максимальной адаптации членов этноса к ландшафту в точке х,у.
Внеэтнические факторы этногенеза моделируются взаимодействием двух слоев: первый - популяции (Р(х,у)) различной этнической принадлежности, второй - ландшафты (Ь(х,у)), образующие месторазвитие для данных популяций .
Межэтнические факторы этногенеза моделируются посредством взаимодействия между популяциями, занимающими соседние точки ландшафта. Для этого популяции обмениваются своими членами (особями-потомками), которые либо выживают в новых условиях, либо отторгаются по принципам, сходным с принципами естественного отбора (см. рис. 13). Перемешивание популяций отражается на динамике поля Р(х, у).
Наиболее сложные внутриэтнические факторы этногенеза моделируются кроссинговером и мутациями - составляющими ГА для популяции Р(х,у) особей (членов этноса) в точке ландшафта х,у. Каждая популяция несет в себе определенный генофонд СП.
Уточнение математической модели
Пусть число основных («эталонных») типов пассионариев равно п. Каждому из них соответствует уникальный стереотип поведения; совокупность стереотипов выберем в качестве базиса {р ,р2,..рп}. Тогда стереотип поведения любой s-особи (особи с индексом s) есть вектор Ps в образованном пространстве. Близость Ps к k-н оси означает сходство s-особи с к-м эталонным пассионарием (кє\..п), а величина \PS\ пропорциональна суммарной энергетике особи.
Популяция точки (xityj) взаимодействует с внешней средой, которая локализована в модели в форме условий, создаваемых ландшафтом. Гармоничные особи обладают стереотипом поведения, позволяющим им быть максимально адаптированными к условиям среды. Можно говорить о том, что каждая точка (xt,yj) месторазвития "цементирует" стереотип поведения Ці = Ц,ХІ,УІ ) адаптации к ландшафту.
В компьютерных экспериментах на модели рассмотрены некоторые стандартные варианты инициализации этнического пространства, изученные и представленные в качестве примеров в ПТЭ. Для данных путей развития событий были получены результаты, хорошо соотносящиеся с ПТЭ и историческими реалиями. Ниже приведены некоторые из них:
1. Достаточно широкий спектр значений параметров настройки модели (скорость мутаций РтШ, приспособляемость особей а и ландшафтов Р) приводит к достижению автоколебательного режима (см. рис. 15). В данном режиме этническая система не требует энергии извне. Автоколебания этнического поля наблюдаются в модели при постоянном уровне мутаций. Таким образом, показано, что причины этногенеза могут быть объяснены свойствами самой биосферы, без привлечения внешних факторов.
2. Обнаружен гораздо более узкий класс значений параметров модели, при которых процесс, сохраняя автоколебания, обладает памятью во времени. Так, на рис. 16 представлены результаты эксперимента в котором после старта из одинаковых начальных состояний (срез ТІ) две реализации модели продемонстрировали похожие результаты. Это позволяет надеяться на возможность идентификации параметров на реальных объектах.
На модели удалось продемонстрировать основные эффекты ПТЭ:
1. При отсутствии внешних угроз (моделируется заданием стартовой комбинации однородных этносов и ландшафта Vx [P(x,y) = L( :,_y)J) этнос существует бесконечно долго, следуя традициям (функции Р, L сохраняют свои статистические характеристики);
2. В поздних стадиях развития (после надлома) этнос невосприимчив к попыткам вернуть утраченную пассионарность (моделируется реакция этноса на введение взвеси из высокопассионарных особей в различных стадиях его адаптации к ландшафту);
3. Эффект гомеостаза ярко проявляется при моделировании двух граничащих разнотипных ландшафтов 7} и Т2 населенных двумя абсолютно адаптированными этносами V(x „W, \?(Х У) = Ї- (Х У) = Р\\ У(х,у)єТ2Р(х У) = Нх,у) = р2\. При отсутствии мутаций (Pmul=0),
автоколебательный процесс здесь не приводит к поглощению одного этноса другим (рис. 17). Не возникает и новых этносов, что говорит о важности механизма мутаций и возможной динамике уровня мутаций у реальных народов.
4. Необходимым условием пассионарного толчка является наличие разнородных ландшафтов, что моделируется достаточно хорошо и объясняется наличием дополнительных степеней свободы генома смежных популяций разнородных ландшафтов.
5. Живучесть этноса обеспечивает не только высокая пассионарность, но и низкая пассионарность этноса-«соседа».
Похожие диссертации на Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических системах
