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

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

Паротькин Николай Юрьевич

ДИФФЕРЕНЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ ОПТИМИЗАЦИИ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

21 2013

Красноярск - 2013

005539421

Работа выполнена в ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» (СибГАУ), г. Красноярск

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

Жуков Вадим Геннадьевич

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

Охорзин Владимир Афанасьевич ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», профессор кафедры прикладной математики

доктор технических наук, профессор Спицын Владимир Григорьевич

ФГБОУ ВПО «Национальна

исследовательский Томский политехнический университет», профессор кафедры

вычислительной техники

Ведущая организация: Омский филиал Федерального государственного

бюджетного учреждения науки «Институт математики им. С.Л. Соболева» Сибирского отделения Российской академии наук (ОФ ИМ СО РАН), г. Омск

Защита состоится «10» декабря 2013 г. в 16 часов на заседании диссертационного совета Д 212.249.02 при ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» по адресу: 660014 г. Красноярск, проспект имени газеты «Красноярский рабочий», 31

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева

Автореферат разослан «8» ноября 2013 г.

Ученый секретарь диссертационного совета

Александр Алексеевич Кузнецов

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

Актуальность. Для решения сложных задач оптимизации на практике часто применяют эволюционные алгоритмы. Однако, в отличие от эволюции, происходящей в природе, эволюционный алгоритм, в процессе решения задачи оптимизации, только моделирует те процессы в популяции, которые являются существенными для развития. Существует большое количество моделей эволюции, которые могут применяться в качестве базиса для проектирования эволюционных алгоритмов оптимизации, например, модели Ч. Дарвина, Ж. Ламарка, Г. де Фриза, Гулда-Эдцриджа и другие. В любом случае эволюционный алгоритм работает с совокупностью индивидов -популяцией, каждый из которых представляет возможное решение проблемы. В процессе работы алгоритм, в рамках выделенного ресурса, исследует пространство поиска путем информационного обмена с внешней средой, то есть популяция всегДа эволюционирует в соответствующей среде. В целом, эволюция подразумевает наличие двух главных аспектов: сохранение и изменение. Для эффективной реализации первого аспекта популяция должна быть устойчивой, стабильной, неизменяемой, то есть информационно дистанцироваться от среды. С другой стороны (второй аспект), без тесного информационного контакта со средой невозможен поиск решения - популяция должна постоянно эволюционировать. Таким образом, требования эволюции с точки зрения информационного обмена популяции со средой являются противоречивыми.

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

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

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

Объектом исследования являются эволюционные алгоритмы оптимизации.

Предметом исследования являются синтетические модели эволюции, применяемые на концептуальном уровне эволюционными алгоритмами оптимизации.

Для достижения поставленной цели необходимо решить следующие задачи:

1) провести анализ моделей эволюции и основанных на них эволюционных алгоритмов оптимизации;

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

3) алгоритмизировать и программно реализовать разработанную модель эволюции;

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

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

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

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

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

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

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

4) разработан и программно реализован новый метод структурно-параметрического синтеза беспроводных локальных сетей стандарта IEEE 802.1 lg дифференцированным генетическим алгоритмом, отличающийся от известных автоматическим способом подбора компонентов сети и

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

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

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

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

Реализация результатов работы. Работа поддержана Фондом содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса») в рамках НИОКР «Автоматизация проектирования беспроводной сети интеллектуальным программным обеспечением» и «Разработка экспертной системы проектирования беспроводной сети на базе клиент-серверной технологии» на 2011-2013 гг.

Результаты диссертационного исследования использованы в ходе выполнения:

1)ФЦП «Исследования и разработки, по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы», мероприятие 1.4. «Проведение проблемно-ориентированных поисковых исследований и создание научно-технического задела по перспективным технологиям в области информационно-телекоммуникационных систем». Тема работы - «Разработка технологии синтеза настроек параметров безопасности автоматизированных систем в защищенном исполнении» (2011-2012 гг.), ГК № 07.514.11.4047 от 06.10.2011.

2) РФФИ. «Разработка коллективов биоинспирированных алгоритмов обнаружения инцидентов информационной безопасности в автоматизированных системах» (2012-2013 гг.), №12-01-31123 от 18.10.2012, №12-01-31123 от 28.05.2013 г.

3) Грант Президента, программа поддержки молодых кандидатов наук, 2013-2014 гг., МК-473.2013.9 «Разработка и исследование биоинспирированных алгоритмов интеллектуального обеспечения безопасности информации в автоматизированных системах».

