Главная » 2014»Август»4 » Скачать Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических бесплатно
3:37 AM
Скачать Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических бесплатно
Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических системах
Диссертация
Автор: Сургутанов, Владимир Владимирович
Название: Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических системах
Справка: Сургутанов, Владимир Владимирович. Развитие методов эволюционных вычислений для моделирования самоорганизации в децентрализованных социальных и технических системах : диссертация кандидата технических наук : 05.13.01 Волгоград, 2005 140 c. : 61 06-5/839
Объем: 140 стр.
Информация: Волгоград, 2005
Содержание:
1 АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ МОДЕЛИРОВАНИЯСАМООРГАНИЗУЮЩИХСЯ СИСТЕМ
11 Нроблема описания самоорганизации в рамках базовыхмоделей сложных систем
111 Сущность явления и виды самоорганизации
112 Недостатки имеющихся базовых моделей сложныхсистем
12 Ноиск базовых алгоритмов самоорганизации в имитационныхмоделях методологии многоагентных систем
121 Нринцииы построения и механизмы самоорганизации вмногоагеитных системах
122 «Искусственная жизиь» и генетические алгоритмы каксредство моделирования эволюции
13 Онтимизационные структуры эволюционных вычислений,осиоваиные на нринцинах самоорганизации
131 Неоднородные архитектуры геиетического ноиска
132 Однородные архитектуры генетического поиска
14 Иараметрическая адаитация в генетических алгоритмах
141 Унравленне уровнем генетического разнообразия
142 Управление направленностью генетическогоразнообразия
15
Выводы
2 УЛУЧШЕНИЕ АДАНТАЦИОИНЫХ СВОЙСТВ НРОСТОГОГЕНЕТИЧЕСКОГО АЛГОРИТМА
21 Методика оценки эффективности генетического алгоритма
211 Оценка вычислительной сложности моделей генетнческогоалгоритма 32- -
212 Оценка процесса сходимости и качества решепия,иайдеипого гепетическим алгоритмом
213 Использовапие компьютерного моделировапия дляанализа свойств гепетических алгоритмов
22 Улучшения свойств простого генетического алгоритма каксредства оптимизации
221 Нричины неэффективности вероятностного отбора
222 Пути повышения эффективности мутаций длявероятностного отбора
223 Анализ эффективности улучшенного онератора мутаций
23
Выводы
3 РАЗВИТИЕ ИДЕЙ ЭВОЛЮЦИОИИЫХ ВЫЧИСЛЕНИЙ ДЛЯМОДЕЛИРОВАНИЯ МЕХАНИЗМОВ САМООРГАНИЗАЦИИ
31 Идея адаптивного генетического алгоритма
32 Невозможность онтимизации интенсивности отбора
33 Невозможность оптимизации иаправления поиска
34 Геиетический алгоритм с внутренней целевой функцией
35 Архитектуры самоорганизации генетического алгоритма
36 Формализация алгоритма самоорганизации генома
37
Выводы
4 РЕШЕНИЕ НРИКЛАДНЫХ ЗАДАЧ МОДЕЛИРОВАНИЯ
41 Моделирование процессов этногенеза
411 Формальное описание модели
412 Уточнение математической модели
413 Результаты моделирования
42 Моделирование поведения абопептов телефонной сети вусловиях альтернативной тарификации
421 Актуальность введения альтериативной тарификации
422 Описапие задачи в терминах иерархического управления
423 Сжатие данных о распределении трафика 94— —
424 Многоагептная система взаимодействия абопеитов сети
425 Результаты оитимизаиии иа модели
Введение:
Современный этап развития естественных наук в изучении явленийразличной природы обнаруживает схожие проблемы, решение которыхведет к выработке общей методологии исследования мира сложныхсистем. Единую причинную модель мира предлагает синергетика, с еенелинейными моделями, аппаратом исследования причин неустойчивости,структурных изменений и явлений самоорганизации. Благодаря взаимномупроникновению идей открывается перспектива дальнейшего развитиянаучных знаний. Успешно происходит трансляция науки о сложном изнеживой природы в проблематику анализа технических систем и динамикисоциальных сред.Актуальность темы. Тем не менее, исследование процессовсамоорганизации, проявление которых в системах макромира отличаетсябольшим разнообразием, затруднено ввиду недостаточной изученностисвойств объектов, образующих элементы систем в таких средах. Врезультате модели конкретных приложений, например, социальныхпроцессов [2, 19, 20, 22, 29, 40], либо ограничены рассмотрениемкогерентной (групповой) самоорганизации и связаны в первую очередь сполевыми и принципиально нелинейными моделями, либо вовсе ее неучитывают. Таким образом, назрела необходимость построения базовыхмоделей континуальной самоорганизации, тесно связанной спрогрессивной эволюцией индивидуальных элементарных открытыхсистем.Широкие возможности моделирования самоорганизации имеются вгибридных системах. Имитационные модели развития здесь производятсяв рамках методологии многоагентных систем (MAC), а популярныминструментом, воспроизводящим эволюционные процессы, служатгенетические алгоритмы (ГА). Привлекательность ГА обусловлена их- 6 сильно нелинейным поведением, функционированием на грани порядка ихаоса. Препятствием на пути использования ГА как базовой моделисамоорганизации является эффект предварительной сходимости (как яркоепроявление отсутствия самоорганизации), в то время как естественнымпроцессам, напротив, присуща живучесть и постоянное развитие.Достаточное число публикаций посвящено исследованию ГА каксредства оптимизации, поиску его оптимальной структуры [12,13,32,38,44]и параметров [5,35,72]. Известны способы снижения рискапредварительной сходимости, обеспечиваемые интеллектуальнойнадстройкой, гибридизацией. Такие меры адекватны задачам оптимизации,но не приемлемы для задач моделирования процессов самоорганизации вдецентрализованных системах.Актуальность темы работы для решения теоретических вопросовзаключается:— в необходимости моделирования механизмов континуальнойсамоорганизации элементарных открытых систем;— в потребности адаптации методов эволюционныхвычислений для моделирования систем эволюционной природы;— в необходимости изучения и в разработке средств сниженияриска предварительной сходимости ГА. Актуальность темы для решения прикладных задач подтверждаетсяпотребностью в моделировании открытых динамических социальных итехнических сред.Целью диссертационной работы является развитие методовэволюционных вычислений для эффективного решения задачмоделирования самоорганизации децентрализованных системэволюционной природы.Для достижения цели в работе решены следующие задачн:1. Разработана методика оценки процесса сходимости ГА длявыявления потенциала самоорганизации алгоритма («живучесть» в- 7 условиях риска предварительной сходимости, способность «выходить излокальных ям»). Создан программный комплекс для исследования влиянияпараметров и структуры типовых моделей ГА на показатели качествасходимости и найден ряд алгоритмических решений улучшения данныхпоказателей в рамках простого ГА (ПГА).2. Определены понятия внутренней целевой функции и мутационныхпоследовательностей и базовые алгоритмы самоорганизации ГА,обеспечиваемой двумя различными структурами параллельного ГА: спеременной интенсивностью отбора и с внутренней целевой функцией.3. Разработан подход к моделированию децентрализованныхсамоорганизующихся систем посредством соединения методологии MACи эволюционных вычислений.4. В рамках подхода и с использованием алгоритма самоорганизацииГА с внутренней целевой функцией построена модель, иллюстрирующаяповедение, типичное для систем агентов социальной среды (на нримерекомплиментарного этнического контакта). Для оценки работоспособностимодели реализован программный комплекс и проведено компьютерноемоделирование.5. На базе стандартных алгоритмических средств эволюционныхвычислений разработана модель и программный комплекс для решенияприкладной задачи моделирования поведения агентов (абонентовтелефонной сети) в условиях введения в действие двух альтернативтарификации.Методы исследований. Решение поставленных задач сопряжено сприменением методологии MAC, методов оптимизации, статистическойобработки данных, имитационного моделирования, объектноориентированного анализа и проектирования программных средств.Достоверность и обоснованность результатов в частиалгоритмических решений по улучшению сходимости ПГАподтверждается сравнением алгоритмов как по общепринятым, так и по- 8 предлагаемым в работе показателям качества. Верификация предлагаемыхмоделей производится сопоставлением качественных результатовкомпьютерного моделирования с имеющимися статистическими даннымии экспертными заключениями, озвученными в научной литературе.Научная новизна. Впервые оптимизационные структурыэволюционных вычислений применены для моделирования процессовсамоорганизации децентрализованных систем. В результате впервыеудалось создать модель комплиментарного этнического контакта в отличиеот известных работ по некомплиментарному взаимодействию социальныхподсистем. При этом:1. В рамках параллельного ГА обнаружены механизмысамоорганизации.2. Определены понятия внутренней целевой функции и мутационныхпоследовательностей как факторов снижения риска предварительнойсходимости и обеспечения самоорганизации ГА.
3. Спроектированы модели ГА, обнаруживающие автоколебаниягенотипов с динамическими аттракторами в кодируемом генамипространстве рещений. Найдены алгоритмические рещения по улучщениюсходимости ПГА. Практнческая значнмость результатов:1. Предлагаемые в работе алгоритмы и подход к моделированиюпроцессов самоорганизации в открытых динамических системах могутбыть использованы для формализации прикладных моделей социальныхсистем с комплиментарным взаимодействием агентов.2. Разработанные алгоритмические рещения по улучщениюсходимости ПГА позволят рещать задачи поиска экстремума больщойразмерности с меньщими временными затратами.- 9 На защиту выносятся:1. Базовые модели самоорганизации ГА, обеспечиваемой двумяразличными структурами параллельного ГА: с переменнойинтенсивностью отбора и с внутренней целевой функцией.2. Подход к моделированию механизмов самоорганизациидецентрализованных систем в рамках методологии MAC и эволюционныхвычислений.3. Решения по улучшению сходимости ПГА, программный комплексоптимальной настройки параметров и структуры типовых моделей ГА.
4. Приложения алгоритмов самоорганизации к решению задачмоделирования социальной системы с комплиментарным взаимодействиемагентов и технической системы динамического распределения ресурса:модель поведения агентов в условиях введения в действие двухальтернатив тарификации.Внедрение.1. Расчеты эффективности от введения повременной оплаты зателефонные переговоры, проведенные с учетом результатовимитационного моделирования поведения агентов в условиях введения вдействие двух альтернатив тарификации, предоставлены управлениютелефонных сетей г. Камышина.2. Программный комплекс компьютерного моделированиякомплиментарного этнического контакта внедрен в учебный процесс накафедре «Истории и археологии» Волгоградского государственногоуниверситета.Апробация работы.Основные результаты работы докладывались на IX и Xмеждународных конференциях «Математика. Компьютер. Образование»(Дубна 2002, Пушино 2003), I, II и III Всероссийских конференциях«Прогрессивные технологии в обучении и производстве» (Камышин 2002,2004, 2005), научном семинаре НИИ Археологии (Волгофад, ВолГУ 2003),- 1 0 конференции молодых ученых (Волгофад, ВолгГТУ 2001), научномсеминаре кафедры САПР ТРТУ (Таганрог 2005).Основное содержанне работы отражено в четырех главах и трехприложениях. В первой главе приводится аналитический обзор методовмоделирования самоорганизующихся систем. Вторая глава посвященапараметрической адаптации ГА к задачам моделирования эволюционныхпроцессов. В третьей главе разрабатываются новые архитектуры ГА дляописания процессов самоорганизации в децентрализованных системах. Вчетвертой главе приводится постановка прикладных задач моделированиясоциальной системы и технической задачи оптимизации с привлечениемразработанных и стандартных алгоритмов эволюционных вычисленийсоответственно. В приложениях приводится материал, поясняющийустройство ГА, расчеты вычислительной сложности (ВС) генерации, обзорконцепций ПТЭ и эксперименты комплексного анализа сходимостиосновных моделей ГА. Результаты работы опубликованы в [54-59].Автор считает своим приятным долгом выразить благодарность ЕленеГеоргиевне Крущель за вклад в формирование научного мировоззрения,Валерию Анатольевичу Камаеву и Сергею Алексеевичу Фоменкову заобсуждение работы и ценные рекомендации по ее содержанию ипредставлению.
