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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Литература)
(→Литература)
Строка 112: Строка 112:
== Литература ==
== Литература ==
* Zbigniew Michalevicz, "Genetic Algorithms + Data Structures = Evolution Programs" (chapter 3: "GAs: Why Do They Work?").
* 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.
+
* Melanie Mitchell, "An Introduction to Genetic Algorithms".
{{ЗаданиеВыполнено|Nikolay Savinov|V.V. Strijov|20 июня 2010}}
{{ЗаданиеВыполнено|Nikolay Savinov|V.V. Strijov|20 июня 2010}}
[[Категория:Практика и вычислительные эксперименты]]
[[Категория:Практика и вычислительные эксперименты]]

Версия 19:51, 27 марта 2011

Содержание

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

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

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


График для размера популяции 5 демонстрирует раннюю сходимость на обучающем множестве (training,5). Графики для размера популяции 10 демонстрируют раннюю сходимость и переобучение (т.е. SSE мало на обучающем множестве и велико на контрольном). Графики для размера популяции 15 показывают сходимость без переобучения.

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

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

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


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

Выводы

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

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


Видно, что для размера популяции 5 результатом работы алгоритма является точка пространства поиска с SSE значительно большим, чем для размеров популяции 10, 15.

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

Четко видно отклонение синей линии, соответствующей размеру популяции 5, от линий, соответствующих значениям 10, 15 (эти линии сливаются). Графики SSE для всех значений, приведенные ранее, показали, что SSE для итоговой точки при значении 5 больше SSE в случаях 10, 15.

Все 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)).


Результат с наименьшим SSE - при размере популяции 15, с наибольшим SSE - при размере популяции 5.

Результат с наибольшим SSE. Никакого сходства с данными.

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

Результат с наименьшим SSE.

Разницы в эффективности для различных значений доли кроссинговера нет. Для всех 3 значений training-графики быстро сливаются (начиная с 30-ой итерации), 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?").
  • Melanie Mitchell, "An Introduction to Genetic Algorithms".
Данная статья была создана в рамках учебного задания.
Студент: Участник:Nikolay Savinov
Преподаватель: Участник:V.V. Strijov
Срок: 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»