Differential Evolution: генетический алгоритм оптимизации функции

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

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

    Под катом приводится краткое описание одного из самых известных генетических алгоритмов вещественной оптимизации — алгоритма дифференциальной эволюции (Differential Evolution, DE). Для сложных задач оптимизации функции n переменных этот алгоритм обладает настолько хорошими свойствами, что зачастую может рассматриваться как готовый «строительный блок» при решении многих задач идентификации и распознавания образов.



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

    Генерация начальной популяции


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

    Воспроизводство потомков


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



    Здесь A и B — случайно выбранные представители популяции, отличные от X и C. Параметр F определяет т.н. силу мутации — амплитуду возмущений, вносимых в вектор внешним шумом. Следует особо отметить, что в качестве шума, искажающего «генофонд» особи C используется не внешний источник энтропии, а внутренний — разность между случайно выбранными представителями популяции. Ниже мы остановимся на этой особенности подробнее.

    Скрещивание производится следующим образом. Задается вероятность P, с которой потомок T наследует очередной (искаженный мутацией) генетический признак от родителя C. Соответствующий признак от родителя X наследуется с вероятностью 1 — P. Фактически n раз разыгрывается бинарная случайная величина с математическим ожиданием P, и для единичных ее значений производится наследование (перенос) искаженного генетического признака от родителя C (т.е. соответствующей координаты вектора C'), а для нулевых значений — наследование генетического признака от родителя X. В результате формируется вектор-потомок T.

    Отбор


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

    Обсуждение особенностей алгоритма DE


    В целом алгоритм DE представляет собой одну из возможных «непрерывных» модификаций стандартного генетического алгоритма. В то же время этот алгоритм имеет одну существенную особенность, во многом определяющую его свойства. В алгоритме DE в качестве источника шума используется не внешний генератор случайных чисел, а «внутренний», реализованный как разность между случайно выбранными векторами текущей популяции. Напомним, что в качестве исходной популяции используется совокупность случайных точек, выбранных из некоторого генерального распределения. На каждом шаге популяция преобразуется по некоторым правилам и в результате на следующем шаге в качестве источника шума снова используется совокупность случайных точек, но этим точкам соответствует уже некий новый закон распределения. Эксперименты показывают, что в целом эволюция популяции соответствует динамике «роя мошек» (т.е. случайного облака точек), движущегося как целое вдоль рельефа оптимизируемой функции, повторяя его характерные особенности. В случае попадания в овраг «облако» принимает форму этого оврага и распределение точек становится таким, что математическое ожидание разности двух случайных векторов оказывается направленным вдоль длинной стороны оврага. Это обеспечивает быстрое движение вдоль узких вытянутых оврагов, тогда как для градиентных методов в аналогичных условиях характерно колебательная динамика «от стенки к стенке». Приведенные эвристические соображения иллюстрируют наиболее важную и привлекательную особенность алгоритма DE — способность динамически моделировать особенности рельефа оптимизируемой функции, подстраивая под них распределение «встроенного» источника шума. Именно этим объясняется замечательная способность алгоритма быстро проходить сложные овраги, обеспечивая эффективность даже в случае сложного рельефа.

    Выбор параметров


    Для размера популяции N обычно рекомендуется значение Q * n, где 5 <= Q <= 10.

    Для силы мутации F разумные значения выбираются из отрезка [0.4, 1.0], причем хорошим начальным значением будет 0.5, но при быстром вырождении популяции вдали от решения следует увеличить параметр F.

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

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

    Численный пример


    Особенности метода DE хорошо иллюстрируются при его запуске на стандартной тестовой функции Розенброка вида



    Эта функция имеет очевидный минимум в точке x = y = 1, который лежит на дне длинного извилистого оврага с крутыми стенками и очень пологим дном.

    При запуске с равномерным начальным распределением 200 точек в квадрате [0, 2] x [0, 2] после 15 шагов получаем вот такое распределение популяции:



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

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



    Ссылки


    • Дамашняя страничка алгоритма содержит много реализаций и примеров использования в разных областях.
    • Статья в Dr. Dobb's Journal содержит очень простую и понятную реализацию на языке C, которую можно взять за основу при использовании алгоритма DE в своих проектах.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 16
    • 0
      Очень интересно, но хотелось бы больше иллюстраций. Рой мошек в овраге зацепил, хочется визуализации… Сравнить ваш метод и обычный и показать как мошки распределяются…
      • 0
        Визуализацию сейчас попробую собрать. Но алгоритм конечно не мой, авторы — Rainer Storn и Ken Price.
        • +6
          Добавил в пост простую анимацию. Это то, что Вы имели в виду?
        • +2
          Куда интереснее как себя поведёт эта штука когда есть много локальных минимумов.
          Когда баловался подобными алгоритмами — частенько популяция вырождалась, приходилось идти на разные ухищрения, чтоб заставить искать глобальный минимум. Теми или иными способами поддерживал разнообразие популяции, а не просто уточнение на каждом шаге.

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

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

            Кстати, DE на самом деле при небольшой силе мутации близок к градиентным методам, поскольку за счет подстройки облака точек к структуре функции он фактически строит аппроксимацию градиента (т.н. «стохастический градиент»). Ну и еще сильно помогает возможность гибко настраивать параметры, в зависимости от задачи, либо усиливая градиентные свойства (и увеличивая скорость сходимости), либо усиливая стохастические свойства (и увеличивая устойчивость к мелким локлаьным минимумам за счет скорости содимости).
          • 0
            Лично мне было бы интересно узнать сравнение данного алгоритма (да и генетических вообще) и, скажем, симплекс-метода. Пусть, для функции 5-10 аргументов с несколькими минимума. В случае использования однопоточного CPU; в случае многопоточного GPU.
            • +1
              Если под симплекс-методом Вы понимаете то, что обычно понимают под этим термином, то он применяется совсем в другой области (линейное программирование). В этой области у него нет конкурентов (в теории — кроме метода элипсоидов, но там громадная константа).

              Если же Вы имели в виду метод симплекса (aka «метод отражений симплекса», aka «метод летающего симплекса»), то этот метод проигравает DE сразу и без вариантов. Отражения симплекса — простейший метод, хуже него только покоординатный спуск.
              • 0
                errata: «метод летающего симплекса» — > «метод шагающего симплекса»
                • 0
                  Я имел в виду тот, который Нелдера-Мида. А какой выигрыш в скорости можно ожидать? Если грубо — это разы или прямо порядки?
                  • +1
                    Ну, тут тоже несколько разные области применения. Выигрыш в скорости для DE будет проявляться на сложных задачах, для которых симплекс будет быстро уменьшаться в размере и двигаться к минимуму очень медленно. В этом случае преимущество может быть и на порядки. Если же оба метода одинаково легко находят минимум, то метод симплексов может оказаться и быстрее, просто из-за своей логической простоты. Ну и будет еще целый класс задач, для которых DE будет давать правильное решение, а симплекс будет застревать в локальном минимуме.

                    Прямым конкурентом метода симплексов является метод Хука-Дживса, который, кстати, работает несколько быстрее него. Ну и Х-Д лучше проходит линии разрыва производной, которые часто появляются при добавлении штрафных функций. Но застравают в локальных минимумах они одинаково часто.
                    • 0
                      Вы несколько расширили мои представления. Спасибо! :)
              • 0
                Во всю использую этот алгоритм для настройки констант в эвристических алгоритмах. При достаточном терпении почти всегда сходится к значениям, позволяющим достичь результата лучше, чем подбор констант в ручную.

                Основное преимущество алгоритма — это хорошая сходимость в практически любых условиях, будь функция практически константная или с кучей локальных минимумов, или ещё с какой «бякой». То есть полная независимость от какого-то дополнительного знания про оптимизируемую функцию.
                • 0
                  Тоже хорошее применение. Я его всегда имел в виду, но в моих проектах каждый раз получалось, что придумать адекватную автоматически вычисляемую функцию качества решения не проще, чем саму эвристику.
                • 0
                  Интересно, будет ли этот метод работать на задаче совмещения изображений (например, создание панорам)
                  • 0
                    В принципе должен. Задача совмещения дает (очень) многоэкстремальную функцию ошибки, но главный минимум там получается очень глубокий. Мы как-то делали софт для совмещения последовательных кадров аэрофотосъемки (там нахлест почти 50% размера кадра, использовалось обычное корреляционное совмещение в спектральной области). Потом заказчик попробовал совместить сканы листов генштабовских карт (там нахлест уже маленький, процентов 10-15) и оказалось, что точное совмещение (неправильное) линий сетки дает гораздо меньшую ошибку, чем совмещение самого изображения (хитрость состояла в том, что наша оценка кросскорреляционной функции становилась все менее точной при приближении к краю изображения).
                    • 0
                      Попробую применить к 3D-облакам… интересно, что получится :)

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