Автор: Иван *, 05 Октября 2010 в 08:22, реферат
Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
История
«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит доказательство теоремы схем.
Описание алгоритма
Схема работы генетического алгоритма
Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов. Где каждый ген может быть битом, числом или неким другим объектом. В классичеких реализация ГА, предпологается что генотип имеет фиксированную длинну. Однако существуют вариации ГА свободные от этого ограничения.
Некотором, обычно случайным образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.
Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит доказательство теоремы схем.
Схема работы генетического алгоритма
Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов. Где каждый ген может быть битом, числом или неким другим объектом. В классичеких реализация ГА, предпологается что генотип имеет фиксированную длинну. Однако существуют вариации ГА свободные от этого ограничения.
Некотором, обычно случайным образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.
Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.
Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:
Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска.
Таким образом, можно выделить следующие этапы генетического алгоритма:
Перед первым шагом
нужно случайным образом
Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей, обычно два.
Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей.
К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определенными операциями мутации.
На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.
Генетические
алгоритмы применяются для
Поиск в одномерном пространстве, без скрещивания.
# include <iostream>
# include <algorithm>
# include <numeric>
int main()
{
using namespace std;
srand((unsigned)time(NULL));
const int N = 1000;
int a[N];
//заполняем нулями
fill(a, a+N, 0);
for (;;)
{
//мутация в случайную сторону каждого элемента:
for (int i = 0; i < N; ++i)
if (rand()%2 == 1)
a[i] += 1;
else
a[i] -= 1;
//теперь выбираем лучших, отсортировав по возрастанию...
sort(a, a+N);
//... и тогда лучшие окажутся во второй половине массива.
//скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
copy(a+N/2, a+N, a /*куда*/);
//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
cout << accumulate(a, a+N, 0) / N << endl;
}
}
| В викиверситете работает «Факультет искусственного интеллекта» |