Популяционные алгоритмы оптимизации: Бинарный генетический алгоритм (Binary Genetic Algorithm, BGA). Часть I

Содержание:

1. Введение
2. Способы представления признаков: вещественное и бинарное
3. Преимущество представления бинарным кодом Грея
4. Методы селекции
5. Виды метода "кроссовер"
6. Виды метода "мутация"
7. Выводы

1. Введение

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

2. Способы представления признаков: вещественное и бинарное

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

Вещественное представление данных используется для представления дробных чисел. Вещественные числа могут иметь десятичную часть и дробную часть, разделенные десятичной точкой. Например, "3.14" и "0.5" являются вещественными числами.

Бинарное представление данных, с другой стороны, использует двоичную систему счисления, в которой числа представлены с помощью двух символов: "0" и "1" и каждая цифра называется битом (от англ. "binary digit"). Например, число "5" может быть представлено в бинарном виде как "101".

Основное отличие между вещественным и бинарным представлением данных заключается в способе кодирования чисел. Вещественные числа обычно кодируются с использованием стандартов, таких как IEEE 754, который определяет форматы для представления чисел с плавающей точкой. В языке MQL5 для вещественных чисел используется тип данных "double", который может описать в сумме 16 значащих цифр в числе. Это означает, что общее количество цифр не может быть больше шестнадцати, к примеру, "9 999 999 999 999 999.0" и "9 999 999.999 999 99" и "0.999 999 999 999 999 9" имеют шестнадцать цифр "9" в суммарном количестве до и после запятой. Почему это важно мы разберёмся позже.

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

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

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

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

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

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

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

3. Преимущество представления бинарным кодом Грея

При всех достоинствах бинарного представления оно имеет существенный недостаток: два близлежащих десятичных числа в бинарном представлении могут отличаться сразу на несколько битов. Например, в бинарном коде переход от 7 (0111) к 8 (1000) влечет изменение всех четырех битов. Это означает, что требуется разное количество битовых операций между разными близкими числами, что приводит к неравномерной вероятности исходов в пространстве поиска, возникновению своеобразных "полос повышенной вероятности" и наоборот - "слепых зон" в оптимизируемых параметрах.

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

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

Ранее мы обсуждали, что число "double" может быть представлено только 16 значимыми цифрами. Давайте рассмотрим пример, чтобы лучше понять, как это может влиять на практике.

Предположим, у нас есть число с 15 значимыми "0" и "1" в 16-м разряде: "0.0000000000000001". Теперь добавим к этому числу 1.0 и получим "1.0000000000000000". Заметим, что цифра "1" в 16-м разряде исчезла, и у нас осталось 15 значимых цифр после запятой. При добавлении нового разряда в целой части числа "double", значимые цифры сдвигаются влево. Таким образом, если у нас есть ненулевая целая часть, мы не можем гарантировать точность до 16-го разряда после запятой.

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

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

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

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

min = -156.675 и max = 456.6789

тогда расстояние между "max" и "min" равно:

distance = max - min = 456.6789 - (-156.675) = 613.3539

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

613 (decimal) = 1 1 0 1 0 1 0 1 1 1 (binary Gray)

Тогда дробная часть будет выглядеть так:

3539 (decimal) = 1 0 1 1 0 0 1 1 1 0 1 0 (binary Gray)

Мы можем хранить целую и дробные части в одной строке, помня при этом используемые количество знаков для обеих частей, что нам позволит с легкостью провести обратное преобразование. В итоге вещественное число будет выглядеть так (знак ":" условно разделяет целую и дробную части):

613.3539 (decimal) =  1 1 0 1 0 1 0 1 1 1  :  1 0 1 1 0 0 1 1 1 0 1 0 (binary Gray)

