Определение 2

Охват схемы S, называемый также длиной схемы и обозначаемый d(S) – это расстояние между первым и последним постоянным символом (т.е. разность между правой и левой крайними позициями, содержащими постоянные символы). Например,

d (10*1) = 4-1 = 3 d (*01*10) = 6-2 = 4

d (*0*1*) = 5-3 = 2 d (*101**) = 4-2 = 2

Охват схемы d(S) – это целое число из интервала [0, L -1]. Отметим, что охват схемы с постоянными символами на первой и последней позиции равен L -1 (как в первом из приведенных примеров). Охват схемы с единственной постоянной позицией равен нулю, в частности, d (**1*) = 0. Охват характеризует содержательность информации, заключенной в схеме.

Перейдем к рассуждениям о влиянии операции скрещивания на обработку схем в генетическом алгоритме. Для анализа влияния данной операции на родительский пул М (k) рассмотрим некоторую хромосому из множества М (k)Ç S, т.е. хромосому из родительского пула, соответствующую схеме S. Вероятность того, что эта хромосома будет отобрана для скрещивания, равна р_с. Если ни один из потомков этой хромосомы не будет принадлежать к схеме S, то это означает, что точка скрещивания должна находиться между первым и последним постоянным символом данной схемы. Вероятность этого равна d (S)/(L -1). Из этого можно сделать следующие выводы.

Вывод 2 (влияние скрещивания)

Для некоторой хромосомы из М (k)Ç S вероятность того, что она будет отобрана для скрещивания и ни один из ее потомков не будет принадлежать к схеме S, ограничена сверху величиной

.

Эта величина называется вероятностью уничтожения схемы S.