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

• Автор: Сургутанов, Владимир Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Волгоград
• Количество страниц: 140 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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 Методика оценки эффективности генетического алгоритма.
2.1.1 Оценка вычислительной сложности моделей генетического алгоритма 1
2.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 Описание задачи в терминах иерархического унравления 4.2.3 Сжатие данных о распределении трафика.
4.2.4 Многоагентная система взаимодействия абонентов сети .
4.2.5 Результаты оптимизации на модели.
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
СПИСОК ИСПОЛЬЗОВАННЫХ СОКРАЩЕНИЙ
ПРИЛОЖЕНИЕ 1
ПРИЛОЖЕНИЕ 2
ПРИЛОЖЕНИЕ 3
ВВЕДЕНИЕ
Современный этап развития естественных наук в изучении явлений различной природы обнаруживает схожие проблемы, решение которых ведет к выработке общей методологии исследования мира сложных систем. Единую причинную модель мира предлагает синергетика, с ее нелинейными моделями, аппаратом исследования причин неустойчивости, структурных изменений и явлений самоорганизации. Благодаря взаимному проникновению идей открывается перспектива дальнейшего развития научных знаний. Успешно происходит трансляция науки о сложном из неживой природы в проблематику анализа технических систем и динамики социальных сред.
Актуальность


Основное содержание работы отражено в четырех главах и трех приложениях. В первой главе приводится аналитический обзор методов моделирования самоорганизующихся систем. Вторая глава посвящена параметрической адаптации ГА к задачам моделирования эволюционных процессов. В третьей главе разрабатываются новые архитектуры Г А для описания процессов самоорганизации в децентрализованных системах. В четвертой главе приводится постановка прикладных задач моделирования социальной системы и технической задачи оптимизации с привлечением разработанных и стандартных алгоритмов эволюционных вычислений соответственно. В приложениях приводится материал, поясняющий устройство ГА, расчеты вычислительной сложности (ВС) генерации, обзор концепций ПТЭ и эксперименты комплексного анализа сходимости основных моделей ГА. Результаты работы опубликованы в [-]. Автор считает своим приятным долгом выразить благодарность Елене Георгиевне Крушель за вклад в формирование научного мировоззрения, Валерию Анатольевичу Камаеву и Сергею Алексеевичу Фоменкову за обсуждение работы и ценные рекомендации по ее содержанию и представлению. В данной главе раскрываются проблемы моделирования самоорганизации в децентрализованных системах (с однотипными элементами - агентами), подчеркивается целесообразность использования ГА и потребность в дополнении их механизмами самоорганизации. Сначала приводится краткое описание сущности явления самоорганизации и ее проявлений (когерентное поведение, прогрессивная эволюция функциональной структуры и баланс процессов противоположной направленности внутри каждого элемента). Далее дается классификация базовых моделей децентрализованных систем, в частности указываются возможности полевых моделей (в фазовых пространствах) по описанию процессов развития структуры и особенности гибридных систем, в большей степени адекватных описанию самоорганизации. Затем приводятся имитационные модели децентрализованных систем (в рамках многоагентного подхода), иллюстрирующие разнообразные проявления самоорганизации. Подчеркивается факт использования ГА (посредством которых эволюционируют агенты) во внутреннем представлении таких моделей. Выдвигается тезис о целесообразности использования ГА в качестве базового алгоритма самоорганизации. В то же время отмечается невозможность использования ПГА и необходимость его структурной и параметрической адаптации к потребностям моделирования самоорганизации. Наконец, делается обзор известных улучшений ГА (в рамках эволюционных вычислений) осуществляемых за счет введения иерархии в его структуру, Подчеркивается потребность в разработке децентрализованных архитектур ГА самоорганизации (не иерархических, без интеллектуальной надстройки). Толчком к проведению исследований послужила постановка двух прикладных задач. Первая задача - моделирование социальной системы на уровне этнических процессов. Наиболее близким к естественнонаучному здесь является подход Л. Н. Гумилева, выражаемый в рамках пассионарной теории этногенеза (ПТЭ), где этнос представляется как система эволюции взаимодействующих элементов [, С. Вторая задача - оптимизация тарифов телефонной связи. Предметом исследования здесь является поведение абонентов в условиях введения в действие двух альтернатив: а) повременная оплата услуг телефонной связи, б) выплата абонентской платы. Действие управляющих параметров: размер абонентской платы и стоимость исходящих вызовов приводит к эволюции трафика сети. При этом происходит взаимодействие абонентов с целью минимизации собственных затрат. Взаимодействие однотипных элементов. В случае этнических систем элементарными взаимодействующими элементами (агентами) являются члены этноса. В оптимизационной задаче — абоненты телефонной сети. Эволюционная природа. Изменение структуры этнической системы в первой задаче и эволюция поведения абонентов и динамика размера и структуры внутрисетевого трафика - во второй. Данные признаки позволяют отнести рассматриваемые прикладные задачи к классу задач моделирования самоорганизации систем.