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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Размножение)
м (Недостатки ГА)
 
(14 промежуточных версий не показаны.)
Строка 1: Строка 1:
[[Изображение:ADN_static.png‎|thumb|ДНК]]
[[Изображение:ADN_static.png‎|thumb|ДНК]]
-
'''Генетический алгоритм''' (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. [[John Holland]]), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.
+
'''Генетический алгоритм''' (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
__TOC__
__TOC__
 +
 +
== Постановка задачи ==
 +
Для '''функции приспособленности''' <tex>W(x)</tex> в пространстве поиска <tex>X</tex> требуется найти <tex>x^*=\arg\max_{x\in X} W(x)</tex> (или <tex>x^*=\arg\min_{x\in X} W(x)</tex>).
== Описание алгоритма ==
== Описание алгоритма ==
 +
# Случайным образом генерируется конечный набор пробных решений: <tex>P^1=\{p_1^1 ... p_n^1\},\qquad p_i^1\in X </tex> (первое поколение, <tex>n</tex> - размер популяции).
 +
# Оценка приспособленности текущего поколения: <tex>F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k) </tex>
 +
# Выход, если выполняется критерий останова, иначе
 +
# Генерация нового поколения посредством операторов селекции <tex>S</tex>, скрещивания <tex>C</tex> и мутаций <tex>M</tex>: <tex>P^{k+1}=M\cdot C \cdot S (P^k,F^k)</tex> и переход к пункту 2.
 +
 +
В процессе селекции <strike>выживают</strike> отбирают только несколько лучших пробных решений, остальные далее не используются. Скрещивание за место пары решений создаёт другую, элементы которой перемешаны каким-то особым образом. Мутация случайным образом меняет какую-нибудь компоненту пробного решения на иную.
 +
 +
==== Иные обозначения ====
 +
Несмотря на внушительный возраст, в генетических алгоритма до сих пор используют различную терминологию, проистекающей как из генетики, так и из кибернетики.
 +
 +
Встречаются такие обозначения:
 +
* Функция приспособленности (Fitness) <tex>W(x)</tex> - целевая функция;
 +
* Особь - пробное решение <tex>p_i^k \in X</tex>;
 +
* Популяция - все поколения, вносящие вклад в последующее. Чаще всего поколение и популяция - синонимы;
 +
* Ген - компонент вектора <tex>x</tex> пространства поиска <tex>X</tex>;
 +
* Скрещивание - кроссинговер (crossingover).
 +
 +
== Применение генетических алгоритмов ==
 +
 +
Генетические алгоритмы применяются для решения следующих задач:
 +
 +
# [[Оптимизация функций]]
 +
# [[Оптимизация запросов в базах данных]]
 +
# Разнообразные [[задачи на графах]] ([[задача коммивояжёра]], [[раскраска]], [[нахождение паросочетаний]])
 +
# Настройка и обучение искусственной [[Нейронная сеть|нейронной сети]]
 +
# [[Задачи компоновки]]
 +
# [[Составление расписаний]]
 +
# [[Игровые стратегии]]
 +
# [[Теория приближений]]
 +
# [[Искусственная жизнь]]
 +
# Биоинформатика (свёртывание белков)
 +
 +
== Подробное описание алгоритма ==
 +
 +
==== Кодирование пространства поиска ====
 +
В ГА часто используют следующие типы кодирования компонент пространства поиска:
 +
* Бинарный, если признак сам по себе является бинарным;
 +
* Численный в двоичной системе. Расширенный вариант бинарного, где используется фиксированное число бит. Самый простой в реализации, но имеет существенный недостаток (см. ниже);
 +
* Кодирование [http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%93%D1%80%D0%B5%D1%8F кодом Грея]. Избавляет от проблем предыдущего варианта, но добавляет накладные расходы на кодирование/декодирование;
 +
* С небинарными операторами скрещивания и мутаций:
 +
** Числа с плавающей запятой. Используются в том случае, когда масштаб изменения признака заранее не известен;
 +
** Номинальные типы и более абстрактные сущности;
 +
* Типы с автоподстройкой...
 +
 +
==== Начальная популяция ====
 +
Начальная популяция генерируется обычно случайно. Единственный критерий - достаточное разнообразие особей, чтобы популяция не свалилась в ближайший экстремум.
 +
 +
==== Оценка приспособленности ====
 +
Оценка приспособленности часто проводится в две стадии. Первая - собственно оценка: <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>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,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\neq0</tex>, и противоположные условия для второго отпрыска. Маска выбирается случайно. Для простоты, ею может быть третья особь.
 +
* В непрерывном пространстве можно ввести такую аналогию для скрещивания:
 +
<tex>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]</tex>, где <tex>P^k(x)</tex> - плотность генофонда к-ой популяции, <tex>\rho(x,y)</tex> - расстояние между двумя особями с генами x и y, M_c - матрица силы скрещивания.
 +
 +