Две программные системы прошли государственную экспертизу и были зарегистрированы в Федеральной службе по интеллектуальной собственности. Программные системы используются в учебном процессе на кафедре безопасности информационных технологий института информатики и телекоммуникаций СибГАУ при выполнении лабораторных и курсовых работ, а так же в рамках программы повышения квалификации «Построение беспроводных локальных вычислительных сетей на основе оборудования Б-1Лпк».

Материалы диссертационного исследования и разработанная программная система были использованы при проектировании и развертывании беспроводной сети АйгМАХ ООО «Логический уровень» в п. Солонцы, Красноярского края.

Основные защищаемые положения:

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

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

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

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

Апробация работы. Основные положения и отдельные результаты диссертационной работы были представлены на Всероссийской научно-практической конференции студентов, аспирантов и молодых специалистов «Актуальные проблемы авиации и космонавтики» (Красноярск, СибГАУ, 2009); IX Всероссийской научной студенческой конференции с международным участием «Молодежь. Общество. Современная наука, техника и инновации» (Красноярск, СибГАУ, 2010); Международных научно-практических конференциях «Решетневские чтения» (Красноярск,

СибГАУ, 2009-2012); I и II Всероссийских научных конференциях «Теория и практика системного анализа» (Рыбинск, Институт системного анализа РАН иРГАТА, 2010,2012).

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

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

Структура работы. Диссертация содержит 109 страниц бсновного текста и состоит из введения, трёх глав, заключения, списка литературы из 101 источника и 4 приложений, содержащих 24 страницы; основной текст диссертации включает 10 таблиц, 32 рисунка.

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

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

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

Так, наиболее распространённая модель эволюции Дарвина и реализующий ее классический генетический алгоритм, не обладают точными средствами по поиску конкретных решений, а задают только общий характер поиска, поэтому существует проблема, что найденное алгоритмом решение является хотя бы локально-оптимальным. Эволюционные алгоритмы, в основе которых лежит модель эволюции Ламарка и применение методов локального поиска, так же зависят от выбора параметров, что оставляет проблему глобальной сходимости алгоритма для конкретной задачи.

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

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

появления и закрепления, основные положения которых отраженны в работах К. Поппера, Ю.П. Алтухова, В.А. Геодакяна, а также в типологической концепции вида и сальтационного видообразования.

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

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

Таким образом, условная упрощенная схема предлагаемой модели эволюции представлена на рисунке 1.

_| Вход

I Популяция

Дифференциация вида (популяции)

1 4

Внешняя Оперативная Консервативная

среда подсистема подсистема

Приспособляемость i—»I Наследственность Адаптация

i

Отбор J

1

Эволюционная

смена форм

Рисунок 1 - Условная схема модели эволюции 8

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

Сформулируем отличительные особенности и основные характеристики дифференцированного генетического алгоритма, реализующего предлагаемую модель эволюции:

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

2) Применение генератора псевдослучайных чисел, обладающего хорошими статистическими характеристиками для повышения качества генерации случайных последовательностей чисел, например, ВВ8-генератор (алгоритм Блюма-Блюма-Шуба).

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

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

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

6) В формировании новых решений могут участвовать только пары

при этом решение Б1к выбирается случайным образом из а

решение по турнирной схеме из 50.

7) Применение различных стратегий формирования нового поколения для оперативной и консервативной подсистем. С учетом сохранения своих специализаций для решений оперативной подсистемы стратегия аутбридинга, а для консервативной - инбридинг.

8) Применение в качестве критерия остановки работы' алгоритма комплексный показатель, который учитывает динамику следующих параметров: дисперсия генотипов и фенотипов оперативной и консервативной субпопуляций, соотношение

Таким, образом, блок-схема дифференцированного генетического алгоритма представлена на рисунке 2.

Генерация новой популяция

Вычисление пригодности индивидов

...................4...........—

Формирование 50 и 5*

л

Определение нового значения 50/5к

X

Критерий останова _

Нет

Вычисление продолжительности жизни индивидов

_........1............_.......

Мутация 5*

Да

Вывод лучшего решения

Рекомбинация

Конец

У

Рисунок 2 - Блок-схема дифференцированного генетического алгоритма

Дифференцированный генетический алгоритм был реализован программно и апробирован на решении тестовых задач безусловной однокритериапьной оптимизации. Устанавливались следующие ограничения на используемые ресурсы при проведении тестирования: количество повторных запусков с одинаковыми параметрами - 50; количество поколений - 100; количество индивидов —100.

