Генетический отбор признаков

Генетический алгоритм моделирует процесс естественного отбора. Подмножеству признаков ставим в соответствие некоторый бинарный вектор $(b_{1},b_{2},\dots ,b_{n})$ где $b_{i}=1$ значит что $i$-й признак входит в признаковое подпространство и $0$ значит что не входит (вектор является упрощенной математической моделью ДНК). Далее определяем операции кроссовера и мутации.

• Одноточечный (singlepoint) кроссовер — $cross(b_{1},b_{2})=(b_{1}^{1},b_{1}^{2},\dots ,b_{1}^{k},b_{2}^{k+1},\dots ,b_{2}^{n})$, где $k$ - выбирается случайно от $1$ до $n$.
• Двуточечный (two point) кроссовер — $cross(b_{1},b_{2})=(b_{1}^{1},b_{1}^{2},\dots ,b_{1}^{k},b_{2}^{k+1},\dots ,b_{2}^{m},b_{1}^{m+1},\dots ,b_{1}^{n})$, где $k,m$ - выбираются случайным образом $1<k<m<n$.
• Равномерный кроссовер — $cross(b_{1},b_{2})=(b^{1},b^{2},\dots ,b^{n})$, где $b^{i}=b_{1}^{i}$ или $b^{i}=b_{2}^{i}$ с вероятностью $\frac{1}{2}$.
• Мутация $mut(b)=\{b^{i}\oplus a^{i}\}_{i=1}^{n}$, где $a^{i}=1$ с вероятностью $\alpha$ и $a^{i}=0$ с вероятностью $1-\alpha ,\alpha \ll 1$.

Далее генерируем случайный набор из $K$ бинарных векторов. И генерируем "новое поколение": берем из набора случайные пары векторов и скрещиваем их при помощи кроссовера, после чего мутируем получившегося потомка. Из всех получившихся признаков (и старое и новое поколение) находим $K$ оптимальных (дающих наилучший результат при обучении). После чего уже для них повторяем алгоритм до сходимости или по количеству итераций. $K$ - параметр алгоритма.

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