Таким образом, мы можем преобразовывать любое вещественное число в пределах 16 разрядов в целой части и 16 разрядов после запятой в дробной части для чисел типа double. Более того, это позволяет нам иметь более 16 значащих цифр в общей сумме разрядов, даже до 32 значащих разрядов и более (ограничено длиной записи числа типа ulong, используемого в функциях для работы с преобразованиями целых десятичных чисел в код Грея и обратно).

Для обеспечения точности дробной части до 16-го знака нам потребуется преобразовать число "9 999 999 999 999 999" (максимально возможное число дробной части):

9999999999999999 (decimal) = 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binary Gray)

Тогда итоговая запись нашего числа 613.9999999999999999 (да да, 16 разрядов после запятой) будет выглядеть так:

613.9999999999999999 (decimal) = 1 1 0 1 0 1 0 1 1 1  :  1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binary Gray)

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

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

Функция "DecimalToGray" принимает в качестве параметров десятичное число "decimalNumber" и ссылку на массив "array", в котором будет храниться результат преобразования. Она выполняет преобразование числа из десятичной системы счисления в код Грея. Для этого она сначала вычисляет значение кода Грея "grayCode", применяя побитовую операцию XOR между "decimalNumber" и его сдвигом на один бит вправо. Затем она вызывает функцию "IntegerToBinary", чтобы преобразовать полученное значение "grayCode" в бинарное представление и сохранить его в массив "array". Для массива используется наиболее экономное хранение целых чисел типом char.

Функция "IntegerToBinary" принимает в качестве параметров число "number" и ссылку на массив "array", в котором будет храниться результат преобразования. Она выполняет преобразование числа из десятичной системы счисления в бинарную систему счисления. В цикле она получает остаток от деления "number" на 2 и добавляет его в массив "array". Затем она делит "number" на 2 и увеличивает счетчик "cnt". Цикл продолжается до тех пор, пока "number" больше нуля. После цикла массив "array" переворачивается, чтобы получить правильный порядок битов.

Функция "GrayToDecimal" принимает в качестве параметров ссылку на массив "grayCode", начальный индекс "startInd" и конечный индекс "endInd". Она выполняет преобразование числа из кода Грея в десятичную систему счисления. Сначала она вызывает функцию "BinaryToInteger", чтобы преобразовать массив "grayCode" в бинарное представление и сохранить его в переменную "grayCodeS". Затем она инициализирует переменную "result" значением "grayCodeS". Затем она выполняет цикл, в котором сдвигает "grayCodeS" на один бит вправо и применяет побитовую операцию XOR с "result". Цикл продолжается до тех пор, пока "grayCodeS" сдвигается вправо и больше нуля. В конце функция возвращает значение "result".

Функция "BinaryToInteger" принимает в качестве параметров ссылку на массив "binaryStr", начальный индекс "startInd" и конечный индекс "endInd". Она выполняет преобразование числа из бинарной системы счисления в десятичную систему счисления. Функция инициализирует переменную "result" нулем. Затем она выполняет цикл, в котором сдвигает "result" на один бит влево и добавляет значение "binaryStr[i]" (бит) к "result". Цикл продолжается от "startInd" до "endInd". В конце функция возвращает значение "result".

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

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4. Методы селекции

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

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

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

• Ранговая селекция (Rank Selection)  —   в этом методе особи ранжируются по их приспособленности, и вероятность выбора особи зависит от ее ранга. Чем выше ранг особи, тем больше шансов у нее быть выбранной. Ранговая селекция может быть полностью пропорциональной, где вероятность выбора особи пропорциональна ее рангу (порядковому номеру), или частично пропорциональной, где вероятность выбора особи увеличивается с ростом ранга по нелинейному закону. Ранговая селекция имеет ряд преимуществ. Во-первых, она позволяет сохранить разнообразие в популяции, поскольку менее приспособленные особи также имеют шанс быть выбранными. Во-вторых, она позволяет избежать проблемы преждевременной сходимости, когда популяция слишком быстро сходится к локальному оптимуму. Ранговая селекция способствует сохранению разнообразия и исследованию более широкого пространства решений. Ранговая селекция схожа с равномерной селекцией, но делает больше упор на выбор более приспособленных особей оставляя шанс быть выбранным менее приспособленным.
  