Исследование эффективности алгоритма на множестве тестовых задач проводилось при варьировании следующих параметров: параметр время жизни - Та(е\{5; 10; 15}; доля индивидов {1/3; 1/5; 1/10); тип скрещивания: {одноточечное, двухточечное}; мутация: {низкая, средняя, высокая}. В таблице 1 приведены данные о выделяемом алгоритму ресурсе для нахождения решения с заданной точностью.

е Функция ш, бит Интервал поиска т ^ . N * 100, %

ш-5 38 [-10; 201 0,0000571 525394 2,760» 10" 0,00000362

Сомбреро 34 Г-10; 31 0,0000991 131181 1,721*10'° 0,00005811

Шекеля 42 [-65,536; 401 0,00005 211072О 4,455*10" 0,00000022

Растригина 36 И0;161 0.0000992 262097 6,869* 10ш 0,00001456

Гиперэлипсойд 32 [-10; 81 0,000274 65693 4,316*10' 0,00023171

Гриванка 32 [-16; 14] 0,000457 65536 4,295*10' 0,00023283

Швефеля 42 [-500; 5001 0,000476 2097152 4,398*10и 2,273*10""'

Розенброка 42 [-512; 5001 0,0004825 2097152 4,398*1012 2,273*10"и'

ю-2 ОеЛтй2 24 [-10; 201 0,000916 32751 1,073*10' 0,00093228

Сомбреро 22 [-10;31 0,000793 16393 2,687*108 0,00372100

Шекеля 28 [-65,536; 40] 0,000805 131101 1,719*10'" 0,00005818

Растригина 24 [-10;16] 0,0007934 32770 1,074*10' 0,00093119

Гиперэлипсойд 24 [-10; 81 0,004394 4096 1,678*10' 0,059604645

Гриванка 26 [-16; 141 0,003662 8192 6,711*10' 0,014901161

Швефеля 36 . [-500; 5001 0,003815 262144 6,872* 10'" 0,00001455

Розенброка- 36 [-512; 5001 0,003860 262144 6,872* 10ш 0,00001455

Приведём описание обозначений из заголовков таблицы 1:

а) е - точность поиска,

б) - длина хромосомы,

в) N1 = {Ь — а)/т, где Л^ - количество точек поискового пространства на 1-ю переменную; т - шаг дискретизации; а,Ь— начало и конец интервала поиска.

г) N - общее количество точек поискового пространства функции.

д) Ыа - количество точек поискового пространства алгоритма (рес>ус), при установленных ограничениях; 100 поколений * 100 индивидов или 10 .

Для определения оптимальных параметров настроек дифференцированного генетического алгоритма было проведено две серии тестов для Ах равного 0,01 и 0,001 (фрагмент результатов исследования представлен в таблице 2). ■

Таблица 2 - Результаты исследования эффективности для тестов Лх = 0,01 и Ах = 0,001

Функция Тест Дх = 0,01 Тест Лх = 0,001

Надёжность (п, %) Скорость (5) Надёжность (и, %) Скорость (5)

Ве1о1^2 100 16,74 100 30,88

Сомбреро 100 21 100 35,8

Шекеля 48 16,21 12 21,17

Растригина 100 7,47 98 23,4

Гиперэлипсойд 100 26,04 98 29,06

Гриванка 100 43,82 100 27,5

Швефеля 62 62,19 46 58,48

Розенброка 72 65,64 95 68,5

Эффективность работы алгоритма оценивалась по критериям надежности (п) и скорости (5):

-п=—, где к - количество запусков, при которых найдено решение с заданной точностью, Ы-общее число запусков;

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

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

1) Меньшее значение параметра Тщг лучше, поскольку за отведенное количество раундов больше индивидов 50 могут перейти в субпопуляцию Однако, дальнейшее уменьшение данного параметра нецелесообразно, т.к. приведет к вырождению алгоритма в классический генетический алгоритм с элитарной селекцией.

2) При среднем (1/5) значении параметра «Доля индивидов Бк» алгоритм ведет себя более предсказуемо и показывает стабильно хорошие результаты, как по надежности, так и по скорости. Это означает, что е субпопуляции Бк достаточно места для сохранения уже апробированных решений, а в 50 - для поиска новых комбинаций.

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

4) Для значения параметра оператора «Мутация» сложно дать рекомендации по выбору, поскольку распределение лучших найденных решений для тестовых функций между величинами мутаций примерно равны.

5) Стоит так же отметить, что алгоритм плохо справляется с оптимизацией функции, для которой характерна проблема «плато», что связано с отсутствием Бк индивидов в окрестности «провала» с глобальным оптимумом.

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

дифференцированного генетического алгоритма при Ти^е = 5 и Бк = 1/5.

Таблица 3 - Сравнительный анализ эффективности алгоритмов безусловной оптимизации

Наихудший ГА Средний ГА Наилучший ГА Коэволюция Диф ГА

п(%) Б п (%) 5 п(%) 8 П(%) в п(%) Э

Сомбреро 22 76,7 25 78,9 32 83,6 24 40,2 100 35,8

Шекеля 26 71,5 57 69,0 78 65,3 66 32,9 12 21,4

Растригина 79 74,6 96 60,9 100 50,7 100 25,8 98 23,4

Гриванка 84 71,2 88 65,5 93 67,1 89 30,9 100 27,5

Розенбрскз 16 68,0 55 69,0 81 70,9 87 49,6 95 68,5

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

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

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

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

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

1) удовлетворение наибольшему количеству критериев.

2) наибольшее значение параметра .

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

Дифференцированный генетический алгоритм решения задач условной оптимизации был реализован программно и апробирован на следующем множестве тестовых функций (таблица 4), для которых интервал изменёния значений переменных - [-10;10], а шаг дискретизации - Дг=0,001.

Таблица 4 - Множество тестовых функций

№ Функция Ограничения Экстремум Решение

1 Р(х,у) = Я-(х-3)2 + 4-(х-3)(.у-3) + 4-(у-3)2 Г-ЗйлгйЗ, 1-3<>><3, тт (х;*У*) = (3;3), Нх*;у') = 63

2 Р(х,у) = 5х+0.5у у<-2х + 5, у*х-1.5, у£2х + \, НО, у* 0 тах о

3 Р(х,у) = \0х-5у |.у+2х-20<0, тах (х*,у*)» (3.65 И8;-6.66667), »69.84817

4 Пх,у)^х2+у2 Гу<7 + 8т(2х), ^ 1 — б1П(2ЛГ), [О < х < 4 тах ) = (4;7.98935), /"(**,У)* 79.82984

