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

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

Галушии Павел Викторович

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

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

АВТОРЕФЕРАТ

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

005042ОО1

1 о •••

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

005042551

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

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

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

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

Ловчиков Анатолий Николаевич

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

Миркес Евгений Моисеевич

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

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

ФГБОУ ВПО «Национальный исследовательский Томский политехнический университет»

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

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

Автореферат разослан « » апреля 2012 г.

Ученый секретарь диссертационного совета доктор физико-математических наук

А. А. Кузнецов

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

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

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

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

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

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

1. Выполнить обзор существующих методов глобальной оптимизации.

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

3. Реализовать предложенные методы в виде программных систем.

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

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

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

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

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

3. Предложены модификации ГА, ВГА и АВГА, позволяющие эффективно решать задачи оптимизации с целочисленными переменными.

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

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

Практическая значимость. Разработанные в ходе исследования алгоритмы реализованы в виде программ «Асимптотический вероятностный генетический алгоритм (АРвА)» и «Глобальная оптимизация локальными и эволюционными мультиагентными

стохастическими алгоритмами (GOLEM-SA)», зарегистрированных в Роспатенте (№2012612374, №2011611158). Данные программные системы позволяют пользователям, не являющимся экспертами в эволюционной оптимизации, эффективно решать сложные практические задачи глобальной оптимизации. Они прошли апробацию на ряде практических задач и продемонстрировали превосходство над существующими аналогами по надёжности и быстродействию.

Реализация результатов работы. Результаты работы вошли в отчёты по НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)», НК-136П/3 «Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.2 и НК-409ПУ49 «Разработка устойчивого гибридного генетического алгоритма для определения кристаллических структур химических соединений из данных порошковой дифракции» по направлению «Физические методы исследования химических соединений» в рамках мероприятия 1.2.1 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы». В 2011 году по результатам исследования диссертанту присуждена Государственная премия Красноярского края в области системного анализа.

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

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

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

3. Учёт взаимосвязи переменных задачи оптимизации в ВГА и АВГА позволяет повысить эффективность этих алгоритмов.

4. АВГА позволяет эффективно решать задачу настройки параметров рыночного алгоритма динамического составления расписания.

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

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

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

научно-практических конференциях «Решетневские чтения» (Красноярск, СибГАУ, 2005, 2006, 2009), на 11-й Международной конференции «Natural Computations» в Шанхае (КНР, 2011), на Международных конференциях «Distributed Computing and Artificial Intelligence» и «Hybrid Artificial Intelligence Systems» в Саламанке (Испания, 2012).

Структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы.

Основное содержание работы

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

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

Вводятся обозначения, используемые в тексте диссертации. Пусть N — размер популяции, / — целевая функция, г — вероятность мутации. Исходная популяция состоит из булевых векторов (//,..., UN размерности М: Uk={uk!,...,uk,,i}. В результате селекции выбираются N векторов Xh...,XN размерности М: Xk={xu,...,xkil}, Р={рь...,рм} — вектор средних арифметических компонент решений, отобранных в ходе селекции:

1 "

Результат действия оператора мутации на вектор Хк будем обозначать Х'к. Вектора Х'к является случайными, так как мутация — стохастическая процедура. Вектор средних для векторов Jf* обозначим P'—{p'i,..., р:

2Х • (1)

Далее в первой главе на основе анализа теоретико-вероятностных свойств вероятностного генетического алгоритма, предлагается новый алгоритм оптимизации — асимптотический вероятностный генетический алгоритм.

Работу ВГА можно описать следующим образом:

1. Распределение значений генов в начале работы — равномерное, положить р(*—1/2,1=1 ...М.

2. Создать популяцию £Л,..., ГУдч в которой компоненты каждого вектора Щ являются независимыми случайными булевыми величинами, причём

3. Вычислить значения целевой функции =/(14).

4. Если выполнен критерий останова — прекращаем работу.

5. Сформировать промежуточную популяцию Х1,...,Хц с помощью выбранного метода селекции.

6. Применить к полученным решениям оператор мутации, мутировавшие решения обозначимХ'ь..., Х'к.

7. Вычислитьр',, 1=7.„М, по формуле (1).

8. Положитьрс=р'ь1=1 ...М.

9. Перейти к шагу 2.

Теорема. Имеют место равенства

Лф;] = 1- + 0-2г)Л,

Следствие. Дисперсия вектора средних «мутировавших» векторов стремится к нулю при размере популяции, стремящемся к бесконечности:

lim D\p'.] = 0.

ЛГ-хо

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

р\ = г + (\-2г)рг

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

Устанавливаются следующие свойства предложенной процедуры:

1. Преобразование (1) является линейным и сжимает отрезок [0;1] до отрезка [г;1-г].

2. Значение р=0,5 является неподвижной точкой отображения (1).

3. Время выполнения асимптотической мутации не зависит от размера популяции.

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

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

Проведём аналогичный анализ для оператора селекции. Будем считать теперь векторы-решения Ui,...,UN случайными, каждому из которых назначена вероятность прохождения отбора (в одном испытании): gi,-,gN-Подсчитаем математическое ожидание вероятности того, что г'-й ген окажется равным единице.

Теорема. Имеет место равенство

N 4=1

Теорема. Имеет место неравенство:

Следствие.

limD[p(]=0.

Л

Так как дисперсия р, стремится к нулю, мы можем использовать вместо случайных значений pt их математические ожидания.

Предложенный оператор можно назвать асимптотической селекцией. В обычных операторах пропорциональной и ранговой селекции вероятности прохождения отбора gj,...,gn вычисляются явно, поэтому они могут быть использованы как реализации асимптотической селекции непосредственно. Алгоритм оптимизации, аналогичный ВГА, но использующий асимптотические мутацию и селекцию, назван асимптотическим вероятностным генетическим алгоритмом (АВГА). Работу АВГА можно описать следующим образом:

1. Распределение значений генов в начале работы — равномерное, положитьр,+—1/2, i~l...M.

2. Создать популяцию Uj,...,UN, в которой компоненты каждого вектора Щ являются независимыми случайными булевыми величинами, причём P{ukr Ц ~Pi-

3. Вычислить значения целевой функции yk=f(Uy).

4. Если выполнен критерий останова — прекращаем работу.

5. Вычислить вероятности прохождения отбора gi,... ,gN.

6. Вычислить величины ¡£А> -

7. Применить к полученному распределению оператор асимптотической мутации p[=r + (l-2г)рг

8. Положитьpi=p'j,i-l...М.

9. Перейти к шагу 2.

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

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

Будем также предполагать, что значения Ук упорядочены по возрастанию. Вероятность выбора значения Ук обозначим как Ьк. Рассмотрим величины

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

Будет иметь место следующее равенство:

Теперь можно вычислить обычные вероятности выбора для значений:

Так как значение Ук встречается в коллективе решений пк раз, и все решения с одинаковым значением целевой функции должны иметь одинаковую вероятность выбора, то вероятность выбора для решения со значением целевой функции Ук равна Ьк/пк. Выражение вероятности выбора особи через вероятности выбора значений можно записать следующим образом:

к

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

В случае отбора без повторов, формула получается более сложной:

[ к\

[ 0, к < Г

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

jfcäf

А,

= Л/JV тах

lstss:

Ф,г) st{N,t)

Доказана следующая теорема:

Теорема. Если г — постоянная величина, то

Ига О, Л, =0.

Далее обосновывается асимптотический вероятностный генетический алгоритм для более общего случая целочисленных (не бинарных) переменных. Пусть г'-я компонента векторов Хк может принимать целочисленные значения из интервала [0;/,-1]. Введём следующее обозначение для вероятностей различных значений: ру — вероятность того, что ¡-я компонента вектора примет значение j. Вероятности значений компонент решений после мутации обозначим р\.

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

Теорема. Имеют место следующие равенства:

77+

Шп

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

Теорема. Распределение вероятностей ближе к равномерному распределению, чем /;„:

АВГА

Рч~

1

/,+1

В результате получен ABl А с целочисленным типом хромосом, аналогичный ранее исследованному бинарному АВГА.

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

Сц = м[хк1хк)\-м[х„]м\хк] \г,] = 1...М.

и одномерные распределения генов, которые определяются величинами р0-. Вычислим элементы корреляционной матрицы:

А=-42=,<,У = 1 -м.

Далее, тем элементам корреляционной матрицы, которые статистически незначимо отличаются от нуля, присваивается нулевое значение. Преобразованную таким образом корреляционную матрицу представляют (с помощью разложения Холецкого) в виде произведения R=STS, где S— верхне-диагональная матрица.

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

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

1. Порождаем М независимых стандартных нормальных случайных величин 2„ составляющие случайный вектор Z={z],...,zM}

2. Вычисляем вектор случайных величин Y-SZ с заданной корреляционной матрицей.

3. Элементы вектора Y преобразуются в значение генов с помощью дискретизации: x^j: t¡(]_i,<)>i<ty, Í-1...M.

Чтобы учитывать взаимосвязи переменных в АВГА, необходимо установить, как ковариационная матрица меняется при мутации. Пусть Хк — одинаково распределённые случайные булевы векторы с компонентами {хы,...,хш}, причём М[х1а]=р1 и Соv(x¡¡j,xy)=Cij. Значение ковариации после мутации обозначим как cV..

