Оператор рекомбинации кроссинговера.

Оператор кроссинговера – это языковая конструкция позволяющая на основе преобразования или скрещивания хромосом родителей или их частей создавать хромосомы потомков. Существует огромное количесвто операторов кроссинговера, т.к. их структура в основном и определяет эффктивность ГА.

Рассмотрим основные операторы кроссинговера.

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

1) Случайно выбираются две хромосомы А = а₁, …, a_n; B= …

2) Выбирается точка разрывак k также случайным образом;

3) Две новые хромосомы А' и В' формируются путем перестановок следующим образом.

A’=a1a2…akb(k+1) … bn

B' = b1b2 … bka(k+1) … an

Пр.

P1= 1 1 1 1 1

P2= 0 0 0 0 0 k=2

p1’ =1 1 0 0 0

p2’ =0 0 0 0 0

2. Двуточечный оператор кросинговера. В Каждой хромосоме определяются две точки оператора кроссинговера и хромосомы обмениваются участками расположенными между двумя точками кроссинговера

р1 = 1 1 1 | 0 1 | 0 0

p2 = 0 0 0 | 1 1 | 1 0 k=3, k=5

p1’= 1 1 1 | 1 1 | 0 0

p2’= 0 0 0 | 0 1 | 1 0

3. Многоточечный оператор выполняется аналогично двуточечному.

p1 = 1| 1 1 0 1 0 0

p2 = 0| 0 0 1 0 1 1

k = 1, k = 3, k = 5

p1’=1| 00 | 01 | 11

p2’=0| 11 | 10 | 00

4. Упорядоченный оператор. Точка разрыва выбирается случайно далее копируется левый сегмент р1 в р1’ остальные позиции в р1’ берутся из р2 в упорядоченном виде с лева направо, исключая элементы уже попавшие в р1'.

p1 = A B C D| E F G H

p2 = G A B E| C D F H k=4

p1’= A B C D| G E F H

p2’= G A B E| C D F H

5. Частично соответсвующие оператру кросинговера.

p1= A B C D E F| G H I J

P2= E C I A D H| J B F G

P1’=A H C D E I| J B F G

P2’=E C F A D B| G H I J

6. Циклический оператор кросинговера.

p1: 1 2 3 4 5 6 7 8 9 10 (1,5), (5,4), (4,1)

p2: 5 3 9 1 4 8 10 8 6 7 (2,3), (3,9), (9,6), (6,8), (8,2),| (7,10), (10,7)

p1’: 1 3 9 5 4 8 10 2 6 7 (5,1), (1,4), (4,5); (3,2), (2,8), (8,6), (6,9), (9,3); (10,7),(7,10)

p2’: 5 8 2 4 1 9 10 6 3 7

7. Универсальный оператор кроссинговера. Используется двоичная маска длина которой равна длине заданной хромосомы. Первый потомок получается на основе сложения первого родителя с маской на основе следующих правил: 0 + 0 = 0; 0+1

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

p1: 0 1 1 0 0 1

p2: 0 1 0 1 1 1

mask: 0 1 1 0 1

p1’: 0 0 0 0 1 1

p2’:

Задание. Выполнить следующие операторы кроссинговера для хромосом p1 и p2.

p1: 1 0 1 0 1 1 0 0 0 1 0

p2: 0 0 1 1 1 0 0 1 0 1 1

1) Одноточечный с к=5

2) Двухточечный с к=2,3

3) Трехточечный к=2,5,7

4) к 2 4 6 8

5) Универальный с маской: 0 0 0 1 1 1 1 0 0 1 1

Оператор мутации – языковая конструкция позволяющая на основе преобразования родительской хромосомы или ее части создавать хромосомы потомка. Реализуется в 2 этапа.

1) Хромосоме А=а1а2а3 … аi-2 ai-1 ai случайным образом выбираются 2 позиции, например 2 и L-1.

2) Гены соответствующие выбранным позициям меняются местами и формируют новую хромосому. Если длина обрабатывемой последовательности невелика, то в процессе мутации можно осуществить полный перебор перестановок генов и найти комбинацию с максимальным значением целевой функции. При длине хромосомы L = 50-200 полный перебор вариантов становится затруднительным, поэтому здесь может выполняться случайно направленный поиск который основан на простом генетическом алгоритме.

1) Одноточечный оператор. Выбирается ген в родительской хромосоме и обменивая его с рядом расположенным геном получают хромосому потомка.

p: 010|011

p’:010|111

2) Двухточечный оператор мутации в котором случайным образом выбираются 2 точки разрыва. Далее выполняется перестановка генов между собой расположенных справа от точек разрыва.

p: A| BCD| EF

p’: A| ECD| BF

Нейронные сети

