Генетический алгоритм поиска экстремума функции

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

Использование

• задать свою функцию f(x) в main.cpp
• скомпилировать программу: g++ -Wall -std=c++11 main.cpp -o main
• отредактировать config.txt под свою задачу
• запустить: ./main в Linux или main.exe в Windows

Описание конфигурационного файла

Программа позволяет задавать следующие параметры:

• mode — режим поиска, варианты min или max для поиска минимума и максимума соответственно

• left_border — левая граница пространства поиска

• right_border — правая граница пространства поиска

• population_size — размер начальной популяции

• max_epochs — максимальное количество эпох

• max_valueless_epochs — количество эпох без улучшения

• quality_epsilon — точность улучшения

• preserved_part — доля/количество защищаемых лучших особей

• selection — режим селекции, варианты: random — случайная, tournament — турнир, roulette — рулетка и cut — отсечением

• selection_part — доля/количество особей, дающих потомство

• crossbreeding — режим скрещивания, варианты: one_point — одноточечное, two_point — двухточечное, uniform — однородное

• mutation — метод мутации, варианты: random — инверсия одного бита, swap — обмен двух битов, reverse — перестановка в обратном порядке последовательности битов

• mutation_probability — вероятность мутации

• debug — использование режима отладки, вывод популяции на каждой эпохе

Устройство особи

Поскольку наиболее естественным видом генома является битовое представление, то и здесь хромосома, являющаяся представление вещественного числа, состоит из целого числа размером M бит. Для получения самого вещественного числа достаточно выполнить простое преобразование вида x = a + bits * (b - a) / 2^M.

Помимо целого числа особь также содержит вещественное число score для хранения значения функции приспособленности (в данном случае для значения оптимизируемой функции f(x)).

Поддерживаемые виды селекции

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

Поддерживаемые виды скрещивания

• одноточечное — случайным образом выбирается одна точка и относительно неё особи обмениваются частями
• двухточечное — аналогично двухточечному, однако выбирается две точки вместо одной
• однородное — равновероятно выбирается бит одного из двух родителей

Поддерживаемые виды мутации

• случайная — случайно выбирается один бит и заменяется противоположным значением
• обменом — случайно выбираются два бита и меняются местами
• перестановкой — случайно выбирается точка и все биты от неё и до старшего бита разворачиваются в обратном порядке

Пример запуска

mode: max
search space: [1, 9]

population size: 25

max epochs: 100
max valueless epochs: 5
quality epsilon: 1e-07
preserved positions: 2

selection: roullete
selection size: 10

crossbreeding: two point
mutation: reverse (0.2)
Epoch 0 best: f(x) = 0.357056, where x = 3.03472
Epoch 1 best: f(x) = 0.363856, where x = 2.76504
Epoch 2 best: f(x) = 0.415285, where x = 5.69276
Epoch 3 best: f(x) = 0.415285, where x = 5.69276
Score has not improved, (iteration: 1)
Epoch 4 best: f(x) = 0.474836, where x = 5.7123
Epoch 5 best: f(x) = 0.474836, where x = 5.7123
Score has not improved, (iteration: 1)
Epoch 6 best: f(x) = 0.612782, where x = 5.76096
Epoch 7 best: f(x) = 0.935024, where x = 5.94472
Epoch 8 best: f(x) = 0.935024, where x = 5.94472
Score has not improved, (iteration: 1)
Epoch 9 best: f(x) = 0.935024, where x = 5.94472
Score has not improved, (iteration: 2)
Epoch 10        best: f(x) = 0.935024, where x = 5.94472
Score has not improved, (iteration: 3)
Epoch 11        best: f(x) = 0.935024, where x = 5.94472
Score has not improved, (iteration: 4)
Epoch 12        best: f(x) = 0.935024, where x = 5.94472
Score has not improved over 5 epoches