Генетические операторы.

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

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

Собственно воспроизводство ведется с помощью оператора кроссовера - скрещива­ния (crossover). При скрещивании два решения-кандидата делятся на несколько частей и обмениваются этими частями, результатом становятся два новых кандидата.

На рис.1 показана операция скрещивания шаблонов битовых строк длины 8. Эти строки делятся на две равные части, после чего формируются два потомка, содержащих по одному сегменту каждого из родителей. Заметим, что разбиение родительских особей на две равные части— это достаточно произвольный выбор. Решения-кандидаты могут разбиваться в любой точке, которую можно выбирать и изменять случайным образом в ходе решения задачи.

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

Мутация (mutation) — это еще один важный генетический оператор. Она состоит в слу­чайном выборе кандидата и случайном изменении некоторых его свойств. Например, мутация может состоять в случайном выборе бита в шаблоне и изменении его значения с 1 на 0 или #. Значение мутации состоит в возможном восполнении важных компонентов решения, отсутст­вующих в исходной популяции. Если в рассмотренном выше примере ни один из членов ис­ходной популяции не содержит 1 в первой позиции, то в процессе скрещивания нельзя полу­чить потомка, обладающего этим свойством. Значение первого бита может измениться лишь вследствие мутации. Этой цели можно также достичь с помощью другого генетического опе­ратора — инверсии (inversion), который заключается в том, что хромосома делится на две части, и затем они меняются местами.

Работа генетического алгоритма продолжается до тех пор, пока не будет достигнуто условие его завершения, например, для одного или нескольких кандидатов значение кри­терия качества не превысит некоторого порога.

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