Генетический алгоритм
В компьютерных науках и исследованиях операций генетический алгоритм ( ГА ) представляет собой метаэвристику , вдохновленную процессом естественного отбора , который принадлежит к более широкому классу эволюционных алгоритмов (ЭА). Генетические алгоритмы обычно используются для создания высококачественных решений задач оптимизации и поиска , полагаясь на биологически вдохновленные операторы, такие как мутация , скрещивание и отбор . [1] Некоторые примеры приложений GA включают оптимизацию деревьев решений.для повышения производительности, решение головоломок судоку , [2] оптимизация гиперпараметров , причинно-следственный вывод , [3] и т. д.
В генетическом алгоритме популяция возможных решений (называемых особями, существами, организмами или фенотипами ) задачи оптимизации эволюционирует в сторону лучших решений. Каждое решение-кандидат имеет набор свойств (их хромосомы или генотип ), которые можно мутировать и изменять; традиционно решения представлены в двоичном виде в виде строк из 0 и 1, но возможны и другие кодировки. [4]
Эволюция обычно начинается с популяции случайно сгенерированных особей и представляет собой итеративный процесс , при этом популяция в каждой итерации называется поколением . В каждом поколении оценивается приспособленность каждого человека в популяции; пригодность обычно представляет собой значение целевой функции в решаемой задаче оптимизации. Более приспособленные особи случайным образом выбираются из текущей популяции, и геном каждой особи модифицируется ( рекомбинируется и, возможно, случайным образом мутирует) для формирования нового поколения. Новое поколение решений-кандидатов затем используется в следующей итерации алгоритма .. Обычно алгоритм завершает работу, когда либо произведено максимальное количество поколений, либо достигнут удовлетворительный уровень приспособленности для популяции.
Стандартное представление каждого решения-кандидата — это массив битов (также называемый битовым набором или битовой строкой ). [4] Массивы других типов и структур могут использоваться практически таким же образом. Основное свойство, которое делает эти генетические представления удобными, заключается в том, что их части легко выравниваются благодаря их фиксированному размеру, что облегчает простые операции кроссинговера . Также можно использовать представления переменной длины, но в этом случае реализация кроссовера более сложна. Древовидные представления изучаются в генетическом программировании , а графические представления изучаются в эволюционном программировании.; сочетание как линейных хромосом, так и деревьев исследуется в программировании экспрессии генов .
Как только генетическое представление и функция пригодности определены, ГА переходит к инициализации популяции решений, а затем к ее улучшению путем повторного применения операторов мутации, скрещивания, инверсии и отбора.
Размер популяции зависит от характера проблемы, но обычно содержит несколько сотен или тысяч возможных решений. Часто начальная популяция генерируется случайным образом, допуская весь диапазон возможных решений ( пространство поиска ). Иногда решения могут быть «засеяны» в областях, где оптимальные решения могут быть найдены.