5 Р(х,у) = -10х-5у х>0, >>£-15, уйх2/ 2, у 2 2х2-20 тга {х*,у*) ч (3.65148;6.66667Х Р(**.У)*> -69.84817

6 F(лг,>0 = Зх2 +5:с(у-8) + 3(>'-8)2 х + у = 0 тт

При проведении исследований были определены следующие начальные условия и параметры алгоритма: для метода динамических и адаптивных штрафов коэффициенты С = 0,5, а = /? = 2, коэффициенты для адаптивных штрафов: р1 = 1,4, /?2 = 1,2, к = 3. Использовалась генерация начальных популяций множеством допустимых решений. Общее количество индивидов в Бк и Б0 субпопуляциях составляло 100, количество поколений -100. Проводилось исследование эффективности, как отдельных штрафных функций, так и их сочетания с модификацией дифференцированного генетического алгоритма.

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

Таблица 5 - Результаты исследования эффективности

Функция Надёжность (и, %) Скорость (5)

1 100 40,47

2 100 49,62

3 40 69,54

4 100 58,74

5 78 65,34

6 45 60,79

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

1) наибольшую эффективность показывает сочетание метода динамического штрафа и модификации алгоритма. Сниженная эффективность адаптивных штрафов связана с наличием двух субпопуляций и частого изменения состава субпопуляции 50;

2) при среднем (1/5) значении параметра «Доля индивидов 5к» алгоритм ведет себя более предсказуемо и показывает стабильно хорошие результаты, как по надежности, так и по скорости.

3) значение параметра Тц^е, необходимо увеличивать при росте сложности задачи.

Сравним эффективность разработанного алгоритма с эффективностью генетического алгоритма при различных наетройках и коэволюционным алгоритмом (таблица 6).

Таблица 6 - Сравнительный анализ эффективности алгоритмов условной оптимизации

Функция Наихудший ГА Средний ГА Наилучший ГА Коэволюция Диф.ГА

п(%) Б п(%) в п (%) Э п(%) Б п(%)

1 1,6 69,8 24,9 64,1 73,6 70,8 99,0 57,8 100 56,06

2 19,0 56,0 73,5 59,6 100 62,6 100 27,0 100 62,17

3 0 - 6,6 73,2 29,2 73,4 99,0 48,0 40 69,54

4 1,4 57,2 55,0 61,5 100 68,0 98,2 39,4 100 58,74

5 0 - 8,0 70,5 32,0 71,0 99,6 50,2 78 65,34

6 2,8 16,5 17,2 50,8 37,2 75,4 34,0 59,0 42 70,69

