Выбор признаков с помощью генетических алгоритмов (пример)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Описание алгоритма)
(→Описание алгоритма)
Строка 16: Строка 16:
Свободные параметры: размер популяции, доля кроссоверинга ( доля особей одного поколения, подвергающихся кроссоверингу ).
Свободные параметры: размер популяции, доля кроссоверинга ( доля особей одного поколения, подвергающихся кроссоверингу ).
#Инициализация( создание начальной популяции необходимого размера ). Хромосомы особей представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: <tex>n=0.</tex>
#Инициализация( создание начальной популяции необходимого размера ). Хромосомы особей представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: <tex>n=0.</tex>
-
#<tex>n:=n+1</tex>. Проверка условий завершения: либо <tex>n</tex> превысило максимально допустимое значение, либо изменения целевой функции SSE для лучшей особи в популяции за некоторое число итераций оказалось слишком малым.
+
#<tex>n:=n+1.</tex> Проверка условий завершения: либо <tex>n</tex> превысило максимально допустимое значение, либо изменения целевой функции SSE для лучшей особи в популяции за некоторое число итераций оказалось слишком малым.
#Селекция( выбор особей для следующего поколения ). Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
#Селекция( выбор особей для следующего поколения ). Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
#Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. [[Генетический алгоритм|Оператор скрещивания]] ). В результате этой операции каждая аллель ( т. е. позиция в хромосоме особи ) случайным образом заполняется геном 1-ого или 2-ого родителя.
#Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. [[Генетический алгоритм|Оператор скрещивания]] ). В результате этой операции каждая аллель ( т. е. позиция в хромосоме особи ) случайным образом заполняется геном 1-ого или 2-ого родителя.

Версия 20:28, 28 апреля 2010

Содержание

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

Постановка задачи

Задана выборка — множество \{x_1,...,x_n|x_i\in\mathbb{R}^M\} значений свободных переменных и множество \{y_1,...,y_n| y_i\in\mathbb{R}\} соответствующих им значений зависимой переменной. Задано множество порождающих функций линейной регрессионной модели \{\mathbf{f}_1,...,\mathbf{f}_N\}, где \mathbf{f}_i:\: \mathbb{R}^M \to \mathbb{R}. Введем обозначения:
c\in\{0,1\}^N, F(c) =\left(\begin{array}{ccc} \mathbf{f}_{i_1}(x_1) & \ldots & \mathbf{f}_{i_k}(x_1)\\ \mathbf{f}_{i_1}(x_2) & \ldots & \mathbf{f}_{i_k}(x_2)\\ \ldots & \ldots & \ldots \\ \mathbf{f}_{i_1}(x_n) & \ldots & \mathbf{f}_{i_k}(x_n)\\ \end{array} \right) , k = ||c||_1,\; {\{i_j\}_{j=1}}^k \subset \{ 1,...,N \}\;: \; c(i_j)=1 при j=1,...,k;
\mathbf{w(c)} = (F(c)^TF(c))^{-1}F(c)^T\mathbf{y};
\mathbf{y(c)} = F(c)\mathbf{w(c)}.
Требуется решить следующую задачу:
SSE(c) = (\mathbf{y}-\mathbf{y(c)})^T(\mathbf{y}-\mathbf{y(c)}) \to min_c.

Описание алгоритма

Свободные параметры: размер популяции, доля кроссоверинга ( доля особей одного поколения, подвергающихся кроссоверингу ).

  1. Инициализация( создание начальной популяции необходимого размера ). Хромосомы особей представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: n=0.
  2. n:=n+1. Проверка условий завершения: либо n превысило максимально допустимое значение, либо изменения целевой функции SSE для лучшей особи в популяции за некоторое число итераций оказалось слишком малым.
  3. Селекция( выбор особей для следующего поколения ). Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
  4. Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. Оператор скрещивания ). В результате этой операции каждая аллель ( т. е. позиция в хромосоме особи ) случайным образом заполняется геном 1-ого или 2-ого родителя.
  5. Мутация. Для каждой особи в каждой аллели с вероятностью 0.01 происходит мутация, которая выражается в замене текущего гена на 0 или 1 случайным образом( равновероятно ).
  6. Возвращение на шаг 2.

