§ 2. Обучающийся генетический алгоритм прогнозирования LGAP [80]

В алгоритме LGAP выделяется четыре этапа его работы: 1) формирование базовых элементов (базовых штаммов); 2) отбор компетентных штаммов; 3) выработка частных вариантов прогноза; 4) получение окончательного прогноза.

Пояснять алгоритм будем с помощью рис. 26.

2.1. Формирование базовых штаммов.

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

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

Рис. 26

Нетрудно видеть, что испытание всех базовых штаммов может превысить возможности компьютера рядового пользователя. Для сокращения перебора используется комбинация метода последовательного наращивания числа элементов (алгоритм Add, описанный в главе 6) с методами генетического программирования [41,156].

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

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

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

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