• Турнирная селекция (Tournament Selection)  — в этом методе случайным образом выбирается небольшое подмножество особей (называемое турниром), и из этого подмножества выбирается особь с наибольшей приспособленностью. Размер турнира определяет, сколько особей будет участвовать в каждом турнире. Турнирная селекция позволяет сохранять разнообразие в популяции, так как даже менее приспособленные особи могут быть выбраны благодаря случайности. Турнирная селекция имеет несколько преимуществ. Во-первых, она позволяет учитывать случайность при выборе родителей, что способствует разнообразию потомства. Во-вторых, она позволяет выбирать родителей из любой области популяции, включая как лучших особей, так и менее приспособленные особи. Турнирная селекция является одним из основных методов выбора родителей в эволюционных алгоритмах и часто используется в сочетании с другими операторами, такими как скрещивание (crossover) и мутация (mutation), для создания нового потомства и продолжения эволюции популяции.
  

• Селекция по рулетке (Roulette Wheel Selection)  — в этом методе каждая особь представлена на воображаемом колесе рулетки пропорционально ее приспособленности. Колесо рулетки "вращается", и выбирается особь, на которую указывает "указатель". Чем выше приспособленность особи, тем больше сектор колеса рулетки она занимает, и тем больше шансов быть выбранной. Селекция по рулетке позволяет выбирать родителей с вероятностями, пропорциональными их приспособленности. Особи с более высокой приспособленностью имеют больший шанс быть выбранными, но даже менее приспособленные особи имеют ненулевую вероятность выбора. Это позволяет сохранить генетическое разнообразие в популяции и исследовать различные регионы пространства поиска решений. Однако следует отметить, что селекция по рулетке может иметь проблему с преждевременной сходимостью, особенно если приспособленности особей сильно различаются. Особи с высокой приспособленностью будут иметь намного больший шанс быть выбранными, что может привести к потере генетического разнообразия, "забиванию" популяции однотипными решениями и застреванию в локальных оптимумах.

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

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

5. Виды метода "кроссовер"

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

Кроссовер работает на уровне генотипов и позволяет комбинировать гены родительских особей для создания новых потомков.

Общий принцип работы метода "кроссовер" заключается в следующем:

1. Выбор родительских особей: из популяции выбираются две особи или несколько особей, которые будут скрещиваться.
   
2. Определение точки скрещивания: точка скрещивания определяет место, где хромосомы родителей будут разделены для создания потомства.
3. Создание потомства: хромосомы родителей разделяются в точке скрещивания, и части хромосом обоих родителей комбинируются для создания нового генотипа потомка. В результате кроссовера образуется один или несколько потомков, которые могут иметь комбинацию генов от обоих родителей.

Рисунок 1. Общий принцип работы метода "кроссовер".

Перечислим основные виды бинарного кроссовера:

• Одноточечный кроссовер (Single-Point Crossover): две хромосомы разделяются в случайной точке, и образуются два потомка путем обмена сегментами хромосом родителей после этой точки.
• Многоточечный кроссовер (Multi-Point Crossover): аналогичен одноточечному, но с несколькими точками разрыва, между которыми сегменты хромосом обмениваются.
  
• Равномерный (uniform) кроссовер: каждый бит потомка выбирается независимо от одного из родителей с равной вероятностью.
  
• Циклический кроссовер (Cycle Crossover): определяет циклы позиций, которые будут обменены между родителями, сохраняя уникальность элементов.
• PMX (Partially Mapped Crossover): сохраняет относительный порядок и позицию элементов из родительских хромосом, используется в задачах, где важен порядок, например, в задаче коммивояжера.
• ОX (Order Crossover): создает потомка, сохраняя порядок генов одного из родителей и наследуя недостающие гены от другого родителя в порядке их появления.
  