Вычислительный эксперимент

Показана работа алгоритма на реальных и модельных данных.

Модельные данные

Данные порождались следующим образом: 

x = [ 1:0.5:20 ]';
y = x + x.^2 + sin( x ) + log( x ) + x.*log( x ) + ( x.^2 ).*sin( x ) + randn( size( x, 1 ), 1 );

Выборка делилась на training и testing части в соотношении 60%:40% случайным образом. Исследовались 2 эффекта: ложная ( ранняя ) сходимость и переобучение.

Результаты на модельных данных

Использовался следующий набор порождающих функций ( всего 12 ):
1,\; x,\; x^2,\; log(x),\; x^3,\; x*log(x),\; x^4,\; x^2*log(x),\; x^2*cos(x),\; cos(x)*log(x),\; x*sin(x)*log(x),\; x^2*cos(x)*log(x).
В наборе не было следующих функций, участвовавших в порождении: sin(x),\; x^2*sin(x).
График training,5 демонстрирует раннюю сходимость. Графики 10 демонстрируют раннюю сходимость + переобучение. Графики 15 показывают сходимость без переобучения.

Подтверждение ранней сходимости для случаев 5, 10. Дольше всех работает 15.

Наглядная демонстрация ранней сходимости и переобучения. В случаях 5, 10 выборка хорошо приближена на training-части, а на test-части наблюдаются сильные отклонения. Для случая 15 - подтверждается отсутствие ранней сходимости, переобучения.

Случаи 0.3, 0.7 характеризуются явным переобучением. Для случая 0.5 переобучение не наблюдается, только незначительная ранняя сходимость.


Наглядная демонстрация переобучения для случаев 0.3, 0.7. В случае 0.5 нет явного переобучения, как уже было замечено ранее.

Выводы

Чем больше размер популяции, тем менее вероятно переобучение и ранняя сходимость. Оптимальное значение доли кроссоверинга равно 0.5.

Реальные данные

Выборка с улыбкой волатильности. 2 независимые переменные: время и страйк, зависимая переменная - волатильность. Выборка делилась как и прежде.

Результаты на реальных данных

Использовался следующий набор порождающих функций ( всего 21 ):
1,\; x(1),\; x(1)^2,\; x(1)^3,\; x(1)^4,\; x(2),\; x(2)^2,\; x(2)^3,\; x(2)^4,\; sin(x(1)),\; sin(x(2)),\; x(1)*x(2),\; x(1)*x(2)^2,\; x(1)*x(2)^3,\; x(1)*x(2)^4,
x(1)^2*x(2),\; x(1)^2*x(2)^2,\; sin(x(1))*x(2),\; sin(x(1))*x(2)^2,\; sin(x(2))*x(1),\; sin(x(2))*x(1)^2.


Случай 10 явно демонстрирует переобучение. Самый лучший результат - в случае 15.

Нормальный результат, но это скорее случайность. График SSE показал, что алгоритм почти сразу случайно попал в минимум.
Переобучение: красный правый угол поверхности "загнут" не в ту сторону.

Самый лучший результат.

Четко видно, что лучший результат достигается при значении параметра = 0.5. В остальных случаях алгоритм попадает в локальный минимум, далекий от оптимального решения.

Ранняя сходимость: правый красный конец недостаточно загнул, левый синий - слишком.

Лучший результат.

Ранняя сходимость, ситуация аналогична 0.3.

Выводы

Подтверждаются выводы, сделанные для модельных данных.

Исходный код

Скачать код MATLAB можно здесь: createArtificialData1D.m, testGaEffeciency.m, gaEffeciency.m, evalSSE.m, plotRes.m, plotRegression.m.
Скачать реальные данные по опционам можно здесь: realOptions2D.txt.

Смотри также

Литература

  • Matlab 7.9.0(R2009b), Product Help\Genetic algorith options.
Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D1%8B%D0%B1%D0%BE%D1%80_%D0%BF%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D0%B3%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»
Личные инструменты