3.3. Теоремы эволюционного моделирования

В ЭМ важным понятием является «элитизм». Он определен как операция, в которой хромосома с наилучшей ЦФ сразу копируется в новую популяцию. Это позволяет не терять лучшие решения в процессе эволюции. С точки зрения исследователей, одним из основных вопросов ГА является вопрос о подобии особей в популяции и, главным образом, о связи подобия с эффективностью.

Д. Холланд для решения этих вопросов в ГА предложил использовать алфавит, состоящий из трех символов: {0,1, *}. Значок * определяется так: «не имеет значения» и вместо него может быть использован 0 или 1. В [88] введено понятие «шаблон» (схема) в ГА, это шаблон подобия, описывающий подмножество особей (строк) в популяции с совпадением в определенных строковых позициях. Шаблон в ГА — это подмножество хромосом, которые моіут быть получены из одной записи.

Например, шаблон (*0001) будет состоять из двух хромосом: (00001) и (10001). А шаблон (*0000) соответствует двум хромосомам вида {(10000), (00000)}. Другой пример: шаблон (*111*) описывает множество хромосом с 4 членами {(01110), (11110), (01111), (11111)}. Шаблон (0*1**), будет уже иметь 8 хромосом длины 5, т. е. в общем случае в хромосоме с L = 5 можно иметь З5 = 243 шаблона, включающих изоморфные схемы. Очевидно, что для хромосомы L = 5 можно иметь 25 = 32 различных альтернативных шаблонов. Это следует из того, что схема (**) имеет в общем З2 = 9 хромосом, т. е. {(**), (*1), (*0), (1*), (0*), (00), (01), (10), (11)}. Из этих 9 хромосом выбираются 4 неизоморфные: {(00), (01), (10), (П)} [89].

В ПГА основная идея — это объединить две хромосомы с ЦФ выше средней, а именно, найти шаблоны типа (11***) и (***111) при решении

задач максимизации ЦФ. Тогда, применяя ОК к данным шаблонам, можно получить хромосому (11111) с наилучшим значением ЦФ при поиске максимума.

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

Рассмотрим, например, хромосому длины L = 6, (111111). Она имеет

26 шаблона, потому что каждая позиция может быть 1 или *. В общем случае считают, что хромосома содержит 2Ь шаблона. Тогда популяция размера Np будет содержать от 2Ь до Np 2Ь шаблонов. Шаблоны определенной короткой длины называют «строительными блоками» [89]. Размер строительных блоков очень важен для быстроты и качества нахождения результата. Рассмотрим примеры строительных блоков для разных шаблонов. Например, в шаблоне (* * * 1) строительным блоком будет элемент 1. В шаблоне (10* * *) строительным блоком будет составной элемент 10. Заметим, что вид строительного блока должен выбираться, исходя из знаний о решаемой задаче, чтобы далее из них как из «кирпичиков» собирать «здание», т. е. решение с лучшей целевой функцией. Причем при реализации ГА должно выполняться условие, чтобы строительные блоки разрывались только в крайних случаях, указанных ЛПР.

ГА в зависимости от размера популяции разделяют на:

•    стационарного состояния;

•    поколенческие.

В стационарных ГА размер популяции является входным постоянным параметром, задаваемым ЛПР. В поколенческих ГА разрешается увеличивать или уменьшать размер популяции в каждой последующей генерации. Следует отметить, что речь в основном идет о появлении Np + N\ потомков (Ni >1), прежде чем начинает реализовываться оператор отбора, устраняющий Ni хромосом с меньшей ЦФ. Вопросы удаления «лишних» хромосом как в стационарных, так и в поколенческих ГА, основаны на нескольких эвристиках:

•    случайное равновероятное удаление хромосом;

•    удаление Ni хромосом, имеющих худшее значение ЦФ;

•    удаление хромосом на основе обратно пропорционального значения ЦФ;

