Генетические алгоритмы относятся к категории задач искусственного интеллекта. Они представляют из себя эвристический метод поиска решения, моделирующий эволюцию видов в природе. Данный метод может быть полезен, когда явный алгоритм поиска решений неизвестен или не существует.
Генетический алгоритм требует для своей работы следующих вещей:
- Функция оценки качества решения. В терминологии эволюции — выживаемость. Использование данной функции позволит отличать более годные решения от менее годных.
- Начальный набор решений. Это может быть просто случайный набор. В эволюции — изначальный набор видов (точнее, их цепочки ДНК).
- Генетические операторы. Они обеспечивают «мутацию» отдельных решений и «скрещивание» решений друг между другом. Мутация — произвольное изменение решения. Скрещивание может представлять собой частичную комбинацию (кусок из одной «цепочки», кусок — из другой), применение какой-либо функции (сложение, умножение) и т. д.
В этом случае получаем примерный алгоритм:
- Сформировать начальный набор решений (текущая популяция размером N).
- Определить самое лучшее решение. Если оно нас устроит, то выход. Результат работы алгоритма — найденное решение.
- Применить к текущей популяции генетические операторы (провести мутацию и скрещивание) и поместить результаты в новую популяцию.
- Также добавить решения из текущей популяции в новую.
- Сгенерировать несколько случайных решений и также добавить их в новую популяцию.
- Отобрать N лучших решений из новой популяции и сделать их текущей популяцией, остальное отбросить.
- Перейти к шагу 2.
В практическом применении данной методологии возможны следующие проблемы:
- Недостаточный размер популяции. В этом случае решения, находящиеся в процессе «становления», будут отброшены слишком рано.
- Чрезмерный размер популяции. Алгоритм будет работать слишком долго.
- Плохой стартовый набор. Все N начальных решений должны быть максимально разнообразны.
- Плохие генетические операторы. Если операторов мало или они не покрывают все разнообразные возможности мутации и комбинирования решений, то процесс поиска решений будет «застревать». Впрочем, отчасти это компенсируется шагом 5.
Генетические алгоритмы применяются в задачах построения расписаний, поиска глобальных оптимумов функций и др.