Теорема. Если все переменные — бинарные, то C'=(l-2r)2C + r(l-r)/.

Теорема. Если ftt=2^j- pv, то имеет место равенство

м

Роль мутации с точки зрения теории численных методов заключается в том, число обусловленности матрицы С' меньше, чем у матрицы С.

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

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

Программная система «Асимптотический вероятностный генетический алгоритм (APGA)» разработана на языке программирования С++ с использованием методологии мультипарадигменного проектирования. Программная система предназначена для решения задач условной и безусловной оптимизации с дискретными и вещественными переменными. В отличие от многих аналогичных программ, целевые функции и функции, задающие ограничения, не выбираются из фиксированного списка, а импортируются из подготовленных специальным образом динамически загружаемых библиотек (.dll в операционных системах семейства Microsoft Windows и .so — в операционных системах семейства GNU/Linux). Такой подход требует определённых навыков программирования от пользователя, но существенно расширяет возможности системы: значения целевой функции могут вычисляться по сколь угодно сложному алгоритму с использованием любых библиотек на языке С++, что принципиально невозможно при использовании интерпретатора или фиксированного набора функций.

В программной системе «Асимптотический вероятностный генетический алгоритм (APGA)» реализованы следующие методы оптимизации: стандартный генетический алгоритм (ГА), вероятностный генетический алгоритм (ВГА) и асимптотический вероятностный генетический алгоритм (АВГА). Для каждого алгоритма существует возможность выбора максимального основания системы счисления для кодирования небинарных переменных (от 2 до 32). Для ВГА и АВГА реализованы версии, учитывающие взаимосвязи между переменными.

Программная система «Глобальная оптимизация локальными и эволюционными. мультиагентными стохастическими алгоритмами (GOLEM-SA)», как и предыдущая, предназначена для решения сложных задач оптимизации, но в ней делается упор на автоматизацию выбора наиболее подходящего алгоритма оптимизации для данной задачи оптимизации, что позволяет решать сложные задачи оптимизации специалистам предметных областей, не являющимися экспертами в области эволюционных методов оптимизации. В данной программной системе реализованы следующие методы оптимизации: мультистарт локального поиска, стандартный генетический алгоритм (ГА), вероятностный генетический алгоритм (ВГА) и асимптотический вероятностный генетический алгоритм (АВГА), метод последовательного популяционного обучения (PBIL), роевые алгоритмы вещественной, дискретной, псевдо-булевой и смешанной оптимизации (PSO, Particle

Swarm Optimization), а также коэвотоционный алгоритм, сочетающий преимущества эволюционных и роевых алгоритмов.

В таблице 1 приведены результаты сравнения на тестовых задачах без шума из набора Black-Box Optimization Benchmarking (ВВОВ) 2010 ГА и методов, не учитывающих корреляции между распределениями: PBIL, АВГА и ВГА. В таблицах 1-3 delta обозначает разность между лучшим значением целевой функции, достигнутым алгоритмом, и значением целевой функции в глобальном оптимуме, а р — это доля запусков, в которых такая разность была достигнута. Лучшим считался алгоритм с меньшей delta, при равных значешшх delta, лучше алгоритм с большим значением р. В таблице 1 полужирным выделены лучшие значения в строке.

Таблица 1. Сравнение методов оптимизации.

не учитывающих корреляции

Алгоритм ГА ВГА АВГА PBIL

Задача delta р delta р delta Р delta Р

F1 1е-6 0,91 1е-6 0,99 1е-6 1 1е-6 1

F2 0,01 0,68 0,01 0,96 0,01 1 ОД 1

F3 1е-5 0,28 1е-5 0,49 1е-5 0,91 1е-3 0,98

F4 1е-3 0,3 1е-3 0,52 1е-3 0,98 1е-3 1

F5 0 0,42 0 0,81 0 1 0 1

F6 1е-4 0,12 1е-4 0,09 1е-5 1 1е-5 1

F7 1е-6 0,98 1е-8 1 1е-9 1 1е-9 0,18

F8 1е-6 0,11 1е-6 0,04 1е-6 0,12 1е-5 0,17

F9 1е-4 0,11 1е-4 0,04 1е-4 0,22 1е-4 0,36

F10 0,1 0,15 0,1 0,09 од 0,15 ОД 0,05

Fil 0,1 0,12 ОД 0,12 ОД од од 0,04

F12 0,01 0,08 0,01 0,12 0,01 од 0,01 0,03

F13 1е-3 0,09 1е-3 0,08 1е-4 0,12 1е-5 0,09