По полученным результатам и их сравнительному анализу можно сделать следующие выводы:

1)при сравнении с классическим генетическим алгоритмом можно сделать вывод, что дифференцированный генетический алгоритм лучше усредненного по эффективности классического алгоритма, но может уступать лучшему при неоптимальных настройках;

2) при сравнении с коэволюционным алгоритмом можно сделать вывод, что данные алгоритмы сравнимы по эффективности.

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

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

В третьей главе приводиться описание применения дифференцир<)ванного генетического алгоритма, реализованного в рамках программных систем, предназначенных для автоматизированного решения задач оптимизации.

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

С помощью дифференцированного генетического алгоритма была решена актуальная практическая задача структурно-параметрического синтеза беспроводных локальных сетей стандарта IEEE 802.1 lg с установленными ограничениями на уровень сигнала вне помещения и на скорость передачи данных внутри помещения. Для ее решения была разработана модель беспроводной сети, позволяющая количественно оценить степень соответствия итоговой сети предъявляемым требованиям на основе следующего перечня входных характеристик: модель точки доступа (РЭС) и места её размещения, модели беспроводных сетевых карт, мощность сигнала активного сетевого оборудования, тип используемых антенн и их ориентация в пространстве. Перечень входных характеристик представляется вектором X, имеющим 8 измерений и суммарную длину не менее 33 бит: Xi - номер модели точки доступа; х2и х3- первая и вторая координата места размещения точки доступа; х4 - уровень мощности сигнал точки доступа; х5 - номер модели антенны точки доступа; х6 - угол поворота антенны точки доступа; х7 - номер модели сетевой карты; х8 - номер модели антенны сетевой карты При расчете границ зоны распространения применялся метод расчета дальности беспроводной связи, и учитывалось ослабление мощности радиосигнала при прохождении через конструкции различной природы. Итоговая целевая функция выражена следующей формулой:

где N - количество точек вне и внутри помещения, где мощность сигнала не должна превышать заданного порога; - мощность сигнала в точке,

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

¡=1

г=1

определяющий критичность уменьшения скорости передачи относительно заданной, задаётся пользователем (рекомендованное значение 0,4); V -требуемая скорость передачи • данных для сетевой карты, изменяется дискретно, имеет 9 значений от 0 Мбит/с до 54 Мбит/с, т.е. задаётся множество {1;2;...;8;9}; - предполагаемая скорость доступа в г-ой

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

параметрического синтеза беспроводных локальных сетей стандарта IEEE 802.11g является задачей условной оптимизации с алгоритмически заданной целевой функцией и ограничениями на множестве разношкальных переменных.

Разработанное модельно-алгоритмическое обеспечение было реализовано в программной системе «Расчет параметров сети Wi-Fi» (рисунок 1), которая осуществляет с помощью дифференцированного генетического алгоритма поиск оптимальных параметров модели, тем самым давая полный набор характеристик для последующего развертывания беспроводной локальной сети.

Рисунок 1 - Экранная форма программной системы «Расчет параметров сети Wi-Fi»

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

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

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

3) большее значение ошибки для кирпичных зданий определяется большей толщиной внешних стен и, следовательно, большей неоднородностью;

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

Оценка точности разработанной модели была проведена для различных помещений. Размер средней абсолютной ошибки составил от 4% до 8%.

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

AFER(X) = g=il№(*)-ri)/r1|. 100 min

т

где F, (X) - предсказанное значения для г'-го периода, полученное алгоритмически на основе НВР; Г/ - реальное значения для /-го периода; т -количество значений временного ряда. Вектор X имеет следующие измерения: Di, D2 - действительные числа, используемые при корректировке универсума U, на котором задается нечеткое множество; п - количество интервалов разбиения универсума U; ае[0,1] - характеризует степень принадлежности лингвистических терм нечеткому множеству. В данной задаче дифференцированный генетический алгоритм играет роль средства их автоматического поиска. Таким образом, в рассматриваемой постановке она сводится к решению задачи однокритериальной безусловной оптимизации с алгоритмически заданной целевой функцией на множестве дискретных и непрерывных переменных. Её решение было автоматизировано в рамках программной системы «Прогнозирование нечетким временным рядом», позволяющей получить достоверный прогноз на основе незначительного количества данных без построения статистической модели в автоматическом режиме.

Исследование эффективности прогнозирования проводилось на данных различной природы, обладающих как сезонной периодичностью, так и

