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

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

ЖУКОВА МАРИНА НИКОЛАЕВНА

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

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

АВТОРЕФЕРАТ

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

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

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», г. Красноярск

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

доктор технических наук, профессор Семёнкин Евгений Станиславович

Официальные оппоненты:

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

кандидат технических наук, доцент Царев Роман Юрьевич

Ведущая организация:

Томский государственный университет

Защита состоится 16 декабря 2004 г. в 14.00 на заседании диссертационного совета Д212.249.02 в Сибирском государственном аэрокосмическом университете им. ак. М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газ. "Красноярский рабочий", 31.

С диссертацией можно ознакомиться в научной библиотеке СибГАУ.

Автореферат разослан 15 ноября 2004 г.

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

И.В. Ковалев

Общая характеристика работы

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

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

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

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

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

- исследовать эффективность стандартных эволюционных алгоритмов решения сложных задач оптимизации на предст азйвсхМйЦИвИАЖВВЮе] тестовых функций,

БИБЛИОТЕКА 1 СПетер 09 Ир'

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

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

- провести исследование эффективности разработанной процедуры на представительном множестве тестовых функций и сравнить ее эффективность со стандартными ЭА,

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

- провести апробацию разработанного подхода на реальной практической задаче.

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

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

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

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

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

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

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

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

Разработанные в диссертации алгоритмы и программная система используются в учебном процессе при проведении занятий по специальным курсам "Системы искусственного интеллекта" и "Адаптивные и эволюционные методы принятия решении в Сибирском государственном аэрокосмическом универси-

/

тете, а также по общему курсу "Методы оптимизации" и специальным курсам "Системный анализ и управление", и "Эволюционные алгоритмы оптимизации" в Красноярском государственном университете.

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

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

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

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

Публикации. По теме диссертации опубликовано тринадцать печатных работ, список которых приведен в конце автореферата.

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Всероссийских конференциях "Решет -невские чтения" (2003-2004 гг.), региональной конференции "Красноярский край - освоение, развитие, перспективы" (2003), Красноярской краевой выставке технических идей и разработок (2003), Красноярской конференции молодых ученых "Информатика и информационные технологии" (2003), международной научно-практической конференции "Системный анализ в проектировании и управлении" (Санкт-Петербург, 2004), межрегиональной научно-практической конференции "Интеллект - 2004", а также на научно-техническом семинаре Института автоматизации управления Высшей специальной школы г. Ульм (FHU, Германия, 2003), научных семинарах экспериментальной лаборатории интеллектуальных технологий и адаптации и кафедры САИО в СибТАУ (20032004 гг.) и научном семинаре кафедры механики и процессов управления Красноярского госуниверситета (2003,2004).

Структура и объем работы. Диссертация содержит 124 страницы основного текста, состоит из введения, трех глав, заключения, списка литературы из 75 наименований и приложения.

Содержание работы

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

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

Практически всегда оптимизируемая функция обладает каким-либо свойством (свойствами): многоэкстремальность, алгоритмическое задание, сложная

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

Генетические и эволюционные алгоритмы (ГА и ЭА) - один из подходов стохастической оптимизации. Они основаны на моделировании генетических процессов биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора.

Стандартная схема генетического алгоритма представлена на рис. 1.

"гас. 1. Схема генетического алгоритма

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

Таб. 1. Описание схем индивидуальных алгоритмов

Алгоритм Тип селекции Схема формирования нового поколения Характер поиска

1 аутбридинг отбор с вытеснением

2 аутбридинг случайным образом глобальный

3 случайным образом отбор с вытеснением

4 турнирная отбор с вытеснением

5 инбридинг отбор с вытеснением

6 турнирная только дети

7 инбридинг только дети локальный

8 инбридинг элитизм

9 турнирная злитизм

10 случайным образом элитизм

11 случайным образом случайным образом

12 инбридинг случайным образом неопределенный

13 аутбридинг случайным образом

14 турнирная случайным образом

15 случайным образом только дети

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

%

кая размерность, сложная конфигурация пространства поиска и т.д. Примеры использованных тестовых функций: 1. функция Rana (Ф5)

F(x,у)-sin+ cosy* + ^ + lj)+ О +1)• cos{j\y + l-x\) sin+

В связи с тем, что ГА является стохастической процедурой, оценка его эффективности осуществляется усреднением по многократным запускам (все исследования проводились при усреднении по 20-ти запускам алгоритмов). Для сравнения алгоритмов использовались следующие показатели: надежность -процент успешных запусков алгоритма (глобальный оптимум найден) от общего числа запусков алгоритма; среднее число итераций до нахождения решения (скорость) - номер итерации, на которой найден глобальный оптимум, усредненный по числу успешных запусков алгоритма. У наилучшего ГА должна быть наибольшая надежность, при равных показателях надежности - наибольшая скорость (наименьшее количество вычислений до обнаружения экстремума).

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

Таким образом, даже после многократных решений задачи (что само по себе плохо для практики) остается неопределенность выбора параметров ГА. Это подтверждает то, что для каждой задачи существует свой наилучший алгоритм. А выбор конкретного алгоритма и настройка его параметров являются очень сложными задачами.

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

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

1. Выбор индивидуальных алгоритмов.

2. Инициализация параметров коэволюционного алгоритма.

3. Работа индивидуальных алгоритмов в течение заданного интервала адаптации.

4. Оценка алгоритмов.