F14 1е-4 0,12 1е-5 0,13 1е-5 ОДЗ 1е-4 0,32

F15 1е-4 0,08 1е-4 ОД 1с-4 0,73 1е-4 0,62

F16 1е-3 0,24 1с-3 0,58 1е-3 0,97 1е-3 0,67

F17 1е-3 0,14 1е-3 0,37 1с-3 0,93 0,01 0,92

F18 од 0,18 0,1 0,24 ОД 0,61 ОД 0,17

F19 1 1,00 ОД 0,06 ОД 0,08 ОД 0,27

F20 0,1 0,54 ОД 0,41 ОД 0,80 од 0,27

F21 од 0,52 од 0,67 од 0,53 од 0,60

F22 0,1 0,13 од 0,40 од 0,27 од 0,67

F23 1 0,98 1 0,61 од 0,87 1 0,93

F24 10 1,00 10 0,86 10 1,00 1 0,67

Победы 1 3 15 9

Из таблицы видно, что АВГА превосходит ГА и ВГА практически на всех задачах по точности и надёжности нахождения решения. Кроме того, АВГА обладает большим быстродействием (на 30-50% быстрее, в зависимости от задачи). АВГА также превосходит другой широко известный метод класса EDA, не учитывающий взаимосвязи между переменными — PBIL.

Необходимо выяснить, как влияет учёт зависимостей между переменными на эффективность алгоритмов оптимизации. В таблице 2 приведены результаты решения задач оптимизации из пакета ВВОВ методами оптимизации, учитывающими корреляции между переменными (BOA - байесовский алгоритм оптимизации). Строка «Улучшения» содержит количество целевых функций, на которых алгоритм с учётом зависимостей между переменными превосходит аналогичный алгоритм без учёта зависимостей. В таблице 2 полужирным выделены случаи, когда учёт корреляций приводит к повышению эффективности решения задачи оптимизации.

Таблица 2. Сравнение методов оптимизации, учитывающих корреляции.

ВГА ВГА-2 АВГА АВГА-2 BOA

Функция delta Р delta р delta Р delta Р delta P

F1 1е-6 0,99 1е-13 1,00 1е-6 1 1е-8 1 le-6 0,41

F2 0,01 0,96 1 0,05 0,01 1 0,01 1 од 0,69

F3 1е-5 0,49 1е-30 0,89 1е-5 0,91 1е-5 0,98 le-3 0,25

F4 1е-3 0,52 од 0,01 1е-3 0,98 1-3 0,98 le-3 0,3

F5 0 0,81 0,01 0,01 0 1 0 1 0 0,38

F6 1е-4 0,09 1е-3 0,03 1е-5 1 1е-5 1 le-4 0,04

F7 1е-8 1 1е-7 0,99 1е-9 1 1е-9 1 le-6 0,14

FS 1е-6 0,04 1е-6 0,42 1е-6 0,12 1е-6 0,19 le-3 0,09

F9 1е-4 0,04 1е-7 0,48 1е-4 0,22 1е-4 0,27 le-3 0,03

F10 ОД 0,09 1е-7 0,82 од 0,15 1е-3 0,03 0Д 0,11

Fil 0,1 0,12 1е-5 0,16 ОД ОД ОД 0,11 0,1 0,06

F12 0,01 0,12 1е-5 0,2 0,01 ОД 1е-4 0,04 0,18 0,01 le-3 0,01 0.02

F13 1е-3 0,08 1е-6 0,96 1е-4 0,12 1с-4

F14 1е-5 0,13 1е-9 033 1е-5 ОДЗ 1е-4 0,03 le-4 0,11

F15 1е-4 0,1 1е-4 0,01 1е-4 0,73 1е-4 0,69 le-4 0,03

F16 1е-3 0,58 1е-3 0,05 1е-3 0,97 1е-3 ОДЗ le-3 0,26

F17 1е-3 0,37 1е-3 0,32 1е-3 0,93 1е-3 0,83 le-2 0,31

F18 0,1 0,24 0,01 0,74 ОД 0,61 ОД 0,32 0Д 0,01

Улучшения 10 7

Из таблицы 2 видно, что учёт корреляций повышает эффективность ВГА для 10 целевых функций. В случае АВГА учёт корреляций повышает эффективность нахождения оптимума для 7 целевых функций, для ещё 4 задач различий нет.

Кроме того, ВГА и АВГА с учётом корреляций превосходят наиболее распространённый метод класса EDA с учётом зависимостей переменных — BOA. Отметим, что BOA обладает существенно меньшим быстродействием, чем АВГА: примерно в 15-30 раз в зависимости от целевой функции.

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

