Применение эволюционного программирования в задачах прогнозирования и управления
Автор: Скобцов Ю.А.
Источник: Ю.О.Скобцов Основи еволюційних обчислень
.– Навчальний посібник.–Донецьк: ДонНТУ,2008.–326с. Мова–російська. стр. 287–291
Применение эволюционного программирования в прогнозировании
Как уже отмечалось, в ранних работах ЭВ использовалось, в основном, при решении задач прогнозирования временных рядов, где целью эволюции популяции конечных автоматов является построение автомата, который способен предсказывать значение следующего входного сигнала. Рассмотрим суть задачи прогнозирования на примере автомата, представленного на рис. 10.3
Рис. 10.3 – Пример автомата для задачи прогнозирования
Задача заключается в определении следующего символа входной последовательности. Допустим приведенный автомат рис.10.3 находится в начальном состоянии С, и на его вход подается последовательность X=011101. В этом случае согласно графу переходов–выходов автомат 288 выдает выходную последовательность Y=110111. Автомат правильно предсказывает если его выходной сигнал zi равен следующему входному сигналу xi+1. В случае равенства zi= xi+1 значение фитнесс–функции увеличивается на 1. Для нашего примера автомат правильно предсказывает 3 из 5 символов входной последовательности. Иногда в фитнесс–функцию вводится штраф за превышение заданного числа состояний автомата.
В качестве примера рассмотрим предсказание следующего символа периодической последовательности, один период которой представляется (101110011101)* [53]. Здесь входной и выходной алфавит конечных автоматов равен {0,1}. В качестве обучающего множества используется множество подпоследовательностей, содержащих первые 20 символов указанной циклической последовательности. Популяция случайно синтезированных конечных автоматов проходит пять поколений эволюции. В качестве фитнесс–функции в данном случае используется средняя абсолютная ошибка (число неправильно предсказанных символов). После короткого периода эволюции в популяции определялась лучшая особь (с минимальной ошибкой), которая далее использовалась для предсказания следующего символа входной последовательности. Такая процедура повторялась 300 раз, и процесс эволюции в итоге состоял из 1500 поколений. Процедура ЭВ оценивалась при каждом прогнозе с использованием совокупной доли корректных прогнозов.
Эксперименты по прогнозированию выполнялись с популяциями, содержащими m={3,5,10,0,100} особей. Число мутаций выбиралось случайно из Mi={1,2,3}. Было выполнено 30 попыток для каждой комбинации m и Mi. Число состояний автоматов варьировалось от 1 до 10. Во всех экспериментах максимальное число состояний ограничивалось сверху 10.
Согласно [53] получены следующие результаты экспериментов для задачи прогнозирования, которые представлены на рис. 10.4. Здесь показано, как изменяется доля правильных прогнозов для лучшего автомата в популяции, усредненная по 30 попыткам для популяций с числом особей 3,5,10,50 и 100 и выполнением от 1 до 3 операторов мутации. Из графика видно, что при первом прогнозе число правильных прогнозов примерно равно 80% (после 30 попыток первого эксперимента). Далее следует небольшой спад, и затем постепенное повышение доли правильных прогнозов примерно до 90%.
Рис. 10.4 – Изменение доли правильных прогнозов для различных мощностей популяций
Применение эволюционного программирования в задачах управления
Кроме задач прогнозирования ЭВ используется при решении задач управления [54]. В этом случае целью является построение в процессе эволюции автомата, который выдает на выход некоторое управляющее воздействие. В дальнейших экспериментах, для определенности, автомат должен выдать выходной сигнал, равный 5. Здесь особи популяции представляют модели целевого устройства управления, которые видоизменяются для того, чтобы получить необходимое выходное управляющее воздействие. Пусть для простоты алфавит автоматов состоит из целых чисел {1,2,…,9}. В первой серии экспериментов [54] в качестве целевого устройства использовался циклический автомат с 3–мя состояниями, представленный на рис. 10.5. Во второй серии экспериментов применялись случайные автоматы с N состояниями.
Рис. 10.5 – Циклический автомат с 3 состояниями
Как видно из рис. 10.5, в качестве начального используется первое состояние автомата. Данный автомат, находясь в 1–м состоянии при подаче входного сигнала i={1,…,8} на выходе генерирует значение i+1 (по модулю 10). При подаче на вход 9 автомат выдает на выход 0 и переходит в следующее состояние n+1. Аналогично во втором состоянии входные символы 0,1,2,…,8 генерируют выходы 2,3,…,9,0 соответственно. И наконец, в последнем третьем состоянии входы 0,1,2,…,8 производят выходы 3,4,….0,1. Аналогично может быть построен подобный циклический автомат для произвольного числа состояний. Отметим, что этот автомат полностью контролируем – то есть для каждого состояния существует входной сигнал, который выдает необходимое управляющее воздействие 5. С другой стороны, случайный автомат с N состояниями может быть либо частично контролируемым (для некоторых состояний существует входной сигнал, выдающий управляющее воздействие), либо неконтролируемым (ни для одного состояния не существует входного сигнала, которые генерирует управляющее воздействие).