Эволюционные вычисления

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

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

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

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

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

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

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

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

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

· эволюционные стратегии;

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

Парадигма генетических алгоритмов была предложена Джоном Холландом (Holland J.H.) в начале 1960-х гг. [21]. Основное отличие генетических алгоритмов заключается в представлении любого варианта решения в виде битовой строки фиксированной длины, манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией. То есть в данном случае применяется единое универсальное представление любой задачи.

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

В основе направления эволюционного программирования лежит идея представления альтернатив в виде универсальных конечных автоматов, способных реагировать на стимулы, поступающие из окружающей среды. Соответствующим образом разрабатывались и операторы воздействия на них. Идеи эволюционного программирования были предложены в 1966 году Фогелем, Оуэнсом и Уолшем (Fogel L.J., Owens A.J., Walsh M.J.).

Дата добавления: 2014-12-29