В таблице 3 приведены результаты сравнения гибридной схемы с худшим результатов аналогичных алгоритмов без учёта корреляций и учётом корреляций на всех итерациях, (А)ВГА-1-2 — это модификация (А)ВГА, в котором на первой половине итераций взаимосвязи переменных не учитываются, а на второй — учитываются. Полужирным выделены результаты, когда гибридная схема позволяет избежать худшего случая.

Таблица 3. Эффективность гибридного метода.

Худшее из ВГЛи ВГА-2 ВГА-1-2 Худшее из АВГА и АВГА-2 АВГА-1-2

Функция delta Р delta Р delta Р delta Р

F1 1е-6 0,99 1е-11 1,00 1е-6 1,00 1е-16 1,00

F2 1 0,05 0,01 0,99 0,01 1,00 0,01 1,00

F3 1е-5 0,49 1е-5 0,51 1е-5 0,91 1е-5 1,00

F4 0,1 0,01 1е-3 0,59 1е-3 0,98 1е-3 1,00

F5 0,01 0,01 0 0,85 0 1,00 0 1,00

F6 1е-3 0,03 1е-4 0,11 1е-5 1,00 1е-5 1,00

F7 1е-7 0,99 1с-9 0,12 1е-9 1,00 1е-9 0,09

F8 1е-6 0,04 1е-4 0,06 1е-б 0Д2 1е-5 0,04

F9 1е-4 0,04 1е-4 0,08 1е-4 0,22 1е-4 0,12

F10 0,1 0,09 ОД 0,12 0,1 0,15 ОД 0,22

F11 0,1 0,12 од 0,20 0,1 0,1 од 0,29

F12 0,01 0,12 0,01 0,12 0,01 0,1 0,01 0,17

F13 1е-3 0,08 1е-3 0,24 1е-4 0,12 1е-4 0,08

F14 1е-5 0,13 1е-5 0,08 1е-4 0,03 1е-4 0,46

F15 1е-4 0,01 1е-4 0,11 1е-4 0,69 1е-4 0,59

F16 1е-3 0,58 1е-3 0,67 1е-3 0,13 1е-3 0,93

F17 1е-3 0,37 1е-3 0,42 1е-3 0,83 1е-3 0,89

F18 0,1 0,24 од 0,27 ОД 0,32 од 0,42

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

В четвёртой главе предложенные алгоритмы оптимизации применяются для решения практической задачи динамического составления расписаний.

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

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

Рыночный алгоритм динамического составления расписания был применён для управления участком окраски грузовых автомобилей. Работы характеризуются цветом, в который должен быть окрашен грузовик. Время окрашивания не зависит от цвета (3 минуты), но если поступающий в камеру окрашивания грузовик должен быть окрашен не в тот же цвет, что предыдущий, то необходимо сменить краску, что также занимает 3 минуты (кроме того, смена краски является затратной). Целью является минимизация общего времени выполнения всех работ. В таблице 4 приведены результаты решения задачи выбора параметров рыночного алгоритма для управления участком окраски грузовиков различными эволюционными алгоритмами (ВГА-2 — ВГА с учётом корреляций, АВГА-2 - АВГА с учётом корреляций). Полужирным выделены лучшие результаты.

Таблица 4. Результаты решения задачи выбора параметров рыночного алгоритма

Алгоритм Среднее Ср. кв. уклонение Затраченное время (секунды)

ГА (двоичный) 4,62 0,89 9,85

ГА (десятичный) 4,69 0,87 9,31

ВГА (двоичный) 4,70 0,74 10,60

ВГА (десятичный) 4,86 0,94 9,99

АВГА (двоичный) 4,65 0,89 9,26

АВГА (десятичный) 4,68 0,66 9,81

ВГА-2 (двоичный) 4,73 0,83 10,27

ВГА-2 (десятичный) 4,90 1.02 9,82

АВГА-2 (двоичный) 4,72 0,78 10,12

АВГА-2 (десятичный) 4,24 0,69 9,11

ВГА-1-2 (двоичный) 3,83 0,63 9,83

ВГА-1-2 (десятичный) 3,74 0,48 10,18

АВГА-1-2 (двоичный) 3,92 0,61 10,22

АВГА-1-2 (десятичный) 3,65 0,61 9,55

РВ1Ь 4,32 0,64 10,28

ВОА 3,62 0,57 23,67

