69786

Основные эволюционные алгоритмы

Контрольная

Информатика, кибернетика и программирование

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

Русский

2014-10-10

169.92 KB

16 чел.

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

Основные эволюционные алгоритмы:

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

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

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

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

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

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

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

2. Генетический алгоритм

Генетический алгоритм (ГА) [2,8,9] – это компьютерная модель эволюции популяции искусственных "особей". Каждый особь характеризуется своей хромосомой Sk, хромосома есть "геном" особи. Хромосома определяет приспособленность особи f(Sk); k = 1,..., n; n – численность популяции. Хромосома есть цепочка символов Sk = (Sk1, Sk2,...,SkN), N – длина цепочки. Символы интерпретируются как "гены" особи, расположенные в хромосоме Sk . Задача алгоритма состоит в максимизации функции приспособленности f(Sk) .

Эволюция состоит из последовательности поколений. Для каждого поколения отбираются особи с большими значениями приспособленностями. Хромосомы отобранных особей рекомбинируются и подвергаются малым мутациям. Формально, схема ГА может быть представлена следующим образом (популяция t-го поколения обозначается как {Sk(t)}):

Шаг 0 . Создать случайную начальную популяцию {Sk(0)}.

Шаг 1. Вычислить приспособленность f(Sk) каждой особи Sk популяции {Sk(t)}.

Шаг 2. Производя отбор особей Sk в соответствии с их приспособленностями f(Sk) и применяя генетические операторы (рекомбинации и точечные мутации) к отобранным особям, сформировать популяцию следующего поколения {Sk(t+1)}.

Шаг 3. Повторить шаги 1,2 для t = 0, 1, 2, ... , до тех пор, пока не выполнится некоторое условие окончания эволюционного поиска (прекращается рост максимальной приспособленности в популяции, число поколений t достигает заданного предела и т.п.).

Имеется ряд конкретных вариантов генетического алгоритма, которые отличаются по схемам отбора, рекомбинаций, по форме представления хромосом и т.д.

Наиболее традиционный вариант генетического алгоритма базируется на следующей конкретной схеме: 1) цепочки символов в хромосомах бинарны (символы Ski принимают значения 0 либо 1), длина цепочек постоянна (N = const), 2) метод отбора пропорционально-вероятностный (см. ниже), 3) рекомбинации производятся по схеме однократного кроссинговера.

Кросиговер

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

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

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

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

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

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

Цель генетических алгоритмов в том, чтобы:

- Абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе

- Моделировать естественные эволюционные процессы для эффективного решения задач науки и техники

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

Генетические алгоритмы отличаются от других оптимизационных и поисковых процедур следующим:

- Работают в основном не с параметрами задачи, а с закодированным множеством параметров

- Осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений

- Используют целевую функцию, а не ее различные приращения для оценки качества принятия решений

- Применяют не детерминированные, а вероятностные правила анализа оптимизационных задач

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

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

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

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

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

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

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

При решении практических задач с использованием генетических алгоритмов обычно выполняют четыре предварительных этапа:

  1.  Выбор способа представления решения
  2.  Разработка операторов случайных изменений
  3.  Определение способов «выживания» решений
  4.  Создание начальной популяции альтернативных решений

Суть работы

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

Основные понятия

Популяция – конечное множество особей.
Особи – хромосомы с закодированным в них множеством параметров.
Ген – атомарный элемент генотипа(свойство хромосомы).
Генотип (структура) – набор хромосом данной особи
Фенотип – набор значений, соответствующий данному генотипу (декодированная структура или множество параметров задачи) – решение, точка пространства поиска.
Аллель – значение конкретного гена, свойства или вариант свойства.
Локус (позиция) – указывает место размещения данного гена в хромосоме. А локи – это множество позиций генов.
Функция приспособленности – мера приспособленности данной особи в популяции.
Идентификация параметров – это определение неизвестных параметров антецедентов и консеквентов нечетких правил путем оптимизации работы нечеткой системы по заданному критерию.
База правил – структура описывающая логику работы апроксиматора /классификатора и состоит из правил.
 
Правила – Элемент базы правил следующего вида.
 
Для задачи аппроксимации:
 
Ri: If x1=A1i and x2=A2i and x3=A3i andandxn=Ani then y=Ψ 
где
x=(x1, x2, x3, …, xn) вектор параметров аппроксимируемой модели;
Aki – нечеткий терм, характеризующий k-ый параметр в i-том правиле; 
Ψ – числовое значение выхода аппроксиматора.
Аппроксиматор — вычислительный блок, на вход которому приходит значения параметров модели и требуется получить число, которое будет близко в модели.
Антецедент – часть правила для задачи аппроксимации, соответствующая части правила до ключевого слова
then 
Консиквент – часть правила для задачи аппроксимации, соответствующая части правила после ключевого слова
then. [1]

