СРАВНИТЕЛЬНОЕ ИССЛЕДОВАНИЕ КЛАССИЧЕСКИХ МЕТОДОВ ОПТИМИЗАЦИИ И ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

Полный текст

На текущий момент развития современной науки и техники, теории и практики существует разнообразный состав сложных задач оптимизации. В постановке задач могут участвовать несколько целевых функций, функционалов, критериев качества, алгоритмически и таблично заданных функций. Целевые функции могут не обладать свойствами унимодальности, выпуклости вверх или вниз, дифференцируемости, линейности и т. д. Ограничения задачи могут образовывать сложную разрывную допустимую область, иметь нелинейный характер и т. д. Это является сложной научной проблемой для классических методов оптимизации. Под оптимизацией в текущей работе рассматривается достижение минимума одной сложной функции без ограничений. В зависимости от условий, накладываемых на целевую функцию, существуют и применяются различные классы методов оптимизации, что является объектом исследования настоящей работы. 23 Вестник СибГАУ. № 4(50). 2013 Формализованная постановка задачи безусловной однокритериальной оптимизации имеет следующий вид. Пусть существует одна целевая функция, оптимум которой необходимо определить. Под оптимумом в настоящей работе и во множестве книг по оптимизации понимается нахождение минимума. Это предположение является несущественным и применяется лишь для стандартизации рассуждений при рассмотрении различных методов. Задачу минимизации и задачу максимизации можно сводить друг к другу: f (x) ^ opt, где x — (x,, x2, ..., xn) є X - вектор решений размерности n; fx) - целевая функция (целевой функционал, критерий качества, алгоритм вычисления показателя качества). Классические методы оптимизации. Существует классификация методов оптимизации по наличию информации о производных функции. 1. Методы нулевого порядка: а) методы «золотого сечения», деления отрезка пополам, метод с использованием чисел Фибоначчи, квадратичная интерполяция, кубическая интерполяция для функций одной переменной; б) метод Хука-Дживса, метод покоординатного спуска Гаусса-Зейделя, генетический алгоритм, последовательный симплексный метод, метод Нелдера-Мида (метод деформируемого многогранника) для функций n переменных. Перечисленные методы используют в процессе оптимизации только значения функции в области значений и значения аргумента в области определения; они не используют значения производных первого, второго и n-го порядков. Все эти методы отлично изложены в источниках [1-3]. Они требуют от функции удовлетворения определенным условиям (например, унимодальная непрерывная выпуклая функция для метода деления отрезка пополам, деления отрезка в отношении «золотого сечения»). 2. Методы первого порядка (градиентные): градиентный метод с фиксированным шагом, градиентный метод с адаптивным шагом, градиентный метод, в котором шаг вычисляется на каждой итерации алгоритма и является решением одномерной задачи оптимизации (метод наискорейшего спуска по антиградиенту), градиентный метод с использованием теории планирования эксперимента (ортогональные планы первого порядка). Данные методы требуют существования первой производной оптимизируемой функции в аналитическом или численном приближённом виде (конечные разности). Данная группа методов использует информацию о направлении спуска к минимуму по антиградиенту, не настраивая при этом величину шага. Метод Флетчера-Ривса (поиск ведется вдоль взаимно сопряжённых направлений) и Давидона-Флетчера-Пауэлла (необходима положительная определённость и симметричность матрицы вторых производных) наиболее быстро сходятся, если оптимизируемая функция квадратичная (для n переменных необходимо n шагов). 3. Методы второго порядка (ньютоновские методы) требуют существования первой и второй производной оптимизируемой функции (например, для вычисления матрицы Гессиана) в аналитическом или численном приближённом виде (конечные разности или ортогональное композиционное планирование второго порядка). Данная группа методов использует информацию о направлении спуска к минимуму по антиградиенту и информацию о выпуклости функций, настраивая при этом величину шага. Если функция не дифференцируема, но является унимодальной, выпуклой и непрерывной, то возможно применение методов нулевого порядка. Методы оптимизации первого и второго порядков очень медленно сходятся вблизи окрестности оптимума, так как или градиент близок к нулю, или матрица вторых производных плохо обусловлена. Кроме того, данные методы сходятся не к глобальному оптимуму, а к ближайшему локальному экстремуму (т. е. очень зависят от выбора начальной точки), что недопустимо при решении многоэкстремальных задач ввиду существенной погрешности вычислений. Также градиентные методы медленно сходятся на овражных плохо масштабированных функциях. Существует следующая классификация методов оптимизации: 1. Стохастические: метод стохастической аппроксимации градиента целевой функции, генетические алгоритмы в любой форме и модификации, глобальная оптимизация методом усреднения координат. Вероятностные методы используют элементы случайности, необходимые для поиска глобального оптимума. Стохастические методы являются псевдослучайными, так как в них используется машинный генератор случайных чисел, удовлетворяющий статистическим проверкам (но возможно применение аналогового генератора, например, связанного с измерением радиоактивности атомов). 2. Детерминированные: все остальные перечисленные в статье методы. В данном классе методов все процедуры поиска строго определены математическими формулами. Генетические алгоритмы возникли в результате наблюдений за функционированием биологических систем. Идею генетических алгоритмов высказал Дж. Холланд в 1975 г. в своей книге «Адаптация в естественных и искусственных системах» [4]. Термин «генетические алгоритмы» ввел Д. Голдберг в 1975 г. [5]. В его книге описывается теория генетических алгоритмов и возможные сферы их применения. «Генетический алгоритм представляет собой метод, отражающий естественную эволюцию методов решения проблем, и в первую очередь задач оптимизации. Генетические алгоритмы - процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей» [6, c. 125]. Модификация генетического алгоритма. В ходе проведения научных исследований с различными классическими методами оптимизации нулевого, первого и второго порядков и классическим генетиче 24 Математика, механика, информатика ским алгоритмом была разработана новая самонастраивающаяся модификация генетического алгоритма в ходе решения задачи оптимизации. Принципы функционирования самонастраивающегося генетического алгоритма: 1. Настройки выбираются случайным образом в соответствии с полученным дискретным распределением вероятностей. 2. Начальные вероятности равны l/z, где z - количество алгоритмов. 3. Через настраиваемое количество поколений s пересчитывается эффективность применяемых настроек (тем самым обеспечивается накопление статистической информации и адаптация алгоритма): f. — avt — —, i — 1, z, ni где avi - средняя пригодность порожденных потомков; fi - общая пригодность индивидов, полученных i-м алгоритмом; nt - количество индивидов, полученных i-м алгоритмом; z - количество алгоритмов. 4. Распределение вероятностей выбора настройки или сочетания настроек для формирования потомков на поколении, кратном S, изменяется в пользу более эффективных за счет менее эффективных: m — max(avi ), i — 1, z , P1 — + ( z - I ·K (g ) z · N ’ P2 — - K(g), z · N где m - максимальная средняя пригодность индивидов; Pl - увеличение вероятности выигравшего алгоритма; P2 - уменьшение вероятности остальных алгоритмов; N - число поколений; K(g) - функция, зависящая от номера поколения g и осуществляющая взвешивание перераспределяемых вероятностей (рассматривалось несколько реализаций: K(g) = const, K(g) -линейная функция, экспонента, гиперболическая функция и др., подбор параметров функции K(g) осуществлялся статистическим анализом из условия обеспечения наилучших значений критериев эффективности модифицированного алгоритма в сравнении со стандартным алгоритмом). 5. Вероятности никогда не становятся равными нулю (осуществлялась настройка минимального значения вероятностей; согласно результатам проведённых экспериментов данное значение оказывает существенное влияние на надежность работы алгоритма и скорость сходимости). 6. Выполнение условия нормировки вероятностей. Итак, выбор настроек осуществляется стохастическим образом в соответствии с полученным дискретным распределением вероятностей настроек в процессе решения задачи оптимизации, без использования априорной информации об эффективности операторов генетического алгоритма, о свойствах задачи и пространства поиска. Программная реализация и эксперименты. В ходе проведения научных исследований были раз работаны программные системы на языке С++ (С++ Builder, см. рисунок), включающие классические и модифицированные алгоритмы оптимизации функций одной и многих вещественных переменных (для генетических алгоритмов применялась бинаризация). Разработанные программные системы были отлажены и протестированы на представительном множестве задач безусловной однокритериальной оптимизации (как унимодальные, монотонные, выпуклые функции, так и многоэкстремальные, недифференцируемые, овражные функции с множеством локальных нерегулярных оптимумов, слабо отличающихся от глобального, с протяженными оврагами в области оптимума, областями плато, разворотом функций относительно начала координат, нелинейностью, высокой размерностью до 100 вещественных переменных). Усреднённые результаты численных экспериментов (500, 1000 прогонов алгоритмов) обрабатывались с использованием непараметрических методов теории вероятностей и математической статистики (критерий Вилкоксона, ANOVA) для проверки статистической устойчивости в программной системе Statistica. Происходило вычисление и статистический анализ трёх критериев эффективности алгоритмов: надёжность, время работы, скорость сходимости. Проведённый статистический анализ доказал непротиворечивость выдвинутых гипотез экспериментальным данным: гипотеза о равенстве законов распределения критериев эффективности алгоритмов в независимых тестах алгоритмов (по 500 или 1000 независимых случайных реализаций) с одинаковыми настройками не противоречит экспериментальным данным, гипотеза о сдвиге законов распределения отвергается. Выполненная программная реализация и исследование классических методов прямого поиска для оптимизации унимодальных функций («золотое сечение», числа Фибоначчи, деление отрезка пополам, квадратичная интерполяция - для функций одной переменной, метод Хука-Дживса - для функций n переменных) позволили получить следующие результаты. Их нужно применять, если известно, что функция унимодальна, непрерывна, выпукла (так как сходимость детерминированного метода быстрее любого стохастического), но они не гарантируют получение глобального оптимума для многоэкстремальных функций. Метод разбиения отрезка в отношении «золотого сечения» (отношение длины всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части) сходится быстрее, чем метод деления отрезка пополам. Метод поиска с помощью чисел Фибоначчи сходится быстрее, чем метод «золотого сечения». Итак, в случае отсутствия априорной информации о свойствах задачи, пространства поиска необходимо пользоваться более универсальными стохастическими методами глобальной оптимизации, например, генетическим алгоритмом. Ввиду очень высокой трудоёмкости настройки классического генетического алгоритма (выбор настроек с локальным, глобальным или неопределенным характером схо 25 Вестник СибГАУ. № 4(50). 2013 димости) целесообразно использовать оригинальную разработанную в настоящей работе самонастраивающуюся модификацию генетического алгоритма, доказавшую высокую эффективность при решении различных классов задач оптимизации и интеллектуального анализа данных [7]: тестовые задачи безусловной и условной однокритериальной и многокритериальной оптимизации (в сочетании с методами SPEA и SPEA2), прикладные задачи условной однокритериальной и многокритериальной оптимизации, задача проектирования и настройки искусственных нейронных сетей в виде моделей многослойных полносвязных персептронов Розенблатта прямого распространения сигнала. Авторы настоящей статьи выражают благодарность преподавательскому составу Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева за ценные советы, рекомендации, хорошую теоретическую подготовку. Рабочие окна системы IT-SAGA 4 t ί C-SAQA Некоторые рабочие окна программной системы IT-SAGA

Об авторах

Владимир Борисович Звонков

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

Email: vladimirzvonkov802@yandex.ru
аспирант 660014, Красноярск, просп. им. газ. «Красноярский рабочий», 31

Алексей Михайлович Попов

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

Email: vm_popov@sibsau.ru
доктор физико-математических наук, профессор, профессор, директор института информатики и телекоммуникаций 660014, Красноярск, просп. им. газ. «Красноярский рабочий», 31

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

Дополнительные файлы