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

Характеристика модификации стандартного генетического алгоритма, особенности принципа его работы. Проверка работоспособности модифицированного алгоритма. Использование критериев Уилкоксона, Манна-Уитни и пакета статистической обработки данных Statistica.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 19.01.2018
Размер файла 25,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на 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

Тип генетического алгоритма

Общее число комбинаций параметров генетического алгоритма

Стандартный

1800

Автонастройка мутации

600

Автонастройка скрещивания

600

Автонастройка селекции

360

Автонастройка мутации и скрещивания

200

Автонастройка селекции и мутации

120

Автонастройка селекции и скрещивания

120

Автонастройка селекции, мутации и скрещивания

40

Использовались оптимальные настройки методов учета ограничений, предварительно подобранные по результатам статистического анализа. Применялась реализация метода лечения, в которой расстояние между индивидами определяется значением их координат, а не значением целевой функции, т.к. было подтверждено, что данный подход является более эффективным [Звонков, 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.

Тип генетического алгоритма

Разброс надежностей

Разброс времени работы (c/500)

Разброс средних поколений (когда алгоритм впервые находит оптимум)

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

Стандартный

[0, 1]

[22, 74]

[21, 84]

[2252, 8512]

Автонастройка селекции

[0.71, 1]

[34, 68]

[26, 59]

[2707, 6013]

Автонастройка мутации

[0, 0.99]

[20, 63]

[21, 84]

[2259, 8516]

Автонастройка скрещивания

[0, 1]

[29, 76]

[22, 85]

[2319, 8545]

Селекции и мутации

[0.88, 0.99]

[33, 66]

[28, 39]

[2907, 3949]

Мутации и скрещивания

[0, 0.99]

[27, 70]

[23, 81]

[2444, 8199]

Селекции и скрещивания

[0.25, 1]

[36, 61]

[28, 66]

[2861, 6732]

Селекции, мутации и скрещивания

[0.93, 1]

[39, 60]

[28, 35]

[2903, 3581]

Результаты решения практических задач (усреднение по 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

...

Подобные документы

  • Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.

    лабораторная работа [20,2 K], добавлен 03.12.2014

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

    реферат [1014,2 K], добавлен 14.01.2016

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

    курсовая работа [714,1 K], добавлен 31.03.2015

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

    курсовая работа [27,9 K], добавлен 23.07.2011

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

    дипломная работа [1,9 M], добавлен 21.06.2014

  • Общее понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов. Основные методы и приемы анализа сложности. Оптимизация, связанная с выбором метода построения алгоритма и с выбором методов представления данных в программе.

    реферат [90,6 K], добавлен 27.11.2012

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

    дипломная работа [979,1 K], добавлен 30.05.2015

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

    контрольная работа [32,8 K], добавлен 20.01.2012

  • Основные аналитические соотношения. Блок схемы и алгоритм решения задачи. Проверка работоспособности алгоритма вручную. Таблица идентификации переменных. Формы входной и выходной печати. Разработка и отладка программы. Инструкция для работы с программой.

    курсовая работа [69,8 K], добавлен 13.02.2012

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

    курсовая работа [1,8 M], добавлен 22.02.2011

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

    курсовая работа [65,3 K], добавлен 16.04.2014

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

    контрольная работа [20,6 K], добавлен 13.09.2009

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

    лабораторная работа [830,3 K], добавлен 28.04.2014

  • Разработка собственного алгоритма сжатия и восстановления данных с использованием возможностей языка C++ в рамках программного продукта "Архиватор". Разработка алгоритма программы, ее первый запуск и тестирование. Проверка работы архивации файлов.

    курсовая работа [325,7 K], добавлен 13.10.2015

  • Сравнительный анализ языков программирования высокого уровня Си и Паскаль. Реализация алгоритма обработки данных. Тестирование и отладка программы или пакета программ. Структура программы на языке Турбо Паскаль. Указатели и векторные типы данных.

    курсовая работа [233,5 K], добавлен 14.12.2012

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

    курсовая работа [1,3 M], добавлен 11.03.2014

  • История создания алгоритма Форда-Фалкерсона, краткое описание его алгоритма, особенности работы, анализ сложности. Создание распараллеленного варианта алгоритма и его краткое описание. Основные характеристики теории графов, специфика, пути и маршруты.

    контрольная работа [246,3 K], добавлен 06.08.2013

  • Основные генетические операторы. Схема функционирования генетического алгоритма. Задачи, решаемые с помощью генетических алгоритмов. Математическая постановка задачи оптимизации. Решение Диофантова уравнения. Программная реализация. Создание пособия.

    курсовая работа [391,4 K], добавлен 20.02.2008

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

    реферат [929,8 K], добавлен 23.09.2013

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

    курсовая работа [1,4 M], добавлен 16.03.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.