Нечеткая система

Нечеткое моделирование осуществляется посредством системы нечеткого вывода, которая выполняет следующие действия [2, 3]: 
1. Преобразует числовую информацию в лингвистические переменные (процесс фаззификации);
 
2. Обрабатывает лингвистическую информацию, выполняя логические операции нечеткой конъюнкции, импликации и агрегации правил;
 
3. Формирует численные результаты (процесс дефаззификации).
Процесс фаззификации описывает предметную область посредством лингвистических переменных и правил естественного языка, содержащих качественную оценку ситуации. Основой для описания ситуации является нечеткое высказывание следующего вида:
 
xi есть Ai или xi = Ai,
где
xi – некоторая величина; Ai – элемент терм-множества лингвистической переменной из исследуемой предметной области.
Обработка лингвистической информации происходит при помощи базы правил. Каждое правило состоит из двух частей: условной и заключительной. Антецедент или условная часть (ЕСЛИ–часть) содержит утверждение относительно значений входных переменных, в консеквенте или заключительной части (ТО–части) указывается значение, которое принимает выходная переменная. Таким образом, нечеткая система типа «много входов – один выход» может быть задана нечеткими правилами следующего вида:
правило 1: ЕСЛИ
x1 = А11 И x2 = А21 И … И xm = Аm1 ТО r = R1;
правило 2: ЕСЛИ
x1 = А12 И x2 = А22 И … И xm = Аm2 ТО r = R2;
………………………………………………………………………………..….….……
правило
n: ЕСЛИ x1 = А1n И x2 = А2n И … И xm = Аmn ТО r = Rn,
где
x1, x2, …, xm – входные переменные; 
r – выходная переменная; 
А
ij – нечеткие области определения входных переменных, которые определены на универсальных множествах X1, X2, …, Xm; 
Rs – значение выходной переменной, которое может быть представлено как действительное число, либо как функция, определенная на входных переменных, либо как нечеткая область определения выходной переменной. Каждая нечеткая область Аij связана с функцией принадлежности  [4].
Процесс дефаззификации зависит от типа нечеткой системы.
 
Рассмотрим нечеткая модель типа синглтон. Она задается правилами вида:
правило
i: 
ЕСЛИ
x1 = А1i И x2 = А2i И … И xm = Аmi ТО r = ai,
где
ai – действительное число.
Модель типа синглтон осуществляет отображение
 , заменяя оператор нечеткой конъюнкции произведением, а оператор агрегации нечетких правил — сложением. Отображение F определяется следующей формулой:
, (1.1)
где
 , 
n — количество правил нечеткой модели;
m — количество входных переменных в модели;
 — функция принадлежности нечеткой области.

Функции принадлежности

Функции принадлежности для нечетких систем представляют собой субъективное представление эксперта о предметной области. Часто такая субъективность помогает снизить степень неопределенности при решении слабо формализованных задач. Как правило, для задания функций принадлежности используются типовые зависимости, параметры которых определяются путем обработки мнений экспертов. Представление произвольных функций при реализации автоматизированных систем часто затруднено, поэтому в реальных разработках такие зависимости аппроксимируются кусочно-линейными функциями [5].
Выход нечёткой модели напрямую зависит от вида функции принадлежности, например, при использовании треугольных функций, получаем:
 (1.2)

Параметрическая идентификация

Параметры функции принадлежности входных переменных нечеткой системы можно представить в следующем виде:
Xromosoma=[N_xromosomi, N_ruls, N_peremennoi, [an,bn,cn] ] (1.3)
где
N_xromosomi – номер генерируемой хромосомы;
N_ruls – номер правила;
N_peremennoi – номер переменной;
[
an,bn,cn] – тройка параметров в модели типа синглтон с треугольными функциями принадлежности.
Параметры, входящие в данный вектор влияют на адекватность модели. Задача параметрической идентификации – определить неизвестные параметры консеквентов нечетких правил путем оптимизации работы нечеткой системы по заданному критерию.
Параметрическая идентификация рассматривается как процесс оптимизации нечеткой модели, который сводится к нахождению таких параметров нечеткой системы, чтобы ошибка вывода была минимальной.
 
