Файл: Лекция д т. н., профессора Курейчика В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы.doc

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

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

Генетический алгоритм состоит из набора генетических операторов.

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

Рассмотрим основные операторы генетических алгоритмов.

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

Существует большое число видов операторов репродукции. К ним относятся:

• 
  Селекция на основе рулетки  это простой и широко используемый в простом генетическом алгоритме (ПГА) метод. При его реализации каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции. Причем, элемент с большим значением ЦФ имеет большую вероятность для выбора.
  
• 
  Селекция на основе заданной шкалы. Здесь популяция предварительно сортируется от «лучшей» к «худшей» на основе заданного критерия. Каждому элементу назначается определенное число и тогда селекция выполняется согласно этому числу.
  
• 
  Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения значений ЦФ. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс продолжается аналогично до тех пор, пока продолжают появляться элитные элементы.
  
• 
  Турнирная селекция. При этом некоторое число элементов (согласно размеру «турнира») выбирается случайно или направленно из популяции, и лучшие элементы в этой группе на основе заданного турнира определяются для дальнейшего эволюционного поиска.
  

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

---

• 
  Случайный выбор хромосом;
  
• 
  Выбор хромосом на основе значений целевой функции.
  

При случайном выборе хромосом частота R образования родительских пар не зависит от значения ЦФ хромосом и полностью определяется численностью популяции N.

,

где β - коэффициент селекции, принимающий в зависимости от условий внешней среды значение 1 - 4.

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

Для реализации первой стратегии с максимизацией ЦФ с вероятностью

,

выбирают разные хромосомы. Здесь ОР – это оператор репродукции, моделирующий естественный процесс селекции, Рr(ОР) – вероятность выбора хромосом для репродукции.

Вторая стратегия реализуется так: часть хромосом выбирается случайным образом, а вторая с вероятностью на основе выражения.

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

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

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

---

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

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

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

Р₁ : 1 1 | 1 1 1

Р₂ : 0 0 | 0 0 0

________________

Р'₁ : 1 1 | 0 0 0

Р'₂ : 0 0 | 1 1 1 .

Итак, одноточечный ОК выполняется в три этапа:

1. 
   Две хромосомы А = а₁, а₂,.., а_L и B = a₁, a₂,.., a_L выбираются случайно из текущей популяции.
   
2. 
   Число k выбирается из {1,2,...,L-1} также случайно. Здесь L - длина хромосомы, k - точка ОК (номер, значение, или код гена, после которого выполняется разрез хромосомы).
   
3. 
   Две новые хромосомы формируются из А и В путем перестановок элементов согласно правилу
   

,

.

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

---

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

Р₁ : 1 1 1 | 0 1 | 0 0

Р₂ : 0 0 0 | 1 1 | 1 0

____________________

Р'₁ : 1 1 1 | 1 1 | 0 0

Р'₂ : 0 0 0 | 0 1 | 1 0 .

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

Пример трехточечного ОК.

Р₁ : 1 | 1 1 |0 1 | 0 0

Р₂ : 0 |0 0 |1 0 | 1 1

____________________

Р'₁ : 1| 0 0 | 0 1 | 1 1

Р'₂ : 0 |1 1 | 1 0 | 0 0 .

Здесь точки ОК делят хромосому на ряд строительных блоков (в данном случае 4). Потомок Р'₁ образуется из нечетных блоков родителя P₁ и четных блоков родителя P₂. Потомок Р'₂ образуется соответственно из нечетных блоков родителя P₂ и четных блоков родителя P₂.

Тогда многоточечный ОК выполняется аналогичным образом.

Упорядоченный оператор кроссинговера. Здесь «разрезающая» точка также выбирается случайно. Далее происходит копирование левого сегмента Р₁ в Р'₁. Остальные позиции в Р'₁ берутся из Р₂ в упорядоченном виде слева направо, исключая элементы, уже попавшие в Р'₁. Например:

Р₁ : A B C D | E F G H

P₂ : G A B E | C D F H

______________________

P'₁ : A B C D | G E F H .

Получение Р'₂ может выполняться различными способами. Наиболее распространенный метод копирования левого сегмента из Р₂, а далее анализ Р₁ методом, указанным выше. Тогда имеем P'₂ : (G A B E | C D F H).

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

Р₁ : A B C D E F | G H I J

P₂ : E C I A D H | J B FG

__________________________

P'₁ : A H C D E I | J B F G .

Аналогично можно получить P'₂:

Р₁ : A B C D E F | G H I J

---

P₂ : E C I A D H | J B F G

__________________________

P'₂ : E C FA D B | G H I J.

Циклический ОК. Циклический ОК выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция P состоит из двух хромосом P={P₁, P₂}. Первый и второй родители и их потомок имеют вид:

Р₁ : 1 2 3 4 5 6 7 8 9 10

P₂ : 5 3 9 1 4 8 10 2 6 7

________________________

P'₁ : 1 3 9 4 5 8 10 2 6 7 .

При выполнении циклического ОК Р'₁ заполняется, начиная с первой позиции, и копирует элемент с первой позиции Р₁. Элементу 1 в Р₁ соответствует элемент 5 в P₂. Следовательно, имеем первый путь в цикле (1,5). Элементу 5 в Р₁ соответствует элемент 4 в Р₂. Имеем второй путь в первом цикле (1,5; 5,4). Продолжая далее, получим, что элементу 4 в Р₁ соответствует элемент 1 в Р₂. Следовательно, сформирован первый цикл (1,5; 5,4; 4,1). Согласно этому циклу элемент 5 переходит в пятую позицию Р'₁, а элемент 4 – в четвертую позицию. Сформируем теперь второй цикл. Элемент 2 в Р₁ соответствует элементу 3 в Р₂. Продолжая аналогично, получим второй цикл (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). Второй потомок получается аналогичным образом. Для каждого элемента в Р₁, Р₂ гены меняются, как показано на следующем примере:

Р₁ : 0 1 1 0 0 1

P₂ : 0 1 0 1 1 1

________________

0 1 1 0 1 0  маска

_______________

P'₁ : 0 0 0 0 1 1

P'₂ : 0 0 1 1 0 1 .

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

---