Из таблицы видно, что лучшее значение целевой функции достигнуто гибридной схемой АВГА (первая половина итераций — без учёта корреляций, вторая половина — с учётом корреляций). При этом использование десятичного кодирования повышает эффективность по сравнению с двоичным кодированием. Аналогично, гибридный ВГА превосходит как стандартный ВГА, так и ВГА с учётом корреляций. Гибридный АВГА превосходит широко распространённый метод класса EDA без учёта корреляций — PBIL, и имеет сравнимую эффективность с методом BOA (отметим, что BOA обладает существенно меньшим быстродействием, в данной задаче — более чем в два раза). АВГА превосходит другие методы эволюционной оптимизации без учёта зависимостей между переменными по быстродействию. АВГА с учётом корреляций превосходит по быстродействию другие методы оптимизации с учётом взаимосвязей между переменными (в том числе, BOA).

Далее рассматривается задача настройки параметров рыночного алгоритма для управления GRID-системой, то есть вычислительной сетью, состоящей из пространственно распределённых вычислительных ресурсов. Был рассмотрен следующий сценарий: задачи, которые должны быть решены с помощью GRID-системы, неизвестны заранее, то есть моменты их появления представляют собой поток случайных событий, а вычислительная сложность и объём задач являются случайными величинами. В качестве критерия качества использовалось среднее время завершения задач (с учётом времени, затрачешюго на пересылку данных) в секундах. Результаты численных экспериментов приведены в таблице 5.

Таблица 5. Результаты решения задачи управления GRID-системой

Алгоритм Среднее Ср. кв. уклонение Затраченное время (секунды)

ГА (двоичный) 21,01 0,58 56

ГА (десятичный) 20,91 1,15 54

ВГА (двоичпый) 20,61 1,27 55

ВГА (десятичный) 20,52 1,11 55

АВГА (двоичный) 20,86 1,22 57

АВГА (десятичный) 20,87 1,27 54

ВГА-2 (двоичный) 20,42 1,52 63

ВГА-2 (десятичный) 20,37 1,45 60

АВГА-2 (двоичный) 20,49 1,23 67

АВГА-2 (десятичный) 20,50 1,29 57

ВГА-1-2 (двоичный) 20,31 1,25 61

ВГА-1-2 (десятичный) 20,29 1,27 57

АВГА-1-2 (двоичный) 20,26 1,17 63

АВГА-1-2 (десятичный) 20,26 1,16 60

РВ1Ь 20,39 1,27 54

ВОА 20,27 1,24 74

Приведённые результаты показывают, что лучшее значение целевой функции было достигнуто гибридным АВГА. Гибридный АВГА превосходит два широко известных метода класса EDA: PBIL (лучшее среднее значение целевой функции) и BOA (при примерно одинаковом среднем значении целевой функции, у гибридного АВГА меньше дисперсия и выше быстродействие). Быстродействие алгоритмов одного класса различается несущественно из-за того, что преобладающим фактором является время вычисления значения целевой функции, а не время проработки алгоритмов.

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

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

При проведении диссертационного исследования получены следующие результаты:

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

2. Предложены модификации ВГА и АВГА, в которых учитываются корреляции между переменными задачи оптимизации.

3. Предложены модификации генетического алгоритма, ВГА и АВГА с небинарным кодированием переменных.

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

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

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

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

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

1. Галушин, П.В. Разработка и исследование асимптотического вероятностного генетического алгоритма / П.В. Галушин, О.Э. Семёнкина // Journal of Siberian Federal University. Mathematics & Physics. № 5(1). — 2011. — p. 46-56.

2. Галушин, П.В. Асимптотический вероятностный генетический алгоритм дискретной оптимизации // П.В. Галушин, О.Э. Семёнкина // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. № 5 (38). —2011. —С. 25-29.

3. Галушин, П.В. Автоматизированная система глобальной оптимизации многоагентными стохастическими алгоритмами / П.В. Галушин, С.Н. Ефимов, Е.С. Семёнкин, И.А. Панфилов // Программные продукты и системы. № 3 (95). — 2011. — С. 97101.

4. Галушин, П.В. Асимптотический вероятностный генетический алгоритм / П.В. Галушин, Е.С. Семёнкин // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. № 4 (25). — 2009. — С. 37-42.

5. Galushin, P.Y. The asymptotic probabilistic genetic algorithm / P.V. Galushin, E.S. Semenkin // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. № 5(26). —2009. —С. 45-49.

6. Galushin, P. Comparative Analysis of Two Distribution Building Optimization Algorithms / P. Galushin, O. Semenkina, A. Shabalov // In: Distributed Computing and Artificial Intelligence. Advances in Intelligent and Soft Computing, Volume 151. - 2012. - pp. 759-766.

7. Shabalov, A., Semenkin E., Galushin, P. Integration of Intelligent Information Technologies Ensembles for Modeling and Classification / A. Shabalov, E. Semenkin, P. Galushin // In: Corchado E. et al. (Eds): Hybrid Artificial Intelligent Systems. - Part I. - Lecture Notes in Computer Science. - Volume 7208. - 2012. - Pp. 365-374.

