Генетические алгоритмы

Генетические алгоритмы

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

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

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

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

ГА производит над особями следующие действия

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

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

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

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

Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
double func(double x)
{
  return sin(M_PI * x / 180) - 1 / x;
}
double mutation(double x0, double x1)  // мутация: генерация случайной величины
{
  const int NUM = 100000000;
  return fabs((double)((rand() * NUM) % (int)((x1 - x0)*NUM) + 1) / NUM) + x0;
}
double inversion(double x, double eps)  // инверсия: поиск в окрестностях точки
{
  static int sign = 0;
  sign++;
  sign %= 2;
  if (sign == 0) return x - eps;
  else return x + eps;
}
void crossover(double *x, double eps, double x0, double x1)  // кроссовер: среднее арифметическое
{
  int k = 99;
  for (int i = 0; i < 8; i++) 
    for (int j = i + 1; j < 8; j++) 
    {
      x[k] = (x[i] + x[j]) / 2;
      k--;
    }
  for (int i = 0; i < 8; i++) 
  {
    x[k] = inversion(x[i], eps); k--;
    x[k] = inversion(x[i], eps); k--;
  }
  for (int i = 8; i < k; i++)
    x[i] = mutation(x0, x1);
}
void sort(double *x, double *y)  // сортировка
{
  for (int i = 0; i < 100; i++)
    for (int j = i + 1; j < 100; j++) 
      if (fabs(y[j]) < fabs(y[i])) {
        double temp = y[i];
        y[i] = y[j];
        y[j] = temp;
        temp = x[i];
        x[i] = x[j];
        x[j] = temp;
      }
}
double genetic(double x0, double x1, double eps)  // поиск решения с использованием ГА
{
  double population[100];
  double f[100];
  int iter = 0;
  for (int i = 0; i < 100; i++)   // Формирование начальной популяции
  {
    population[i] = mutation(x0, x1);
    f[i] = func(population[i]);
  }
  sort(population, f);
  do {
    iter++;
    crossover(population, eps, x0, x1);
    for (int i = 0; i < 100; i++) 
      f[i] = func(population[i]);
    sort(population, f);
  } while (fabs(f[0]) > eps && iter<20000);
  cout << iter << " iterations" << endl;
  return population[0];
}
int main() 
{
  srand(time(NULL));
  cout << genetic(1.0, 10.0, 0.000001);
  cin.get();
  return 0;
}

Результат выполнения
Генетический алгоритм: результат выполнения

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

Прокрутить вверх