==== Оператор мутаций ====
 +
Оператор мутаций просто меняет произвольное число элементов в особи на другие произвольные. Фактически он является неким диссипативным элементом, с одной стороны вытягивающим из локальных экстремумов, с другой - приносящим новую информацию в популяцию.
 +
* Инвертирует бит в случае бинарного признака.
 +
* Изменяет на некоторую величину числовой признак. Причём, скорее на ближайший.
 +
* Заменит на другой номинальный признак.
 +
* В непрерывном пространстве можно ввести следующую аналогию:
 +
<tex>P^{k+1}(x)=\int_{X}dyP^{k}(y) \exp\Bigl[-(x-y)^{T}M_m(x-y)\Bigr]</tex>, где <tex>P^k(x)</tex> - плотность генофонда к-ой популяции, M_c - матрица силы мутаций.
-
Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
+
==== Критерии останова ====
* нахождение глобального, либо субоптимального решения;
* нахождение глобального, либо субоптимального решения;
* выходом на «плато»;
* выходом на «плато»;
Строка 14: Строка 86:
* исчерпание заданного числа обращений к целевой функции.
* исчерпание заданного числа обращений к целевой функции.
-
Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска.
 
-
Таким образом, можно выделить следующие этапы генетического алгоритма:
 
-
# Создание начальной популяции
 
-
# Вычисление функций приспособленности для особей популяции (оценивание)
 
-
# (Начало цикла)
 
-
## Выбор индивидов из текущей популяции (селекция)
 
-
## Скрещивание и\или мутация
 
-
## Вычисление функций приспособленности для всех особей
 
-
## Формирование нового поколения
 
-
## Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).
 
-
== Кодирование генома ==
+
== Эвристики ==
 +
Генетические алгоритмы богаты возможностями встраивания различных эвристик. До сих пор не существует (и не будет!) точных критериев оптимального размера популяции, способов мутаций и скрещивания, выбора начальной популяции и т.п.
-
На первом этапе создания ГА требуется решить, какие признаки и как(Вектор типов) будут закодированы в хромосому. В природе каждый элемент [[ген|гена]] может иметь только 4 возможных варианта (4 азотистых основания ДНК: Тимин, Гуанин, Аденин, Цитозин). В ГА часто используют следующие типы кодирования:
+
==== Плоидность ====
-
* Бинарный, если признак сам по себе является бинарным;
+
Каждая особь состоит не из одного, а нескольких пробных решений. Каждый кратный элемент пробного решения имеет активный(доминантный) или неактивный(рецессивный) статус, и, тем самым, проявляет или не проявляет (или же проявляет с определённой интенсивностью) себя при вычислении целевой функции. Кратность пробных решений в особи называется плоидностью (2 - диплоидный набор, 3 - триплоидный, n - n-плоидный набор).
-
* Численный в двоичной системе. Расширенный вариант бинарного, где используется фиксированное число бит. Самый простой в реализации, но имеет существенный недостаток (см. ниже);
+
-
* Код Грея[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%93%D1%80%D0%B5%D1%8F]. Избавляет от проблем предыдущего варианта, но добавляет накладные расходы на кодирование/декодирование;
+
-
* Без побитовых операторов скрещивания и мутаций:
+
-
** Числа с плавающей запятой. Используются в том случае, когда масштаб изменения признака заранее не известен;
+
-
** Номинальные типы и более абстрактные сущности;
+
-
* Типы с автоподстройкой. Основа мета-ГА.
+
-
== Целевая функция ==
+
Преимущества:
 +
*Вытягивает популяцию из локального экстремума, т.к:
 +
**Поддерживает генетическое разнообразие, не позволяет вырождаться;
 +
**Позволяет естественным путём воссоздать аналог инцеста.
 +
Недостатки:
 +
*Усложнение алгоритма;
 +
