Эволюционный алгоритм с автоматическим выбором генетических операторов

Размещено на http://www.allbest.ru/

Эволюционный алгоритм с автоматическим выбором генетических операторов

В.Б. Звонков (vova_oven@mail.ru)

С.Н. Ефимов (efimov@bk.ru)

Аннотация

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

Введение

Генетические алгоритмы применяются при решении сложных задач оптимизации (безусловная и условная одно- и многокритериальная оптимизация многоэкстремальных алгоритмически заданных функций многих разношкальных переменных, задачи нестационарной оптимизации и т.д.). Генетические алгоритмы обладают некоторыми свойствами (универсальность, отсутствие необходимости в априорной информации о конкретной задаче, адаптивность, эффективный глобальный и локальный поиск, малая доля использования поискового пространства и т.д.), благодаря которым они применяются при решении задач, с которыми стандартные методы оптимизации или метод полного перебора не справляются. Многие системы оптимизации основаны на генетических алгоритмах [Бугаев, 2007]. Недостатком эволюционных алгоритмов является требование тщательного выбора настроек для каждой решаемой задачи с целью получения оптимального решения за приемлемое время. Если для тестовых задач возможен полный перебор всех настроек ГА, то для многих реальных задач такой подход является недопустимым. Целевая функция в реальных задачах может вычисляться по сложному алгоритму и требовать значительного времени на проработку (например, поиск пути роботом в лабиринте или эксперимент на реальном объекте). В связи с этим, представляется актуальным решение проблемы уменьшения количества настраиваемых параметров. Это обеспечит эффективное использование генетического алгоритма пользователями, не являющимися специалистами в эволюционной оптимизации, а также сократит материальные и временные затраты.

1. Модификация эволюционного алгоритма

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

Принципы работы предложенных алгоритмов состоит в следующем:

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

Начальные вероятности равны , где z - число алгоритмов (число комбинаций настраиваемых параметров).

На каждом поколении оценивается эффективность применяемых настроек (по средней пригодности порожденных потомков):

,

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

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

,

,

,

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

Вероятности никогда не становятся равными нулю.

Безусловное выполнение условия нормировки вероятностей.

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

2. Проверка работоспособности модифицированного алгоритма

Для апробации алгоритма был выбран стандартный набор тестовых задач безусловной и условной однокритериальной оптимизации, принятый в научном сообществе [Hansenetal., 2009]. Методика тестирования стандартная. Работоспособность подхода была также проверена на трех реальных практических задачах: формирование инвестиционного портфеля предприятия (на примере Химзавода - филиала ФГУП «Красмаш»), формирование кредитного портфеля банка (Красноярский филиал банка Москвы) и оптимизация управления кредитным финансированием проектов с длительным инвестиционным циклом (на примере ОАО «Информационные спутниковые системы»). Общее число комбинаций настроек на одной задаче для стандартного алгоритма безусловной оптимизации составляет 360 (5 типов селекции, 3 вида скрещивания, 3 уровня мутации, 2 способа управления популяцией, концепция элитизма и ее отсутствие, 2 способа представления индивидов). Было рассмотрено 5 методов учета ограничений в задачах условной оптимизации: динамические штрафы, адаптивные штрафы, смертельные штрафы, лечение, лечение + смертельные штрафы [Michalewicz, 1995]. Общее количество комбинаций настроек стандартного алгоритма условной оптимизации составляет 1800. Детали приведены в таблице 1.

Табл. 1

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

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

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

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

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

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

Так как время работы любого генетического алгоритма зависит от конфигурации ЭВМ, то приведем кратко конфигурацию системы: центральный процессор - IntelCore i7-920, работающий натактовой частотой 3.6 ГГц, материнская плата - Gigabyte GA EX-58-UD3R. Объем ОЗУ, требуемый при данных параметрах тестирования, равен 9 Мбайт. Работоспособность программной системы проверена в операционных системах WindowsXP/Vista/7 и MandrivaLinux 2010.0.

В таблице 2 приведены усредненные результаты тестирования стандартного и модифицированных алгоритмов на 10 тестовых задачах (число независимых запусков - 500, бинарные строки по 46-50 бит, ресурсы - 100 индивидов на 100 поколений). Усреднение производилось по множеству тестовых задач. Из полученных усредненных результатов определялся разброс надежностей, разброс времен работы алгоритмов при различных сочетаниях настроек, оценка скорости сходимости алгоритмов к оптимуму. Настройки, при которых надежность работы алгоритма была равна 0, не учитывались.

Табл. 2.

Результаты решения практических задач (усреднение по 100 прогонам):

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

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

Заключение

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

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

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

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

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

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

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

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

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

Благодарности. Работа выполнена при финансовой поддержке:

НИР 2.1.1/2710 «Математическое моделирование инвестиционного развития региональных экономических систем». АВЦП "Развитие научного потенциала высшей школы" на 2009-2010 гг.

НИР НК-136П/3 «Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами"

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

[Бугаев, 2007] Бугаев А.С., Система оптимизации на генетических алгоритмах // Информационные технологии и вычислительные системы. 2007. № 3.

[Звонков, 2009] Звонков В.Б. Применение генетического алгоритма с автовыбором селекции к решению задач безусловной и условной однокритериальной оптимизации // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием (12-13 ноября 2009 г.). - Томск: Изд-во Том.ун-та, 2009. Ч. 2.

[Клешков, 2006] Клешков В.М., Семенкин Е.С. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного машиностроительного предприятия // Проблемы машиностроения и автоматизации. 2006. № 3.

[Пуртиков, 2001] Пуртиков В.А. Оптимизация управления формированием кредитного портфеля банка: дисс. … канд. техн. наук. - Красноярск: САА, 2001.

[Семенкин и др., 2010] Генетический алгоритм. Стандарт. Часть I. Описание стандартного генетического алгоритма (сГА) [Internet] http://www.harrix.org/main/project_standart_ga.php, версия от 10.03.2010.

[Hansen et al., 2009] Hansen N. Real-Parameter Black-Box Optimization Benchmarking 2009: Experimental Setup. INRIA research report RR-6828, 2009.

[Michalewicz, 1995] Michalewicz Z. Genetic algorithms, numerical optimization and constraints // Proc. of the Sixth Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, 1995.

Размещено на Allbest.ru