Мозг человека состоит из белого и серого веществ. Белые – тела нейронов, а серые – соединяющие их нервные волокна. Каждый нейрон состоит из 3-х частей: тело клетки, дендриты, аксон. Нейрон получает информацию через свои дендриты и передает ее дальше через аксон разветвляющийся на конце на тысячи синапсов – нервных нитей соединяющих нейроны между собой.

Простейший нейрон может иметь до 10 000 дендритов принимающих сигналы от других клеток. В мозгу содержатся приблизительно 10^11 нейронов каждый нейрон связан с 10^3 нейронами. Т.о. образом нейроная сеть содержит 10^14 взаимосвязей. Каждый нейрон может находиться в двух состояниях: возбужденный и невозбужденный. В возбужденное состояние нейрон приходит под воздействием электрическим сигналов поступающих к нему от других нейронов, когда эти воздействия становятся достаточно большими. В возбужденном состоянии нейрон сам посылает электрический сигнал другим соединенным с ним нейронам.

Математический нейрон МакКаллока-Питтса

Исторически, первой работой по нейронным сетям считается публикация У. МакКаллока и У. Питтса изданное в 1945г. Её авторы выдвинули идею математического нейрона, т.е. устройства моделирующего нейрон мозга человека. Так же как и биологический нейрон, математический имеет несколько входов и 1 выход. Каждый вход мат нейрона число которых обохначим как j, принимает входные сигналы x_j. Мат нейрон умножает каждый вход икс итый на весовой коэффициент и суммирует полученные взвешенные входные сигналы. Выходной сигнал нейрона может принимать 2 значения 1 или 0 по следующим формулам:

y=1, if S>=Q

y=0, if S<Q

где Q - порог чувствительности нейрона.

S = Sw_jx_j

Если взвешенная сумма входных сигналов S не достигает некоторой пороговой величины, то мат нейрон не возбужден и его выход = 0. А если же входные сигналы достаточно интенсивны и их сумма достигает порогового значения, то нейрон переходит в возбужденное состояние и его выход = 1.

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

Q

S

Q=1 ИЛИ

Q=0 НЕТ

Q=2 И

Персептрон Розенблатта и правило Хебба.

Идея мат нейрона была реализована в 1958 Фрэнком Розенблатом сначала в виде компьютерной программы, а затем в виде электронного устройства моделирующего человеческий глаз.

Рассмотрим персептрон классифицирующий цифры на четные и нечетные

Если на фотоэлемент попадает изображение какой-либо цибры, то элемент вырабатывает 1, в противном случае = 0. Персептрон согласно формулам 1 – 3 Выполняет суммирование входных сигналов умноженные на весовые коэффициенты w_j первоначально заданные датчиком случайных чисел. После этого сумма сравнивается с порогом чувствительности Q также заданным случайным образом. Цель обучения персептрона состоит в том, чтобы выходной сигнал y был равен 1, когда накладываются изображение четной цифры и = 0 если цифра нечетная.

Такая цель достигается путем корректировки весовых коэффициентов нейрона. Если, например, на вход нейрона подается изображение четной цифры 4 и выходной сигнал случайной оказался равен 1, то корректировать веса не нужно. Если же выход не правильный, то нужно увеличить веса тех активных входов которые способствуют возбуждению нейрона.

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

Шаг 1. Датчиком случайных чисел всем синаптическим весам wj (j = 1,..., 12) и порогу чувствительности нейрона присвоить некоторые малые случайные значения.

Шаг 2. Предъявить персептрону какую-либо цифру. Системой фотоэлементов вырабатывается входной вектор xj (j = 1,..., 12).

Шаг 3. Нейрон выполняет взвешенное суммирование входных сигналов

и вырабатывает выходной сигнал y = 1, если S q, или y = 0, если S < q.

Шаг 4а. Если выходной сигнал правильный, то перейти на шаг 2.

Шаг 4б (Первое правило Хебба). Если выходной сигнал неправильный и равен нулю, то увеличить веса активных входов: добавить каждому синаптическому весу величину j-го входного сигнала

Шаг 4в (Второе правило Хебба). Если выходной сигнал неправильный и равен единице, то уменьшить веса активных входов, например, с помощью аналогичной формулы:

Шаг 5. Перейти на шаг 2 или завершить процесс обучения.

При обучении персептрона возникает вопрос: Всегда ли алгоритм обучения персептрона приводит к желаемым результатам. Ответ на этот вопрос дает теорема сходимости персептрона.

Если существует множество значений весов, которые обеспечивают конкретное различение образов, то в конечном итоге алгоритм обучения персептрона приводит либо к этому множеству, либо к эквивалентному ему множеству, такому, что данное различение образов будет достигнуто.

Дата добавления: 2015-07-15