Генетические алгоритмы

Генетические алгоритмы представляют собой эвристические, стохастические методы оптимизации, которые были предложены впервые в 1975 году Холландом. В их основу положена идея эволюции с естественным отбором, которая предлагалась еще Дарвином.

Генетические алгоритмы работают с множеством особей, то есть популяцией, где каждая особь может послужить решением какой-то определенной проблемы. Каждую особь приходится оценивать на степень ее приспособленности в зависимости от того, насколько хорошим является решение задачи, соответствующее ей. Если рассматривать это в соотношении с природой, то там оценивается степень эффективности организма при конкурентной борьбе за ресурсы. Особи, которые заметно сильнее приспособлены, могут воспроизводить потомство при помощи перекрестного скрещивания с иными представителями популяции. Это становится причиной появления новых особей, в которых сочетаются некоторые характеристики, передающиеся в наследство от родителей.

Менее приспособленные особи смогут воспроизвести потомство с меньшей вероятностью, так что свойства, которыми они обладают, будут постепенно исчезать в процессе эволюции из всей популяции. Иногда случаются спонтанные изменения в генах, или мутации. Получается, что хорошие характеристики из поколения в поколение будут распространены по всей популяции. Скрещивание особей, которые являются наиболее приспособленными, приводит к тому, что исследуются участки поиска, представляющие наибольшую перспективу. В конечном итоге находится решение задачи. Генетические алгоритмы обладают преимуществом, состоящим в том, что он находит за относительно непродолжительный промежуток времени приблизительные решения, представляющие собой оптимальные. Стоит рассмотреть данный вопрос касательно программирования.

Генетические алгоритмы состоят из следующих компонентов:

- хромосома, представляющая собой решение рассматриваемой проблемы, состоит из генов. Эта популяция хромосом считается начальной;

- набор операторов (предназначается для генерации новых решений на основе новых популяций);

- целевая функция (предназначена для того, чтобы оценивать приспособленность решений).

Для генетических алгоритмов существует стандартный набор операторов: селекция, мутация и скрещивание. Можно рассмотреть применение генетических алгоритмов при помощи уточнения того, для чего предназначен каждый конкретный оператор. Оператор селекции производит отбор хромосом в соответствии с тем, каковы значения их функций приспособленности. Тут представлены как минимум два наиболее популярных оператора: турнир и рулетка. Метод рулетки предполагает осуществление отбора особей посредством n запусков. Для каждого члена используемой популяции в колесе рулетки содержится по одному сектору необходимой величины. Члены популяции с заметно более высоким показателем приспособленности при таком отборе будут чаще выбираться, чем представители, имеющие низкую приспособленность. При турнирном методе реализуется n турниров, позволяющих выбрать n особей. В основу каждого турнира заложена выборка k элементов из популяции, при этом среди них должна быть выбрана лучшая особь.

Если и далее рассматривать алгоритмы программирования, то стоит сказать о методе, называемом скрещивание. Оператором скрещивания осуществляется обмен частями хромосом между парой или хромосомами в одной популяции.

Последний оператор – мутации – стохастическое изменение части хромосом.

Конкретное рассмотрение применения генетических алгоритмов представляет собой более объемный материал, чем может уместиться в статье, поэтому его стоит рассматривать отдельно.