Генетический алгоритм

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

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

Версия 22:04, 9 ноября 2008

ДНК

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Содержание

1 Постановка задачи
2 Описание алгоритма
- 2.1 Иные обозначения
3 Применение генетических алгоритмов
4 Подробное описание алгоритма
5 Эвристики
- 5.1 Диплоидность
- 5.2 Мета ГА
6 Простейший пример ГА
7 Эффективность генетических алгоритмов
- 7.1 Тестовые функции
8 Мнения
9 Преимущества ГА
10 Недостатки ГА
11 Читайте также
12 Ссылки

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

Для функции приспособленности $W(x)$ в пространстве поиска $X$ требуется найти $x^*=\arg\max_{x\in X} W(x)$ (или $x^*=\arg\min_{x\in X} W(x)$ ).

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

Случайным образом генерируется конечный набор пробных решений: $P^1=\{p_1^1 ... p_n^1\},\qquad p_i^1\in X$ (первое поколение, $n$ - размер популяции).
Оценка приспособленности текущего поколения: $F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k)$
Выход, если выполняется критерий останова, иначе
Генерация нового поколения посредством операторов отбора $S$ , скрещивания $C$ и мутирования $M$ : $P^{k+1}=M\cdot C \cdot S (P^k,F^k)$ и переход к пункту 2.

Отбор проходят только несколько лучших пробных решений, остальные далее не используются. Скрещивание за место пары решений создаёт другую, элементы которой перемешаны каким-то особым образом. Мутация случайным образом меняет какую-нибудь компоненту пробного решения на иную.

Иные обозначения

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

Встречаются такие обозначения:

Функция приспособленности (Fitness) $W(x)$ - целевая функция;
Особь - пробное решение $p_i^k \in X$ ;
Популяция - все поколения, вносящие вклад в последующее. Чаще всего поколение и популяция - синонимы;
Ген - компонент вектора $x$ пространства поиска $X$ ;
Оператор скрещивания - оператор кроссинговера (crossingover).

Применение генетических алгоритмов

Генетические алгоритмы применяются для решения следующих задач:

Оптимизация функций
Оптимизация запросов в базах данных
Разнообразные задачи на графах (задача коммивояжёра, раскраска, нахождение паросочетаний)
Настройка и обучение искусственной нейронной сети
Задачи компоновки
Составление расписаний
Игровые стратегии
Теория приближений
Искусственная жизнь
Биоинформатика (свёртывание белков)

Подробное описание алгоритма

Кодирование пространства поиска

В ГА часто используют следующие типы кодирования компонент пространства поиска:

Бинарный, если признак сам по себе является бинарным;
Численный в двоичной системе. Расширенный вариант бинарного, где используется фиксированное число бит. Самый простой в реализации, но имеет существенный недостаток (см. ниже);
Кодирование кодом Грея. Избавляет от проблем предыдущего варианта, но добавляет накладные расходы на кодирование/декодирование;
С небинарными операторами скрещивания и мутаций:
- Числа с плавающей запятой. Используются в том случае, когда масштаб изменения признака заранее не известен;
- Номинальные типы и более абстрактные сущности;
Типы с автоподстройкой...

Начальная популяция

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

Оценка приспособленности

Оценка приспособленности часто проводится в две стадии. Первая - собственно оценка: $F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k)$ . Вторая - дополнительные преобразования. Например, ею может быть нормировка к виду $F^{k'}=\{f_1^{k'} ... f_n^{k'}\},\qquad f_{i}^{k'}=(f_i^k-f_0)/(f_1-f_0)$ , где $f_1$ и $f_0$ , соответственно, лучший и худший показатели в текущей популяции.

Оператор отбора (селекции)

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

Оператор скрещивания

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

В одноточечном варианте, результатом скрещивания родителей $p_i^k=\{a_1,a_2,... a_n\},\qquad p_j^k=\{b_1,b_2,...b_n\}\in P^k$ в $k$ -ой популяции станут два

элемента популяции $k+1$ , такие что $p_i^{k+1}=\{a_1,... ,a_c,b_{c+1},.. ,b_n\},\qquad p_j^{k+1}=\{b_1,... ,b_c,a_{c+1},...a_n\}\in P^{k+1}$ , где точка $c$ выбирается случайно. В двухточечном варианте, соответственно, точек пересечения будет две, и они также выбираются случайно. Легко расширить эту конструкцию и до n точек. Нужно заметить, что в случае нечётного n, происходит n+1-точечный кроссинговер с n+1-ой точкой между последней и первой компонентами.

Скрещиванием с маской является результат в виде двух потомков с компонентами, принадлежность которых определяется по битовой маске. Т.е. результатом скрещивания родителей $p_i^k=\{a_1,a_2,... ,a_n\},\qquad p_j^k=\{b_1,b_2,...,b_n\}\in P^k$ в $k$ -ой популяции станут два