трендом. В таблице 7 представлен пример результатов прогнозирования на 10 шагов вперед для ежемесячной миграции населения Красноярского края НВР, нейронной сетью и 3 статистическим моделями. Критериями оценки эффективности метода являлись следующие виды ошибок: Error - средняя относительная ошибка прогнозирования, МРЕ - средняя процентная ошибка прогнозирования, AFER - средняя относительная ошибка аппроксимации.

Таблица 7 - Ошибки прогнозирования миграции

Оценка прогноза / метод Иммиграция Эмиграция

НВР НС 1 2 3 НВР НС 1 2 3

Error, % 10,56 18,96 17,29 11,25 18,43 5,81 13,71 16,5 11,04 4,77

МРЕ, % 3,79 -1,48 -1,51 4,17 8,15 -2,29 -13,7 4,65 2,83 -0,58

AFER, % 15,75 6,68 8,53 11,57 14,19 9,9 9,58 6,19 9,39 14,91

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

В заключение диссертации приведены основные результаты и выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В ходе выполнения диссертационной работы получены следующие результаты:

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

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

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

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

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

Таким образом, в диссертационной работе разработан, программно реализован, исследован и проверен на тестовых и прикладных задачах новый

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в ведущих рецензируемых научных журналах и изданиях

1. Жуков В.Г., Золотарёв В.В., Заболоцкая Н.С., Паротькин Н.Ю., Ширкова Е.А. Применение факторного анализа и эволюционного алгоритма оптимизации для решения задачи управления информационными рисками систем электронного документооборота // Научно-технический журнал «Системы управления и информационные технологии». - № 3 (37) . - 2009. - С. 51 - 55.

2. Жуков В.Г., Паротькин Н.Ю. Дифференцированный адаптивный генетический алгоритм // Вестник Новосибирского государственного университета. Серия: Информационные технологии. - Т.9(1). - 2011. - С. 5 -11.

3. Жуков В.Г., Паротькин Н.Ю. Автоматизированная система проектирования беспроводной сети IEEE 802.11 // Программные продукты и системы. - № 3. - 2012. - С. 202 - 207.

4. Жуков В.Г., Паротькин Н.Ю., Хеирхабаров Т.С. Дифференцированный адаптивный алгоритм генетического программирования // В мире научных открытий. - 11.5 (35). - 2012. - С. 276 -295.

Публикации в сборниках трудов конференций

5. Паротькин Н.Ю. Разработка модифицированного генетического алгоритма для решения сложных задач оптимизации в сфере ИБ // Актуальные проблемы авиации и космонавтики; Сиб. гос. аэрокосмич. ун-т. -Красноярск: 2009. - С. 313 - 314.

6. Жуков В.Г., Паротькин Н.Ю. Использование модифицированного генетического алгоритма для оптимизации структуры сети Wi-Fi // Актуальные проблемы безопасности информационных технологий: материалы III Международной заочной научно-практической конференции; Сиб. гос. аэрокосмич. ун-т. Красноярск, 2009. - С. 63 - 67.

7. Паротькин Н.Ю. Разработка модифицированного генетического алгоритма для решения сложных задач оптимизации // Решетневские чтения; Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2009. - С. 447 - 448.

8. Жуков В.Т., Паротькин Н.Ю. О применении генетического алгоритма для решения задачи оптимизации беспроводной локальной сети // Теория и практика системного анализа: Труды I Всероссийской научной конференции. - Т. II. — Рыбинск: РГАТА имени П. А. Соловьева, 2010. -С. 136- 143.

9. Паротькин Н.Ю. Wireless network setup by genetic algorithm // Молодежь. Общество. Современная наука, техника и инновации; Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2010. - С. 85 - 86.

10. Паротькин Н.Ю. Использование видеопроцессора при решении тестовых задач оптимизации // Решетневские чтения; Сиб. гос. аэрокосмич. ун-т. - Красноярск: 2010. - Ч. 2. - С. 414.

11. Паротькин Н.Ю. Интеллектуальная система выбора эффективных параметров сети WiFi // Молодежь и .высокие технологии: материалы всероссийской студенческой олимпиады (Всероссийский конкурс компьютерных программ). - Вологда: ВоГТУ, 2011. - С. 19 - 21.

12. Паротькин Н.Ю. Об автоматизации прогнозирования временных рядов дифференцированным генетическим алгоритмом // Решетневские чтения; Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2011. - Ч. 2. - С. 488 - 489.

13. Жуков В.Г., Паротькин Н.Ю. О применении дифференцированного генетического алгоритма при обнаружении инцидентов информационной безопасности // Решетневские чтения; Сиб. гос. аэрокосмич. ун-т. -Красноярск, 2011. - Ч. 2. - С. 657 - 658.

