3.1.  Определение и структура генетических алгоритмов

Исторически считается, что научное направление «эволюционные вычисления» является основным, использующим (моделирующим) эволюционные механизмы живой природы. Оно включает в себя три главных направлен™ фундаментальных исследований: генетические алгоритмы, эволюционное моделирование (в некоторых работах говорят об эволюционных стратегиях) и эволюционное программирование [16-19, 23-25, 88-98].

В своих, работах И. Букатова [93, 94] сформулировала новое направление «эвоинформатика». Эвоинформатика определяется как совокупность алгоритмических, программных и аппаратных средств, основанных на имитации механизмов ЕС для синтеза структур обработки информации. И. Букатова предложила архитектуру эволюционного поиска, состоящего из следующих компонент: моделирование цели, имитация основных законов дарвинизма, соревнование, отбор. Основу алгоритмов эволюционного и структурного поиска здесь составляют самообучающиеся и адаптивные алгоритмы. Самоорганизующиеся вычисления основаны на распараллеливании эволюционных процессов аналогично эволюции Ч. Дарвина, происходящих на основе механизмов синергетики. Такая эволюционно-вычислительная технология включает генерацию эволюционных систем, эволюционный синтез заданных моделей, поэтапное управление и интерпретацию моделей из БЗ.

Генетические алгоритмы — это новая область исследований, которая появилась в результате работ Д. Холланда и его коллег [88-90, 99-107]. ГА, описанные Д. Холландом, заимствуют в своей терминологии многое из естественной генетики. Впервые они были применены к таким научным проблемам, как распознавание образов и оптимизация. ГА представляет собой адаптивный поисковый метод, который основан на селекции лучших элементов в популяции, подобно эволюционной теории Ч. Дарвина.

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

Эволюционный поиск с точки зрения преобразования информации в интеллектуальной ИС — это последовательное преобразование одного конечного нечеткого множества промежуточных решений в другое. Само преобразование можно назвать алгоритмом поиска, или генетическим алгоритмом.

ГА — это не просто случайный поиск. Они эффективно используют информацию, накопленную в процессе эволюции. Цель ГА состоит в том, чтобы:

•    абстрактно и формально объяснить адаптацию процессов в ЕС и интеллектуальной ИС;

•    смоделировать естественные эволюционные процессы для эффективного решения оптимизационных задач науки и техники.

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

ГА, согласно [88-90], отличаются от других оптимизационных и поисковых процедур следующим:

•    работают в основном не с параметрами задачи, а с закодированным множеством параметров;

•    осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве

решений;

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

•    применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р = {рі, р2, • • •, Рі , • • •, Pnp} есть множество элементов Рі. Здесь Np — размер популяции. Каждый элемент этой популяции Р*, как правило, представляет собой одну или несколько хромосом, или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называются лоци или локус для одной позиции, т. е. ген — подэле-

мент (элемент в хромосоме), локус — позиция в хромосоме, аллель — значение гена.

Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита {0,1}, хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины семь на основе двоичного алфавита может служить хромосома р* = (0001101). Элементы в ГА часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители создают новую популяцию. Генерация, т. е. процесс реализации одной итерации алгоритма, называется поколением.

Эволюция популяции согласно [89-91] — это чередование поколений, в которых хромосомы изменяют свои значения так, чтобы каждое новое поколение наилучшим способом приспосабливалось к внешней среде. В интеллектуальной ИС общая генетическая упаковка называется генотипом. В ЕС организм формируется посредством связи генетической упаковки с окружающей средой и называется фенотипом.

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

Каждая популяция обладает наследственной изменчивостью. Это означает, что имеет место случайное отклонение от наиболее вероятного среднего значения ЦФ. Отклонение описывается нормальным законом распределения случайных величин, но, в отличие от ЕС, наследственная изменчивость не затухает, как всякая флуктуация. При этом наследственные признаки закрепляются, если они имеют приспособительный характер, т. е. обеспечивают популяции лучшие условия существования и размножения.

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

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

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

