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

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

Вывод 4.1

Ожидаемое значение fo(S, /с), т.е. ожидаемое значение количе­ства хромосом родительского пула М(к), соответствующих схеме S, определяется выражением

F(/c)

Из этого следует, что если схема S содержит хромосомы со значением функции приспособленности, превышающим среднее зна­чение (т.е. приспособленность схемы S на /с-й итерации оказывается большей, чем среднее значение функции приспособленности хромо­сом из популяции Р(/с), и поэтому F(S, к) I F(k) > 1), то ожидаемое ко­личество хромосом из родительского пула М(к), соответствующих схеме S, будет больше количества хромосом из популяции Р(/с), соот­ветствующих схеме S. Поэтому можно утверждать, что селекция вы­зывает распространение схем с приспособленностью «лучше сред­ней» и исчезновение схем с «худшей» приспособленностью.

Прежде чем приступить к анализу влияния генетических опера­торов скрещивания и мутации на хромосомы из родительского пула, определим необходимые для дальнейших рассуждений понятия по­рядка и охвата схемы. Пусть L обозначает длину хромосом, соответ­ствующих схеме S.

а 4. Генетические алгоритмы

Порядок (order) схемы S, иначе называемый счетностью схемы и обозначаемый o(S) - это количество постоянных позиций в схеме, т.е. нулей и единиц в случае алфавита {0, 1, *}. Например, о(10*1) = 3 о(*01*10) = 4 о(**0*1*) = 2 о(*101**) = 3

Порядок схемы o(S) равен длине L за вычетом количества сим­волов *, что легко проверить на представленных примерах (для L = 4 с одним символом * и для L = 6 с двумя, четырьмя и тремя символа­ми *). Легко заметить, что порядок схемы, состоящей исключительно из символов *, равен нулю, т.е. о(****) = 0, а порядок схемы без едино­го символа * равен L; например, о(10011010) = 8. Порядок схемы o(S) - это всегда целое число из интервала [О, L].

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

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

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

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

Перейдем к рассуждениям о влиянии операции скрещивания на обработку схем в генетическом алгоритме. Прежде всего отметим, что одни схемы оказываются более подверженными уничтожению в процессе скрещивания, чем другие. Например, рассмотрим схемы S-i = 1****0* и S₂ = **01***, а также хромосому ch = [1001101], соответ­ствующую обеим схемам. Видно, что схема S₂ имеет больше шансов «пережить» операцию скрещивания, чем схема S-,, которая больше подвержена «расщеплению» в точках скрещивания 1, 2, 3, 4 и 5. Схе­му S₂ можно разделить только при выборе точки скрещивания, рав­ной 3. Обратим внимание на охват обеих схем, который - это очевид­но оказывается существенным в процессе скрещивания.

В ходе анализа влияния операции скрещивания на роди­тельский пул М(к) рассмотрим некоторую хромосому иэ множества М(к) п S, т.е. хромосому из родительского пула, соответствующую схеме S. Вероятность того, что эта хромосома будет отобрана для скрещивания, равна р_с. Если ни один из потомков этой хромосомы не будет принадлежать к схеме S, то это означает, что точка скрещива­ния должна находиться между первым и последним постоянным сим-

4.7. Основная теорема о генетических алгоритмах 149

волом данной схемы. Вероятность этого равна d(S)l(L - 1). Из это можно сделать следующие выводы:

Дата добавления: 2015-06-04