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

Генетический алгоритм (ГА) разработан Джоном Голландом (John Holland) в 1975 году в Мичиганском университете.

В дальнейшем Д. Голдберг (D. Goldberg) выдвинул ряд гипотез и теорий, помогающих глубже понять природу генетических алгоритмов.

К.ДеДжонг (K. DeJong) первым обратил внимание на важность настройки параметров ГА для общей эффективности работы и предложил свой оптимальный вариант подбора параметров, который послужил основой для всех дальнейших исследований.

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

Так как алгоритм в процессе поиска использует некоторую кодировку множества параметров вместо самих параметров, то он может эффективно применяться для решения задач дискретной оптимизации, определённых как на числовых множествах, так и на конечных множествах произвольной природы.

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

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

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

Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975).

Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином (1857).

ГА работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы.

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

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

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

Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.

Компоненты ГА

1. Хромосома. Решение рассматриваемой проблемы. Состоит из генов.

2. Начальная популяция хромосом.

3. Набор операторов для генерации новых решений из предыдущей популяции.

4. Целевая функция для оценки приспособленности (fitness) решений.

Чтобы применять ГА к задаче, сначала выбирается метод кодирование решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строк представляет возможное решение задачи. По существу, такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов в строке - хромосоме.