ГА дает ряд преимуществ при решении практических задач. Одно из таких преимуществ — это адаптация к изменяющейся окружающей среде. В реальной жизни проблема, которая была поставлена для решения изначально, может претерпеть огромные изменения в процессе своего решения. При использовании традиционных методов все вычислен™ приходится начинать заново, что приводит к большим затратам машинного времени. При эволюционном подходе популяцией служит БЗ, которую можно анализировать, дополнять и видоизменять применительно к изменяющимся условиям. Для этого не требуется полный перебор. Другое преимущество ЭМ для решения задач состоит в способности быстрой генерации достаточно хороших решений.

При решении практических задач с использованием ЭМ, необходимо выполнить следующие четыре предварительных этапа:

•    выбрать способ представления решения;

•    разработать операторы случайных изменений;

•    определить законы выживания решения;

•    создать начальную популяцию.

Рассмотрим некоторые особенности выполнен™ этих этапов.

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

Достаточно сложным является этап выбора случайного оператора (или операторов) для генерации потомков. Их существует огромное число. В ЕС используются два основных типа размножения: половое и бесполое. При половом размножении два родителя обмениваются генетическим материалом, который используется при создании потомка. Бесполое размножение — это фактически клонирование, при котором происходят различные мутации при передачи информации от родителя к потомку. Эти операторы очень важны при ЭМ, однако в общем случае для интеллектуальной ИС можно применить и операции, которые не существуют в ЕС. Например, использовать материал от трех или более родителей, проводить голосование при выборе родителей. Фактически нет пределов в использовании различных операторов и нет никого смысла только слепо копировать законы природы и ограничиваться ими.

Успех ЭМ во многом зависит от того, насколько хорошо взаимодействуют между собой схема представления, операторы случайных изменений и способ определен™ ЦФ. Поэтому для определенного класса задач более

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

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

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

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

Отметим, что популяция обязательно является конечным множеством. В каждой генерации хромосомы являются результатом применения некоторых генетических операторов. В простых ГА (ПГА) Д. Гольдберга существует три основных оператора (или функции, или шага, или процесса): селекция (репродукция), кроссинговер (скрещивание) и мутация [89].

Рассмотрим кратко эти основные операторы. Натуральная селекция — это процесс, посредством которого хромосомы, имеющие более высокое значение ЦФ (с сильными признаками), получают большую возможность для репродукции, чем слабьте хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичные или различные потомки.

Существует много различных видов селекции. Рассмотрим основные из них:

•    Селекция на основе рулетки — это самый простой и наиболее используемый в ПГА метод. При его использовании каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции, причем элемент с большим значением ЦФ имеет большую вероятность для выбора.

•    Селекция на основе заданной шкалы. Здесь популяция предварительно сортируется от «лучшей» особи к «худшей» на основе заданного критерия. Каждому элементу назначается определенное число и далее селекция выполняется согласно этому числу.

•    Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения ЦФ. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс идет до тех пор, пока продолжают появляться элитные элементы.

•    Турнирная селекция. При этом некоторое число элементов (согласно размеру «турнира») выбирается случайно или направленно из популяции, и лучшие элементы в этой группе на основе заданного турнира определяются для дальнейшего генетического поиска.

Кроме описанных, существует большое число других методов селекции, которые можно условно классифицировать на три группы [19]. К первой группе отнесем вероятностные методы селекции. Ко второй — детерминированные . К третьей — различные комбинации методов из первой и второй групп. Поиски оптимальных методов селекции непрерывно продолжаются. Дело в том, что основной трудностью решения оптимизационных задач с большим количеством локальных оптимумов является предварительная сходимость алгоритмов. Другими словами, происходит попадание решения в один, далеко не самый лучший, локальный оптимум. Различные методы селекции и их модификации как раз и позволяют в некоторых случаях решать проблему предварительной сходимости алгоритмов. Следует отметить, что исследователи ГА все более склоняются к мысли применять комбинированные методы селекции с использованием предварительных знаний о решаемых задачах и предварительных результатах.

