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

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

Перейти к: навигация, поиск

Содержание

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

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

Задана выборка — множество \{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.

Замечание

Существует еще одна распространенная модификация оператора кроссинговера - одноточечная, когда случайным образом выбирается позиция в хромосоме, и относительно этой позиции хромосомы особей обмениваются "половинками" (см. Оператор скрещивания). Относительно этой модификации существует важная теорема - теорема схемы, которая имеет наглядную интерпретацию в терминах рассматриваемой задачи. Кратко изложим основную идею, строгую формулировку и доказательство теоремы можно найти в книге Zbigniew Michalevicz, "Genetic Algorithms + Data Structures = Evolution Programs".
Пусть имеется какая-то начальная популяция. Рассмотрим некоторую совокупность признаков, не очень большую и не очень сильно "разбросанную" по хромосоме, дающую приближение лучше, чем в среднем по данной популяции. Тогда количество появлений такой совокупности признаков в последующих популяциях будет расти экспоненциально (конечно, не до бесконечности, но на протяжении некоторого числа популяций). Таким образом, "хорошие" наборы признаков сохраняются и распространяются по популяции. Казалось бы, стоило использовать одноточечный кроссинговер. Однако это лишь приближенная гипотеза, на практике кроссинговер с маской часто работает лучше, и в данном исследовании было решено использовать именно его.

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

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

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

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

x = [ 1:0.5:20 ]';
y = x + x.^2 + sin( x ) + log( x ) + x.*log( x ) + ( x.^2 ).*sin( x ) + sqrt( D ) * 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).

Случай небольшой дисперсии (D=1)


График 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.

Случай значительной дисперсии (D=400)





Выводы

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

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

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

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

Использовался следующий набор порождающих функций (всего 26):
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,\; 1/(x(1)+0.1),\; 1/(x(2)+0.1),
log(0.1+x(1)),\; log(0.1+x(2)),\; exp(x(1)).


Самый лучший результат - в случае 15, самый плохой - в случае 5.

Самый плохой результат. Никакого сходства с данными.

Неплохой результат, но видно, что красный край недостаточно загнут вверх.

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

Особой разницы в эффективности для различных значений параметра не видно. Для всех 3 значений training-графики быстро сливаются, test-графики тоже достаточно близки.

На всех 3 графиках видно, что поверхности почти не отличаются, все очень похожи на данные выборки.

Выводы

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

Исходный код

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

Смотри также

Литература

  • Zbigniew Michalevicz, "Genetic Algorithms + Data Structures = Evolution Programs" (chapter 3: "GAs: Why Do They Work?").
  • Matlab 7.9.0(R2009b), Product Help\Genetic algorith options.
Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 28 мая 2010

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

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

Источник — «http://poligon.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»