Генетические алгоритмы
Генетические алгоритмы - это метод решения задач оптимизации. В методе используются идеи, почерпнутые из эволюционной биологии: наследование признаков, мутация, естественный отбор и кроссовер []. Определяется множество кандидатов, среди которых ищется решение задачи. Кандидаты представляются в виде списков, деревьев или иных структур данных.
Общая схема генетического алгоритма выглядит следующим образом:
- создать начальный набор кандидатов;
- оценить качество каждого кандидата в текущем наборе;
- выбрать пары наиболее качественных кандидатов для воспроизводства;
- применить оператор кроссовера;
- применить оператор мутации;
- если не выполнено условие останова, перейти к шагу 2.
Начальный набор кандидатов, как правило, формируется случайным образом. На множестве кандидатов определяется оценочная функция, задающая качество кандидата, то есть то, насколько он близок к верному решению. При выборе кандидатов для воспроизводства более качественные кандидаты имеют больше шансов. По двум выбранным кандидатам предыдущего поколения оператор кроссовера строит кандидата следующего поколения. Оператор мутации вносит малые случайные изменения кандидатов. Алгоритм завершается, когда выполняется условие останова. Часто используются следующие условия останова:
- достигается заданное количество поколений;
- найдено верное решение;
- за заданное количество итераций максимальное качество кандидатов в популяции не улучшилось;
- различные комбинации предыдущих условий.
Генетические алгоритмы позволяют решать задачи, для которых не применимы традиционные методы оптимизации. Одной из областей применения генетических алгоритмов является автоматическая генерация тестов для программного обеспечения.