Участник: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^{32} [/math]. Таким образом, для кодирования нам потребуется 32 бита или 4 байта (что соответствует типу int в современных реализациях языка C). Случайным образом выбирая число от 0 до [math] 2^{32} [/math] получим номер интервала. За значение аргумента примем середину этого интервала. Таким образом мы получили представление вещественных чисел с помощью двоичного кода. Алгоритм взят из .

3. Популяция

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

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

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

5. Мутация

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

6. Селекция

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

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

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

---

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