5. Проверка критерия остановки: если данный критерий срабатывает, то выводим лучшее найденное решение и алгоритм прекращает работу, иначе шаг 6.

6. Перераспределение ресурса (на основе оценки, полученной на шаге 4).

7. Переход на шаг 3.

Так как коэволюционный алгоритм основывается на конкурирующих стратегиях алгоритмов, то для субпопуляций необходимо ввести функцию пригодности. С помощью этой функции определяется лучшая популяция и ей дается больше возможностей для воспроизводства. Пусть Г — интервал адаптации, ¿г-(Аг)=1, если 1-я популяция в момент к содержит наилучшего (по всем популяциям) индивида, ¿=0 означает текущую ситуацию, к=1 - предыдущую и т. д. Тогда качество /-Й популяции можно вычислить по формуле:

^'Т -к

«.-Е-

к +1

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

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

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

Рис. 2. Поведение лучшего индивида (коэволюционный алгоритм показан сплошной жирной

линией)

Происходящий в ходе поиска процесс перераспределения ресурсов между алгоритмами можно увидеть на рис. 3.

поколения коэволюция

Рис.3. Перераспределение ресурса в ходе поиска глобального оптимума функции Сомбреро

Здесь: алгоритмы 1 и 2 - с глобальным характером поиска, алгоритмы 7 и 8 - с локальным характером поиска и алгоритм 13 - с неопределенным характером поиска. На рисунке видно, как на первых шагах оптимизации оба алгоритма с локальным характером проигрывают, но затем один из них (алгоритм 7) попадает в хорошую область, найденную с помощью алгоритмов с глобальными свойствами, которые лидировали на первых шагах. Затем алгоритмом с локальными свойствами осуществляется быстрый спуск к более точному значению глобального оптимума.

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

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

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

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

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

Таб 3 Результаты исследования зависимости эффективности коэволюционного алгоритма от величины интервала адаптации

Величина интервала адаптации Функция Шекеля (п=2) Функция Сомбреро (п=2) Функция Гриванка (п=10>

Надежность (%) Скорость Надежность (%) Скорость Надежность (%) Скорость

2 10 10 - . - -

3 60 13 60 15 45 13

4 85 13 70 14 50 14

5 т 12 80 13 ' № 12

6 т 12 85 14 65 12

7 т 12 80 12 . 13

8 60 13 60 12 60 13

9 50 12 60 10 45 12

10 50 12 60 11 10 10

15 20 10 30 10 5 10

20 30 10 30 10 5 10

в) Исследование зависимости эффективности коэволюционного от количества индивидуальных алгоритмов. В таблице 4 приведен пример полученных

результатов для трех тестовых функций

Таб 4 Результаты исследования зависимости надежности _ коэволюционного алгоритма от количества индивидуальных алгоритмов

Кол-во Функция Шекеля (п=2) Функция Сомбреро (п=2) Функция Гриванка (п=10)

надежность скорость надежность скорость надежность скорость

2 10% 3 30% 3 - -

3 15%..... 7 35% 4 10% 3

4 25% 5 40% 5 15% 4

5 10% 3 30% 3 1Й% г

6 10% 4 20% 2 5% 2

7 10% 8 20% 4 - -

8 5% 3 10% 3 - -

г) Исследование зависимости эффективности коэволюционного алгоритма от характеров поиска индивидуальных алгоритмов.

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

I Номер комбинации коэволю Функция Шекеля (а-2) ционного алгоритма от хара Функция Сомбреро (п=2) ктера включенных алгоритмо Функция Гриванка (п=10)

надежность скорость надежность скорость надежность скорость

1 £5% ' " 4 75% 6 55% 3

2 80% 5 65% 5 50% 6

1 з 30% 5 35% 5 30% 6

Здесь комбинация 1 - в состав коэволюционного алгоритма включались два

лучших алгоритма с глобальным характером поиска, два лучших алгоритма с локальным характером поиска и один лучший алгоритм с неопределенными свойствами;

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

комбинация 3 - выбор алгоритмов производился случайно (независимо от их свойств)

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

и

1. Размер "штрафа" - 15% от размера популяции индивидуального алгоритма, величина "социальной карточки" — 15%.

2. В состав коэволюционного алгоритма включать комбинацию из 3-5 алгоритмов, обладающих различными характерами поиска.

3. Интервал адаптации должен составлять 5-6 поколений коэволюции.

Выработанные рекомендации по настройке параметров коэволюционного

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

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

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

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

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

Таб. 6. Классификация алгоритмов, оснащенных механизмами _учета нестационарности целевой функции

Алгоритм Тип селекции Схема формирования нового поколения Характер поиска Механизм учета нестационарности

1 аутбридинг отбор с вытеснением глобальный явная память

2 неявная память

3 гипермутационная схема

4 турнирная элитизм локальный явная память

5 неявная память

6 гипермутационная схема

7 панмиксия случайным образом неопределенный явная память

8 неявная память

9 гнсермутационная схема

Тестирование алгоритмов проводилось на стандартном множестве тестовых функций, используемых в мировой практике для тестирования алгоритмов нестационарной оптимизации. Среди них:

1. Наиболее часто используемая тестовая задача - семейство динамических функций Осмера. Функция задается в следующем виде: ^(х,/) = 1 — е 200*(м<'» ^ где ф = 0.04([1/20]), щмхе[1.000; 2.000}

2. Функция Трояновского-Михалевича:

//

Данная функция полимодальная с настраиваемым числом локальных минимумов. Основная идея при генерации целевой функции такова: задан гиперкуб в пространстве по"-4™ "й-"™"" ™"°"-;лен как разрешенная область поискового пространства: ^ ~ ГТ РМ), где п - размерность пространства. По ка-

1=1

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

/»(*) = ^^О/ _•*•<)(-*•/ ~<?(), где д, и г, - соответственно нижняя и верхняя

границы текущего гиперкубика по 1-й компоненте поискового пространства, <я)Т - коэффициент высоты экстремума в центре текущего гиперкубика. Функция Трояновски-Михалевича рассмотрена при различной размерности поискового пространства: 2, 6 и 18.

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

Результаты исследования эффективности индивидуальных алгоритмов показали, что, как и в случае исследования индивидуальных алгоритмов для стационарной оптимизации, нельзя однозначно сказать о превосходстве определенного алгоритма. Но по большинству лучших результатов можно выявить в каждой группе алгоритмов наиболее эффективный алгоритм (алгоритмы 1, 5 и 7) и проранжировать остальные алгоритмы в порядке убывания показателя надежности. При этом было установлено, что просто перезапуск стандартного генетического алгоритма сильно уступает алгоритмам для нестационарной оптимизации не только в надежности нахождения решения (лучший результат перезапуска - 40%, результаты специализированных алгоритмов - 75% - 100%), но и практически в два раза по времени выхода на оптимум.

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

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

и

ла ж! зи ьо ьяй /-и аи зо та

поколения

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

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

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

а) От размеров штрафа и социальной карточки.

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

Соц. карта \штраф 2% 5% 10% 15% 20% 25% 30% 35% 40%

3% 15 25 35 35 25 25 15 20 10

5% 25 40 35 20 20 10 20 30 10

10% 25 35 65 45 55 25 20 15 5

15% 25 20 55 80 70 30 25 10 5

20% 25 35 60 60 85 30 20 10 5

25% 25 20 30 35 45 35 20 10 0

30% 35 20 15 15 20 20 35 10 0

35% 40 25 15 15 20 30 15 25 5

40% 25 35 25 25 25 10 15 20 5

б) От величины интервала адаптации.

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

Размер интер вала Функция Осмера п=1 Функция Трояновского-Михалевича

п=2 п=6 п=18

Надеж ность скорость Надеж ность скорость Надеж ность скорость Надеж ность скорость

2 10 10 20 16 5 17 5 20

3 60 13 55 17 10 15 5 16

4 85 13 65 11 45 13 45 14

5 85 12 65 12 45 13 55 13

6 80 12 75 13 60 12 55 13

7 80 12 65 И 55 12 40 12

8 60 13 55 14 40 14 45 12

9 50 12 50 И 30 11 25 11

в) От количества включенных алгоритмов.

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

Кол-во Функция Осмера п=1 Функция Трояновского-Михалевича

п=2 п=6 11=18

Надежность скорость Надежность скорость Надежность скорость Надежность скорость

2 50% 13 30% 13 30% 18 5% 20

3 65% 12 55% 14 40% 16 20% 20

4 т И т% 11 ' 80% 14 55% 16

5 70% 13 60% 13 «5% .12 45% ¿5 „

6 40% 14 20% 14 35% 17 40% 20

7 40% 18 20% 16 20% 17 5% 20

г) От характера включенных алгоритмов.

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

Номер Функция Осмера Функция Трояновского-Михалевича

комби- I =1 г =2 п=6 ц =18

нации Надежность скорость Надежность скорость Надежность скорость Надежность скорость

1 95% 8 $5% 6 90% 11 90% 13

2 80% 8 75% 9 50% 15 30% 16

3 40% 12 40% 13 30% 13 30% 18

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

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

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

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

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

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

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

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

if

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

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

Отчгг

