Генетический алгоритм на основе оценки временных рядов

В классической реализации ГА реализуется действие естественного отбора (ЕО) на уровне индивидов. В нишевых алгоритмах, кроме того, учитывается и ЕО на уровне ниш. Однако достаточно распространенная в микробиологии точка зрения на ЕО, как на отбор генов [12] в ГА распространение не получила.

Будем считать конкуренцию между генами за попадание в следующее поколение — требуемой основой для отбора на уровне генов. Мерой оценки генов будем считать стабильность значения гена в процессе смены поколений на основе статистически накапливаемых данных.

Предлагаемый в данной работе ГА на основе статистики относится к классу нечетких ГА с вещественным кодированием. В отличие от SANUX в данном алгоритме сбор статистики ведется по аллелям лучшего представителя популяции, а не по всей популяции целиком, что повышает производительность алгоритма. Необходимо сформулировать нечеткие правила управления, которые будут задавать параметры операторов рекомбинации:

П1: Если история гена нестабильная То вероятность его наследования невелика.

П2: Если приспособленность индивида хорошая То вероятность его наследования достаточно велика

Второе нечеткое правило введено с целью предотвратить попадание в локальный оптимум.

Стабильность истории гена будем определять по контрольным картам Шухарта (ГОСТ Р 50 779.40−96), которые предназначены для статистического анализа и управления качеством технологических процессов.

Карты Шухарта используются для определения, находится ли процесс в статистически управляемом состоянии. Для достаточно надежного расчета требуется не менее 20−30 параметров — членов временного ряда исследуемого процесса, которые откладываются по оси Y. Практическое использование карт Шухарта основывается на утверждении, что чем статистически управляемей процесс, тем выше его качество и тем меньше ошибок в течение процесса.

Карты Шухарта составляются следующим образом:

• 1. Производится временная выборка исследуемого параметра процесса.
• 2. Составляется 2-мерная матрица данных размерностью, где N-длина временного ряда. Таким образом, первая строка матрицы — временной вектор параметра, вторая строка — время.
• 3. Строится тренд с использованием какого-либо из методов аппроксимации (например, с использованием метода наименьших квадратов). Если же нет необходимости учитывать тренд процесса, то строится медиана как

.

где N — длина временного ряда.

4. Рассчитывается среднеквадратичное отклонение от среднего значения (либо тренда), как.

.

где N — длина временного ряда.

5. Если полосу допуска не попадает более чем 0.7% членов временного ряда, то процесс считается статистически неуправляемым. И, следовательно, требуется внешнее управление процессом для повышения его качества. Для более жесткого управления качеством процесса используется следующее соотношение: если полосу допуска не попадает более, чем 5.54% членов временного ряда, то процесс считается статистически неуправляемым.

Стандартное использование карт Шухарта предполагает четкое управление процессом. В предлагаемом алгоритме используется следующее четкое правило управления:

l Если временной ряд гена является статистически неуправляемым, То скачкообразно повысить коэффициент мутации до значения M*K с последующим динамическим снижением до прежнего уровня:

;

l Иначе динамически понижать коэффициент мутации до значения.

.

где K — эмпирически выбрано равным 2.0, Nдлина временного ряда, — значение коэффициента мутации в момент времени t.

Управление коэффициентом мутации проводится раз в N поколений.

Также можно предложить следующее четкое правило управления ГА на основе карт Шухарта:

l Если временной ряд приспособленности лучшего представителя популяции является статистически неуправляемым, То скачкообразно повысить коэффициент размер популяции до значения P*K с последующим динамическим снижением до прежнего уровня:

;

l Иначе динамически понижать коэффициент мутации до значения.

.

где K — эмпирически выбрано равным 2.0, Nдлина временного ряда, — размер популяции в момент времени t.

Управление размером популяции проводится раз в N поколений.

Заметим, однако, что варьирование параметра K может оказывать значительное влияние на сходимость алгоритма. В связи с этим предлагается использовать нечеткую меру оценки качества исследуемого процесса.

Таким образом, правила управления преобразуются к виду:

• l Если временной ряд гена является значительно статистически неуправляемым, То скачкообразно повысить коэффициент мутации на значительно большую величину с последующим динамически плавным снижением до прежнего уровня в течение N поколений;
• l Если временной ряд гена является полностью статистически управляемым, То динамически плавно понижать коэффициент мутации до небольшого значения в течение N поколений.

Где курсивом выделены нечеткие переменные, полужирным шрифтом выделены функциональные части правила.

Управление коэффициентом мутации проводится раз в N поколений.

Для управления же размером популяции можно предложить следующие нечеткие правила управления ГА на основе карт Шухарта:

• l Если временной ряд приспособленности лучшего представителя популяции является значительно статистически неуправляемым, То скачкообразно повысить размер популяции на значительно большую величину с последующим динамически плавным снижением до прежнего уровня в течение N поколений;
• l Если временной ряд приспособленности лучшего представителя популяции является полностью статистически управляемым, То динамически плавно понижать размер популяции до небольшого значения в течение N поколений.

Управление размером популяции проводится раз в N поколений.