Участник:Kilkavteste 607/Генетический алгоритм
Свойства и структура алгоритма
Общее описание алгоритма
Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Можно выделить следующие этапы генетического алгоритма:
- Задание целевой функции (функции приспособленности) для особей популяции
- Создание начальной популяции
- Цикл (пока не выполнится критерий останова):
- Размножение (скрещивание)
- Мутирование
- [Кросиннговер] - по желанию
- Вычисление значения целевой функции для всех особей, полученных в результате предыдущих этапов цикла
- Формирование нового поколения (селекция)
Критериями останова могут служить:
- нахождение глобального, либо субоптимального решения;
- исчерпание числа поколений, отпущенных на эволюцию;
- исчерпание времени, отпущенного на эволюцию.
Необходимо заметить, что не существует общепринятых стандартов реализации генетического алгоритма, поэтому каждый может самостоятельно решить, как именно он будет реализовывать конкретный этап эволюционного процесса.