элемента популяции $k+1$ , такие что $p_i^{k+1}=\{c_1,...,c_n\},\qquad p_j^{k+1}=\{d_1,..., d_n\}\in P^{k+1}$ , где $c_i=a_i$ при $m_i=0$ и $c_i=b_i$ при $m_i\neq=0$ . И противоположные условия для второго отпрыска. Маска выбирается случайно. Ею может быть третья особь.

В непрерывном пространстве можно ввести такую аналогию для скрещивания:

$P^{k+1}(x)=\int_{X}dy P^{k}(x)P^{k}(y) \exp\Bigl[-\frac{(x-y)^{T}M_c(x-y)}{\rho(x,y)}\Bigr]$ , где $P^k(x)$ - плотность генофонда к-ой популяции, $\rho(x,y)$ - расстояние между двумя особями с генами x и y, M_c - матрица силы скрещивания.

Оператор мутаций

Оператор мутаций просто меняет произвольное число элементов в особи на другие произвольные. Фактически он является неким диссипативным элементом, с одной стороны вытягивающим из локальных экстремумов, с другой - приносящим новую информацию в популяцию.

Инвертирует бит в случае бинарного признака.
Изменяет на некоторую величину числовой признак. Причём, скорее на ближайший.
Заменит на другой номинальный признак.
В непрерывном пространстве можно ввести следующую аналогию:

$P^{k+1}(x)=\int_{X}dyP^{k}(y) \exp\Bigl[-(x-y)^{T}M_m(x-y)\Bigr]$ , где $P^k(x)$ - плотность генофонда к-ой популяции, M_c - матрица силы мутаций.

Критерии останова

нахождение глобального, либо субоптимального решения;
выходом на «плато»;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию;
исчерпание заданного числа обращений к целевой функции.

Эвристики

Генетические алгоритмы богаты возможностями встраивания различных эвристик. До сих пор не существует (и не будет!) точных критериев оптимального размера популяции, способов мутаций и скрещивания, выбора начальной популяции и т.п.

Диплоидность

...

Мета ГА

....

Простейший пример ГА

Подбор ключа 2048 бит

#include <stdio.h>
#include <stdlib.h>
 
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
#define KEY_LEN 2048 // Длина ключа
bool key[KEY_LEN]; //Неизвестный ключ
 
#define POP_SIZE 20 // Размер популяции
#define ELITE 5 // Количество привелигированных особей
struct gen_struct { // Особь, кортеж из генов и значения пригодности
 bool gen[KEY_LEN];
 int fitness;
 gen_struct(){ //Инициализация случайными значениями
  for(int i=0;i<KEY_LEN;++i)
   gen[i]=(random()%2==0);
 }
 bool operator<(const gen_struct & g)const{
  return (g.fitness>fitness);
 }
 gen_struct(const gen_struct& g){
  for(int i=0;i<KEY_LEN;++i) gen[i]=g.gen[i];
  fitness=g.fitness;
 }
 void Mutate(){ //Оператор мутаций
  gen[random()%KEY_LEN]=random()%2;
 }
 void Crossingover(gen_struct & g){ //Оператор скрещивания
  for(int i=0;i<KEY_LEN;++i){
   if(random()%2){
    gen[i]=g.gen[i];
   }
  }
 }
};
 
int Fitness(bool gen[]){ //Целевая функция
 int ret=0;
 for(int i=0;i<KEY_LEN;i++){
  ret+=(key[i]!=gen[i]);
 }
 return ret;
}
 
 
void GA(gen_struct &ret){
 vector<gen_struct> pop;
 pop.resize(POP_SIZE);
 while(1){
  for(int i=0;i<POP_SIZE;++i)
   if((pop[i].fitness=Fitness(pop[i].gen))==0){
      ret=pop[i];
      return;
     }
  sort(pop.begin(), pop.end());
  for(int i=ELITE;i<POP_SIZE;++i){// 5 лучших остаются без изменений
   pop[i].Crossingover(pop[random()%(ELITE)]);
   pop[i].Mutate();
  }
 }
}
 
 
int main(){
  for(int i=0;i<KEY_LEN;i++){
    key[i]=(random()%2==0);
  }
  gen_struct ret;
  GA(ret);
  cout << "key=";
  for(int i=0;i<KEY_LEN; i++){
    cout << ret.gen[i];
  }
  cout << endl;
}

Эффективность генетических алгоритмов

Холланд недвусмысленно пишет^{[источник?]}, что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.

Существуют некоторый класс функций (HDF), с которым за приемлемое время (пока?) справляются только генетические алгоритмы.

Тестовые функции

...

Мнения

Конвергенция с генетикой и синтетической теории эволюции

Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает «подсматривать» оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п. Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.

Нейронные сети и эволюционное моделирование

ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.