При этом оценивается качество нечеткого вывода по значениям ошибки вывода (– разницы между значениями выходной переменной из таблицы наблюдений
f(x) и значениями F(x), полученными нечеткой системой. Исследуются три типа ошибки вывода:
Среднеквадратичная ошибка:
 
 (1.4)
Среднеабсолютная ошибка:
 (1.5)
Максимальная ошибка:
 (1.6)
Ошибки вывода представляются в следующем виде:
Error_for_xromosoma=[N_xromosomi, N_type_error] (1.7)
где
N_xromosomi – номер хромосомы,
N_type_error-тип ошибки.
Для задач параметрической идентификации нечеткой системы адаптируется алгоритм эволюционной стратегии [1].

Эволюционная стратегия

Эволюционная стратегия — эвристический метод оптимизации в разделе эволюционных алгоритмов, основанный на адаптации и эволюции. Стратегия основана на механизмах естественного отбора и наследования. В ней используется принцип выживания наиболее приспособленных особей. Преимущества алгоритма перед другими методами оптимизации заключаются в параллельной обработке множества альтернативных решений. [3]
Алгоритм работает с популяцией особей (хромосом), каждая из которых представляет собой упорядоченный набор параметров задачи, подлежащих оптимизации. Основной характеристикой каждой особи является ее мера приспособленности.
При поиске решения в эволюционной стратегии вначале происходит мутация и скрещивание особей для получения потомков, затем происходит детерминированный отбор без повторений лучших особей из общего поколения родителей и потомков. В качестве мутации часто используется добавление нормально распределенной случайной величины к каждой компоненте хромосомы. При этом параметры нормального распределения самоадаптируются в процессе выполнения алгоритма.
 
Работа алгоритма представляет собой итерационный процесс, который продолжается до выполнения одного из условий останова:
• выполнение заданного числа поколений;
• прекращение улучшения популяции.

Алгоритм эволюционной стратегии для настройки нечеткой системы

Классический алгоритм эволюционной стратегии для настройки нечеткой системы приведен ниже:
Вход:
Таблица наблюдений;
Выход:
Оптимизированная база правил. Значение ошибки нечеткого вывода.
Алгоритм:
Шаг 1. Задание количества термов
Шаг 2. Построение базы правил для каждой хромосомы:
• Построение нечетких термов, равномерно распределенных по каждой переменной
• Задание консеквентов для каждого правила методом ближайшего из таблицы наблюдение
Шаг 3. Генерация хромосом
Шаг 4. Подсчет ошибок
Шаг 5. Выбор параметров алгоритма эволюционной стратегии:
• задание количества итераций
• количество точек скрещивание и алгоритм скрещивание
• вероятность мутации
• тип алгоритма селекции
Шаг 6. Генерация начальной популяции
Шаг 7. Вычисление меры приспособленности.
 
Если достигнуто условие выхода Шаг 11, иначе Шаг 8
Шаг 8. Применение алгоритма скрещивания
Шаг 9. Применение алгоритма мутации
Шаг 10. Селекция и отбор хромосом для новой популяции. Переход на Шаг 7
Шаг 11. Вывод решения – «наилучшей» хромосомы

Алгоритмическая часть программы

В среде визуального программирования Microsoft Visual Studio 2010 была написана программа, предназначенная для параметрической идентификации нечетких систем, в основе которой лежат алгоритм эволюционной стратегии.
Входными данными является таблица наблюдений, выходными – набор параметров нечеткой системы, обеспечивающий наиболее адекватное построение модели, и значения основных ошибок, по которым оценивается адекватность.
 
Реализованы несколько типов оператора скрещивания: многоточечный и унифицированный тип. Селекция – случайный отбор, турнирный отбор, рулеточный отбор и стратегия элитаризма. В результате применения оператора мутации случайным образом вносятся изменения в гены некоторых особей. Исследована многоточечная случайная мутации.

Заключение

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

Литература

1. S. Hoche, and S. Wrobel. A Comparative Evaluation of Feature Set Evolution Strategies for Multirelational Boosting. Proc. 13th Int. Conf. on ILP 2003.
2. Espinosa J., Vandewalle J., Wertz V. Fuzzy logic, identification and predictive control. — London: Springer-Verlag, 2005. — 263 p.
3.
Рутковская Д., Пилиньский М., Рутковский Л.: Нейронные сети, генетические алгоритмы и нечеткие системы. — М.: Горячая линия-телеком, 2006. — 452 с.
4. Ходашинский И.А. Технология идентификации нечетких моделей типа синглтон и Мамдани. / Труды
VII международной конференции «Идентификация систем и задачи управления» SICPRO ’08. Москва, 28-31 января 2008 г. Институт проблем управления им. В.А. Трапезникова РАН. — М: Институт проблем управления им. В.А. Трапезникова РАН, 2008. — С. 137-163.
5. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. — М.: «Нолидж», 2000. 352
c.
6. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. — М.: Высш. шк., 2005. — 544
c