8. Galushin, P.V. Design and analysis of asymptotic genetic algorithm / P.Y. Galushin, O. E. Semenkina // Proc. of the 11th International Conference of Natural Computations. — 2011. — p. 1082-1087.

9. Shabalov, A. Automatized design application of intelligent information technologies for data mining problems / A. Shabalov, E. Semenkin, P. Galushin // Proc. of the 11th International Conference of Natural Computations. — 2011. — p. 2596-2599.

10. Галуишн, П.В. Об асимптотическом вероятностном генетическом алгоритме / П.В. Галушин // Решетнёвские чтения: Материалы XIII Междунар. науч. конф., посвящ. 45-летию Сиб. гос. аэрокосмич. ун-та имени акад. М. Ф. Решетнева. (10-12 ноября 2009, г. Красноярск) / Под общ. ред. С. И. Сенашова. - Сиб. гос. аэрокосмич. ун-т. - Красноярск, 2009. - 4. 2. - С. 409-411.

11. Галушин, П.В. Динамическое составление расписания адаптивными методами / П.В. Галушин // Вестник университетского комплекса: Сб. науч. трудов / Под общ. ред. профессора Н.В. Василенко. - Красноярск: ВСФ РГУИТП, НИИ СУВПТ, — 2006.— Выпуск 7 (21). — С. 111-115.

12. Галушин, П.В. Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами (GOLEM-SA): свидетельство о государственной регистрации программы для ЭВМ / П.В. Галушин, С.С. Бежитский, и др. — М.: Реестр программ для ЭВМ, 2011. Номер гос. per. №2011611158.

13. Галушин, П.В. Асимптотический вероятностный генетический алгоритм (APGA): свидетельство о государственной регистрации программы для ЭВМ / П.В. Галушин — М.: Реестр программ для ЭВМ, 2012. Номер гос. per. .N'»2012612374.

Галушин Павел Викторович Асимптотический вероятностный генетический алгоритм решения сложных задач глобальной оптимизации Автореферат Подписано к печати 16.04.2012. Формат 60x84/16 Уч. изд. л. 1.0 Тираж 100 экз. Заказ № /?0~ Отпечатано в отделе копировальной и множительной техники СибГАУ.

660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31

61 12-5/3612

Министерство образования и науки Российской Федерации ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева»

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

Галушин Павел Викторович

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

ОПТИМИЗАЦИИ

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

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

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

Содержание

Содержание 2

Введение 4

1 Асимптотический вероятностный генетический алгоритм псевдо-булевой оптимизации 9

1.1 Обзор существующих методов глобальной оптимизации . . 9

1.2 Асимптотическая мутация......................................20

1.3 Асимптотическая селекция.........................25

Выводы и результаты................................................28

2 Обобщения асимптотического вероятностного генетического алгоритма 30

2.1 Асимптотическая турнирная селекция........................30

2.2 АВГА и ВГА для оптимизации функций целочисленных

(не бинарных) переменных....................................42

2.3 Учёт взаимосвязей между переменными в АВГА............48

Выводы и результаты................................................58

3 Программная реализация предложенных методов 60

3.1 Программная система «Асимптотический вероятностный генетический алгоритм»........................................60

3.2 Программная система «Глобальная оптимизация локальными и эволюционными многоагентными стохастическими алгоритмами (GOLEM-SA)» ..............73

3.3 Тестирование алгоритмов, не учитывающих взаимосвязи переменных......................................................76

3.4 Тестирование алгоритмов, учитывающих взаимосвязи

переменных......................................................78

Выводы и результаты................................................82

4 Эвристические алгоритмы динамического составления

расписаний 85

4.1 Динамическое составление расписаний........................85

4.2 Применение рыночного алгоритма для управления цехом окраски грузовиков ............................................90

4.3 Применение рыночного алгоритма для управления &1ГО-системой..................................................93

Выводы................................................................95

Заключение 97

Список литературы 99

Список публикаций автора 116

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Предложены модификации ГА, ВГА и АВГА, позволяющие эффективно решать задачи оптимизации с целочисленными (не бинарными) переменными.

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

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

Практическая значимость. Разработанные в ходе исследования алгоритмы реализованы в виде программ «Асимптотический вероятностный генетический алгоритм (АРСА)» и «Глобальная оптимизация локальными и эволюционными многоагентными

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

Реализация результатов работы. Результаты работы вошли в отчёты по НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009-2010 годы)», НК-136П/3 «Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.2 и НК-409П/49 «Разработка устойчивого гибридного генетического алгоритма для определения кристаллических структур химических соединений из данных порошковой дифракции» по направлению «Физические методы исследования химических соединений» в рамках мероприятия 1.2.1 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы».