Опишем теперь методы кроссинговера. В литературе часто их называют операторами кроссинговера (ОК). Основная функция ОК — создавать хромосомы потомков на основе различного скрещивания родителей. Существует огромное число ОК, так как их структура в основном и определяет эффективность ГА. Кратко рассмотрим основные ОК, известные в литературе, и их модификации.

Одноточечный (простой) ОК. Перед началом работы одноточечного ОК определяется так называемая точка О К, или разрезающая точка, которая обычно определяется случайно. Эта точка определяет место в двух

хромосомах, где они должны быть «разрезаны». Например, пусть популяция Р состоит из двух хромосом Р = {рі,р2}, которые выступают в качестве родителей. Пусть первый и второй родители имеют вид р± : (11111), Р2 : (00000). Выберем точку ОК между вторым и третьим генами в Р2. Тогда, меняя элементы после или перед точкой ОК между двумя родителями, можно создать два новых потомка. В нашем примере получим:

Итак, одноточечный OK в интеллектуальной ИС выполняется в три этапа:

1.   Две хромосомы А = «і, а2, • • •, аь и В = а[, af2,..., выбираются случайно из текущей популяции.

2.   Число к выбирается из {1, 2,..., L — 1} также случайно. Здесь L — длина хромосомы, к — точка ОК (номер или значение, код гена, после которого выполняется разрез хромосомы).

3.   Две новые хромосомы формируются из А и В путем перестановок элементов согласно правилу

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

В двухточечном ОК определяются две точки ОК, и гены обмениваются между ними. Например:

Отметим, что точки ОК в двухточечном ОК также определяются случайно. Существует много модификаций двухточечного ОК.

Развитием двухточечного ОК является многоточечный ОК или ІѴ-то- чечный ОК, он выполняется аналогично двухточечному ОК, хотя большое число «разрезающих» точек может привести к потере «хороших» родительских свойств.

Порядковый оператор кроссинговера. В порядковом ОК «разрезающая» точка также выбирается случайно. Далее происходит копирование

левого сегмента р± в р[. Остальные позиции в р[ берутся из р2 в упорядоченном виде слева направо, исключая элементы, уже попавшие в р[. Например:

Получение р'2 может выполняться различными способами. Наиболее распространенный метод — копирование левого сегмента из р2, а далее анализ р± методом, указанным выше. Тогда имеем pf2 : (G А В Е | С D F Н).

Частично-соотвемствующий ОК. Здесь также случайно выбирается «разрезающая» точка или точка ОК. Дальше анализируются сегменты в обоих родителях и устанавливается частичное соответствие между элементами первого и второго родителей с формированием потомков. При этом правый сегмент р2 переносится в р[, левый сегмент р± переносится в р[ с заменой повторяющихся генов на отсутствующие (гены, находящиеся в частичном соответствие). Например:

Циклический ОК. Циклический ОК выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция Р состоит

из двух хромосом Р = {pi, Р2 } • Первый и второй родители и их потомок имеют вид:

При выполнении циклического ОК р[ заполняется, начиная с первой позиции, и копирует элемент из первой позиции р±. Элементу 1 в р± соответствует элемент 5 в р2. Следовательно, имеем первый путь в цикле

(1,5). Элементу 5 в р± соответствует элемент 4 в р2. Имеем второй путь в первом цикле (1, 5; 5,4). Продолжая далее, получим, что элементу 4 в р± соответствует элемент 1 в р2. Следовательно, сформирован первый цикл

(1, 5; 5, 4; 4,1). Согласно этому циклу элемент 5 переходит в пятую позицию р'ъ а элемент 4 — в четвертую позицию. Сформируем теперь второй цикл. Элемент 2 в рі соответствует элементу 3 в р2 • Продолжая аналогично, получим второй цикл (2, 3; 3,9; 9, 6; 6,8; 8, 2) и третий (7,10; 10, 7) циклы. Следовательно, в р[ элемент 3 расположен во втором локусе, т. е. на второй позиции, элемент 9 — в третьем, элемент 6 — в девятом, элемент 8 — в шестом, элемент 2 — в восьмом, элемент 10 — в седьмом и элемент 7 — в десятом локусах. Циклический ОК и его модификации эффективно применяются для решения комбинаторно-логических задач, задач на графах и гиперграфах и других, оптимизационных задач.

Универсальный ОК. В настоящее время он популярен для решения различных задач теории расписаний. Вместо использования разрезающей точки (точек) здесь определяют двоичную маску, длина которой равна длине заданных хромосом. Получение потомков выполняется на основе правил сложения булевой алгебры соответствующих генов родителей и маски (0 + 0 = 0, 0 + 1 = 1, 1 + 1 =0). Для каждого элемента в рі, р2 гены меняются, как показано на следующем примере:

Маска обычно выбирается случайно с заданной вероятностью или на основе генератора случайных чисел. При этом чередование 0 и 1 в маске происходит с вероятностью « 0,5 (т. е. приблизительно в 50% случаев). В некоторых случаях используются параметризированный универсальный ОК, где маска может выбираться с вероятностью для 1 или 0 выше, чем 0,5. Такой вид маски эффективен, когда хромосомы кодируются в двоичном алфавите.

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

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

2.   В выбранной хромосоме для г-го гена, расположенного слева от точки «жадного» ОК, определяется частичная ЦФ, т. е. стоимость пути от і-го гена к рядом находящемуся гену. Аналогичные действия выполняются по определению стоимости пути во всех остальных хромосомах, выбранных для «жадного» ОК.

3.   В хромосому «потомок» выбирают тот ген, у которого значение ЦФ выше (ниже) при максимизации (минимизации) ЦФ.

4.   Процесс продолжается, пока не будет построена хромосома «потомок». Если в процессе реализации «жадного» ОК возникает цикл или тупик, то в потомок выбираются нерассмотренные гены с лучшей ЦФ. Например, пусть популяция Р состоит из трех родительских хромосом Р = {рі,Р2,Рз}, где pi:(abcde); p2:(bdeca); p3:(ebadc). Причем стоимость (ЦФ) для каждого гена в хромосоме задана матрицей:

Согласно алгоритму выберем точку «жадного» ОК между генами b и с в хромосоме рі. Теперь выбор (b-с) дает значение ЦФ, равное 4; выбор (Ь-а) определяет ЦФ со значением 15, а выбор (b-d) определяет ЦФ, равную 3. При решении задачи минимизации ЦФ выберем путь (b-d). Продолжая далее, получим путь реализации «жадного» ОК (рис. 3.1). Итак, хромосома потомка р': (b d с а е) имеет суммарную ЦФ, равную 18 (3 +1 + 6 + 8 = 18), а ЦФ родителей для р\ равна 15 + 4 + 1 + 9 = 29, для р2 равна 3 + 9 + 10 + + 6 = 28 и для рз равна 2 + 15 + 7 + 1 = 25. Стратегию «жадного» ОК можно выполнять различными способами.

Следует отметить, что исследователи продолжают поиск оптимального ОК.

Рассмотрим кратко основные операторы мутации (ОМ). Мутация необходима потому, что предотвращает потерю важного генетического материала [88-92]. Обычно ОМ является одноточечным оператором, который случайно выбирает ген в хромосоме и обменивает его на рядом расположенный ген. Например, одноточечный ОМ имеет вид:

Двухточечный ОМ заключается в перестановке генов, расположенных справа от точек разрыва. Например:

Процесс преобразования в ЕС и ИС обычно происходит толчками. При этом важную роль играют толчковые мутации. Они не изменяют размера и строения хромосом, а изменяют взаимное расположение генов в хромосоме.

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

Согласно Д. Холланду, ОМ выполняется следующим образом:

1.   В хромосоме А = (аі, а2, аз,..., аь_2, а^-і, а^) определяются случайным образом две позиции (например, а2 и а^-і).

2.   Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома. ОМ — А' = (аі, а^-і, аз,..., аь-2, а2, а^).

Заметим, что в ПГА ОК — бинарная операция, а ОМ — унарная операция. Кроме того, ОК и ОМ соответствуют перестановкам элементов внутри заданного множества. Важным понятием в ОМ является шкала мутации, которая определяет, какой процент общего числа генов в популяции видоизменяется в каждой генерации. Для оптимизационных задач вероятность ОК обычно принимают равной 0,6 + 0,99, а вероятность ОМ от 0,6 и меньше [16-19].

Кроме мутации, популярным и используемым в ЕС и ИС является оператор инверсии. В операторе инверсии случайным образом определяется одна или несколько точек инверсии, внутри которых элементы инвертируются.

Генетический оператор инверсии в ГА Д. Холланда [88] состоит из следующих шагов:

1.   Хромосома В — (&і, Ь2,..., Ъь) выбирается случайным образом из текущей популяции.

2.   Два числа у[ и у'2 выбираются случайным образом из множества {0, 1, 2, ..., L + 1}, далее определяем у\ — тт{у[, у!2} и у2 — = та х{у[,у'2}.

3.   Новая хромосома формируется из В путем инверсии сегмента, который лежит справа от позиции у\ и слева от позиции у2 в хромосоме В.

Тогда, после применения оператора инверсии, получаем Ві : Ві = (Ьі,...,ЬУ1, Ьу21, Ьу2 2,..., Ьу1+1, Ьу2,..., Ъ^).

Например, для двухточечного оператора инверсии получим:

Для одноточечного оператора инверсии запишем:

Кроме простого оператора инверсии, в [89] описан специальный оператор инверсии. В нем точки инверсии определяются с заданной вероятностью для каждой новой создаваемой хромосомы в популяции. Оператор инверсии до последнего времени не получил широкого использования при решении оптимизационных задач.

Рассмотрим оператор транслокации. Он представляет собой комбинацию ОК и оператора инверсии. В процессе транслокации случайным образом производится один разрыв в каждой хромосоме. При формировании потомка р[ берется левая часть до разрыва из родителя рі и инверсия правой части до разрыва из р2. При создании р'2 берется левая часть р2 и инверсия правой части р\. Приведем пример оператора транслокации:

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

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

Тогда потомокр[ можно сформировать случайным образом, взяв первый элемент (один или несколько генов) из рі, второй из р2, третий из рз и четвертый из р4. При этом должны быть отброшены повторяющиеся решения, или решения, содержащие одинаковые элементы. Так, вариант р[ : (1412) должен быть отброшен как содержащий две единицы, а вариант р'2 : (2143) является легальным (допустимым или реальным). Очевидно, что оператор

сегрегации можно реализовать различными способами в зависимости от способа выбора генов из хромосом.

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

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

Рассмотрим теперь понятие рекомбинации. Функция рекомбинации определяет, как новая генерация хромосом будет построена из родителей и потомков. Другими словами, функция рекомбинации — это анализ и преобразование популяции при переходе из одной генерации в другую. Существует много путей выполнения рекомбинации [16-19, 89]. Один из них состоит из перемещения родителей в потомки после каждого генетического оператора (ГО). Другой путь заключается в перемещении некоторого процента популяции, используя потомков в течение каждой генерации. Обычно в ГА задается параметр W(P), который управляет этим процессом. Так, Np(l — W(Р)) элементов в популяции Р, выбранных случайно, могут «выжить» в следующей генерации. Здесь Np — размер популяции. Величина W (Р) = 1 означает, что целая предыдущая популяция перемещается в новую в каждой генерации. При дальнейшей реализации алгоритма лучшие элементы из родителей и потомков будут выбираться для формирования новой популяции.