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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Литература)
(→Замечание)
Строка 22: Строка 22:
#Возвращение на шаг 2.
#Возвращение на шаг 2.
=== Замечание ===
=== Замечание ===
-
Существует еще одна модификация оператора кроссинговера - одноточечная, когда случайным образом выбирается позиция в хромосоме, и хромосомы особей обмениваются подстроками, заключенными между этой позицией и правым концом строки (см. [[Генетический алгоритм|Оператор скрещивания]]). Для этой модификации справедлива [[теорема схемы]], которая имеет наглядную интерпретацию в терминах рассматриваемой задачи. Кратко изложим основную идею (строгую формулировку и доказательство теоремы можно найти в <ref> Zbigniew Michalevicz, "Genetic Algorithms + Data Structures = Evolution Programs" (chapter 3: "GAs: Why Do They Work?") </ref>). <br />
+
Существует еще одна модификация оператора кроссинговера - одноточечная, когда случайным образом выбирается позиция в хромосоме, и хромосомы особей обмениваются подстроками, заключенными между этой позицией и правым концом строки (см. [[Генетический алгоритм|Оператор скрещивания]]). Для этой модификации справедлива [[теорема схемы]], которая имеет наглядную интерпретацию в терминах рассматриваемой задачи. Кратко изложим основную идею. <br />
Пусть имеется какая-то начальная популяция. Рассмотрим некоторую совокупность признаков, не очень большую и имеющую не очень большое расстояние между крайними левыми и правыми позициями в хромосоме, дающую приближение в смысле SSE лучше, чем в среднем по данной популяции. Тогда количество появлений такой совокупности признаков в последующих популяциях будет расти экспоненциально на протяжении некоторого числа популяций. Таким образом, наборы признаков с высоким качеством сохраняются и распространяются по популяции. <br />
Пусть имеется какая-то начальная популяция. Рассмотрим некоторую совокупность признаков, не очень большую и имеющую не очень большое расстояние между крайними левыми и правыми позициями в хромосоме, дающую приближение в смысле SSE лучше, чем в среднем по данной популяции. Тогда количество появлений такой совокупности признаков в последующих популяциях будет расти экспоненциально на протяжении некоторого числа популяций. Таким образом, наборы признаков с высоким качеством сохраняются и распространяются по популяции. <br />
Однако в данном исследовании используется кроссинговер с маской, для которого теорема схемы формально не может применяться.
Однако в данном исследовании используется кроссинговер с маской, для которого теорема схемы формально не может применяться.

Версия 09:28, 12 июня 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.

Замечание

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

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

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

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

Данные порождались следующим образом (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=160000)


Видно, что при значениях параметра = 5 алгоритм сработал плохо, при 10, 15 - нормально.

Начиная с 36-ой итерации все графики сливаются.

Четко видно отклонение синей линии, соответствующей значению 5.

Все 3 графика сливаются, как уже было замечено ранее.

Выводы

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

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

Выборка с улыбкой волатильности. 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.

Смотрите также

Литература

  • Matlab 7.9.0(R2009b), Product Help\Genetic algorith options
Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 20 июня 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»