Так же кроссоверы применяют не только для бинарного представления, но и для вещественного, т.е, основные виды вещественного кроссовера включают в себя:

• Блендовый кроссовер (BLX-α): создает потомков, значения которых выбираются случайно внутри диапазона, определенного значениями родителей и параметром "α", который расширяет этот диапазон.
• Симметричный блендовый кроссовер (SBX): использует различные распределения вероятностей для генерации потомков, значения которых находятся между значениями родителей, с учетом степени различия между родителями.
  
• Вещественный кодированный кроссовер (real-coded crossover): применяет арифметические операции к вещественным числам, например, путем усреднения или взвешенного суммирования значений родителей.
  
• Дифференциальный кроссовер (Differential Crossover): используется, например, в дифференциальной эволюции, где новый вектор генерируется путем добавления взвешенной разницы между двумя индивидами к третьему.
  
• Интерполяционный кроссовер (Interpolation Crossover): создает потомков путем интерполяции между значениями родителей, что может включать линейную или нелинейную интерполяцию.
  
• Кроссовер с нормальным распределением (Normal Distribution Crossover): потомки генерируются с использованием нормального распределения вокруг значений родителей, что позволяет исследовать пространство решений вокруг родительских точек.
  

6. Виды метода "мутация"

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

В биологии мутация встречается крайне редко и обычно оказывает ограниченное влияние на потомство. Количество особей каждого вида в природе исчисляется миллионами, поэтому генетический материал популяции очень разнообразен, если, конечно, речь не идёт об исчезающих видах (даже есть определение "бутылочного горлышка" - это минимальное количество особей, ниже которого вид исчезнет). В отличие от живой природы в большинстве реализаций генетических алгоритмов мутации также являются редким явлением, примерно на уровне 1-2%. Это особенно важно в генетических алгоритмах, где размер популяции обычно невелик, и близкородственное скрещивание может стать проблемой, а эволюционные тупики встречаются чаще, чем в биологической эволюции. В биологии мы обычно говорим о популяциях, состоящих из миллионов особей, в то время как в генетических алгоритмах (и в алгоритмах оптимизации вообще) мы имеем дело всего с десятками или сотнями особей и мутация является единственным способом добавить новую информацию в генофонд популяции.

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

Итак, мутация играет несколько важных ролей:

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

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

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

• Одноточечная мутация (single-point mutation): в этом случае происходит инверсия значения одного случайно выбранного бита в бинарной строке. Например, если у нас есть строка "101010", то одноточечная мутация может изменить ее на "100010".
• Многоточечная мутация (multi-point mutation): в этом случае выбирается несколько случайных позиций в бинарной строке, и значения на этих позициях инвертируются. Например, если у нас есть строка "101010", то многоточечная мутация может изменить ее на "100000" или "001010".
  
• Мутация с вероятностью изменения каждого бита (probability-based mutation) или стохастической мутацией (stochastic mutation): в этом случае каждый бит имеет определенную вероятность измениться при мутации.
  
• Инверсия полная (complete inversion): в этом случае происходит полная инверсия битов в бинарной строке. Например, если у нас есть строка "101010", то инверсия изменит ее на "010101".
• Инверсия точечная (point inversion): в этом случае случайно выбирается точка разрыва в генетической последовательности, хромосома делится на две части в этой точке и части меняются местами.  

Рисунок 2. Мутация с вероятностью изменения каждого бита (probability-based mutation).

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

• Оператор случайной мутации (Random Mutation Operator).
• Оператор гауссовой мутации (Gaussian Mutation Operator).
• Арифметический оператор вещественного сдвига, также известный как arithmetic real number creep operator.
• Геометрический оператор вещественного сдвига, также известный как geometrical real number creep operator.
• Степенной (power) оператор мутации.
• Оператор неравномерной мутации Михалевича (Michalewicz's non-uniform operator).
• Динамический (dynamic) оператор мутации.

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

7. Выводы

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