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