Решение задачи оптимизации с помощью генетического алгоритма

Решение задачи оптимизации с помощью генетического алгоритма

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Кафедра биомедицинской инженерии

КОНТРОЛЬНАЯ РАБОТА

по дисциплине: «Методы обработки БМИ»

Выполнила:

студентка 3 курса

группы БМИза-12/13-1

факультета Биомедицинской инженерии

Карнаух Е.С.

Харьков 2015

Содержание

1.    Операторы выбора родителей

2.      Бинарная рекомбинация (кроссинговер)

2.1  Одноточечный кроссинговер (Single-pointcrossover)

2.2    Двухточечный кроссинговер

.3      Многоточечный кроссинговер (Multi-point crossover)

.4      Однородный кроссинговер (Uniform crossover)

2.5    Триадный кроссинговер (Triadic crossover)

2.6    Перетасовочный кроссинговер (Shuffler crossover)

2.7    Кроссинговер с уменьшением замены

3.    Решение задачи оптимизации с помощью генетического алгоритма

1. Операторы выбора родителей

Существует несколько подходов к выбору родительской пары. Наиболее распространенными операторами выбора родителей являются следующие:

Панмиксия - самый простой оператор отбора. В соответствии с ним каждому члену популяции сопоставляется случайное целое число на отрезке [1; n], где n - количество особей в популяции. Будем рассматривать эти числа как номера особей, которые примут участие в скрещивании. При таком выборе какие-то из членов популяции не будут участвовать в процессе размножения, так как образуют пару сами с собой. Какие-то члены популяции примут участие в процессе воспроизводства неоднократно с различными особями популяции. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.

Инбридинг представляет собой такой метод, когда первый родитель выбирается случайным образом, а вторым родителем является член популяции ближайший к первому. Здесь «ближайший» может пониматься, например, в смысле минимального расстояния Хемминга (для бинарных строк) или евклидова расстояния между двумя вещественными векторами. Расстояние Хемминга равно числу различающихся локусов (разрядов) в бинарной строке. Пример определения родства бинарных хромосом при выборе родительской пары для хромосомы 1010001 показан в Таблице 1.1

Таблица 1.1 - Хеммингово расстояние между хромосомами популяции и хромосомой 1010001

При аутбридинге также используют понятие схожести особей. Однако теперь брачные пары формируют из максимально далеких особей. Последние два способа по разному влияют на поведение генетического алгоритма. Так, инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению по пуляции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта. Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области. Инбридинг и аутбридинг бывает генотипным (когда в качестве расстояния берется разность значений целевой функции для соответствующих особей) и фенотипным (в качестве расстояния берется расстояние Хемминга).

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

При турнирном отборе (tournament selection) из популяции, содержащей N особей, выбираются случайным образом t особей, и лучшая из них особь записывается в промежуточный массив (Рис. 1.1 ). Эта операция повторяется N раз. Особи в полученном промежуточном массиве затем используются для скрещивания (также случайным образом). Размер группы строк, отбираемых для турнира, часто равен 2. В этом случае говорят о двоичном (парном) турнире. Вообще же t называют численностью турнира. Преимуществом данного способа является то, что он не требует дополнительных вычислений.

Рис. 1.1 - Турнирный отбор

В методе рулетки (roulette-wheel selection) особи отбираются с помощью N «запусков» рулетки, где N - размер популяции. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален вероятности попадания в новую популяцию P(i), вычисляемой по формуле:

P (i) = f (i) P N i=1 f (i) ,

где f(i) - пригодность i-й особи. Ожидаемое число копий i-ой хромосомы после оператора рулетки определяются по формуле Ni = P(i)N. При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. Другие способы отбора можно получить на основе модификации выше приведенных. Так, например, в рулеточном отборе можно изменить формулу для вероятности попадания особи в новую популяцию.

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

2. Бинарная рекомбинация (кроссинговер)

Рекомбинацию бинарных строк принято называть кроссинговером (кроссовером) или скрещиванием.

2.1 Одноточечный кроссинговер (Single-point crossover)

Моделируется следующим образом.Пусть имеются две родительские особи с хромосомами

X = {xi , i ∈ [0;L]} и Y = {yi , i ∈ [0;L]} .

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

Таблица 2.1 - Одноточечный кроссинговер

Также применяется двух- и N-точечный кроссинговер.

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

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

Рис 2.1 - Двухточечный кроссинговер

.3 Многоточечный кроссинговер (Multi-point crossover)

Для многоточечного кроссинговера (Multi-point crossover), выбираем m точек разреза ki ∈ {1, 2, . . . , Nvar}, i = 1 : m, Nvar - количество переменных (генов) в особи. Точки разреза выбираются случайно без повторений и сортируются в порядке возрастания. При кроссинговере происходит обмен участками хромосом, ограниченными точками разреза и таким образом получают двух потомков. Участок особи с первым геном до первой точки разреза в обмене не участвует. Сравним следующие две особи по 11 двоичным генам.

Выберем точки разреза кроссинговера:

Создадим двух новых потомков:

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

.4      Однородный кроссинговер (Uniform crossover)

