Автор работы: Пользователь скрыл имя, 26 Декабря 2013 в 13:30, реферат
Благодаря открытиям последних ста лет современной науке известны все основные механизмы эволюции, связанные с генетическим наследованием. Эти механизмы достаточно просты по своей идее, но остроумны (если к природе применимо это слово) и эффективны. Удивительно, но простое моделирование эволюционного процесса на компьютере позволяет получить решения многих практических задач. Такие модели получили название “генетические алгоритмы” и уже широко применяются в различных областях.
ВВЕДЕНИЕ 3
История появления эволюционных алгоритмов 5
Генетические Алгоритмы 8
Общий вид генетического алгоритма 12
Генетические операторы 14
Особенности генетических алгоритмов 16
Когда применяют генетический алгоритм. 19
Список используемой литературы: 22
Рис.1 Традиционная схема генетического алгоритма
В последние годы, реализовано много генетических алгоритмов и в большинстве случаев они мало похожи на этот Генетические Алгоритмы. По этой причине в настоящее время под термином "генетические алгоритмы" скрывается не одна модель, а достаточно широкий класс алгоритмов, подчас мало похожих друг от друга. Исследователи экспериментировали с различными типами представлений, операторов кроссовера и мутации, специальных операторов, и различных подходов к воспроизводству и отбору.
Хотя модель эволюционного развития, применяемая в Генетические Алгоритмы, сильно упрощена по сравнению со своим природным аналогом, тем не менее Генетические Алгоритмы является достаточно мощным средством и может с успехом применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно, решить другими методам. Однако, Генетические Алгоритмы, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время. Генетические Алгоритмы не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Там, где задача может быть решена специальными методам, почти всегда такие методы будут эффективнее Генетические Алгоритмы и в быстродействии и в точность найденных решений. Главным же преимуществом Генетические Алгоритмы является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Даже там, где хорошо работаю существующие методики, можно достигнуть улучшения сочетанием их с Генетические Алгоритмы.
Общий вид генетического алгоритма
Вначале ГА-функция
генерирует определенное
Рис. 2. Структура хромосомы
Обычно хромосомы
Целое |
Двоичный код |
Код Грея |
0 |
0000 |
0000 |
1 |
0001 |
0001 |
2 |
0010 |
0011 |
3 |
0011 |
0010 |
4 |
0100 |
0110 |
5 |
0101 |
0111 |
6 |
0110 |
0101 |
7 |
0111 |
0100 |
8 |
1000 |
1100 |
9 |
1001 |
1101 |
10 |
1010 |
1111 |
11 |
1011 |
1110 |
12 |
1100 |
1010 |
13 |
1101 |
1011 |
14 |
1110 |
1001 |
15 |
1111 |
1000 |
Популяция – совокупность решений на конкретной итерации, количество хромосом в популяции задаётся изначально и в процессе обычно не изменяется. Для ГА пока не существует таких же чётких математических основ, как для НС, поэтому при реализации ГА возможны различные вариации.
Начальная популяция — конечный набор допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса, однако формирование "хорошей" начальной популяции (например, из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума. Это отличается от стандартных методов, когда начальное состояние всегда одно и то же.
Каждая хромосома популяции оценивается функцией эффективности , и ей в соответствии с этой оценкой присваивается вероятность воспроизведения .- Вычисление коэффициента выживаемости (fitness).
В соответствии с вероятностями воспроизведения Pi генерируется новая популяция хромосом, причём с большей вероятностью воспроизводятся наиболее эффективные элементы. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Воспроизведение осуществляется при помощи генетических операторов кроссинговера (скрещивание) и мутации.
Если найдено
Жизненный цикл
популяции - это несколько случайных
скрещиваний и мутаций, в
Генетические операторы
Генетические операторы необходимы, чтобы применить принципы наследственности и изменчивости к виртуальной популяции. Помимо отличительных особенностей, о которых будет рассказано ниже, у них есть такое свойство как вероятность. Т.е. описываемые операторы не обязательно применяются ко всем скрещиваемым особям, что вносит дополнительный элемент неопределенности в процесс поиска решения. В данном случае, неопределенность не подразумевает негативный фактор, а является своебразной "степенью свободы" работы генетического алгоритма.
Оператор кроссинговера (crossover operator), также называемый кроссовером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Моделирует процесс скрещивания особей.
Пусть имеются две
родительские особи с хромосомами
Х={xi, i=1,L} и Y={yi, i=1,L}. Случайным образом
определяется точка внутри хромосомы,
в которой обе хромосомы делятс
Рис.3. Кроссинговер
Данный тип кроссинговера называется одноточечным, т.к. при нем родительские хромосомы разрезаются только в одной случайной точке. Также существует 2-х и n-точечный операторы кроссинговера. В 2-х точечном кроссинговере точек разрыва 2, а n-точечный кроссинговер является своебразным обобщением 1- и 2-точечного кроссинговеров для n > 2. Кроме описанных типов кроссинговера есть ещё однородный кроссинговер. Его особенность заключается в том, что значение каждого бита в хромосоме потомка определяется случаным образом из соответствующих битов родителей. Для этого вводится некоторая величина 0<p0<1, и если случайное число больше p0, то на n-ю позицию первого потомка попадает n-й бит первого родителя, а на n-ю позицию второго - n-й бит второго родителя. В противном случае к первому потомку попадает бит второго родителя, а ко второму - первого. Такая операция проводится для всех битов хромосомы. Вероятность кроссинговера самая высокая среди генетических операторов и равна обычно 60% и больше.
Оператор мутации (mutation operator) необходим для "выбивания" популяции из локального экстремума и способствует защите от преждевременной сходимости. Достигаются эти чудеса за счет того, что инвертируется случайно выбранный бит в хромосоме, что и показано на рис.4.
Рис.4 Мутация
Так же как и кроссинговер, мутация проводится не только по одной случайной точке. Можно выбирать некоторое количество точек в хромосоме для инверсии, причем их число также может быть случайным. Также можно инвертировать сразу некоторую группу подряд идущих точек. Вероятность мутации значительно меньше вероятности кроссинговера и редко превышает 1%. Среди рекомендаций по выбору вероятности мутации нередко можно встретить варианты 1/L или 1/N, где L - длина хромосомы, N - размер популяции.
Необходимо также отметить, что есть мнение, что оператор мутации является основным поисковым оператором и известны алгоритмы, не использующих других операторов (кроссинговер, инверсия и т.д.) кроме мутации.
Особенности генетических алгоритмов
Генетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известны два основных пути решения таких задач - переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать.
Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера. Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).
Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.
Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 1030 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально.
Второй популярный способ основан на методе градиентного спуска. При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия.
Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.
Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение.
Однако, комбинируя переборный и градиентный методы, можно надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета.
Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск.
На рисунке показано, что такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач.
Итак, если на некотором
множестве задана сложная
Однако, ГА, как и
другие методы эволюционных