В 2011 году по результатам исследования диссертанту присуждена Государственная премия Красноярского края в области системного анализа.

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

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

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

3. Учёт взаимосвязи переменных задачи оптимизации в ВГА и АВГА позволяет повысить эффективность этих алгоритмов.

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

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

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

Апробация результатов работы. Результаты работы были представлены на Всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики» (Красноярск, СибГАУ, 2005 г.), Международных научно-практических конференциях «Решетнёвские чтения» (Красноярск, СибГАУ, 2005, 2006 и 2009 гг.), на 11-й Международной конференции «Natural Computations» в Шанхае (КНР, 2011 г.), на Международных конференциях «Distributed Computing and Artificial Intelligence» и «Hybrid Artificial Intelligence Systems» в Саламанке (Испания, 2012 г.).

Структура работы. Диссертация содержит 95 страниц основного текста и состоит из введения, четырёх глав, заключения, списка литературы на 140 источников. Основной текст диссертации включает 8 таблиц, 15 рисунков.

Глава 1 Асимптотический

генетический алгоритм оптимизации

вероятностный псевдо-булевой

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

1.1 Обзор существующих методов глобальной оптимизации

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

Методы глобальной оптимизации должны решать две противоречащие друг другу задачи: искать локальный минимум и уклоняться от него, так как нет полной уверенности, что данный локальный минимум является одновременно глобальным [21].

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

функции возникают в моделях, которые необходимо оптимизировать в различных областях: проектирование сверхбольших интегральных схем (СБИС) [40, 43], статистической механике [43, 53], теории надёжности [102], информатике [81], статистике [112, 113], экономике [70], финансах [74, 86, 87], исследовании операций [68, 110, 132], менеджменте [133], дискретной математике [62, 69, 121], планировании производства [37].

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

Исторически первыми методами глобальной оптимизации были метод Монте-Карло и основанный на нём метод мулътистарта. Случайным образом выбирается точка, из которой осуществляется спуск с помощью выбранного алгоритма локального поиска. Этот процесс повторяется, пока не будут исчерпаны вычислительные ресурсы, выделенные на решение задачи, либо не будет найдено уд о в л ст во р и те л ь н ое решение [114]. Недостаток метода мультистарта заключается в том, что один и тот же локальный оптимум может быть найден несколько раз. Одним из способов устранения этого недостатка является адаптивное изменение распределения стартовых точек в пространстве поиска но мере получения информации о свойствах целевой функции в ходе процесса оптимизации [17, 21].

Другой подход к преодолению этого недостатка используется в методах группировок (clustering methods) [125]: после выполнения нескольких шагов локального поиска производится кластерный анализ полученных точек, если удаётся выделить ярко выраженные группы точек, то каждая группа точек заменяется одной точкой (например лучшей из группы), а остальные устраняются, дальнейший поиск ведётся из полученных таким образом точек. Разработано множество модификаций исходного метода группировок. Одной из таких модификаций является топографический мет,од (topographical

method) [126].

Методы покрытий и методы интервалов [58, 72] являются детерминированными и гарантируют, что глобальный оптимум будет найден с заданной точностью, однако для использования данных методов требуется некоторая априорная информация о свойствах целевой функции: методы покрытия (в одномерном случае метод покрытий называют методом Шуберта-Пиявского [20]) требует знания константы Липшица целевой функции, а метод интервалов применим только к дважды непрерывно дифференцируемым целевым функциям, причём первая и вторая производная целевой функции должны иметь в области поиска конечное число нулей. Большинство методов интервалов использует стратегию ветвей и границ [101].

Существует группа методов, основанных на модификации целевой функции. Так например, в методе туннелей [65] (tunneling method) после того, как найден некоторый локальный оптимум, решается задача оптимизации сконструированной специальным образом туннельной функции, что позволяет покинуть область притяжения текущего локального минимума. Недостатком данного метода является то, что туннельная функция имеет овражный характер.

Другой подход заключается в сглаживании целевой функции [12, 19, 28]. В результате сглаживания целевая функция приобретает удобные для методов оптимизации свойства (исчезают разрывы и уменьшается число локальных экстремумов). К этой же группе можно отнести методы, основанные на аппроксимации целевой функции, например с помощью непараметрической оценки кривой регрессии [16]. Ещё одним методом, основанным на идеях непараметрической статистики, является метод усреднения координат [23].

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

поиска [11].

В последнее время появилось большое количество эвристических методов глобальной оптимизации, в основе которых лежат аналогии с физическими, биологическими и социальными процессами. Так в методе имитации отжига (Simulated annealing) [30, 96] используется анало