Увеличение поисковых способностей генетических алгоритмов с помощью прогнозирования временных рядов

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

Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).



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

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

Для увеличения ПС ГА применяются так называемые адаптивные алгоритмы. Их идея заключается в динамическом изменении различных параметров ГА.К адаптивным ГА также можно отнести так называемые статистические алгоритмы. Идея этих алгоритмов состоит в изучении статистики некоторых параметров ГА. Один из первых статистических алгоритмов — SANUX, который был предложен Янгом в 2002 году. Это бинарный ГА, основанный на предположении о сходимости значений аллелей.
Суть этого предположения проста и интуитивно очевидна: хромосомы сходятся к оптимальному решению на уровне аллелей, то есть каждое значение в хромосоме сходится к какому-то оптимальному варианту.
Я сказал, что предположение интуитивно очевидно, поскольку оно не доказано, но работает.
Кстати, доказанных для ГА практически применимых теорем можно пересчитать по пальцам одной руки, так что если кто-то чувствует в себе силы, то всегда есть шанс вписать себя в историю.

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

Если ряд для аллели является статистически управляемым, то на этом основании несложно предположить о значении аллели в следующей популяции. Если же ряд является неуправляемым, то существует несколько возможностей выбора значения аллели, которые практически не улучшают ПС, поэтому допустимо использовать значения аллелей из шаблонов с достаточно высокой приспособленностью.
При этом, для бинарного ГА достаточно около 15-20 поколений для сбора статистики. В случае же целочисленного ГА, чем больше поколений прошло, тем лучше.

Хочется отметить, что данный способ построения хромосом имеет смысл применять на задачах больших размерностей.

Так же с помощью анализа временных рядов аллелей можно динамически управлять операторами скрещивания (кроссинговер) и мутации, а так же изменять размер популяции. При этом достигается значительное увеличение ПС ГА.
  • +23
  • 3,7k
  • 4
Поделиться публикацией

Комментарии 4

    0
    Итак, Генетические алгоритмы оптимизируют временные ряды, которые оптимизируют генетические алгоритм. Но не будет ли результатом такой «рекурсии», то что мы потеряем приспособляемость генетических алгоритмов и сведем их к рядам.
    Это как нейросети и стат. анализ.
      +1
      Я понял иначе… Наблюдаем за хромосомами в течение некоторого количества поколений -> накапливаем статистику для каждого гена (статистика аллели?) -> Когда удостоверимся, что статистика накоплена, делаем вывод о том, какое значение должен иметь каждый конкретный ген. Правильно?
      Я только не понял, что означает «статистически (не)управляемые».
        0
        1)Да, абсолютно правильно.
        2)Процесс находится в статистически управляемом состоянии, если изменчивость вызвана только случайными причинами. При этом, поскольку мы предполагаем, что нам известны все способы воздействия на параметры алгоритма, то статистическую управляемость можно понимать, как статистическую стабильность. Подробнее можно почитать тут.
        0
        Правомерное замечание. Но ГА, которым мы решаем задачу, и ГА, которым можно прогнозировать временной ряд — это два различных алгоритма. К тому же применять ГА для прогнозирования временных рядов для самих же ГА — не самая лучшая идея, поскольку с помощью тех же статистических карт это можно сделать гораздо лучше.
        ГА — это не универсальный тип алгоритмов. У них есть определённы области применения. И это нужно учитывать, когда при решении какой-то задачи взгляд падает на ГА (этот взгляд может оказаться далеко не оптимальным).

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

      Самое читаемое