Одноточечный и многоточечный кроссинговер определяют точки разреза, которые разделяют особи на части. Однородный кроссинговер (Uniform crossover) создает маску (схему) особи, в каждом локусе которой находится потенциальная точка кроссинговера. Маска кроссинговера имеет ту же длину, что и скрещивающиеся особи. Создать маску можно следующим образом: введем некоторую величину 0 < p0 < 1, и если случайное число больше p0, то на n-ю позицию маски ставим 0, иначе - 1. Таким образом, гены маски представляют собой случайные двоичные числа (0 или 1). Согласно этим значениям, геном потомка становится первая (если ген маски = 0) или вторая (если ген маски = 1) особь-родитель.

Например, рассмотрим особи:

Для каждого создаваемого потомка создадим маску из 11 случайно выбранных элементов из множества {0; 1}:

Создадим потомков по следующему правилу: если на i-ом месте в соответствующей маске стоит 1, то ген 1 родителя переходит потомку, иначе наследуется ген второго родителя. Получим следующие особи:

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

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

.5      Триадный кроссинговер (Triadic crossover)

Данная разновидность кроссинговера отличается от однородного тем, что после отбора пары родителей из остальных членов популяции случайным образом выбирается особь, которая в дальнейшем используется в качестве маски. Далее 10 % генов маски мутируют. Затем гены первого родителя сравниваются с генами маски: если гены одинаковы, то они передаются первому потомку, в противном случае на соответствующие позиции хромосомы потомка переходят гены второго родителя. Генотип второго потомка отличается от генотипа первого тем, что на тех позициях, где у первого потомка стоят гены первого родителя, у второго потомка стоят гены второго родителя и наоборот.

•        Перетасовочный кроссинговер (Shuffler crossover)

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

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

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

. Решение задачи оптимизации с помощью генетического алгоритма

Таблица 3.1 - Целевая функция и фенотип

Генотип:

0 1 0 0 = 4

1 0 1 0 = 10

0 0 0 0 = 16

1 0 1 1 = 27

Находим целевое значение функции:(x1)=³√64*4⁴+12=37(x2)= ³√64*10⁴+12=98(x3)= ³√64*16⁴+12=173(x4)= ³√64*27⁴+12=336

Определяем среднее значение целевой функции:

F(x)= )=f(x1)+ f(x2)+ f(x3)+ f(x4)/4 = 161

Полученную популяцию разложим на рулетке для проведения выбора хромосом при помощи программы Matlab.

('unif',0,100,1,1)([4,10,16,27])('1 хромосома','2 хромосома','3 хромосома','4 хромосома')

Построили рулетку для отбора хромосом в виде объемной круговой диаграммы и прокрутили ее 4 раза. Получили такие результаты: = 81= 91= 13= 91

Рис. 3.1 - Рулетка с распределением фенотипов

По полученным случайным значениям определили, что 4-й (2 попадания) и 3-й (2 попадание) фенотипы оказались пригодными к выживанию, т.е. составили родительский пул.

Таблица 3.2 - Выбор партнера для скрещивания

Первое скрещивание:

0 1 0 0

1 0 1 0

0 0 0 0

1 0 1 1

) 0 1 0 | 1 0          2) 1| 1 0 1 1

1 0 0 | 0 0            0| 0 1 0 0

Выполняем операцию мутации для 8, 3, 1, 7 позиций хромосом:

0 1 0 0 0              1 1 1 0 0 = 28

0 0 1 0                 1 1 1 1 0 = 30

0 1 0 0                 1 0 1 0 0 = 20

1 0 1 1                 0 1 0 1 1 = 11

Таблица 3.3 - Результат применения генетических операторов

Определяем среднее значение целевой функции:

F(x)=(f(x1)+ f(x2)+ f(x3)+ f(x4))/4=(352+385+229+110)/4=993

Второе скрещивание:

1 1 0 0

1 1 1 0

0 1 0 0

1 0 1 1

) 1 1 1 | 1 0          2) 0 | 1 0 1 1

0 1 | 0 0               1 | 1 1 0 0

Выполняем операцию мутации для 8, 3, 1, 7 позиций хромосом:

1 1 1 0 0

0 1 1 0

1 1 0 0

1 0 1 1

Таблица 3.4 - Результат применения генетических операторов

Определяем среднее значение целевой функции:

F(x)=(f(x1)+ f(x2)+ f(x3)+ f(x4))/4=(76+277+122+336)/4=203

Третье скрещивание:

1 0 0 0

1 0 1 0

1 1 0 0

1 0 1 1

) 1 1 0 | 1 0          2) 1 | 1 0 1 1

1 1 | 0 0             0 | 1 0 0 0

Выполняем операцию мутации для 8, 3, 1, 7 позиций хромосом:

1 1 0 0 0

1 1 1 0

1 0 0 0

1 0 1 1

Таблица 3.5 - Результат применения генетических операторов

F(x)=(f(x1)+ f(x2)+ f(x3)+ f(x4))/4=(122+18+289+110)/4= 134

=0:31;=3*x.^3 + 8;= f(12)= f(29)= f(10)= f(6)= mean(f)= random('unif',0,100,1,1)= random('unif',0,100,1,1)= random('unif',0,100,1,1)= random('unif',0,100,1,1)([f1,f2,f3,f4])(f,x)on(x0,f0,'ro')(x1,f1,'gv')(x2,f1,'ms')('function', '1 generation','2 generation', '3 generation');