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

Материал из 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, { 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»
Личные инструменты