14. Жуков В.Г., Паротькин Н.Ю. Автоматизированное проектирование и контроль границ зоны подключения беспроводной локальной сети // Сборник работ победителей отборочного тура Всероссийского конкурса научно-исследовательских работ студентов, аспирантов и молодых ученых по нескольким междисциплинарным направлениям. — Новочеркасск: Лик, 2011.-С. 18-20.

15. Жуков В.Г., Паротькин Н.Ю., Федорова Е.Ю. О решении задачи прогнозирования миграции в красноярском крае // Труды II всероссийской научной конференции молодых ученых с международным участием Теория и практика системного анализа ТПСА'2012. - Т. I. - Рыбинск: РГАТУ им. П.А. Соловьева, 2012. - С. 163 - 172.

16. Паротькин Н.Ю. О применении дифференцированного генетического алгоритма для решения задач условной оптимизации // Решетневские чтения; Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2012. - Ч. 2. -С. 500-501.

Зарегистрированные программные системы

17. Паротькин, Н.Ю. Расчет параметров сети Wi-Fi: Свидетельство о государственной регистрации программы для ЭВМ / В.Г. Жуков, Н.Ю. Паротькин. - М.: Реестр программ для ЭВМ, 2010. - № гос. per. 2010610148.

18. Паротькин, Н.Ю. Прогнозирование временных рядов: ' Свидетельство о государственной регистрации программы для ЭВМ / В.Г. Жуков, Н.Ю. Паротькин. - М.: Реестр программ для ЭВМ, 2011. - № гос. per. 2011614846.

Паротькин Николай Юрьевич

Дифференцированный генетический алгоритм решения сложных задач

оптимизации '

Автореферат

Подписано к печати 06.11.2013 Формат 60х&М 6

Уч. изд. л. 1.0 Тираж 100 экз. Заказ № -г

Отпечатано: «Оперативная полиграфия». 660049, г. Красноярск, ул. К. Маркса 62, оф. 120, тел. (391) 226-31-31.

Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва

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

04201450804

Паротькин Николай Юрьевич

ДИФФЕРЕНЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ

СЛОЖНЫХ ЗАДАЧ ОПТИМИЗАЦИИ

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

Диссертации на соискание ученой степени кандидата технических наук

Научный руководитель: к.т.н., доцент Жуков В.Г.

Красноярск - 2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ....................................................................................................4

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК..........................................................95

ПРИЛОЖЕНИЕ А.......................................................................................111

ПРИЛОЖЕНИЕ Б.......................................................................................121

ПРИЛОЖЕНИЕ В.......................................................................................124

ПРИЛОЖЕНИЕ Г.......................................................................................133

ВВЕДЕНИЕ

Актуальность. Для решения сложных задач оптимизации на практике часто применяют эволюционные алгоритмы. Однако, в отличие от эволюции, происходящей в природе, эволюционный алгоритм, в процессе решения задачи оптимизации, только моделирует те процессы в популяции, которые являются существенными для развития. Существует большое количество моделей эволюции, которые могут применяться в качестве базиса для проектирования эволюционных алгоритмов оптимизации, например, модели Ч. Дарвина, Ж. Ламарка, Г. де Фриза, Гулда-Элдриджа и другие. В любом случае эволюционный алгоритм работает с совокупностью индивидов - популяцией, каждый из которых представляет возможное решение проблемы. В процессе работы алгоритм, в рамках выделенного ресурса, исследует пространство поиска путем информационного обмена с внешней средой, то есть популяция всегда эволюционирует в соответствующей среде. В целом, эволюция подразумевает наличие двух главных аспектов: сохранение и изменение. Для эффективной реализации первого аспекта популяция должна быть устойчивой, стабильной, неизменяемой, то есть информационно дистанцироваться от среды. С другой стороны (второй аспект), без тесного информационного контакта со средой невозможен поиск решения - популяция должна постоянно эволюционировать. Таким образом, требования эволюции с точки зрения информационного обмена популяции со средой являются противоречивыми.

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

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

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

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

Объектом исследования являются эволюционные алгоритмы оптимизации. Предметом исследования являются синтетические модели эволюции, применяемые на концептуальном уровне эволюционными алгоритмами оптимизации.

Для достижения поставленной цели необходимо решить следующие задачи:

1) провести анализ моделей эволюции и основанных на них эволюционных алгоритмов оптимизации;

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

3) алгоритмизировать и программно реализовать разработанную модель эволюции;

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

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

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

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

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

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

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

