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

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

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

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

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

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

· Эволюционные стратегии.

· Эволюционное программирование.

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

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

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

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

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

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

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