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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 23: Строка 23:
== Вычислительный эксперимент ==
== Вычислительный эксперимент ==
-
Цель вычислительного эксперимента -
+
Показана работа алгоритма на реальных и модельных данных.
[[Изображение:logo.png|100px|thumb|Рисунок с подписью. Выровнен по правому краю.]]
[[Изображение:logo.png|100px|thumb|Рисунок с подписью. Выровнен по правому краю.]]
-
=== Описание данных ===
+
=== Модельные данные ===
 +
Данные порождаются следующим образом:
 +
<source lang="matlab">
 +
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 );
 +
</source>
=== Выполнение алгоритма ===
=== Выполнение алгоритма ===
=== Визуализация результатов ===
=== Визуализация результатов ===

Версия 20:13, 27 апреля 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, { ij }j=1k⊂{ 1,...,N } : c( ij )=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 );

Выполнение алгоритма

Визуализация результатов

Исследование свойств алгоритма

Исходный код

Скачать листинги алгоритмов можно здесь: createArtificialData1D.m, testGaEffeciency.m, gaEffeciency.m, evalSSE.m, plotRes.m, plotRegression.m,

Смотри также

Литература

Данная статья является непроверенным учебным заданием.
Студент: Участник:Николай Савинов
Преподаватель: Участник:В.В. Стрижов
Срок: 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»
Личные инструменты