Сущность эволюционного подхода к вычислениям

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

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

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей эволюционного процесса. Среди этих моделей можно выделить три основные парадигмы :

  • Генетические алгоритмы.
  • Эволюционные стратегии.
  • Эволюционное программирование.

Основное отличие генетических алгоритмов заключается в представлении любой альтернативы решения в виде битовой строки фиксированной длины, манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией. То есть в данном случае применяется единое универсальное представление любой задачи. Парадигму генетических алгоритмов предложил Джон Холланд, опубликовавший в начале 60-х годов ее основные положения. А всеобщее признание она получила после выхода в свет в 1975 году его классического труда Адаптация в естественных и искусственных системах.

Эволюционные стратегии, напротив, оперируют объектами, тесно связанными с решаемой задачей. Каждая из альтернатив решения представляется единым массивом численных параметров, за каждым из которых скрывается, по сути, аргумент целевой функции. Воздействие на данные массивы осуществляется, в отличие от генетических алгоритмов, с учетом их смыслового содержания и направлено на улучшение значений входящих в них параметров. Парадигму эволюцибнных стратегий предложили в 1973 году Реченберг (I. Rechenberg) в своей работе Эволюционные стратегии: оптимизация технических систем на основе принципов биологической эволюции и в 1977 году Шефель (Н.-Р. Schwefel) в работе Численная оптимизация компьютерных моделей посредством эволюционной стратегии.

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

Особенности эволюционного подхода

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

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

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

Случайные записи:

Байесовский подход. Суть байесовской эконометрики


Похожие статьи:

Добавьте постоянную ссылку в закладки. Вы можете следить за комментариями через RSS-ленту этой статьи.
Комментарии и трекбеки сейчас закрыты.