(просмотр, ох 147» Ш спрямям р#1ТЖ1ЯТ*«)

Т

Сасмма

шпгамаг» кабаодсюс

м орафссймтскк* --?-

к Блохрябош кошявциг

Рис. 5. Схема программной системы

Программная система Coevolution v.2.0. прошла экспертизу и зарегистрирована в отраслевом фонде алгоритмов и программ (номер гос. регистрации -50200400873 от 03.08.2004).

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

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

Система Coevolution v2.0 может применяться как отдельно, так и в составе более крупных диалоговых систем поддержки принятия решений.

Апробация разработанного подхода проведена на задаче моделирования и оптимизации параметров канала с многолучевым распространением для цифрового радио, которая решалась в рамках проекта "Modeling and optimization of DRM signals" совместно с институтом автоматизации Ульмского университета прикладных исследований (Fachhochschule Ulm, Германия, 2003).

В настоящее время, в связи с актуальностью проблемы повышения эффективности использования радиочастотного спектра в радиосвязи, активно разрабатывается новая концепция цифрового радиовещания - DRM. Идея метода состоит в том, что необходим только один передатчик, с помощью которого приемники по всему миру будут получать сигналы высокого качества. При передаче сигнал (до 30-ти MHz) отражается от верхних слоев ионосферы и таким образом распространяется. При этом в передатчике существует 6 типов каналов,

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

Рис. 6. Общая схема задачи

где: S(t) - входной сигнал, R(t) - выходной сигнал из "истинной" модели, R(t) - выходной сигнал из упрощенной модели.

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

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

Рис 7. Функция ошибки передачи сигнала для 6-го канала (по осям X и У изменяются параметры модели, по оси Z показана величина функции ошибки)

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

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

Обыкновенный генетический алгоритм справился с поставленной задачей только в комбинации с методом локального поиска (старт локального поиска происходил после резкого улучшения в генетическом алгоритме — см. рис. 8). Результаты поиска параметров показаны в таблице 11.

Таб. 11. Результаты решения задачи для каналов 1,2,4 и 5

Рис. 8. Поведение ГА в ходе решения задачи

Номер канала Ошибка (%

сиг-нал/шу м 0% сиг-нал/шу м 70% сиг- нал/шу м 50% снг- нал/шу м 40% сигнал/ту и 30%

1 0.29676 0.3601 0.43360 0.44379 0.45575

2 0.34766 0.39444 0.41087 2.29124 2.35966

4 0.35834 0.38486 0.3856 3.03792 3.09568

5 0.44127 0.46808 0.47966 2 89652 2.98614

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

Таб. 12. Результаты решения задачи для каналов 1,2,4 и 5

Номер Ошибка (%)

канала сигнал/шум сигнал/шум сигнал/шум сигнал/шум сигнал/шум

0% 70% 50% 40% 30%

1 0.2967606 0.3401 0.3606 0.443798 0.455751

2 0.3476643 0.354448 0.40583 2.12454 2.23565

4 0.35834 0.34486 0.36574 3.01394 3.01538

5 0.441275 0.438088 0.489487 2.65268 2.89612

Таким образом, коэволюционный алгоритм для стационарных задач оптимизации позволил достигнуть результат (для каналов 1,2,4 и 5 при шуме в 60% и 70%) не хуже, чем результат найденный обыкновенным ГА, а при меньшей амплитуде шума еще и лучше.

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

Таб. 13. Результаты решения задачи для каналов 1,2,4 и 5

Номер канала Ошибка (%)

сигнал/шум 0% сигнал/шум 70% сигнал/шум 50% сигнал/шум 40% сигнал/шум 30%

1 0.1976 0.2491 0.2614 0.449 0.455

2 0.294743 0.33958 0.39517 2.125 2.265

4 0.331234 0.33986 0.35874 3 094 3.018

5 0.401215 0.41798 0.44719 2 668 2.812

Для других двух каналов (4, 6) необходимо построение более сложной модели, так как имеющихся параметров данной модели не хватает для адекватного описания происходящего в этих каналах процесса передачи сигнала.

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

а

Основные результаты и выводы

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

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

- данная процедура реализована в виде программного продукта, соответствующего современным требованиям,

- проведено исследование эффективности разработанной процедуры на представительном множестве тестовых функций и осуществлен сравнительный анализ ее эффективности со стандартными ЭА,

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

- проведена апробация разработанного подхода на реальной практической задаче.

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

Публикации по теме диссертации:

1. Емельянова М.Н. Decision of some economic optimization problems with help of evolutionary algorithm with coevolution strategy / M.H, Емельянова // Сборник трудов региональной конференции "Красноярский край - освоение, развитие, перспективы".- Красноярск: КрасГАУ, 2003- С. 36-38.

2. Емельянова М.Н. Применение эволюционного алгоритма с коэволюцион-ной стратегией в экономико-математическом моделировании / М.Н. Емельянова // Сборник трудов Всероссийской конференции "11е Туполевские чтения" / Казань: КГАУ, 2003. - С. 12-14.

3. Емельянова М.Н. Об эволюционных алгоритмах решения сложных задач оптимизации / Гуменникова А.В., Емельянова М.Н., Семенкин Е.С., Сопов Е.А // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева: Сб. научн. трудов.- Красноярск: СибГАУ, 2003.-С. 14-23.

4. Емельянова М.Н. Эволюционные алгоритмы для многокритериальной и многоэкстремальной оптимизации / А.В. Гуменникова, М.Н. Емельянова, В.А. Клешков // Вестник НИИ СУВПТ (Вып. 13): Сб. научн. трудов.- Красноярск: НИИ СУВПТ, 2003 — С. 237-248.

5. Емельянова М.Н. Об оптимизации многоэкстремальных задач с помощью коэволюционного алгоритма / Емельянова М.Н. // Сборник трудов межвузовской конференции "Информатика и информационные технологии". - Красноярск: КГТУ, 2003. - С. 69-70.

6. Емельянова М.Н. Коэволюционный алгоритм решения сложных задач оптимизации / Емельянова М.Н. // Сборник трудов 42-й научно-практической конференции студентов, аспирантов и молодых ученых СибТАУ. - Красноярск: СибТАУ,2004.

7. Емельянова М.Н. Коэволюционные алгоритмы и их применение в задаче оптимизации цифрового радиосигнала / Емельянова М.Н. // Вестник Университетского комплекса (Вып. 1): Сб. научн. трудов. - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. - С. 189-198.

8. Емельянова М.Н. Исследование коэволюционных алгоритмов и их применение в задаче оптимизации цифрового радиосигнала / Емельянова М.Н. // Сборник трудов межрегиональной научно-практической конференции «Интеллект - 2004». - Красноярск: СИБУП, 2004. - С. 21-23.

9. Емельянова М.Н. Коэволюционный алгоритм решения сложных задач оптимизации / Емельянова М.Н. // Сборник трудов VIII Международной научно-практической конференции "Системный анализ в проектировании и управлении". - Санкт-Петербург: СПГПУ, 2004. - С. 48-51.

10. Емельянова М.Н. Исследование эффективности коэволюционного алгоритма / Емельянова М.Н., Семенкин Е.С. // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева: Сб. научн. трудов. - Красноярск: СибГАУ, 2004. - С. 28-34.

11. Емельянова М.Н. Программная система "Coevolution vl.O" (система решения сложных задач оптимизации с помощью коэволюционного алгоритма) / Емельянова М.Н., Семенкин Е.С. // М.: ВНТИЦ (№ гос. per. 502004008732004). -12 с.

12. Жукова М.Н. О влиянии величины интервала адаптации на эффективность работы коэволюционного алгоритма / Жукова М.Н. // Сборник трудов VH[ Всероссийской научной конференции с международным участием "Решет -невские чтения". - Красноярск: СибГАУ, 2004. - С. 31-33.

13. Жукова М.Н. Коэволюционный алгоритм решения нестационарных задач оптимизации / Жукова М.Н. // Сборник трудов III Всероссийской научно-практической конференции "Информационные технологии и математическое моделирование (ИТММ)". - Анжеро-Судженск: филиал КГУ, 2004. - С. 21-22.

Жукова Марина Николаевна Коэволюционный алгоритм решения сложных задач оптимизации

Автореферат

Подписано к печати //.2004 Формат 60x84/16

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

Отпечатано в СибГАУ 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

Введение.

Глава I. Разработка и исследование эффективности коэволюционного алгоритма решения стационарных задач оптимизации

§ 1.1. Исследование эффективности стандартного генетического алгоритма.

§ 1.1.1. Множество тестовых функций для исследования эффективности ГА.•.

§ 1.1.2. Исследование эффективности стандартного ГА на множестве тестовых функций.

§ 1.2. Обоснование коэволюционного алгоритма.

§ 1.3. Исследование эффективности коэволюционного алгоритма.

§ 1.4. Исследование зависимости свойств коэволюционного алгоритма от выбора его параметров.

Выводы.

Глава II. Разработка и исследование эффективности коэволюционного алгоритма решения нестационарных задач оптимизации

§ 2.1. Адаптация генетического алгоритма в условиях нестационарности целевой функции.

§ 2.2. Обоснование коэволюционного алгоритма.

§ 2.3. Исследование эффективности коэволюционного алгоритма.

§ 2.4. Исследование зависимости свойств коэволюционного алгоритма от выбора его параметров.

Выводы.

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

§3.1. Описание программной системы.

§ 3.2. Описание работы с программной системой.

§ 3.3. Описание системы цифрового радиовещания в формате DRM.

§ 3.4. Постановка задачи оптимизации параметров канала с многолучевым распространением для цифрового радио.

§ 3.5. Решение задачи оптимизации параметров канала цифрового радио стандартным генетическим алгоритмом.

§ 3.6. Решение задачи оптимизации параметров канала цифрового радио коэволюционным алгоритмом.

Выводы.

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

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

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

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

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

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

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

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

- провести исследование эффективности разработанной процедуры на представительном множестве тестовых функций и сравнить ее эффективность со стандартными ЭА,

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

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

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

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

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

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

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

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

Разработанная на основе коэволюционного алгоритма программная система решения сложных задач оптимизации прошла экспертизу и Зарегистрирована в Отраслевом фонде алгоритмов и программ (№ гос. регистрации 50200400873 от 03.08.2004), что делает ее доступной широкому кругу специалистов по моделированию и оптимизации сложных систем.

Разработанные в диссертации алгоритмы и программная система используются в учебном процессе при проведении занятий по специальным курсам "Системы искусственного интеллекта" и "Адаптивные и эволюционные методы принятия решений" в Сибирском государственном аэрокосмическом университете, а также по общему курсу "Методы оптимизации" и специальным курсам "Системный анализ и управление", и "Эволюционные алгоритмы оптимизации" в Красноярском государственном университете.

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

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

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

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

Публикации. По теме диссертации опубликовано тринадцать печатных работ, список которых приведен в конце автореферата [12-24].

Апробация работы. Основные положения и отдельные результаты диссертации докладывались и обсуждались на Всероссийских конференциях "Решетневские чтения" (2003-2004 гг.), региональной конференции "Красноярский край - освоение, развитие, перспективы" (2003), Красноярской краевой выставке технических идей и разработок (2003), Красноярской конференции молодых ученых "Информатика и информационные технологии" (2003), международной научно-практической конференции "Системный анализ в проектировании и управлении" (Санкт-Петербург, 2004), межрегиональной научно-практической конференции "Интеллект -2004", а также на научно-техническом семинаре Института автоматизации управления Высшей специальной школы г. Ульм (FHU, Германия, 2003), научных семинарах экспериментальной лаборатории интеллектуальных технологий и адаптации и кафедры САИО в СибГАУ (2003-2004 гг.) и научном семинаре кафедры механики и процессов управления Красноярского госуниверситета (2003, 2004).

Структура и объем работы. Диссертация содержит 109 страниц основного текста, состоит из введения, трех глав, заключения, списка литературы из 105 наименований и приложения.

Выводы

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

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

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

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

Таким образом, практическая задача "Моделирования и оптимизации параметров канала с многолучевым распространением для цифрового радио" продемонстрировала необходимость применения специализированных методов оптимизации (эволюционных и генетических алгоритмов). При этом обыкновенный генетический алгоритм справился с поставленной задачей только в комбинации с методом локального поиска. В то время как коэволюционный алгоритм стационарной оптимизации позволил достигнуть результат (для каналов 1, 2, 4 и 5 при отношении сигнал к шуму в 40 и 30%), по крайней мере, не хуже чем результат найденный комбинацией обыкновенного генетического алгоритма и метода локального спуска, а при меньшей амплитуде шума еще и лучше. А применение коэволюционного алгоритма для решения нестационарных задач оптимизации позволило решить поставленную задачу в режиме непрерывной передачи сигналов.

Заключение

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

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

1. Абдеев Р.Ф. Философия информационной цивилизации. М.: ВЛАДОС, 1994.

2. Акопян A.M. Генетические алгоритмы для решения задачи глобальной оптимизации. URL: http://www.cp.niif.spb.Su/inpe/4/gaover/gaover.htm

3. Антамошкин А. И др. Системный анализ: проектирование, оптимизация и приложения, т. 2. Под общ. ред. А. Антамошкина, Сибирское отделение Международной инженерной академии Красноярск: САА, 1996.

4. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. М.: Высшая школа, 1998, 573с.

5. Базы данных. Интеллектуальная обработка информации / В.В. Корнеев, А.Ф. Гареев, С.В. Васютин, В.В. Райх- М.: Издатель Молгачева С.В.: Нолидж, 2001.- 496 с.

6. Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.

7. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. URL: http://saisa.chat.ru/ga/summer 97.html

8. Батищев Д.И., Скидкина Л.Н., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно генетических алгоритмов / Мужвуз. сборник, ВГТУ, Воронеж, 1994.

9. Волкова, В.Н. Основы теории систем и системного анализа: Учебник для студентов вузов, обучающихся по специальности "Системный анализ и управление" / В.Н. Волкова, А.А. Денисов 2-е изд., перераб. и доп.- СПб.: Изд-во СПбГТУ, 2001.-512 с.

10. Гайдышев, И. Анализ и обработка данных: Специальный справочник / И. Гайдышев.- СПб: Питер, 2001.- 752 с.

11. Дегтярев Ю. И. Системный анализ и исследование операций. М.: Высшая школа, 1996.

12. Емельянова М.Н. Применение эволюционного алгоритма с коэволюционной стратегией в экономико-математическом моделировании / М.Н. Емельянова // Сборник трудов Всероссийской конференции "IIs Туполевские чтения" / Казань: КГАУ, 2003. С. 1214.

13. Емельянова М.Н. Эволюционные алгоритмы для многокритериальной и многоэкстремальной оптимизации / А.В. Гуменникова, М.Н. Емельянова, В.А. Клешков // Вестник НИИ СУВПТ (Вып. 13): Сб. научн. трудов.- Красноярск: НИИ СУВПТ, 2003.— С. 237-248.

14. Емельянова М.Н. Об оптимизации многоэкстремальных задач с помощью коэволюционного алгоритма / Емельянова М.Н. // Сборник трудов межвузовской конференции "Информатика и информационные технологии". Красноярск: КГТУ, 2003. - С. 69-70.

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

16. СибГАУ. Красноярск: СибГАУ, 2004.

17. Емельянова М.Н. Коэволюционные алгоритмы и их применение в задаче оптимизации цифрового радиосигнала / Емельянова М.Н. // Вестник Университетского комплекса (Вып. 1): Сб. научн. трудов. -Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2004. С. 189-198.

18. Емельянова М.Н. Программная система "Coevolution vl.0" (система решения сложных задач оптимизации с помощью коэволюционного алгоритма) / Емельянова М.Н., Семенкин Е.С. // М.: ВНТИЦ (№ гос. per. 502004008732004). 12 с.Л

19. Жукова М.Н. О влиянии величины интервала адаптации на эффективность работы коэволюционного алгоритма / Жукова М.Н. //

20. Сборник трудов VIII Всероссийской научной конференции с международным участием "Решетневские чтения". Красноярск: СибГАУ, 2004.-С. 31-33.

21. Исаев С. А. Популярно о генетических алгоритмах. URL: http://saisa.chat.rU/ga/ga-pop.html#top

22. Ириков, В.А. Распределенные системы принятия решений. Теория и приложения / В.А. Ириков, В.Н. Тренев.- М.: Наука: Физматлит, 1999 — 288 с.

23. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений: Энциклопедия программиста: Пер. с англ. / Р. Хэзфилд, JI. Кирби, Д. Корбит и др.- К.: Диасофт, 2001.- 736 с.

24. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений: Энциклопедия программиста: Пер. с англ. / Р. Хэзфилд, JL Кирби, Д. Корбит и др.- К.: Диасофт, 2001 736 с.

25. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных: интеллектуальная обработка информации. М.: Нолидж, 2000. 352 с.

26. Кристиансен, Т. Perl: Библиотека программиста / Т. Кристиансен, Н. Торкингтон СПб.: Питер, 2001 - 736 с.

27. Липаев, В.В. Управление разработкой программных средств: Методы, стандарты, технология / В.В. Липаев- М.: Финансы и статистика, 1993.- 160 с.

28. Майерс, Г. Искусство тестирования программ / Г. Майерс; Пер с англ. под ред. Б.А. Позина М.: Финансы и статистика, 1982 - 176 с.

29. Олейников В.А. Основы оптимального и экстремального управления. М.: Высшая школа, 1969, 296с.

30. Орлов, С.А. Технологии разработки программного обеспечения: Учебник / С.А. Орлов.- СПб.: Питер, 2002.- 464 с.

31. Основы цифровой обработки сигналов: Курс лекций / А.И. Солонина, Д. А. Улахович и др. СПб.: БХВ - Петербург, 2003.

32. Пантелеев, А.В. Методы оптимизации в примерах и задачах: Учеб. пособие / А.В. Пантелеев, Т.А. Летова- М.: Высшая школа, 2002 544

33. Поиск подходов к решению проблем / И.В. Прангишвили, Н.А. Абрамова, В.Ф. Спиридонов и др.- М.: Синтег, 1999 284 с.

34. Прангишвили, И.В. Системный подход и общесистемные закономерности / И.В. Прангишвили М.: Синтег, 2000 - 528 с.

35. Прангишвили, И.В. Энтропийные и другие системные закономерности: Вопросы управления сложными системами / И.В. Прангишвили; Ин-т проблем управления им. В.А. Трапезникова М.: Наука, 2003.- 428 с.

36. Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т.- 2-е изд., испр- Т.1: Айвазян, С.А. Теория вероятностей и прикладная статистика / С.А. Айвазян, B.C. Мхитарян М.: ЮНИТИ-ДАНА, 2001 - 656 с.ч

37. Растригин Л. А. Адаптация сложных систем. М.: Наука, 1980.

38. Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма. URL:http://www.keldysh.ru/BioCyber/Lecture 10.html

39. Рихтер С. Г. Цифровое радиовещание. М.: Горячая линия Телеком, 2004.

40. Семенкин Е.С., Лебедев В.А. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами. М.: МАКС Пресс, 2002. - 320 с.

41. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Адаптивные поисковые методы оптимизации сложных систем-Красноярск: СИБУП, 1997.-355 с.

42. Семенкин Е.С., Терсков В.А. Модели и методы оптимизации систем управления сложными объектами. Красноярск: СЮИ МВД РФ, 2000. -211 с.

43. Соммервилл, И. Инженерия программного обеспечения: 6-е издание: Пер. с англ. / И. Соммервилл.- М: Издательский дом "Вильяме", 2002 — 624 с.

44. Стариков A. BaseGroup Labs. Генетические алгоритмы -математический аппарат. URL: http://www.basegroup.ru/genetic/math.htm

45. Столлингс, В. Операционные системы: 4-е издание: Пер. с англ. / В. Столлингс.- М.: Издательский дом "Вильяме", 2002 848 с.

46. Таха, X. Введение в исследование операций: 6-е издание: Пер. с англ. / X. Таха М: Издательский дом "Вильяме", 2001 - 912 с.

47. Трахтенгерц, Э.А. Компьютерная поддержка принятия решений / Э.А. Трахтенгерц- М.: Синтег, 1998 376 с.

48. Трахтенгерц, Э.А. Субъективность в компьютерной поддержке V управленческих решений / Э.А. Трахтенгерц М.: Синтег, 2001.- 256 с

49. Уорсли, Дж. PostgreSQL. Для профессионалов / Дж. Уорсли, Дж. Дрейк.- СПб.: Питер, 2003.- 496 с.

50. Фогель JI., Оунэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. Пер с англ. Зайченко Ю. П. Под ред. Ивахненко А. Г. М.:Мир, 1969.

51. Фокс, Дж. Программное обеспечение и его разработка: Пер. с англ. / Дж. Фокс.- М.: Мир, 1985.- 368 с.

52. Черноруцкий, И.Г. Методы оптимизации и принятия решений: Учебное пособие / И.Г. Черноруцкий.- СПб: Лань, 2001 384 с.

53. Шилдт, Г. Полный справочник по С: 4-е издание: Пер. с англ. / Г. Шилдт.- М.: Издательский дом "Вильяме", 2002 704 с.

54. Эбен, М. FreeBSD. Энциклопедия пользователя: Пер. с англ. / М. Эбен, Б. Таймэн- К.: ООО "ТИД "ДС", 2002.- 736 с.

55. Banzhaf W., Francone F. D., Nordin P. «The Effect of Extensive Use of the Mutation Operator on Generalization in Genetic Programming» Department of Computer Science, Dortmund University, Germany

56. Branke J. Memory Enchanced Evolutionary Algorithms for Changing Optimization Problems, Institute AIFB, University of Karlsruhe, 1999.

57. Branke J. Evolutionary Approaches to Dynamic Optimization Problems. Updated Survey. Institute AIFB, University of Karlsruhe, 1999.

58. Cramer Nichael Lynn «А representation for the adaptive generation of simple sequential programs» Proceedings of an International Conference on Genetic

59. Algorithms and Their Applications. Hillsdale, NJ: Lawrence Erlbaum Associates 1985.

60. DeJong K. A. An analysis of the behavior of a class of genetic adaptive ц. systems, doctoral dissertation, University of Michigan, 1975, Dissertation

61. Abstracts International 36(10)5140B.

62. Eggermont J., Lenaerts T. Non-stationary Function Optimization using Evolutionary Algorithms with a Case-based Memory, Leiden Institute of Advanced Computer Science, Leiden University.

63. Eiben A. E., Baeck Т., Schoenauer M., Schwefel H. P. (Eds.) Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V). Berlin: Springer, 1999.

64. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, Massachusetts: Addison-Wesley, 1989.

65. Ф 68. Grefenstette J. J. Genetic algorithms for changing environments, Navy center for Applied Research in Artificial Intelligence, Naval Research Laboratory, Washington, DC 20375, USA.

66. Hemert J. et al. A "Futurist" approach to dynamic environments, 2000.

67. Holland, J. H. (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1992 (2nd edition).

68. Koza John R. «Genetic programming tutorial» URL: http://www.genetic-programming.com/gpanimatedtutorial.html

69. Koza John R. «Hierarchical genetic algorithms operating on populations of computer programs» Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo: Morgan Kaufman, 1989

70. Oppacher F., Wineberg M. The Shifting Balance Genetic Algorithm: Improving the GA in a Dynamic Environment. Intelligent System Research

71. Unit, School of Computer Science, Carleton University, Ottawa, Canada, K1S 5B6.

72. Poli Riccardo «Exact Schema Theory for Genetic Programming and % Variable-Length Genetic Algorithms with One-Point Crossover». Genetic

73. Programming and Evolvable Machines, 2, 2001.

74. Schwefel H.-P., R. Maenner (Eds.), Parallel Problem Solving from Nature -Proc. 1st Workshop PPSN, Berlin: Springer.

75. Trojanowski K., Michalewich Z. Searching for Optima in Non-stationary Environments, Institute of Computer Science, Polish Academy of Science, 1999.77. ITU-R Regulations.

76. Алябьев С.И., Воднев B.A., Попов О.Б. Цифровая передача и обработка сигналов ЗВ в трактах формирования и первичного распределения

77. Ф программ: Учебное пособие / МИС. М., 1989, 82 с.

78. Быховский М.А. Круги памяти (Очерки истории развития радиосвязи и вещания в XX столетии). М., МЦНТИ, ООО «Мобильные коммуникации», 2001. - 224 с.

79. Быховский М.А., Дотолев В.Г., Зубарев Ю.Б. Проблемы выделения полос частот для наземного цифрового звукового вещания в России // Электросвязь, 2000, №6, с. 18 21.

80. Быховский М.А., Дотолев В.Г., Дьячков, М.Н. и др. Рекомендации по решению проблем внедрения в России новых технологий радиосвязи и вещания // Электросвязь, 2001, №3, с. 10-15.

81. Гитлиц М.В. Перспективы цифровой обработки и передачи звуковых сигналов//Электросвязь, 1991, N2, с. 18-22.Л

82. Городников А.С. Цифровое радиовещание // Итоги науки и техники. Сер. Связь. М.: ВИНИТИ, 1991, т. 7, с. 80-142.

83. Дворецкий И.М., Дриацкий И.Н. Цифровая передача сигналов звукового вещания. М.: Радио и связь, 1987. - 192 с.

84. Денин А., Кацнельсон J1. Система цифрового радиовещания "Эврика-147" // Радио, 1996, № 8, с.30-32.

85. Донцова Г.А. Исследование и разработка методов анализа и обработки сигнала звукового вещания с использованием комплексного представления. Автореферат диссертации на соискание ученой степени кандидата технических наук. Москва, МТУСИ, 2001.

86. Ефимов А.П. Цифровые методы в радиовещании: Учебное пособие / ВЗЭИС.-М., 1988.-90с.

87. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк J1.M. Теория передачи сигналов. М.: Радио и связь, 1986. - 304 с.

88. Иванов А.Б., Крупенников А.В. Система мониторинга качества сетей связи // Вестник связи, 2001, № 2, с. 51-56.

89. Иванчин А.Н., Литвин С.А., Попов О.Б., Рихтер С.Г. Эффективность обработки сигналов звукового вещания / Электросвязь, 2002, № 6, с. 7-10.

90. Иванчин А.Н., Рихтер С.Г. DRM современный стандарт цифрового радиовещания // Broadcasting. Телевидение и радиовещание, № 7 (27) ноябрь 2002, с. 60-64; №8 (28) декабрь 2002, с. 57-61.

91. Исаев А., Мишенков С. Цифровое радиовещание: состояние и перспективы // Радио, 1996, № 11, с. 6-7.

92. Кацнельсон Л. Результаты сравнительных испытаний систем цифрового звукового радиовещания // Радио, 1998, № 4, с. 68-70.

93. Лейбов А.З. Цифровое звуковое вещание // Электросвязь, 1993, N9, с. 27-29.

94. Помехоустойчивость и эффективность систем передачи информации / А.Г. Зюко, А.И. Фалько, И.П. Панфилов и др.; Под ред. А.Г. Зю-ко. М.: Радио и связь, 1985. - 272 с.

95. Прокис Дж. Цифровая связь. Пер. с англ./ Под ред. Д.Д. Кловского. -М.: Радио и связь. 2000. 800 с.

96. Регламент радиосвязи Российской Федерации. Вып.1. Утв. Госкомиссией по радиочастотам, М., 1999.

97. Рихтер С.Г. О путях внедрения цифрового радиовещания в России // Научно-техническая конференция. М., МТУСИ, 2000. Тезисы докладов, с. 205-206.

98. Спутниковая связь и вещание: Справочник. 3-е изд., перераб. и доп. Под ред. Л .Я. Кантора. - М.: Радио и связь, 1997. - 528 с.

99. Титов А., Рихтер С. Цифровое радиовещание в России как сделать и для кого? // Broadcasting. Телевидение и радиовещание № 7 (19) ноябрь 2001, с. 66-69.

100. Digital Radio: The sound of the Future. The Canadian Vision. Task Force of the Introduction of Digital Radio. Ottawa, Canada. Cat. No Co22-132/1993e, ISBN 0-662-20678-9.

101. European Telecommunication Standard ETSI TS 101 980 VI. 1.1 (200109). Technical Specification. Digital Radio Mondiale (DRM); System Specification.105. http://www.ibusiness.ru.