Генетический алгоритм является методом для решения как ограниченных, так и без ограничений задач оптимизации, который основан на естественном выборе, процессе, который управляет биологической эволюцией. Генетический алгоритм неоднократно модифицирует население отдельных решений. На каждом шаге генетический алгоритм выбирает индивидуумов наугад из текущего населения, чтобы быть родительскими элементами, и использует их, чтобы производить детей для следующей генерации. На протяжении последующих поколений население «развивается» к оптимальному решению. Можно применить генетический алгоритм, чтобы решить множество задач оптимизации, которые плохо подходят для стандартных алгоритмов оптимизации, включая задачи, в которых целевая функция является прерывистой, недифференцируемой, стохастической или сильно нелинейной. Генетический алгоритм может решить проблемы mixed integer programming, где некоторые компоненты ограничены целочисленными.
Генетический алгоритм использует три основных типа правил на каждом шаге, чтобы создать следующую генерацию из текущего населения:
Правила отбора выбирают индивидуумов, называемых родительскими элементами, которые вносят вклад в население в следующей генерации.
Правила Crossover объединяют два родительских элементов, чтобы сформировать детей для следующей генерации.
Правила мутации применяют случайные изменения к отдельным родительским элементам для формирования детей.
Генетический алгоритм отличается от классического, основанного на производной, алгоритма оптимизации двумя основными способами, как обобщено в следующей таблице.
| Классический алгоритм | Генетический алгоритм |
|---|---|
Генерирует одну точку в каждой итерации. Последовательность точек приближается к оптимальному решению. | Генерирует население точек при каждой итерации. Лучшая точка в населении приближается к оптимальному решению. |
Выбирает следующую точку последовательности путем детерминированного расчета. | Выбирает следующее население путем расчета, которое использует генераторы случайных чисел. |