Содержание к диссертации
Введение
1 Эволюционные модели и алгоритмы оптимизации 11
1.1 Классические модели эволюции 11
1.2 Модель синтетической эволюции 18
1.3 Модели эволюции, построенные на полиморфизме 25
1.4 Выводы 33
2 Разработка и исследование дифференцированного генетического алгоритма 35
2.1 Модель дифференцированного генетического алгоритма 35
2.2 Дифференцированный генетический алгоритм решения задачи безусловной оптимизации 36
2.3 Исследование эффективности дифференцированного ГА решения задачи безусловной оптимизации 43
2.4 Дифференцированный генетический алгоритм решения задачи условной оптимизации 51
2.5 Исследование эффективности дифференцированного генетического алгоритма решения задачи условной оптимизации 54
2.6 Выводы 57
3 Применение дифференцированного генетического алгоритма при решении сложных задач оптимизации 59
3.1 Программная система исследования эффективности ГА 59
3.2 Задача структурно-параметрического синтеза сети Wi-Fi 64
3.2.1 Постановка задачи 64
3.2.2 Алгоритм расчет зоны действия сигнала 68
3.2.3 Программная реализация метода расчта параметров сети Wi-Fi 74
3.2.4 Проверка корректности модели беспроводной сети 78
3.3 Применение ГА при прогнозировании временных рядов 81
3.3.1 Постановка задачи 81
3.3.2 Описание алгоритма построения нечеткого временного ряда82
3.3.3 Программная реализация метода прогноза на основе нечеткого временного ряда 85
3.3.4 Проверка эффективности алгоритма на тестовых данных 88
3.4 Выводы 92
Заключение 93
Библиографический список
- Модели эволюции, построенные на полиморфизме
- Дифференцированный генетический алгоритм решения задачи безусловной оптимизации
- Дифференцированный генетический алгоритм решения задачи условной оптимизации
- Алгоритм расчет зоны действия сигнала
Введение к работе
Актуальность. Для решения сложных задач оптимизации на практике часто применяют эволюционные алгоритмы. Однако, в отличие от эволюции, происходящей в природе, эволюционный алгоритм, в процессе решения задачи оптимизации, только моделирует те процессы в популяции, которые являются существенными для развития. Существует большое количество моделей эволюции, которые могут применяться в качестве базиса для проектирования эволюционных алгоритмов оптимизации, например, модели Ч. Дарвина, Ж. Ламарка, Г. де Фриза, Гулда-Элдриджа и другие. В любом случае эволюционный алгоритм работает с совокупностью индивидов -популяцией, каждый из которых представляет возможное решение проблемы. В процессе работы алгоритм, в рамках выделенного ресурса, исследует пространство поиска путем информационного обмена с внешней средой, то есть популяция всегда эволюционирует в соответствующей среде. В целом, эволюция подразумевает наличие двух главных аспектов: сохранение и изменение. Для эффективной реализации первого аспекта популяция должна быть устойчивой, стабильной, неизменяемой, то есть информационно дистанцироваться от среды. С другой стороны (второй аспект), без тесного информационного контакта со средой невозможен поиск решения - популяция должна постоянно эволюционировать. Таким образом, требования эволюции с точки зрения информационного обмена популяции со средой являются противоречивыми.
В качестве решения данной проблемы алгоритм, вне зависимости от применяемой модели, как эволюционирующая система, удерживает популяцию на некотором оптимальном информационном расстоянии от среды. Например, для реализации первого аспекта используется селективное давление совместно с принципом элитизма, а для второго аспекта применяются операторы рекомбинации и мутации. Однако такой подход порождает дополнительные трудности - например, выбор оптимальных значений параметров генетического алгоритма для решаемой задачи, а также, в зависимости от стратегии поиска, остаются проблемы преждевременной сходимости и стагнации. Источником, описанных трудностей, как правило, является сама концепция алгоритма - модель эволюции.
Таким образом, разработка моделей эволюции и алгоритмов на их основе, позволяющих интегрировать в рамках единого подхода решения по альтернативным эволюционным задачам сохранения и изменения для обеспечения оптимальных условий решения сложных задач оптимизации является актуальной научно-технической задачей.
Целью диссертационной работы является совершенствование эволюционных алгоритмов решения сложных задач оптимизации, направленное на повышение эффективности их работы путем модификации применяемой модели эволюции.
Объектом исследования являются эволюционные алгоритмы оптимизации.
Предметом исследования являются синтетические модели эволюции, применяемые на концептуальном уровне эволюционными алгоритмами оптимизации.
Для достижения поставленной цели необходимо решить следующие задачи:
-
провести анализ моделей эволюции и основанных на них эволюционных алгоритмов оптимизации;
-
разработать модель эволюции, позволяющую эвристическим итеративным методом поиска интегрировать в рамках единого подхода решения по альтернативным эволюционным задачам;
-
алгоритмизировать и программно реализовать разработанную модель эволюции;
-
провести исследование на множестве тестовых данных и определить параметры, существенно влияющие на эффективность разработанного алгоритма и выработать рекомендации по их настройке;
-
провести апробацию разработанного алгоритма на решении сложных практических задач оптимизации, относящихся к классам условной и безусловной однокритериальной оптимизации с алгоритмически заданными целевыми функциями на множестве разношкальных переменных.
Методы исследования. При выполнении диссертационной работы использовались методы эволюционных вычислений, оптимизации, нечеткой логики, теории вероятности и математической статистики, теории алгоритмов, системного анализа, теории радиосвязи, методика разработки интеллектуальных информационных систем и другие.
Научная новизна проведенных исследований и полученных в работе результатов заключается в следующем:
-
разработана модифицированная синтетическая модель эволюции для генетического алгоритма, отличающаяся от известных наличием механизмов внутривидовой дифференциации популяции и специализации решений по альтернативным эволюционным задачам, и позволяющая повысить эффективность работы алгоритма.
-
разработан, программно реализован и исследован новый дифференцированный генетический алгоритм безусловной оптимизации, отличающийся от известных способом накопления, апробации и селекции решений, и позволяющий сократить вычислительные затраты за счет повышения скорости поиска решения без снижения точности.
-
разработан, программно реализован и исследован новый дифференцированный генетический алгоритм условной оптимизации, отличающийся от известных новым способом учета ограничений, и обладающий меньшим количеством настраиваемых параметров при сопоставимых показателях надежности и скорости поиска решения.
-
разработан и программно реализован новый метод структурно-параметрического синтеза беспроводных локальных сетей стандарта IEEE 802.1 lg дифференцированным генетическим алгоритмом, отличающийся от известных автоматическим способом подбора компонентов сети и
настройкой их параметров, и позволяющий количественно оценить степень соответствия модели беспроводной сети предъявляемым требованиям и ограничениям.
Теоретическая значимость результатов диссертационного исследования состоит в разработке новых эволюционных алгоритмов решения сложных задач безусловной и условной оптимизации, основанных на модифицированной синтетической модели эволюции, и методе структурно-параметрического синтеза беспроводных локальных сетей, позволяющего подбирать компоненты сети и настраивать их параметры дифференцированным генетическим алгоритмом с соблюдением заданных ограничений. Разработанные эволюционные алгоритмы позволяют интегрировать в рамках единого подхода решения по альтернативным эволюционным задачам сохранения и изменения путем дифференциации популяции решений, что определяет вклад результатов диссертационного исследования в теорию и практику применения эволюционных алгоритмов оптимизации.
Практическая значимость. На основе разработанного в ходе диссертационного исследования дифференцированного генетического алгоритма создано алгоритмическое обеспечение для программных систем, которое позволяет, используя рекомендации по настройки его параметров, широкому кругу специалистов, не владеющих аппаратом эволюционных алгоритмов, эффективно решать сложные задачи оптимизации, возникающие в реальной практике.
Материалы диссертационного исследования и разработанные программные системы были использованы для решения задачи структурно-параметрического синтеза беспроводных локальных сетей, а также задач прогнозирования курса валют, рождаемости, миграции населения и ряда других.
Реализация результатов работы. Работа поддержана Фондом содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса») в рамках НИОКР «Автоматизация проектирования беспроводной сети интеллектуальным программным обеспечением» и «Разработка экспертной системы проектирования беспроводной сети на базе клиент-серверной технологии» на 2011-2013 гг.
Результаты диссертационного исследования использованы в ходе выполнения:
1)ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы», мероприятие 1.4. «Проведение проблемно-ориентированных поисковых исследований и создание научно-технического задела по перспективным технологиям в области информационно-телекоммуникационных систем». Тема работы - «Разработка технологии синтеза настроек параметров безопасности автоматизированных систем в защищенном исполнении» (2011-2012 гг.), ГК№ 07.514.11.4047 от 06.10.2011.
-
РФФИ «Разработка коллективов биоинспирированных алгоритмов обнаружения инцидентов информационной безопасности в автоматизированных системах» (2012-2013 гг.), №12-01-31123 от 18.10.2012, №12-01-31123 от 28.05.2013 г.
-
Грант Президента, программа поддержки молодых кандидатов наук, 2013-2014 гг., МК-473.2013.9 «Разработка и исследование биоинспирированных алгоритмов интеллектуального обеспечения безопасности информации в автоматизированных системах».
Две программные системы прошли государственную экспертизу и были зарегистрированы в Федеральной службе по интеллектуальной собственности. Программные системы используются в учебном процессе на кафедре безопасности информационных технологий института информатики и телекоммуникаций СибГАУ при выполнении лабораторных и курсовых работ, а так же в рамках программы повышения квалификации «Построение беспроводных локальных вычислительных сетей на основе оборудования D-Link».
Материалы диссертационного исследования и разработанная программная система были использованы при проектировании и развертывании беспроводной сети AirMAX ООО «Логический уровень» в п. Солонцы, Красноярского края.
Основные защищаемые положения:
-
разработанная модифицированная синтетическая модель эволюции позволяет создать новый класс эволюционных алгоритмов, обладающих механизмами внутривидовой дифференциации популяции решений.
-
разработанный дифференцированный генетический алгоритм безусловной оптимизации с дифференциацией популяции решений по альтернативным эволюционным задачам превосходит стандартный генетический алгоритм по надежности и быстродействию.
-
дифференциация популяции решений и контроль перехода решений между субпопуляциями позволяют создать новый способ учета ограничений и применять дифференцированный генетический алгоритм для решения задач условной однокритериальной оптимизации.
-
метод структурно-параметрического синтеза беспроводных локальных сетей дифференцированным генетическим алгоритмом позволяет в автоматизированном режиме выбирать и размещать беспроводное оборудование, и оптимизировать его параметры настройки в соответствии с заданными ограничениями.
Апробация работы. Основные положения и отдельные результаты диссертационной работы были представлены на Всероссийской научно-практической конференции студентов, аспирантов и молодых специалистов «Актуальные проблемы авиации и космонавтики» (Красноярск, СибГАУ, 2009); IX Всероссийской научной студенческой конференции с международным участием «Молодежь. Общество. Современная наука, техника и инновации» (Красноярск, СибГАУ, 2010); Международных научно-практических конференциях «Решетневские чтения» (Красноярск,
СибГАУ, 2009-2012); І и II Всероссийских научных конференциях «Теория и практика системного анализа» (Рыбинск, Институт системного анализа РАН иРГАТА,2010,2012).
Диссертация в целом обсуждалась на научно-технических семинарах кафедры системного анализа и исследования операций СибГАУ и кафедры безопасности информационных технологий СибГАУ.
Публикации. По теме диссертации опубликовано шестнадцать работ, в том числе четыре в изданиях из перечня ВАК, а также зарегистрированы две программные системы.
Структура работы. Диссертация содержит 109 страниц основного текста и состоит из введения, трёх глав, заключения, списка литературы из 101 источника и 4 приложений, содержащих 24 страницы; основной текст диссертации включает 10 таблиц, 32 рисунка.
Модели эволюции, построенные на полиморфизме
По приведенной схеме эволюции возможно составить алгоритм решения оптимизационной задачи, интерпретировав каждый блок, как некоторую операцию над множеством решений [15, с. 102]. 1. Популяция. Пусть существует популяция альтернативных решений исходной задачи и задано дискретное время эволюции Т, определяющее количество итераций алгоритма. 2. Наследственность. После реализации каждой итерации алгоритма появляется новое поколение (потомство) альтернативных решений. 3. Изменчивость. В новой популяции (поколении) остаются отличающиеся друг от друга альтернативные решения. 4. Отбор. По заданным правилам отбираются элитные решения с лучшим значением целевой функции. Это соответствует принципу Ч. Дарвина «выживают сильнейшие». 5. Эволюционная смена форм. Лучшие решения, выживают в результате реализации схемы эволюции Дарвина и они постепенно, поколение за поколением становятся преобладающими (доминирующими) в данной популяции.
Дадим развернутую интерпретацию представленного алгоритма. Его работа осуществляется с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, следовательно, свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.
Так воспроизводится новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие представители предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи.
История эволюционных алгоритмов началась с разработки ряда различных независимых моделей. Идея применения эволюционного моделирования для прикладных математических и компьютерных задач появилась в начале 50-х годов с развитием генетики. В 1954 году была опубликована работа «Численные примеры процессов эволюции» («Esempi numerici di processi di evoluzione») норвежско-итальянского математика Нильса
Алла Баричелли [58], но она не получила широкой известности. В последующие годы им были изданы еще две работы «Symbiogenetic evolution processes realized by artificial methods» [57] и «Numerical testing of evolution theories» [56], – направленные на понимание природного феномена наследственности. Примерно в то же время австралийский генетик Алекс Фрейзер опубликовал серию работ по моделированию искусственного отбора организмов: «Simulation of genetic systems by automatic digital computers. 5. linkage, dominance, and epistasis» [78] и «Simulation of genetic systems» [77]. Несмотря на то, что работы обоих авторов были направлены, прежде всего, на понимание природного феномена наследственности, работа Фрейзера имеет много общего с сегодняшним видением генетических алгоритмов. Он моделировал эволюцию 15-битных строк и подсчитывал процентное содержание особей с удачным фенотипом в успешных поколениях, что на сегодняшний момент применятся во всех эволюционных алгоритмах без исключения. Его работы напоминают оптимизацию функций, однако в работах Фрейзера нет ни одного упоминания о возможности использования генетического алгоритма для решения искусственных задач. Основателем современной теории генетических алгоритмов (ГА) считается Джон Холланд. В первых его работах внимание уделялось, прежде всего, способности природных систем к адаптации, а его главной целью было создание такой системы, которая могла бы приспосабливаться к любым условиям окружающей среды. Д. Холланд впервые предложил алгоритм, который известен как упрощенный «репродуктивный план Д. Холланда» [85, 86]. «Репродуктивный план Д. Холланда» был структурирован и изложен Кеннетом Де Йонгом (Kenneth De Jong) в диссертации «An analysis of the behavior of a class of genetic adaptive systems» [66] на степень доктора философии в 1975 и ряде более поздних публикаций [67, 65]. В работе Д. Йонга был проведен анализ операторов эволюционного процесса. К ним относятся кроссинговер, инверсия, мутация и др. Предложен ряд функций, которые стали эталоном для проведения компьютерных экспериментов с использованием различных эволюционных стратегий и алгоритмов. Предложенная математическая модель эволюционного процесса представляется как способность «лучших» индивидуумов оказывать большее влияние на состав новой популяции на основе длительного выживания их более многочисленных потомков. Подробно классический генетический алгоритм (ГА) был описан Д. Гольдбергом на основе работ Д. Холланда в [79]. В 1975 году Холланд публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems» [85]. В ней он впервые ввл термин «генетический алгоритм» и предложил схему классического генетического алгоритма (рисунок 2).
Дифференцированный генетический алгоритм решения задачи безусловной оптимизации
На основе описанной модели был разработан дифференцированный генетический алгоритм (ДГА), использующий в качестве базиса принципы классического генетического алгоритма [39, 23], следовательно, он применим для решения задачи однокритериальной безусловной оптимизации. Приведем описание данного алгоритма.
Для каждого индивида, представляющего отдельное решение задачи, необходимо хранить значение параметров целевой функции (хромосомы), тип индивида (для сохранения информации или эволюционных изменений (соответственно Sk и So) и время жизни индивида (Tlife), т.е. в скольких раундах эволюции он «выжил». Первоначально популяция делится на особи двух типов sk и so в некотором соотношении. В процессе работы алгоритма оно меняется по закону синуса для управления работой алгоритма, аналогично изменению внешней среды.
В данной работе кодирование гена осуществлялось битовой строкой, представляемой как положительное целое число длиной 64 бита, которое в процессе реализации алгоритма определялось типом unsigned_int64. Это позволяет кодировать каждым геном до 264 или 1019 возможных вариантов значений. Сам же набор генов (хромосома), характеризующий некоторое значение целевой функции, представлен в качестве одномерного массива размерностью равной количеству генов. Выбор такого представления обусловлен тем, что наибольшую эффективность среди различных способов представления чисел при вычислениях дают именно целые беззнаковые, а современные процессоры обладают разрядностью регистров в 64 бита, что позволяет им максимально эффективно обрабатывать числа именно данной разрядности.
Другой особенностью реализации представления чисел в гене, применнной в данной работе, является представление десятичного числа не бинарным кодом. Это обусловлено тем, что в бинарном коде соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в двоичном представлении различаются в четырх позициях, что значительно увеличивает пространство поиска и тем самым затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Решением данной проблемы является использование кодирования, при котором соседние числа отличаются меньшим количеством позиций, а в идеале значением одного бита. Таким кодом является код Грея [70], который целесообразно использовать при реализации генетических алгоритмов, поскольку он не увеличивает бинарное пространство поиска. Этот вид бинарного кодирования десятичных чисел был применен в данной работе.
Для преобразования из двоичного кода в код Грея при программной реализации алгоритма была использована следующая функция [29]: unsigned _int64 grayencode (unsigned _int64 grey) {
Так как в качестве диапазонов поиска для генов практически всегда используются интервалы не представимые с помощью целых чисел, то необходимо использовать разбиение заданного интервала на N пронумерованных промежутков. При этом длина промежутка не должна превышать установленной точности поиска решения для переменной. В качестве значения переменной выбирается середина интервала. Такая схема представления позволяет избежать лишних значений переменных, которые образуются при разбивании интервала на промежутки с точностью 10–N. Для пояснения приведм формулу для пересчета к-го интервала в число из промежутка [а, Ь] разбитого на 2N частей (2.1).
Из-за особенностей дифференцированного ГА стандартные генераторы псевдослучайных чисел не могут быть применены, поскольку имеют нормальное распределение, т.е. для них выше вероятность получить число из некоторой части диапазона. По условию работы алгоритма требуется получать равномерное распределение сгенерированных значений по всему диапазону. Для решения этой задачи был использован BBS-генератор (алгоритм был предложен в 1986 году Л. Блюмом, М. Блюмом и М. Шубом). Приведм алгоритм данного генератора псевдослучайных чисел [88].
Для получения числа длиной k–бит необходимо k–раз вычислить xi из 4 пункта алгоритма и формировать биты искомого числа из последних бит вычисленных xi. Вероятность получить 1 в i+1 бите в данном алгоритме равна , следовательно, числа, получаемые при его использовании, будут иметь равномерный закон распределения [16]. Блок-схема BBS-генератора приведена на рисунке 11.
Формирование популяции. Первоначально значения хромосом в популяции заполняется случайными числами, распределнными по равномерному закону (используется BBS–генератор), которые преобразуются в код Грея. После этого популяция сортируется по значению целевой функции. Отбирается необходимое количество sk индивидов, которые показали наилучшее значение целевой функции.
Раунд алгоритма. В каждом раунде раз формируется потомок. Для этого случайно выбирается первый родитель из числа индивидов. Второго родителя выбираем по турнирной схеме [73] из числа So индивидов, т.е. n-раз выбираем случайного представителя и среди данной выборки выбираем того, у которого значение целевой функции лучше. Если значения равны, то тот у которого значение параметра Tlife больше. При определении случайного родителя необходимо обязательно использовать генератор случайных чисел с равномерным распределением, для того чтобы все представители популяции имели одинаковые шансы стать родителями. После определения пары родителей формируется потомок путм скрещивания (одноточечное, двухточечное или равномерное) и к нему применяется оператор мутации [71]. При формировании потомка рассматриваются различные комбинации хромосом, полученные от родителя и полученные в ходе скрещивания хромосом родителей, и из них выбирается лучшая по значению целевой функции. После этого потомок сравнивается по значению целевой функции с родителем. Если потомок лучше, то он замещает so родителя, а его время жизни обнуляется. Если лучше родитель, то потомок отбрасывается, а время жизни родителя увеличивается на 1.
После окончания формирования потомков происходит изменение соотношения количества и индивидов друг к другу. При недостатке sk индивидов они добавляются из So. При этом используются индивиды с самым большим «временем жизни». Если новый размер Sk меньше, чем на предыдущей итерации алгоритма, то избыток переносятся в So, при этом время жизни у перенеснных индивидов обнуляется. Далее осуществляется поиск индивидов для сохранения их «генетической» информации в ядре решений, т.е. перенос индивида из So в Sk. Для этого просматриваем всех индивидов So и отбираем тех, чь время жизни больше заданного значения Tlife. После этого для каждого индивида So в отдельности производится поиск среди таких, что имеют наихудшее значение целевой функции и срок жизни больше Tlife или имеют срок жизни больше 2Tlife. После этого сравниваем значение целевой функции найденного индивида со значением функции индивида. Если лучшее значение у , то заменяем им при этом обнуляем
Дифференцированный генетический алгоритм решения задачи условной оптимизации
Самостоятельной задачей при прогнозировании на основе нечетких временных рядов является определение оптимальных значений, обеспечивающих максимальную точность прогнозирования, для действительных чисел Dj, D2, используемых при корректировке универсума U, количества интервалов разбиения п универсума U и параметра а є [0,1] вместо степени принадлежности 0,5 в лингвистических термах Аг. Применение ГА позволит автоматизировать нахождение оптимальной комбинации значений выше перечисленных параметров. Поэтому хромосома для генетического алгоритма будет иметь вид: фи D2, п, а).
Количество бит и диапазон значений для Dj и D2 определяется пользователем, но предустановленным значением для них будет являться принадлежность интервалу [0, d], где d=Dmax-Dmin. Для кодирования и є [2, nmax], где (т - количество значений временного ряда), необходимо выделить 5 бит. Для ає[0,1] - 7 бит. В качестве целевой функции может быть использована функция (3.13) и е следует минимизировать. Во время работы ГА возможно появление комбинация параметров, при которой при вычислении по формулам (3.10), (3.12) получиться значение вида “0/0”, вследствие наличия группы логических нечетких зависимостей с неопределенными правыми частями. Для исключения данных решений из дальнейшего рассмотрения необходимо назначить им максимально худшее значение функции пригодности – 100.
В качестве ГА был использован дифференцированный ГА, описанный ранее. Алгоритм построения нечеткого временного ряда (для деффазификации при поиске решения используется только метод центра тяжести, а так же учет повторяющихся НМ) и дифференцированный генетический алгоритм, позволяющий находить его оптимальные параметры, были реализованы в виде программного средства. Его интерфейс представлен на рисунке 31.
В левой части окна находиться текстовая область для вывода информации об индивидах в популяции каждого 10 поколения. Для каждого индивида приводятся значение переменных в хромосоме в следующем порядке: (D1,D2,n,). Правее находиться полоса прогресса, заполняемая по мере исчерпания ресурса вычислений. В правой части окна на двух вкладках представлена в виде графиков информация о работе ГА (выводиться значение целевой функции для наилучшего, наихудшего индивида текущей популяции и среднее значение целевой функции) и строится временной ряд с найденными наилучшими параметрами после окончания работы генетического алгоритма.
В нижней части окна расположен ряд управляющих кнопок. Для начала работы с программой необходимо загрузить данные со значениями временного ряда из текстового файла. Он имеет следующий формат. В первой строке указывается общее количество фактов во временном ряду. Далее непосредственно идут значения фактов по порядку, причем каждое значение располагается на новой строке. Загрузка файла осуществляется при помощи кнопки «Открыть». Она вызывает стандартное окно открытия файла, в котором необходимо указать файл с данными. После этого станет доступна кнопка «Пар НВР». Она осуществляет вызов окна с параметрами нечеткого временного ряда (рисунок 32).
В полях ввода пользователь может указать собственные максимально возможные значения параметров D1, D2. Между этими полями для справки выводятся значения Dmin, Dmax рассчитанные по значениям временного ряда. Количество бит для D1, D2 может быть изменено при помощи соответствующих переключателей под полями, при использовании которых автоматически изменятся шаг дискретизации для данных переменных, отображаемый над полями ввода. Пользователь так же может указать максимальное количество интервалов п, оно будет увеличено до ближайшего целого числа, являющего степенью 2.
После всех предварительных настроек становиться доступна кнопка «Старт», которая осуществляет запуск ГА для нахождения оптимальных параметров НВР. По окончанию работы алгоритма под графиком будут отображены данные о наилучшем найденном решении (значения всех переменных в хромосоме), значении целевой функции для него, номер итерации, на которой оно было найдено, и общее количество вычислений целевой функции. Кроме того будут построены три графика: - красный - реальное значение временного ряда; - зеленый - прогнозируемые значения, рассчитанные с помощью НВР с использование в качестве итогового метода дефаззификации метода центра тяжести; - синий - прогнозируемые значения, рассчитанные с помощью НВР с использование в качестве итогового метода дефаззификации метода левого модального значения.
Соответственно для первого и второго метода в самом низу окна приводятся процентные значения средней относительной ошибки прогноза и относительной ошибки прогнозирования.
Под окном вывода информации о работе ГА расположено 4 поля ввода соответствующих Dj, D2, п, а. Это дает пользователю возможность, введя интересующие его значения параметров, построить НВР. Он строится с использованием двух методов дефаззификации (центра тяжести и левого модального значения). Результаты расчетов будут отображены на графиках и вычислены относительные ошибки прогнозирования.
Проверка эффективности алгоритма на тестовых данных Для проверки работоспособности реализованного алгоритма проведем с его помощью прогнозирование и моделирование 9 временных рядов, описывающих процессы из различных областей [97]. Результаты их прогнозирования приведены в приложении В.
Была программно реализована модель для краткосрочного прогнозирования процессов, представленных временными рядами с короткой длиной актуальной части, в условиях отсутствия априорной информации о вероятностных характеристиках процесса, на основе нечетких временных рядов. В связи с тем, что параметры модели имеют довольно большой диапазон изменений и не всегда очевидно, какие из них будут давать приемлемый результат моделирования и прогнозирования, необходимо было автоматизировать процесс подбора их оптимальных значений. Данная задача была осуществлена при помощи генетического алгоритма, позволяющего, используя незначительное количество вычисление, находить достаточно хорошие комбинации параметров.
Совместная работа двух реализованных алгоритмов позволила уменьшить ошибку прогнозирования на шаг вперед для 4 тестовых временных рядов, относящихся к различным сферам, до 0,2 – 2%, что является хорошим результатом. Хорошие результаты были получены для временных рядов как обладающих четко выраженной сезонной составляющей, так и нет.
Использование двух методов дефаззификации позволило получить два возможных прогноза и сравнить их между собой. В большинстве случаев лучшие результаты показывал метод центра тяжести.
При применении метода к сильно зашумлнным данным точность аппроксимации значительно снизилась за счет наличия случайного зашумления, которое не может быть спрогнозировано на основе предыдущих данных. При этом точность предсказания тестового значения уменьшилась до 3%, что все равно позволяет использовать данный метод для прогнозирования.
При использовании предварительно очищенных от шума данных ошибка прогноза и аппроксимации стала меньше 0,5%. Следовательно, данный метод наиболее эффективен при работе со слабо зашумленными данными или данными, прошедшими предварительную очистку от шума.
Алгоритм расчет зоны действия сигнала
Результаты проведенных исследований показывают, что использование нечетких временных рядов совместно с дифференцированным генетическим алгоритмом позволяет создать программное средство, обладающее минимум настраиваемых параметров для достижения оптимальных показателей надежности прогнозирования при стандартных настройках. Рассматриваемая модель подходит для краткосрочного прогнозирования как стационарных, так и нестационарных коротких временных рядов, что подтверждается низким значением ошибки на тестовых данных.
Сравнение эффективности нечетких временных рядов с другими методами прогнозирования позволяет говорить о сопоставимом уровне качества прогноза и аппроксимации. При этом будет затрачено меньше ресурсов на доказательство применимости статистической модели к обрабатываемым данным. В сравнении с другим интеллектуальным методом анализа данных (нейросетью) данная комбинация алгоритмов незначительно уступает ей в точности аппроксимации и значительно превосходит в точности прогнозирования. При этом следует учитывать, что использованная для тестирования нейронная сеть обладала простейшей структурой. Данный момент определялся тем, что неподготовленный пользователь самостоятельно выберет наиболее простой вариант, поэтому он будет эквивалентен настройки 5 параметров в комбинации НВР и ГА.
Следовательно, рассмотренная комбинация алгоритмов и созданная на их основе программная система предназначена для пользователей, мало знакомых с математической статистикой, но при этом желающих получить достоверный прогноз на основе незначительного количества статистических данных [26]. 3.4 Выводы
В данной главе продемонстрированы решения практических задач, относящихся к сложным задачам оптимизации, а именно автоматическое проектирование беспроводных сетей и прогнозирование временных рядов. Отличительной особенностью программ для решения описанных задач является использование в них интеллектуальных информационных технологий, минимизирующих влияние человека на поиск оптимального решения, что достигается благодаря использованию интеллектуального метода поиска решений, а именно, дифференцированного генетического алгоритма.
Кроме того разработанные программные средства имеют коммерческую ценность, поскольку либо не имеют аналогов, т.к. подобные задачи рассчитывались раньше только экспертом и не были автоматизированы, либо предлагают простоту получения конечного результата, не требуя знаний математической статистики. ЗАКЛЮЧЕНИЕ
В современном информационном обществе, когда требуется быстро принять правильное решение, использование аппарата интеллектуальных информационных технологий позволяет находить оптимальное решение возникающих задач в короткие сроки без привлечения сторонних специалистов. Поэтому разработка алгоритмов, относящихся к данному направлению, на сегодняшний день является одной из актуальных научно-практических задач.
В работе рассматривается разработка, исследование и применение к решению практических задач дифференцированного генетического алгоритма. По итогам диссертационного исследования были получены следующие результаты.
1. Разработана модифицированная синтетическая модель эволюции для генетического алгоритма, отличающаяся от известных наличием механизмов внутривидовой дифференциации популяции и специализации решений по альтернативным эволюционным задачам.
2. Разработан, программно реализован и исследован новый дифференцированный генетический алгоритм безусловной оптимизации, отличающийся от известных способом накопления, апробации и селекции решений.
3. Разработан, программно реализован и исследован новый дифференцированный генетический алгоритм условной оптимизации, отличающийся от известных способом учета ограничений.
4. Разработан и программно реализован новый метод структурно-параметрического синтеза беспроводных локальных сетей дифференцированным генетическим алгоритмом, отличающийся от известных автоматическим способом подбора структурных компонентов сети и настройкой их параметров с соблюдением заданных ограничений. 5. Эффективность разработанных алгоритмов продемонстрирована в ходе решения задачи структурно-параметрического синтеза беспроводных локальных сетей, а также задач прогнозирования курса валют, рождаемости, миграции населения и ряда других.
Таким образом, в диссертационной работе разработан, программно реализован, исследован и проверен на тестовых и прикладных задачах новый дифференцированный генетический алгоритм решения задач безусловной и условной оптимизации, обладающий эффективностью, сопоставимой по сравнению с известными подходами, и позволяющий успешно решать широкий круг практических задач, что является вкладом в теорию и практику эволюционных алгоритмов оптимизации.