*Требует большего числа итераций до схождения в экстремум.
-
Целевая функция или функция приспособленности (Fitness) имеет ключевой значение для ГА. Она вместе с вектором типов признаков задаёт саму задачу оптимизации. Вычисление функции приспособленности практически всегда полагается самым трудоёмким процессом, так что вся реализация ГА сведена к уменьшению обращений к этой внешней функции. Например, в природе вычисление целевой функции особи - суть вся жизнь особи от рождения, онтогенеза, рождения и ухода за собственными потомками. В то время как суть ГА - деление и слияние нескольких клеток в репродуктивной системе. В практических задачах вычисление целевой функции - вычисление какой-то сложно устроенной функции или обращение к базе данных.
+
Отдельная статья: [[плоидность]]
-
== Создание начальной популяции ==
+
==== Мета ГА ====
 +
....
-
Перед первым шагом нужно случайным образом создать некую начальную популяцию; даже если она окажется совершенно неконкурентоспособной (сравнивать-то пока не с чем!), генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности. Итогом первого шага является популяция H, состоящая из N особей.
 
-
== Отбор ==
 
-
На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется "в живых" на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.
+
== Простейший пример ГА ==
 +
Подбор ключа 2048 бит
 +
<source lang="C">
 +
#include <stdio.h>
 +
#include <stdlib.h>
 +
#include <iostream>
 +
#include <algorithm>
 +
#include <vector>
-
== Размножение ==
+
using namespace std;
-
Размножение в генетических алгоритмах обычно половое - чтобы произвести потомка, нужны несколько родителей; обычно, конечно, нужны ровно два (Варианты с несколькими родителями пока либо не исследовались, либо ни к чему не привели{{нет источников}}). Размножение в разных алгоритмах определяется по-разному - оно, конечно, зависит от представления данных. Главное требование к размножению - чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, "смешав" их каким-либо достаточно разумным способом. В простейшем случае, для того чтобы провести операцию размножения, нужно выбрать (1-s)p/2 пар гипотез из H и провести с ними размножение, получив по два потомка от каждой пары (если размножение определено так, чтобы давать одного потомка, нужно выбрать (1 - s)p пар), и добавить этих потомков в H'. В результате H' будет состоять из N особей. Более сложные алгоритмы могут работать сразу с несколькими поколениями или не иметь чёткого понятия "поколение" (см., например, [[Когортный ГА (Холланд)|Когортный ГА]]).
+
#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;
 +
}
-
К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определенными операциями мутации.
 
-
В природе мутация происходят постоянно и преимущественно причиной её является ошибки репликации ДНК при делении клеток. Есть мнение{{источник?}}, что организмы не стали отказываться от механизмов мутаций, хоть и могли.
+
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;
 +
}
-
Генетические алгоритмы применяются для решения следующих задач:
+
</source>
-
# [[Оптимизация функций]]
 
-
# [[Оптимизация запросов в базах данных]]
 
-
# Разнообразные [[задачи на графах]] ([[задача коммивояжёра]], [[раскраска]], [[нахождение паросочетаний]])
 
-
# Настройка и обучение искусственной [[Нейронная сеть|нейронной сети]]
 
-
# [[Задачи компоновки]]
 
-
# [[Составление расписаний]]
 
-
# [[Игровые стратегии]]
 
-
# [[Теория приближений]]
 
-
# [[Искусственная жизнь]]
 
-
# Биоинформатика (свёртывание белков)
 
