Применение генетических алгоритмов для решения оптимизационных задач

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

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

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

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

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

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