•    удаление хромосом на основе заданной турнирной стратегии.

Можно предложить еще ряд эвристик удаления, но в [91] отмечено,

что удаление худших хромосом может привести к преждевременной утрате разнообразия и, следовательно, к попаданию ЦФ в локальный оптимум. Оставление в популяции большого числа хромосом с «плохой» ЦФ приведет к слепому поиску.

Выделяют три особенности алгоритма эволюции:

•    каждая новая популяция состоит только из «жизнеспособных» хромосом;

•    каждая новая популяция «лучше» (в смысле ЦФ) предыдущей;

•    в процессе эволюции последующая популяция зависит только от предыдущей.

Для количественной оценки шаблонов в ГА введены две характеристики [88, 89]: порядок шаблона — о (Н); определенная длина шаблона — S (Н).

Порядок шаблона — число закрепленных позиций (в двоичном алфавите это число единиц и нулей, представленных в шаблоне). Например, для шаблона Я = (о*****) порядок шаблона о (Я) = 1.

Определенная длина шаблона — это расстояние между первой и последней позициями нулей и единиц. Например, для схемы Н = (011*1**), получаем S (Н) = 5 — 1 = 4, а для схемы Н = (0******) получаем S (Н) = = 1 — 1 = 0.

При выполнении оператора рекомбинации хромосомы копируются пропорционально значению их ЦФ или, более точно, хромосома і получает выбор с вероятностью Р^(ОР), определяемой выражением:

Пусть имеется некоторый шаблон Н, который присутствует в популяции Р1 (это популяция Р после реализации t генераций алгоритма), тогда обозначим т(Н, і) число хромосом популяции Р1, которые являются элементами шаблона Н. После получения набора непересекающихся популяций размера Np с перемещением части хромосом из популяции Р1 (здесь t означает номер поколения или условный параметр времени) предполагается получить т(Н, t + 1) представителей схемы Н в генерации популяции Pt+1. Тогда выражение т(Н, t + 1) определится по формуле:

где f(H) — средняя ЦФ хромосом, представленных схемой Н в генерации t.

Если обозначить среднюю ЦФ всей популяции как

то

Из полученного выражения видно, что ЦФ определенного шаблона изменяется как отношение средней ЦФ шаблона к средней ЦФ популяции. Пусть ЦФ шаблона остается выше среднего значения ЦФ шаблона на величину с х / (ж), где с > 0 — константа. Тогда имеем:

Начиная с t = 0 и считая с > 0 константой получаем уравнение:

Данное выражение показывает, что с течением времени число хороших хромосом популяции экспоненциально растет, а число хромосом, имеющих ЦФ ниже средней, в популяции экспоненциально уменьшается.

Правило репродукции Д. Холланда запишется так: шаблон с ЦФ выше среднего значения существует и копируется в следующую генерацию, а шаблон с ЦФ ниже среднего — устраняется [88]. Если хромосомы из предыдущей популяции копируются в новую популяцию без обмена генами, то поисковое пространство не увеличивается и процесс затухает. Поэтому во всех ГА кроме оператора рекомбинации используются различные генетические операторы, такие как кроссинговер, мутация и другие. Они создают новые хромосомы и увеличивают или уменьшают количество шаблонов в популяции.

Нижняя граница вероятности выживания шаблона после применения ОК может быть приближенно определена для любой популяции. Для крос- синшвера внутри строки (хромосомы) доступно (L — 1) точек. Так как шаблон в ГА выживает, когда точка ОК попадает вне «определенной длины», то вероятность выживания для простого ОК записывается так:

где L — длина хромосомы, т. е. суммарная длина, входящих в нее генов.