4) разработан и программно реализован новый метод структурно-параметрического синтеза беспроводных локальных сетей стандарта IEEE 802.1 lg дифференцированным генетическим алгоритмом, отличающийся от известных автоматическим способом подбора компонентов сети и настройкой их параметров, и позволяющий количественно оценить степень соответствия модели беспроводной сети предъявляемым требованиям и ограничениям.

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

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

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

Реализация результатов работы. Работа поддержана Фондом содействия развитию малых форм предприятий в научно-технической сфере по программе «У.М.Н.И.К.» («Участник молодежного научно-инновационного конкурса») в рамках НИОКР «Автоматизация проектирования беспроводной сети интеллектуальным программным обеспечением» и «Разработка экспертной системы проектирования беспроводной сети на базе клиент-серверной технологии» на 2011-2013 гг.

Результаты диссертационного исследования использованы в ходе выполнения:

1)ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы», мероприятие 1.4. «Проведение проблемно-ориентированных поисковых исследований и создание научно-технического задела по перспективным технологиям в области информационно-телекоммуникационных систем». Тема работы - «Разработка технологии синтеза настроек параметров безопасности автоматизированных систем в защищенном исполнении» (2011-2012 гг.), ГК№ 07.514.11.4047 от 06.10.2011.

2) РФФИ «Разработка коллективов биоинспирированных алгоритмов обнаружения инцидентов информационной безопасности в автоматизированных системах» (2012-2013 гг.), №12-01-31123 от 18.10.2012, №12-01-31123 от 28.05.2013 г.

3) Грант Президента, программа поддержки молодых кандидатов наук, 2013-2014 гг., МК-473.2013.9 «Разработка и исследование биоинспирированных алгоритмов интеллектуального обеспечения безопасности информации в автоматизированных системах».

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

так же в рамках программы повышения квалификации «Построение беспроводных локальных вычислительных сетей на основе оборудования Б-Ьшк».

Материалы диссертационного исследования и разработанная программная система были использованы при проектировании и развертывании беспроводной сети АцМАХ ООО «Логический уровень» в п. Солонцы, Красноярского края. Основные защищаемые положения:

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

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

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

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

Апробация работы. Основные положения и отдельные результаты диссертационной работы были представлены на Всероссийской научно-практической конференции студентов, аспирантов и молодых специалистов «Актуальные проблемы авиации и космонавтики» (Красноярск, СибГАУ, 2009); IX Всероссийской научной студенческой конференции с международным участием «Молодежь. Общество. Современная наука, техника и инновации» (Красноярск, СибГАУ, 2010); Международных научно-практических

конференциях «Решетневские чтения» (Красноярск, СибГАУ, 2009-2012); I и II Всероссийских научных конференциях «Теория и практика системного анализа» (Рыбинск, Институт системного анализа РАН и РГАТА, 2010, 2012).

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

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

Структура работы. Диссертация содержит 109 страниц основного текста и состоит из введения, трёх глав, заключения, списка литературы из 101 источника и 4 приложений, содержащих 24 страницы; основной текст диссертации включает 10 таблиц, 32 рисунка.

1 ЭВОЛЮЦИОННЫЕ МОДЕЛИ И АЛГОРИТМЫ ОПТИМИЗАЦИИ

1.1 Классические модели эволюции

В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие как пища или вода. Те особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов воспроизвести потомков. Слабо приспособленные либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространяться в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению «супер приспособленного» потомка, чья приспособленность больше, чем приспособленность любого из его родителя, тем самым реализуется отбор индивидов по принципу «выживает сильнейший». Таким образом, вид развивается, все лучше приспосабливаясь к среде обитания, т.е. наступает эволюционная смена форм (рисунок 1). Впервые вся совокупность данных заключений появилась в работах Ч. Дарвина [94].

Рисунок 1 - Упрощенная схема модели эволюции Ч. Дарвина

По приведенной схеме эволюции возможно составить алгоритм решения оптимизационной задачи, интерпретировав каждый блок, как некоторую операцию над множеством решений [15, с. 102].

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

2. Наследственность. После реализации каждой итерации алгоритма появляется новое поколение (потомство) альтернативных решений.

3. Изменчивость. В новой популяции (поколении) остаются отличающиеся друг от друга альтернативные решения.

4. Отбор. По заданным правилам отбираются элитные решения с лучшим значением целевой функции. Это соответствует принципу Ч. Дарвина «выживают сильнейшие».

5. Эволюционная смена форм. Лучшие решения, выживают в результате реализации схемы эволюции Дарвина и они постепенно, поколение за поколением становятся