Участник:Kilkavteste 607/Генетический алгоритм

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

Автор описания: А. С. Горбатова

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Можно выделить следующие этапы генетического алгоритма:

• Задание целевой функции (функции приспособленности) для особей популяции
• Создание начальной популяции
• Цикл (пока не выполнится критерий останова):

• • Размножение (скрещивание)
  • Мутирование
  • [Кросиннговер] - по желанию
  • Вычисление значения целевой функции для всех особей, полученных в результате предыдущих этапов цикла
  • Формирование нового поколения (селекция)

Критериями останова могут служить:

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

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

1.2 Математическое описание алгоритма

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

1. Функция приспособленности

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

[math] \\ F(x) = sin(x_1)\cdot sin(x_2)\cdot sin(x_3), [/math] где [math] x = (x_1, x_2, x_3) [/math]

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

2. Особь в популяции

За особь в популяции выберем трехмерный вектор вещественных чисел (геномов). Числа будут иметь особенность (ведь их нужно как-то кодировать). Воспользуемся двоичным кодированием следующим образом: выберем интервал допустимых значений аргумента функции, в нашем случае будем рассматривать интервал [math] x_i \in [-\pi; \pi] [/math]. Разобьем данный интервал на части, в зависимости от выбранной точности, в нашем случае, на [math] 2^{29} [/math]. Таким образом, для кодирования нам потребуется 30 бит. Случайным образом выбирая число от [math] 0 [/math] до [math] 2^{29} [/math] получим номер интервала. За значение аргумента примем середину этого интервала. Таким образом мы получили представление вещественных чисел с помощью двоичного кода. Алгоритм взят из .

3. Популяция

Начальная популяция будет состоять из [math] 10000 [/math] особей. Каждая особь представляет собой набор трех геномов, сформированных случайным образом, как указано в п.2.

4. Скрещивание

Для скрещивания берем 2 родителей - соседних особей по популяции (первый со вторым, третий с четвертым и так далее). После этого случайным образом определяется точка разрыва генома, затем от первого родителя берется первая часть нового генома (до точки разрыва), от второго - вторая. Таким образом получим первого потомка. Получим второго потомка, также определив случайным образом точку разрыва, взяв от второго родителя гены до точки разрыва, от первого - после. Потомки заменят в новой популяции своих родителей. (Очень семейная реализация, придумана лично мной.)

5. Мутация

В процессе мутации будут участвовать все особи. Это необходимо для поддержания разнообразия популяции. Случайным образом выбирается число от 0 до 100. Задается процент мутации. Если полученное число меньше или равно числу, равному проценту мутации, то мутация есть. Тогда выбирается еще одно случайное число от [math] 0 [/math] до [math] 29 [/math], и выбирается ген для мутации (меняем в побитовом представлении 0 на 1 или 1 на 0). Если полученное число больше числа, равного проценту мутации, то особь не мутирует. В нашем случае зададим процент мутации 20.

6. Селекция

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

7. Критерий останова

За критерий останова взято ограниченное число поколений, равное [math] 512 \cdot 10^{4} [/math].

---

Примечание: в процессе компьютерной реализации могут быть изменены некоторые точные величины.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма состоит из 3 частей:

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

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

3. Проверка приспособленности: декодирование вещественных чисел (кодировка указана в п.1.1), вычисление значения функции приспособленности для каждого представителя популяции и сравнение полученного значения с сохраненным минимумом.

1.4 Макроструктура алгоритма

1. Генерация первого поколения.
2. Оценка приспособленности первого поколения и нахождение первичного минимума.
3. Эволюция:

• Скрещивание
• Мутация
• Оценка приспособленности (поиск лучшего решения)

1.5 Схема реализации последовательного алгоритма

Входные данные:

• Функция приспособленности [math]F(x)[/math]
• Размерность функции приспособленности [math]DIM[/math]
• Интервал поиска минимума [math][a,b][/math]
• Размер популяции [math]P[/math] особей
• Количество рассматриваемых поколений [math]G[/math] (критерий останова)
• Количество бит, используемых для кодирования вещественных чисел [math]B[/math]

Генерация первого поколения:

• Генерация вектора [math]population[/math] размера [math]P*DIM[/math] случайных целых чисел из интервала [math][0, B][/math]
• Оценка приспособленности вектора [math]population[/math]: нахождение первичного минимума [math]min[/math] по всем особям популяции

Начало эволюции. Цикл по поколениям [math]g \in (0; G)[/math]

• Цикл по размерности [math]dim \in [1; DIM][/math]
  • Цикл по особям в популяции [math]p \in [1; P][/math]
    • Скрещивание();
    • Мутация();
• Проверка приспособленности текущего поколения (поиск лучшего минимума)

Конец эволюции
Выходные данные:

• Минимальное значение функции, найденное алгоритмом [math]min[/math]

1.6 Последовательная сложность алгоритма

Самыми частыми операциями в алгоритме являются генерация случайного числа, вычисление синуса, декодирование вещественного числа, обращение к памяти и перезапись нового числа. Посчитаем количество данных операций при последовательной реализации алгоритма.
Обозначения: [math]P[/math] - число особей в поколении, [math]DIM[/math] - размерность функции приспособленности [math]F(x)[/math], [math]G[/math] - количество поколений эволюции [math][/math]

1. Генерация случайного числа. Для генерации первого поколения необходимо [math]P\cdot DIM[/math] операций. Для скрещиваний в каждом поколении нужно [math]P\cdot DIM[/math] генераций случайных чисел. Для мутаций в каждом поколении минимум [math]P\cdot DIM[/math] генераций, максимум [math]2\cdot P \cdot DIM[/math]. Итого по всем поколениям: [math]P + P \cdot DIM \cdot G + 2 \cdot P \cdot DIM \cdot G = O(PG)[/math] операций генерации случайных чисел.

2. Вычисление синуса от числа. На первой популяции нужно вычислить ......