== Эффективность генетических алгоритмов ==
== Эффективность генетических алгоритмов ==
-
Холланд недвусмысленно пишет{{источник?}}, что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.
+
Холланд недвусмысленно пишет[http://qai.narod.ru/Papers/holland_2000.html], что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.
 +
 
 +
Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[http://qai.narod.ru/Papers/holland_2000.html] справляются только генетические алгоритмы.
 +
 
 +
== Тестовые функции ==
 +
В процессе разработки эффективной реализации генетического алгоритма появляется необходимость простой тестовой функции, которая
 +
# учитывает все сильные стороны ГА (многомерная, многоэкстремальная и т.п.);
 +
# имеет аналитическое точное решение.
 +
# проста в реализации
 +
# её проблематично "взломать"
-
Существуют некоторый класс функций ([[HDF (Holland)|HDF]]), с которым за приемлемое время (пока?) справляются только генетические алгоритмы.
+
Самая банальная, сферическая функция, <tex>W(x)=\sum_{i=1}^N (x_i-x_i^*)^2</tex> моментально решается любым алгоритмом спуска.
 +
Многоэкстремальная <tex>W(x)=\sum_{i=1}^N\Bigl[ 1-cos(x_i-x_i^*)+0.001 (x_i-x_i^*)^2 \Bigr]</tex>. Подобных функций можно придумать(и было придумано) большое количество, но малое число из них удовлетворяет нужным требованиям. Холландером были предложены функции HDR[http://qai.narod.ru/Papers/holland_2000.html], которые изначально строятся с целью обеспечения всех выдвинутых условий.
== Мнения ==
== Мнения ==
==== Конвергенция с генетикой и синтетической теории эволюции ====
==== Конвергенция с генетикой и синтетической теории эволюции ====
-
Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает "подсматривать" оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят <strike>свою поддержку</strike> подтверждение и у биологов. Например, такие явления как [[n-плоидный набор хромосом|га- ди- и квадру- плоидные наборы хромосом]], [[n-плоидный набор хромосом|инцест]], [[Мета-ГА|удвоение гена]], [[Мета-ГА|управление скоростью мутаций]], [[Мета-ГА|триггеры]] и т.п.
+
Прообраз генетического алгоритма пришёл из биологии и, несомненно, продолжает «подсматривать» оттуда ответы на многие вопросы, возникающие при проектированию эффективных реализаций генетических алгоритмов. Более того, идеи по оптимизации ГА находят подтверждение и у биологов. Например, такие явления как га- ди- и квадру- плоидные наборы хромосом, инцест, удвоение гена, управление скоростью мутаций, триггеры и т.п.
-
Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить [[n-плоидный набор хромосом]], объектные сущности вместо генов и т.п.
+
Тем не менее, математика и кибернетика позволяет выйти за пределы химической реальности клетки и представить n-плоидный набор хромосом, объектные сущности вместо генов и т.п.
==== Нейронные сети и эволюционное моделирование ====
==== Нейронные сети и эволюционное моделирование ====
-
[[Нейронная сеть|ИНС]] и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.
+
ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.
==== Аналогия с другими алгоритмами ====
==== Аналогия с другими алгоритмами ====
Строка 101: Строка 222:
Также у ГА есть аналогия со случайным поиском с адаптацией.
Также у ГА есть аналогия со случайным поиском с адаптацией.
Во многих стохастических алгоритмах можно найти аналогию с ГА.<!-- добавить ещё -->
Во многих стохастических алгоритмах можно найти аналогию с ГА.<!-- добавить ещё -->
-
 
== Преимущества ГА ==
== Преимущества ГА ==
-
*Большое число свободных параметров, позволяющим эффективно встраивать эвристики (см. [[Мета-ГА]]);
+
*Большое число свободных параметров, позволяющим эффективно встраивать эвристики;
*Эффективное распараллеливание;
*Эффективное распараллеливание;
*Работает заведомо не хуже абсолютно случайного поиска;
*Работает заведомо не хуже абсолютно случайного поиска;
*Связь с биологией, дающая некоторую надежду на исключительную эффективность ГА в природе.
*Связь с биологией, дающая некоторую надежду на исключительную эффективность ГА в природе.
-
 
== Недостатки ГА ==
== Недостатки ГА ==
*Большое количество свободных параметров, которое превращает "работу с ГА" в "игру с ГА";
*Большое количество свободных параметров, которое превращает "работу с ГА" в "игру с ГА";
*Недоказанность сходимости;
*Недоказанность сходимости;
-
просты целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска.
+
простых целевых функциях (гладкие, один экстремум и т.п.) генетика всегда проигрывает по скорости простым алгоритмам поиска.
-
 
+
-
== Некоторые конкретные реализации ==
+
-
*[[Простой ГА]] (sGA)
+
-
*[[Простой непрерывный ГА]]
+
-
*[[Когортный ГА (Холланд)|Когортный ГА]] (cGA)
+
-
*[[Мета-ГА]] (mGA) - некая абстрактная реализация самообучающегося ГА
+
== Читайте также ==
== Читайте также ==
-
*[[Теорема схемы (Holland)|Теорема схемы]]
+
*[[Теорема схемы]]
-
*[[Операторы ГА]] - пример в непрерывном пространстве
+
-
*[[HDF (Holland)|Hyperplane-defined functions]]
+
-
*[[n-плоидный набор хромосом]] -- Га- ди- и т.д набор. Здесь же особенности инцеста.
+
...
...
-
 
== Ссылки ==
== Ссылки ==
Строка 133: Строка 242:
[http://basegroup.ru/library/optimization Генетические алгоритмы на basegroup.ru] <br />
[http://basegroup.ru/library/optimization Генетические алгоритмы на basegroup.ru] <br />
[http://gaul.sourceforge.net/documentation.html GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA] <br />
[http://gaul.sourceforge.net/documentation.html GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA] <br />
 +
[http://neuroschool.narod.ru/books/evogrbn.html Демон Дарвина...] -- Отлично рассмотрен с точки зрения математики накопительный эффект от рецессивности (см. выше "плоидность");<br />
 +
[http://masters.donntu.edu.ua/2005/fvti/trubarov/library/kpi_ga.pdf Г. К. Вороновский и др., ''Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности''] -- пример положительного эффекта диплоидности на качество схождения ГА в глобальном экстремуме.<br />
 +
 +
[[Категория:Эволюционные алгоритмы]]
 +
[[Категория:Дискретная оптимизация]]

Текущая версия

ДНК
ДНК

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

Содержание


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

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

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

  1. Случайным образом генерируется конечный набор пробных решений: P^1=\{p_1^1 ... p_n^1\},\qquad p_i^1\in X (первое поколение, n - размер популяции).
  2. Оценка приспособленности текущего поколения: F^k=\{f_1^k ... f_n^k\},\qquad f_i^k=W(p_i^k)
  3. Выход, если выполняется критерий останова, иначе
  4. Генерация нового поколения посредством операторов селекции 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).

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

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

  1. Оптимизация функций
  2. Оптимизация запросов в базах данных
  3. Разнообразные задачи на графах (задача коммивояжёра, раскраска, нахождение паросочетаний)
  4. Настройка и обучение искусственной нейронной сети
  5. Задачи компоновки
  6. Составление расписаний
  7. Игровые стратегии
  8. Теория приближений
  9. Искусственная жизнь
  10. Биоинформатика (свёртывание белков)

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

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

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

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

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

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

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

Оценка приспособленности часто проводится в две стадии. Первая - собственно оценка: 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\neq0, и противоположные условия для второго отпрыска. Маска выбирается случайно. Для простоты, ею может быть третья особь.

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

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 - матрица силы мутаций.

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

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


Эвристики

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

Плоидность

Каждая особь состоит не из одного, а нескольких пробных решений. Каждый кратный элемент пробного решения имеет активный(доминантный) или неактивный(рецессивный) статус, и, тем самым, проявляет или не проявляет (или же проявляет с определённой интенсивностью) себя при вычислении целевой функции. Кратность пробных решений в особи называется плоидностью (2 - диплоидный набор, 3 - триплоидный, n - n-плоидный набор).

Преимущества:

  • Вытягивает популяцию из локального экстремума, т.к:
    • Поддерживает генетическое разнообразие, не позволяет вырождаться;
    • Позволяет естественным путём воссоздать аналог инцеста.

Недостатки:

  • Усложнение алгоритма;
  • Требует большего числа итераций до схождения в экстремум.

Отдельная статья: плоидность

Мета ГА

....


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

Подбор ключа 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;
}


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

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

Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[2] справляются только генетические алгоритмы.

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

В процессе разработки эффективной реализации генетического алгоритма появляется необходимость простой тестовой функции, которая

  1. учитывает все сильные стороны ГА (многомерная, многоэкстремальная и т.п.);
  2. имеет аналитическое точное решение.
  3. проста в реализации
  4. её проблематично "взломать"

Самая банальная, сферическая функция, W(x)=\sum_{i=1}^N (x_i-x_i^*)^2 моментально решается любым алгоритмом спуска. Многоэкстремальная W(x)=\sum_{i=1}^N\Bigl[ 1-cos(x_i-x_i^*)+0.001 (x_i-x_i^*)^2 \Bigr]. Подобных функций можно придумать(и было придумано) большое количество, но малое число из них удовлетворяет нужным требованиям. Холландером были предложены функции HDR[3], которые изначально строятся с целью обеспечения всех выдвинутых условий.

Мнения

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

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

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

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

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

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

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

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

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

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

Читайте также

...

Ссылки

Генетические алгоритмы и не только
Генетические алгоритмы на basegroup.ru
GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA
Демон Дарвина... -- Отлично рассмотрен с точки зрения математики накопительный эффект от рецессивности (см. выше "плоидность");
Г. К. Вороновский и др., Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности -- пример положительного эффекта диплоидности на качество схождения ГА в глобальном экстремуме.

Личные инструменты