На написание статьи, подтолкнула публикация Прогнозирование временных рядов.
Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).
Под поисковыми способностями генетического алгоритма будем понимать его способность к созданию хромосомы, соответствующей произвольной точке пространства поиска.
Характеристика ГА, которая описывает ПС, не выражается численно. На ПС ГА влияют различные факторы, например, численность популяции, выбранные операторы скрещивания и мутации, а так же другие факторы. При этом правомерно предположить, что чем выше поисковые способности ГА, тем меньшая популяция требуется, а уменьшение популяции влечёт уменьшение количества вычислений функции приспособленности.
При построении ГА мало кто обращает достаточно внимания на то, каким образом будут создаваться хромосомы для нового поколения, хотя при удачном выборе алгоритма создания новых хромосом можно значительно увеличить ПС.
Для увеличения ПС ГА применяются так называемые адаптивные алгоритмы. Их идея заключается в динамическом изменении различных параметров ГА.К адаптивным ГА также можно отнести так называемые статистические алгоритмы. Идея этих алгоритмов состоит в изучении статистики некоторых параметров ГА. Один из первых статистических алгоритмов — SANUX, который был предложен Янгом в 2002 году. Это бинарный ГА, основанный на предположении о сходимости значений аллелей.
Суть этого предположения проста и интуитивно очевидна: хромосомы сходятся к оптимальному решению на уровне аллелей, то есть каждое значение в хромосоме сходится к какому-то оптимальному варианту.
Я сказал, что предположение интуитивно очевидно, поскольку оно не доказано, но работает.
Кстати, доказанных для ГА практически применимых теорем можно пересчитать по пальцам одной руки, так что если кто-то чувствует в себе силы, то всегда есть шанс вписать себя в историю.
Теперь применим данную гипотезу к построению новых хромосом.
Для каждой аллели в хромосоме будем вести временной ряд. Далее каким-то образом прогнозируется следующее значение данного ряда, и оно выбирается в качестве аллели хромосомы. Помимо алгоритмов, предложенных в статье, неплохо себя зарекомендовал следующий алгоритм:
Если ряд для аллели является статистически управляемым, то на этом основании несложно предположить о значении аллели в следующей популяции. Если же ряд является неуправляемым, то существует несколько возможностей выбора значения аллели, которые практически не улучшают ПС, поэтому допустимо использовать значения аллелей из шаблонов с достаточно высокой приспособленностью.
При этом, для бинарного ГА достаточно около 15-20 поколений для сбора статистики. В случае же целочисленного ГА, чем больше поколений прошло, тем лучше.
Хочется отметить, что данный способ построения хромосом имеет смысл применять на задачах больших размерностей.
Так же с помощью анализа временных рядов аллелей можно динамически управлять операторами скрещивания (кроссинговер) и мутации, а так же изменять размер популяции. При этом достигается значительное увеличение ПС ГА.
Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).
Под поисковыми способностями генетического алгоритма будем понимать его способность к созданию хромосомы, соответствующей произвольной точке пространства поиска.
Характеристика ГА, которая описывает ПС, не выражается численно. На ПС ГА влияют различные факторы, например, численность популяции, выбранные операторы скрещивания и мутации, а так же другие факторы. При этом правомерно предположить, что чем выше поисковые способности ГА, тем меньшая популяция требуется, а уменьшение популяции влечёт уменьшение количества вычислений функции приспособленности.
При построении ГА мало кто обращает достаточно внимания на то, каким образом будут создаваться хромосомы для нового поколения, хотя при удачном выборе алгоритма создания новых хромосом можно значительно увеличить ПС.
Для увеличения ПС ГА применяются так называемые адаптивные алгоритмы. Их идея заключается в динамическом изменении различных параметров ГА.К адаптивным ГА также можно отнести так называемые статистические алгоритмы. Идея этих алгоритмов состоит в изучении статистики некоторых параметров ГА. Один из первых статистических алгоритмов — SANUX, который был предложен Янгом в 2002 году. Это бинарный ГА, основанный на предположении о сходимости значений аллелей.
Суть этого предположения проста и интуитивно очевидна: хромосомы сходятся к оптимальному решению на уровне аллелей, то есть каждое значение в хромосоме сходится к какому-то оптимальному варианту.
Я сказал, что предположение интуитивно очевидно, поскольку оно не доказано, но работает.
Кстати, доказанных для ГА практически применимых теорем можно пересчитать по пальцам одной руки, так что если кто-то чувствует в себе силы, то всегда есть шанс вписать себя в историю.
Теперь применим данную гипотезу к построению новых хромосом.
Для каждой аллели в хромосоме будем вести временной ряд. Далее каким-то образом прогнозируется следующее значение данного ряда, и оно выбирается в качестве аллели хромосомы. Помимо алгоритмов, предложенных в статье, неплохо себя зарекомендовал следующий алгоритм:
Если ряд для аллели является статистически управляемым, то на этом основании несложно предположить о значении аллели в следующей популяции. Если же ряд является неуправляемым, то существует несколько возможностей выбора значения аллели, которые практически не улучшают ПС, поэтому допустимо использовать значения аллелей из шаблонов с достаточно высокой приспособленностью.
При этом, для бинарного ГА достаточно около 15-20 поколений для сбора статистики. В случае же целочисленного ГА, чем больше поколений прошло, тем лучше.
Хочется отметить, что данный способ построения хромосом имеет смысл применять на задачах больших размерностей.
Так же с помощью анализа временных рядов аллелей можно динамически управлять операторами скрещивания (кроссинговер) и мутации, а так же изменять размер популяции. При этом достигается значительное увеличение ПС ГА.
