Эволюционные вычисления и эволюционное программирование

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

Достоинства эволюционных вычислений:

· широкая область применения;

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

· пригодность для поиска в сложном пространстве решений большой размерности;

· отсутствие ограничений на вид целевой функции;

· ясность схемы и базовых принципов эволюционных вычислений;

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

Недостатки эволюционных вычислений:

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

· относительно высокая вычислительная трудоемкость, которая однако преодолевается за счет распараллеливания на уровне организации эволюционных вычислений и на уровне их непосредственной реализации в вычислительной системе;

· относительно невысокая эффективность на заключительных фазах моделирования эволюции (операторы поиска в эволюционных алгоритмах не ориентированы на быстрое попадание в локальный оптимум);

· нерешенность вопросов самоадаптации.

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

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

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

2) Оценка решения.

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

3) Генерация потомков.

3.1) Репликация путем копирования родителя.

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

3.3) Оценка потомка происходит путем определения значения его функции соответствия

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

5) Критерий останова. В качестве критерия останова могут быть следующие заданные пользователем события:

a) достижение в ходе эволюции заданного числа поколений tmax;

b) достижение заданного уровня качества, когда, например, значение функций соответствия всех особей в популяции превысило некоторое по

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

Параметры ЭП выбираются таким образом, чтобы обеспечить скорость работы алгоритма и поиск как можно лучшего решения.

 

Алгоритм имитации отжига

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

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

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

Характер изменения температуры оказывает огромное влияние на тща­тельность исследования пространства поиска и скорость сходимости алго­ритма. Наиболее очевидным вариантом является её линейное уменьшение, когда на каждом шаге алгоритма значение температуры уменьшается на не­которую константу, пока не достигнет нуля. Возможны, однако, и более сложные (и, вместе с тем, более эффективные) способы управления темпера­турой. Можно снижать температуру от значения до каждые не­сколько итераций. Значение , очевидно, должно лежать в пределах (0; 1). Также можно заранее выбрать число итераций и уменьшать значение тем­пературы через каждые несколько итераций до значения , где константу обычно выбирают равной 1, 2 или 4. Чем больше ее значение, тем медленнее будет снижаться температура.

Меметический алгоритм

Мем - единица культурного обмена, т. е. аналог гена в культуре. Мемом можно назвать жест, слово или идею; любая единица культурной информа­ции, которая может быть передана от человека к человеку путём имитации или обучения — это мем.

Мемы ведут себя так же, как и гены. Мемы передаются между поколениями, мутируют и проходят отбор. Как и гены, мемы стремятся к саморепликации. Неудачные мемы постепенно исчезают, удачные надолго закрепляются в хозяевах, разносторонне влияя на их поведение.

В общих чертах меметический алгоритм состоит из следующих этапов:

Шаг 1. Создание начальной популяции. Особи в популяции могут быть сгенерированы случайным образом либо при помощи специальной процеду­ры инициализации.

Шаг 2. Локальный поиск. Каждая из особей в популяции осуществляв поиск локального оптимума в своей окрестности. Для осуществления локального поиска Москато ис­пользовал алгоритм имитации отжига. В более поздних работах предлагались менее сложные в вычислительном отношении алгоритмы, такие, как алго­ритм подъёма. Оптимальным же является применение детерминированных алгоритмов, использующих информацию о структуре области поиска.

Шаг 3. Взаимодействие особей. Особи могут взаимодействовать двуМя способами: путём кооперации или соревнования. Кооперация. Для обмена информацией между особями может служить процедура, аналогичная применению оператора двухточечного скрещивания в генетических алгоритмах. Технически, при этом выбирается некоторый диапазон в пределах длины решения, и соответствующие сегменты двух ре­шений меняются местами. В результате получаются две новые особи, к кото­рым впоследствии применяется процедура локальной оптимизации. Соревнование. Процедура селекции в целом аналогична таковой в гене­тических алгоритмах и обычно заключается в отборе наиболее приспособ­ленных особей в популяции и исключении из неё менее приспособленных.

Шаг 4. Если не достигнут критерий окончания поиска, переход на шаг 1 иначе выбор лучшего решения из популяции. Наряду с подсчётом числа итераций и оцен­кой улучшения результата определение целесообразности окончания поиска в меметических алгоритмах может включать оценку разнообразия особей. Обычно в случае вырождения популяции бессмысленно продолжать поиск.

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

Алгоритм культурного обмена

Общие сведения. Алгоритм культурного обмена или культурный алгоритм (Cultural Algorithm, CA) является одним из направлений искусственного интеллекта, который основан на моделировании и использовании и использовании эволюционных процессов общественных структур. Он представляет собой совокупность двух пространств, взаимодействие между которыми определяется соответствующим протоколом или набором правил (рисунок 1).

Первое пространство – это «общество», второе – «общественное мнение». Компонента «общество» состоит из индивидуумов, каждый из которых обладает собственным видением решения проблемы в исследуемой сфере. Лучшие (по установленным критериям) из таких суждений, за период существования поколения общества, формирует компоненту «Общественное мнение». Протокол (передача-влияние), в свою очередь, определяет меняющуюся с течением времени зависимость одного компонента от другого: обновление пространства мнений при появлении новых поколений и влияние полученных текущих решений на генерацию новых. Описание работы алгоритма представлено с помощью диаграммы деятельности UML (рисунок 2).

Робототехника

Распознавание образов

Кластерный анализ

Построение деревьев решений

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

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

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