Например, рассмотрим хромосому Р = (01111000) и два шаблона Яі = = (**і***о*) и Я2 = (***11***). Шаблон Hi имеет определенную длину S (Hi) = 7 — 3 = 4, и если точка ОК выбирается равновероятно среди 8 — 1 = 7 мест, то вероятность разрушения шаблона равна 4/7 или он выживает с вероятностью 3/7. Аналогично, шаблон Я2 имеет определенную длину S (Я2) = 5 — 4 = 1 и разрушается с вероятностью 1/7, а выживает с вероятностью 6/7.

Если ОК выполняется посредством случайного выбора, например с вероятностью Р(ОК), то вероятность выживания схемы определится таким образом:

где а — коэффициент, определяющий применение модифицированных ОК, а рй 1-Л. Допуская независимость оператора рекомбинации и ОК, получим объединенную оценку их действия:

Из данного выражения следует, что шаблоны хромосом с ЦФ выше средней и короткой определенной длиной S (Н) имеют возможность экспоненциального роста в новой популяции [82, 83].

Рассмотрим влияние модифицированных ОМ на возможность выживания хромосом с лучшей ЦФ на следующих генерациях. Для того, чтобы после ОМ шаблон Н хромосомы выжил в следующей генерации, все специфические позиции должны выжить. Выживание одиночной позиции имеет вероятность (1—Р(ОМ)). Шаблон Н выживает, когда каждая из о (Н) закрепленных его позиций выживает. При умножении вероятности (1 — Р(ОМ)) самой на себя о (Н) раз мы получаем вероятность выживания шабло-

на (1 — Р(ОМ))о(Я). При малых значениях Р(ОМ) <С 1 вероятность выживания шаблона может быть аппроксимирована выражением:

где (3 — коэффициент, определяющий применение модифицированных ОМ, /? рй 1-^3. Тогда предполагается, что произвольный шаблон Н получает ожидаемое число копий в следующей генерации после модифицированных оператора рекомбинации, ОК и ОМ:

Это выражение по аналогии с [82, 83] назовем модифицированной фундаментальной теоремой ГА.

Вероятность выживания шаблона Н в следующих генерациях после применения оператора инверсии запишется в виде [88, 89]:

где Р(ОИ) — вероятность выбора хромосомы, соответствующей шаблону Н из популяции на заданном шаге генерации (вероятность оператора инверсии); (р — коэффициент, определяющий применение модифицированных операторов инверсии, 1-^3. Тогда фундаментальная теорема ГА (3.4) с учетом оператора инверсии запишется:

Данное выражение перепишем в упрощенном виде:

При использовании оператора сегрегации вероятность выживания шаблона на следующей генерации определяется по формуле

где 7 — коэффициент, определяющий применение модифицированных операторов сегрегации, 7 рй 1 3.

Для оператора транслокации вероятность выживания запишется

При использовании оператора удаления вероятность выживания шаблона на следующей генерации определяется по формуле:

где S — коэффициент, определяющий применение оператора удаления, S рй «1-=-2.

При использовании оператора вставки вероятность выживания шаблона на следующей генерации определяется так:

где Л — коэффициент, определяющий применение оператора вставки, Л рй

«1-Г 2.

Тогда модифицированная фундаментальная теорема ГА с учетом всех рассмотренных генетических операторов для решения инженерных оптимизационных задач примет вид

Основная теорема ГА, приведенная Д. Холландом, показывает асимптотическое число схем, «выживающих» при реализации ПГА на каждой итерации. Выражение (3.7), в отличие от теоремы Холланда, показывает асимптотическое число хромосом, «выживающих» при реализации модифицированных операторов кроссинговера, мутации, инверсии, сегрегации, транслокации, удаления и вставки на каждой генерации. Очевидно, что это число приблизительное. Оно меняется в зависимости от вероятности применения того или иного ГА. Особенное влияние на число «выживающих» и «умирающих» хромосом при реализации ГА оказывает значение ЦФ отдельной хромосомы и всей популяции и знания о конкретной решаемой задаче. Во многих инженерных задачах имеются специальные знания, позволяющие построить аппроксимационную модель.

Лемма 3.1. Если на некотором шаге генерации ГА Рі(ГА) есть вероятность того, что хромосома рі определяет потомка на этом шаге и ?2 (ГА) есть вероятность, что рі уничтожается в течение этого шага, то ожидаемое число потомков хромосомы рі есть Рі (ГА)/Р2 (ГА).

Рассмотрим, например, хромосому длины L = 7 и две схемы, представляющие ее:

где I — символ, обозначающий точку кроссинговера. Схема Н\ после ОК, скорей всего, будет уничтожена потому, что 1 в позиции 2 и 0 в позиции 7 расположатся в различных новых хромосомах после ОК. Ясно, что схема

Н2 будет выживать, так как после ОК число 1 в позиции 4 и 0 в позиции 5 будут в той же самой новой хромосоме. Хотя точка ОК выбрана случайно, ясно, что схема Н\ менее приспособлена к выживанию, чем схема Н2. Если точка ОК выбирается случайно среди L —1 = 7—1 = 6 возможных позиций, то схема Н\ уничтожается с вероятностью Р(d) = S (Hi) /(L — 1) = 5/6, она же (схема Н\) выживает с вероятностью Pi(s) = 1 — Р(d) = 1/6. Аналогичным образом, схема Н2 имеет S (Н2) = 1 и вероятность ее уничтожения Р(d) = 1/6, а вероятность выживания Pi(s) = 5/6.

Вернемся к примеру Д. Гольдберга вычисления максимума функции /(ж) = ж2. В добавление к имеющейся информации пусть имеются три частные схемы Hi = (1****), Н2 = (*10**) и Н3 = (1***0), описанные в табл. 3.4.

В табл. 3.5 во втором столбце приведем ожидаемое число копий хромосом, которые должны перейти из генерации t в генерацию t + 1 после оператора рекомбинации, а в третьем столбце реальное число копий хромосом, которые должны перейти из генерации t в генерацию t + 1 после оператора рекомбинации. В четвертом и пятом столбце приведены аналогичные результаты после выполнения всех генетических операторов. В четвертом и шестом столбцах таблицы 3.5 приведены номера хромосом.

Рассмотрим сначала схему Ні.В течение репродукции хромосомы копируются с вероятностью, определенной согласно величине их ЦФ. Из первой строки табл. 3.4 следует, что хромосомы номеров 2, 4 являются представителями схемы Н\ (см. табл. 3.3). После оператора рекомбинации получены две копии схемы и хромосомы с номерами 2, 4 вошли в популяцию. Проверим, соответствует ли это число фундаментальной теореме. Из (3.4) при

а,   /? = 1 ожидается получить т(Н, t)f(H) / f(x) копий. Вычисляя значение средней ЦФ /(Яі), получим (256 + 441)/2 = 348,5. Разделив это число на значение средней ЦФ популяции (f(x) = 222,5) и умножая на число Н\

схем в момент времени t (га (Я, t) = 2), получим ожидаемое число Н\ схем в момент времени (t + 1), т. е. га(Я, t + 1) = 2 • 348,5/222,5 = 3,13. Сравнивая это число с реальным числом копий (схем) — 2, видим, что получили менымее число копий.

Продолжая определим, что ОК не может дать дальнейший эффект, так как определенная длина S (Яі) = 1 предотвращает разрыв единственного бита. Далее, если для ОМ взять Р(ОМ) = 0,01, то ожидается га(Я, £+1) х х Р(ОМ) = 3 • 0,01 = 0,03, но не существует битового обмена с тремя копиями в трех хромосомах. Как результат, для схемы Яі получаем ожидаемое экспоненциальное увеличение числа схем, что соответствует (3.4). Рассмотрим теперь схемы Я2 и Я3 с двумя закрепленными позициями. Схема Я2 имеет также две хромосомы в начальной популяции (номера 3, 4) и имеет две копии в следующей репродукции. Вычисляем га(Я2) = 2 • 245/222,5 = = 2. Здесь 245 — средняя ЦФ схемы, а 222,5 — средняя ЦФ популяции. Для Я3 получим только одну хромосому и га(Я3) = 1 • 256/222,5 = 1,15. Здесь 256 — значение средней ЦФ схемы.

Заметим, что для короткой схемы Я2 две копии—это хороший результат и ОК может случиться только один раз за четыре возможности (L — 1 = = 5 - 1 = 4). В схеме Я2 = (*|0|1|*|*) — это единственная реальная возможность, которая может дать новую копию. Как результат, схема Я2 выживает с высокой вероятностью. Действительное число Я2 схем есть га(Я2 ,£ + 1)^2. Для схемы Я3, так как 8 (Я3) = 4, ОК обычно разрушает ее.

Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, не существует или он нечеткий, или каждый раз зависит от конкретной задачи. Часто возникает вопрос, а сколько новых схем в новой генерации необходимо, сколько реально, сколько полезно [89]?

Д. Холланд считает, что количество шаблонов, которое может быть получено из популяции размера Np с длинной хромосом, равной L, лежит между 2Ь и Np • 2Ь. Д. Гольдберг и Д. Холланд отмечают, что число «эффективных» шаблонов составляет ориентировочно величину ІѴ| [88, 89].

Рассмотрим популяцию Np двоичных хромосом длины L. Будем считать только шаблоны, которые выживают с вероятностью большей, чем константа P(s). Как результат упрощения, рассмотрим простой ОК и ОМ с малой вероятностью выполнения. Это приведет к рассмотрению только тех шаблонов, где г < 1 — Р (s). Будем считать только те шаблоны, где длина L(s) < e(L — 1) + 1. Ясно, что существует 2Ь^~Х таких шаблонов. Для вычисления общего числа шаблонов возьмем заданный шаблон и будем перемещать его вдоль хромосомы на каждом шаге. Выполним этот шаг общее число L — L(s) + 1 раз и тогда можно вычислить общее число шаблонов длины L(s) или меньше следующим образом:

Данная формула показывает число шаблонов для одной хромосомы. Очевидно, для целой популяции число шаблонов ориентировочно определяется как

 

Размер популяции обычно берут равным Np = 2Li-s^2. Считают, что нижняя граница числа шаблонов, «выживающих» после ГА, ориентировочно равна [88, 89]:

Если учесть, что Np = 2L^/2, то получим

Следовательно, число схем «выживания» пропорционально кубу размера популяции и имеет порядок N(s) = ojNp, где и — коэффициент (о; = 1 4).

В большинстве ГА и ЭМ используется механизм или процедура случайного скрещивания. В биологии это имеет место, когда пол индивида не определен. В инженерных задачах обсуждаются различные механизмы и модели этого процесса. Основные из них описаны в [91]:

•    Ml — вытеснение (crowding factor). Этот механизм определяет способ и порядок замены старых хромосом из генерации t новыми после генерации t +1. При этом из популяции удаляются «похожие на себя» хромосомы и остаются отличающиеся.

•    М2 — разделение (sharing). Этот механизм вводит зависимость ЦФ хромосомы от их распределения в популяции и поисковом пространстве. Это позволяет копиям старых хромосом или близких к ним не появляться в популяциях.

•    М3 — введение идентификаторов (tagging). Специальным хромосомам присваиваются метки. Операторы ГА применяются только к помеченным хромосомам.

Сформулируем описание ГА в виде научной теории. Отметим, что способ построения научной теории, в основе которой используются исходные положения, называемые аксиомами, а все остальные предложения теории получаются как логические следствия аксиом, называется аксиоматический метод. Основным в нем является метод интерпретаций.

Пусть каждому исходному понятию и отношению аксиоматической теории ЭМ поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации. Всякому утверждению U теории ЭМ ставится в соответствие некоторое высказывание 17* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ЭМ соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ГА, которая, в частности, может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ЭМ.

Пусть теория ЭМ проинтерпретирована в теории ГА таким образом, что все аксиомы Аі теории ЭМ интерпретируются истинными суждениями А* теории ГА. Тогда всякая теорема теории ЭМ, т. е. всякое утверждение А,

логически выведенное из аксиом Аі в ЭМ, интерпретируется в ГА некоторым утверждением А*, выводимым в ГА из интерпретаций А* аксиом Аі

и,   следовательно, истинным [109].

Метод интерпретаций позволяет также решать вопрос о независимости систем аксиом: для доказательства того, что аксиома А теории ЭМ не зависит от остальных аксиом этой теории, т. е. не выводима из них,

и,   следовательно, необходима для получения всего объема данной теории, достаточно построить такую интерпретацию ЭМ, в которой аксиома А была бы ложна, а все остальные аксиомы этой теории истинны. Уточнением понятия аксиоматической теории является понятие формальной системы. Это позволяет представлять математические теории как точные математические объекты и строить общую теорию или метатеорию таких теорий. Всякая формальная система строится как точно очерченный класс выражений-формул, в котором некоторым точным образом выделяется подкласс формул, называемых теоремами данной формальной системы. При этом формулы формальной системы непосредственно не несут в себе содержательного смысла. Их можно строить из произвольных знаков и символов. Общая схема построения произвольной формальной системы ЭМ такова:

1.   Язык системы ЭМ: аппарат алгебры логики; теория множеств; теория графов.

1.1. Алфавит — перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.

1.2. Правила образования (синтаксис): правила, по которым из элементарных символов строятся формулы системы ЭМ. Правила:

•    построения модели эволюции;

•    конструирования популяций;

•    построения ЦФ;

•    разработки генетических операторов;

•    репродукции популяций;

•    рекомбинации популяций;

•    редукции.

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

2.   Аксиомы системы ЭМ. Выделяется некоторое множество конечных формул, которые называются аксиомами системы. В ЭМ существует большое число аксиом. Основные из них следующие:

•    « Выживание сильнейших», т. е. переход решений с лучшей целевой функцией в следующую генерацию.

•    Размер популяции после каждой генерации остается постоянным.

•    Обязательное применение во всех генетических алгоритмах операторов кроссинговера и мутации.

•    Число копий (решений), переходящих в следующую генерацию, определяется по формуле (3.7).

3.   Правила вывода ЭМ. Фиксируется конечная совокупность предикатов Пі, П2,..., Щ на множестве всех формул системы. Пусть П (х±,... ..., хПг+\) — какой-либо из этих предикатов (щ > 0). Если для данных формул Fi,..., Fn%+1 утверждение П (F\,..., Fn%+1) истинно, то говорят, что формула FUi+1 непосредственно следует из формул F\,..., Fni+1 по правилу П

Заданием 1, 2, 3 исчерпывается задание формальной системы ЭМ как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ЭМ называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ЭМ, либо непосредственно следует из каких-либо предшествующих ей этой последовательности формул по одному из правил вывода Пі системы.

Всякую конкретную математическую теорию ЭМ можно перевести на язык подходящей формальной системы таким образом, что каждое ложное или истинное предложение теории ЭМ выражается некоторой формулой системы. Метод интерпретаций позволяет устанавливать факт относительной непротиворечивости, т. е. доказывать суждения типа: «если теория ГА непротиворечива, то непротиворечива и теория ЭМ». В общем проблема непротиворечивости не решена и является одной из основных в математике [109].

В заключении отметим, что существуют четыре основных отличия ГА от оптимизационных методов:

•    прямое преобразование кодов;

•    поиск из популяции, а не из единственной точки;

•    поиск через элементы (слепой поиск);

•    поиск, использующий стохастические и модифицированные операторы, а не детерминированные правила.

Использование ЭМ и ГА при решении инженерных задач позволяет уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.