Исходный URL: Mitchell M. Introduction to genetic algorithms (Mit,1999/ 162s.)

1.5 ЭЛЕМЕНТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

Оказывается, что нет никакого строгого определения "генетического алгоритма", принятого всеми в семействе эволюционного вычисления, которое отличает ГА от других эволюционных методов вычисления. Однако можно сказать, что большинство методов под названием "ГА" имеют, по крайней мере, в общем, следующие элементы: популяции хромосом, выбор согласно значимости, кроссинговер для создания нового потомства, и случайную мутацию нового потомства. Инверсия ГА - четвертый элемент по Холланду, редко используется в сегодняшнем выполнении, и его преимущества, если таковые вообще имеются, хорошо не установлены. (Инверсия будет обсуждена подробно в главе 5.)

Хромосомы в популяции ГА обычно берут в форме строк битов. Каждое местоположение в хромосоме принимает два возможных значения: 0 и 1. Каждая хромосома может быть представлена как точка в области поиска вариантов решения. ГА обрабатывает популяции хромосом, последовательно заменяя одну такую популяцию другой. ГА наиболее часто использует fitness-функцию, которая соответствует значимости (fitness) на каждую хромосому в текущей популяции. Значимость хромосомы зависит от того, как удачно хромосома способствует разрешению проблемы.

Примеры Fitness - функций

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

(Riolo 1992). Здесь варианты решения - значения y, которые могут быть закодированы как строки битов, представляющие вещественные числа. При вычислении fitness-функции переводят данную строку битов x в вещественное число y и затем оценивают функцию в том значении. Значимость строки – значение функции в данной точке.

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

IHCCVASASDMIKPVFTVASYLKNWTKAKGPNFEICISGRTPYWDNFPGI,

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

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

ГА Операторы

Самая простая форма генетического алгоритма вовлекает три типа операторов: выбор, кроссинговер (одноточечный) и мутация.

Выбор – этот оператор выбирает хромосомы в совокупности для воспроизводства. Чем значимее хромосома, тем больше вероятность того, что она будет выбрана для воспроизводства.

Кроссинговер – этот оператор беспорядочно выбирает точку и обменивает части до и после этой точки между двумя хромосомами, чтобы создать два потомства. Например, строки 10000100 и 11111111 могли пересечься после третьего бита в каждой, чтобы произвести два потомства 10011111 и 11100100. Оператор кроссинговера грубо подражает биологической рекомбинации между двумя едино хромосомными (гаплоид) организмами.

Мутация – этот оператор беспорядочно зеркально отражает некоторые из битов в хромосоме. Например, строка 00000100 могла бы быть видоизменена в ее второй позиции, чтобы выпустить 01000100. Мутация может произойти в каждой разрядной позиции в строке с малой вероятностью, обычно весьма малой (например, 0.001).

1.6 ПРОСТОЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

Учитывая ясно определенную проблему, которая будет решена, и представление строки битов для вариантов решения, простой ГА работает следующим образом:

1. Начинаем со случайно сгенерированной совокупностью n l-битовых хромосом (варианты решения проблемы).

2. Вычислить значимость f(x) каждой хромосомы x в совокупности.

3. Повторять следующие шаги, пока n потомств не было создано:

a. Выберите пару родительских хромосом из текущей совокупности, вероятность выбора является прямо пропорциональной функцией значимости. Выбор сделан "с заменой", т.е., та же самая хромосома может быть выбрана не раз в качестве родителя.

b. С вероятностью p_c ("вероятность кроссинговера" или "разряд кроссинговера"), пересеките пару в случайно выбранной точке (выбранной с равномерной вероятностью), чтобы формировать два потомства. Если пересечение не происходит, формируется два потомства, которые являются точными копиями их соответствующих родителей. (Обратите внимание, что здесь разряд кроссинговера определен так, чтобы быть вероятностью, что два родителя пересекутся в единственной точке. Есть также версии ГА с "многоточечным кроссинговером", в которых разряд кроссинговера для пары родителей – это количество точек, в которых кроссинговер имеет место.)

c. Произвести мутацию двух потомств в каждом разряде с вероятностью p_m (вероятность мутации или разряд мутации), и разместить окончательные хромосомы в новую совокупность.

Если n нечетный, один новый член популяции может быть отвергнут наугад.

4. Замените текущую популяцию новой популяцией.

5. Идите в шаг 2.

Каждую итерацию этого процесса называют поколением. ГА типично выполняется с помощью итераций для 50-500 или более поколений. Полный набор поколений называют выполнением. В конце выполнения есть часто одна, или более, весьма пригодных хромосом в популяции. Так как случайность играет большую роль в каждом выполнении, два выполнения с различными случайными источниками будут вообще производить различные детальные поведения. Исследователи ГА часто сообщают о статистике (типа лучшей значимости, найденной в выполнении и поколения, в котором индивидуум с этой лучшей значимостью был обнаружен), усредненной по многим различным выполнениям ГА по одной и той же проблеме.

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

Как более детальный пример простого ГА, предположим, что l (строковая длина) равна 8, что f(x) является равной номеру в строке битов x (чрезвычайно простая функция значимости, используемая здесь только для иллюстративных целей), что n (размер совокупности) равен 4, что p_c = 0.7, и что p_m = 0.001. (Подобно функции значимости, эти значения l и n были выбраны для простоты. Более типичные значения l и n находятся в диапазоне 50-1000. Значения данных p_c и p_m довольно типичны.)

Начальная (случайно сгенерированная) популяция могла бы выглядеть следующим образом:

Общий метод выбора в ГА - это пропорционально значимый выбор, в котором число раз, которое индивидуум, как ожидается, воспроизведется, является равным его значимости, разделенной на среднее число значимости в популяции. (Это эквивалентно тому, что биологи называют "выбором жизнеспособности".)

Простой метод осуществления пропорционально значимого выбора – это "осуществление выборки колеса рулетки" (Goldberg 1989a), который является концептуально эквивалентным предоставлению каждому индивидуума сектором кругового колеса рулетки, равного области значимости индивидуума. Колесо рулетки запускается, шар останавливается на одном секторе, и соответствующий индивидуум будет выбран. В n = 4 примере, колесо рулетки запускали бы четыре раза; первые два вращения могли бы выбрать хромосомы B и D для того, чтобы быть родителями, и вторые два вращения могли бы выбрать хромосомы B и C для того, чтобы быть родителями. (Фактически А может быть не выбрана только по удачному жребию. Если бы колесо рулетки вращали много раз, средние результаты были бы ближе к ожидаемым значениям.)

Как только пара родителей выбрана, с вероятностью p_c они пересекаются, чтобы сформировать два потомства. Если они не пересекаются, то потомство – это точные копии каждого родителя. Предположим в примере выше, что родители B и D пересекаются после первой разрядной позиции, которая формирует потомство E = 10110100 и F = 01101110, и родителей B и C не пересекаются, вместо этого формируя потомства, которые являются точными копиями B и C. Затем, каждое потомство подвержено мутации в каждом разряде с вероятностью p_m. Например, предположим, что потомство E видоизменено в шестом разряде, чтобы сформировать E' = 10110000, потомства F и C не видоизменены вообще, и потомство B видоизменено в первом разряде, чтобы сформировать B' = 01101110. Новой совокупностью будет следующее:

Обратите внимание, что в новой совокупности, хотя лучшая строка (со значимостью 6) была потеряна, средняя значимость повысилась с 12/4 до 14/4. Выполнение итераций этой процедуры, в конечном счете, приведет к строке со всеми единицами.