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

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

(Различия между версиями)

Версия 19:32, 27 апреля 2010

Содержание

1 Постановка задачи
2 Описание алгоритма
3 Вычислительный эксперимент
4 Исходный код
5 Смотри также
6 Литература

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

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

Задана выборка — множество $\{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||₁, { i_j }_j=1^k⊂{ 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.$

Описание алгоритма

Свободные параметры: размер популяции, доля кроссоверинга ( доля особей одного поколения, подвергающихся кроссоверингу ).

Инициализация( создание начальной популяции необходимого размера ). Особи представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: n=0.
Селекция( выбор особей для следующего поколения ). n:=n+1. Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. Оператор скрещивания.

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

Цель вычислительного эксперимента -

Рисунок с подписью. Выровнен по правому краю.

Описание данных

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

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

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

Исходный код

Скачать листинги алгоритмов можно здесь: 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»

Категории: Непроверенные учебные задания | Учебные материалы

@@ Строка 12: / Строка 12: @@
 Требуется решить следующую задачу: <br />
 <tex>SSE(c) = (\mathbf{y}-\mathbf{y(c)})^T(\mathbf{y}-\mathbf{y(c)}) \to min_c.</tex>
 == Описание алгоритма ==
+Свободные параметры: размер популяции, доля кроссоверинга ( доля особей одного поколения, подвергающихся кроссоверингу ).
+#Инициализация( создание начальной популяции необходимого размера ). Особи представляют собой битовые векторы со случайными компонентами. Счетчик числа итераций: n=0.
+#Селекция( выбор особей для следующего поколения ). n:=n+1. Селекция выполняется на основе оценки SSE всех особей. Используемый механизм таков: на единичном отрезке каждой особи выделяется участок, длина которого пропорциональна SSE. Далее алгоритм-селектор движется вдоль отрезка с фиксированным шагом, выбирая каждый раз ту особь, над которой находится. Начальная точка выбирается случайно, при этом начальное расстояние до левого конца должно быть меньше шага.
+#Кроссоверинг. Выбирается число особей, равное доли кроссоверинга * размер популяции. С парами особей выполняется так называемый кроссоверинг с маской( см. [[Генетический алгоритм|Оператор скрещивания]].
 == Вычислительный эксперимент ==