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

Размещено на http://www.allbest.ru/

Лекция №6

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

1. История появления генетических алгоритмов

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

2. Основные понятия

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач оптимизации (поиска оптимального решения). Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный", открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.

Основные принципы ГА были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличии от эволюции, происходящей в природе, ГА только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.

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

ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью особей, каждая из которых представляет возможное решение данной проблемы.

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

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

где и - максимальное и минимальное значение аргумента целевой функции;

- погрешность решения задачи;

n - количество бит, используемых для кодирования значения аргумента.

Количество особей M в популяции определяется, как правило, эмпирическим путем, желательно из интервала .

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

В классическом генетическом алгоритме отбор наиболее приспособленных особей осуществляется случайным образом с помощью различных методов генерации дискретных случайных величин, имеющих различные законы распределения. Среди данных методов следует упомянуть отбор методом “колеса рулетки, пропорциональный отбор, отбор с вытеснением, равновероятный отбор и т.д. Каждый из перечисленных методов имеет как свои достоинства, так и недостатки, например, общим недостатком указанных методов является то, что при их использовании в некотором поколении наилучшие особи популяции могут быть потеряны. Одним из способов преодоления этого недостатка является использование элитного отбора, который предусматривает сохранение “наилучшей” особи в популяции (“лучшая” особь всегда переходит в следующее поколение).

На третьем этапе реализуется операция скрещивания особей. Смысл данной процедуры сводится к нахождению новых комбинаций генетического кода хромосом путем обмена случайным образом участков генетического кода у двух особей, прошедших отбор. Это способствует “получению” дополнительного числа новых особей, среди которых могут оказаться как более приспособленные, так и менее приспособленные особи. Это явление объясняется тем, что точка скрещивания (локус) выбирается случайным образом.

На четвертом этапе к особям популяции, полученным в результате скрещивания, применяется операция мутации. С помощью данной операции можно получать принципиально новые генотипы и фенотипы особи, что приводит к еще большему разнообразию особей в рассматриваемой популяции. Суть этого оператора заключается в следующем: в популяции случайным образом выбирается особь и так же случайно выбирается позиция гена, в которой значение изменяется на противоположное ( или ). Внесение таких случайных изменений позволяет существенно расширить пространство поиска приемлемых решений задачи целочисленной оптимизации.

В процессе работы алгоритма все указанные операторы применяются многократно и ведут к постепенному изменению исходной популяции в направлении улучшения значения функции пригодности.

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

· сформировано заданное число поколений,

· популяция достигла заданного уровня качества (например, 80% особей имеют одинаковую генетическую структуру или одинаковое значение функции пригодности),

· достигнут некоторый уровень сходимости, при котором улучшение популяции не происходит.

3. Классический (традиционный) генетический алгоритм

Имеются много способов реализации идеи биологической эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме.

НАЧАЛО

Создать начальную популяцию

Оценить приспособленность каждой особи

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ.

Работа простого ГА

Простой ГА случайным образом генерирует начальную популяцию. Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении ГА реализуется отбор пропорционально приспособленности, одноточечный кроссинговер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции:

Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора, n выбранных особей подвергаются кроссинговеру (иногда называемому рекомбинацией) с заданной вероятностью Pc.

n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссинговер. Соответственно с вероятностью 1-Pc кроссинговер не происходит и неизмененные особи переходят на стадию мутации. Если кроссинговер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссинговер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

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

Пример. Найти максимум функции (1) для целочисленной переменной , принимающей значения от 0 до 31.

Решение:

1. Используя двоичную систему счисления, закодируем числа от 0 до 31. Тогда хромосомы приобретут вид двоичных последовательностей, состоящих из 5 битов (0 как 00000, 31 как 11111)

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

3. Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (N=6). Пусть выбраны хромосомы:

, ,

, ,

Соответствующие им фенотипы - это числа от 0 до 31:

=19, =3, =7, =21, =8, =29

По формуле (1) рассчитаем значения функции приспособленности для каждой хромосомы в популяции, получим:

723, 19, 99, 883, 129

1683

4. Селекция хромосом осуществляется методом рулетки.

Используя формулы (4.1) и (4.2) получим, что

, , , ,

,

Рис 2

Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому (рис 2).

Допустим, что выбраны числа: 97, 26, 54, 13, 31, 88. Это означает выбор хромосом , , , , , .

5. Пусть скрещивание выполняется с вероятностью . Допустим, что для скрещивания сформированы пары и , и , и . Кроме того, случайным образом выбрана точка скрещивания, равная 3 для хромосом и , а также точка скрещивания, равная 2 для хромосом и . При условии, что вероятность мутации , в новую популяцию включаются хромосомы

, , , , ,

Декодировав полученные последовательности, вычислим функции принадлежности данных хромосом:

, , , , , .

Продолжая данный процесс, уже на следующей итерации может быть получено хромосома [11111], с фенотипом равным 31, значение функции приспособленности которой будет наибольшим (равно 1923).

4. Настройка параметров генетического алгоритма

В настоящее время исследователи ГА предлагают много других операторов отбора, кроссинговера и мутации. Вот лишь наиболее распространенные из них.

Турнирный отбор. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

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

Двухточечный кроссовер и равномерный кроссовер.

В двухточечном кроссинговере выбираются две точки разрыва, и родительские хромосомы обмениваются участком генетического кода, который находится между двумя этими точками. В равномерном кроссинговере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.

Размер популяции. Размер популяции является весьма важным элементом ГА. Если популяция слишком мала, генетического материала может не хватить для решения задачи. Размер популяции также влияет на коэффициент применения операторов скрещивания и мутации.

5. Области применения генетических алгоритмов

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

Генетический алгоритм используется для решения многих задач оптимизации:

· составление расписаний (производственных, учебных и т.д.)

· задачи раскроя-упаковки

· аппроксимации и т.д.

Размещено на Allbest.ru