Аналогия с другими алгоритмами

В случае отключённого кроссинговера ГА начинает вести себя по образу случайного поиска. Также у ГА есть аналогия со случайным поиском с адаптацией. Во многих стохастических алгоритмах можно найти аналогию с ГА.

Преимущества ГА

Большое число свободных параметров, позволяющим эффективно встраивать эвристики;
Эффективное распараллеливание;
Работает заведомо не хуже абсолютно случайного поиска;
Связь с биологией, дающая некоторую надежду на исключительную эффективность ГА в природе.

Недостатки ГА

Большое количество свободных параметров, которое превращает "работу с ГА" в "игру с ГА";
Недоказанность сходимости;
В просты целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска.

Ссылки

Генетические алгоритмы и не только
Генетические алгоритмы на basegroup.ru
GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC»

Категории: Статьи с утверждениями без источников | Эволюционные алгоритмы

@@ Строка 57: / Строка 57: @@
 ==== Оценка приспособленности ====
-Оценка приспособленности часто проводится в две стадии. Первая - собственно оценка: <tex>F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k) </tex>. Вторая - дополнительные преобразования. Например, ею может быть нормировка к виду <tex>F^{k'}=\{f_1^{k'} ... f_n^{k'}\},\qquad f_{i'}^k=(f_i^k-f_0)/(f_1-f_0) </tex>, где <tex>f_1</tex> и <tex>f_0</tex>, соответственно, лучший и худший показатели в текущей популяции.
+Оценка приспособленности часто проводится в две стадии. Первая - собственно оценка: <tex>F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k) </tex>. Вторая - дополнительные преобразования. Например, ею может быть нормировка к виду <tex>F^{k'}=\{f_1^{k'} ... f_n^{k'}\},\qquad f_{i}^{k'}=(f_i^k-f_0)/(f_1-f_0) </tex>, где <tex>f_1</tex> и <tex>f_0</tex>, соответственно, лучший и худший показатели в текущей популяции.
 ==== Оператор отбора (селекции) ====
@@ Строка 64: / Строка 64: @@
 ==== Оператор скрещивания ====
 Чаще всего скрещивание производят над двумя лучшими особями. Результатом является также обычно две особи с компонентами, взятыми от их родителей. Цель этого оператора - распространение хороших генов по популяции и стягивание плотности популяции к тем областям, где она итак велика в том предположении, что "нас много там, где хорошо".
-*В одноточечном варианте, результатом скрещивания родителей <tex>p_i^k=\{a_1,a_2,... a_n\},\qquad p_j^k=\{b_1,b2,...b_n\}\in P^k</tex> в <tex>k</tex>-ой популяции станут два
+*В одноточечном варианте, результатом скрещивания родителей <tex>p_i^k=\{a_1,a_2,... a_n\},\qquad p_j^k=\{b_1,b_2,...b_n\}\in P^k</tex> в <tex>k</tex>-ой популяции станут два
 элемента популяции <tex>k+1</tex>, такие что <tex>p_i^{k+1}=\{a_1,... ,a_c,b_{c+1},.. ,b_n\},\qquad p_j^{k+1}=\{b_1,... ,b_c,a_{c+1},...a_n\}\in P^{k+1}</tex>, где точка <tex>c</tex> выбирается случайно.  В двухточечном варианте, соответственно, точек пересечения будет две, и они также выбираются случайно. Легко расширить эту конструкцию и до n точек. Нужно заметить, что в случае нечётного n, происходит n+1-точечный кроссинговер с n+1-ой точкой между последней и первой компонентами.
-* Скрещиванием с маской является результат в виде двух потомков с компонентами, принадлежность которых определяется по битовой маске. Т.е. результатом скрещивания родителей <tex>p_i^k=\{a_1,a_2,... ,a_n\},\qquad p_j^k=\{b_1,b2,...,b_n\}\in P^k</tex> в <tex>k</tex>-ой популяции станут два
+* Скрещиванием с маской является результат в виде двух потомков с компонентами, принадлежность которых определяется по битовой маске. Т.е. результатом скрещивания родителей <tex>p_i^k=\{a_1,a_2,... ,a_n\},\qquad p_j^k=\{b_1,b_2,...,b_n\}\in P^k</tex> в <tex>k</tex>-ой популяции станут два
 элемента популяции <tex>k+1</tex>, такие что <tex>p_i^{k+1}=\{c_1,...,c_n\},\qquad p_j^{k+1}=\{d_1,..., d_n\}\in P^{k+1}</tex>, где <tex>c_i=a_i</tex>  при <tex>m_i=0</tex> и <tex>c_i=b_i</tex> при <tex>m_i\neq=0</tex>. И противоположные условия для второго отпрыска. Маска выбирается случайно. Ею может быть третья особь.
 * В непрерывном пространстве можно ввести такую аналогию для скрещивания: