Искусственный интеллект. Основные направления и этапы развития

Хромосома, содержащая в своих локусах конкретные значения генов, называется генотипом (генетическим кодом). Генотип содержит всю наследственную генетическую информацию об особи. Конечное множество всех допустимых генотипов называют генофондом.

При взаимодействии особи с внешней средой ее генотип порождает фенотип .

Фенотип можно оценить количественно с помощью функции приспособленности к внешней среде (функции фитнесса).

Фитнесс Fit() каждой особи равен численному значению функции J(X), вычисленной для допустимого решения XD (). Чем больше значение функции финтесса при решении задачи нахождения max J(X), тем лучше особь приспособлена к внешней среде.

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

1. необходимо найти один или несколько глобальных экстремумов;

2. представление параметров описания объектов может быть как в непрерывном, так и в дискретном (или даже в словесном) виде.

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

ГА относится к эвристическим методам, так как его сходимость в математическом смысле для всех типов задач не доказана.

Схема генетического алгоритма

Методы формирования популяции

Совокупность особей образует популяцию (численностью r). Эволюция популяции рассматривается как чередование поколений. Номер поколения отождествляется с моментом времени t = 0,1,...,Т, где Т -- жизненный цикл популяции, определяющий период ее эволюции. Совокупность генотипов всех особей образует хромосомный набор, который полностью содержит в себе генетическую информацию.

Наиболее известны три метода формирования популяции:

1) метод "одеяло" - известны все решения, среди них с помощью генетического алгоритма находят наилучшее;

2) метод "дробовик" - случайным образом формируется множество решений;

3) дублируется (улучшается) уже известное решение.

Способы представления хромосом:

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

2) представление хромосом в виде вещественных чисел.

3) представление хромосом с помощью кода Грея.

Селекция sl хромосом связана с выбором пары хромосом из популяции с целью аккумуляции всех лучших функциональных признаков, имеющихся в популяции.

Существует несколько способов селекции:

1. лучший с лучшим (сохранение лучшего решения);

2. лучший с худшим (получение генетического разнообразия);

3. случайный выбор.

Скрещивание осуществляется с помощью двух генетических операторов:

1) Оператор кроссинговера.



2) Оператор мутации.

Применяется для предотвращения потери важного генетического материала в процессе биологической эволюции.

Мутация m - изменение части хромосомы с целью получения другого решения.

Для двоичного представления меняется один из разрядов (0 на 1 или 1 на 0). Мутация, при которой меняется только один ген, называется генной. Существует хромосомная мутация.

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

Для сохранения популяции используется естественный отбор. Необходимо оценить все хромосомы популяции. Для этого используется функция оценки или функция фитнесса.

Функция фитнесса должна быть выражена в терминах фенотипа (а не генотипа).

.

Каждая переменная () должна быть представлена в явном виде.

Функция фитнесса - оценочная функция (оценивает значимость хромосомы для популяции).

Виды функции оценки:

1) аналитический вид;

2) специальные программы;

3) НС.

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

Заканчивается работа алгоритма:

1) при нахождении хромосомы заданного вида;

2) при завершении определённого числа итераций.

Иллюстрация работы генетического алгоритма

I. Условие. Даны два числа. Найти число, содержащее наибольшее число единиц.

Решение.

Сформируем восемь хромосом:

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

111001100101	H1	7
011011100100	H2	6
101100111110	H3	8
010011000000	H4	3
011101000000	H5	4
100011001001	H6	5
101110111010	H7	8
000010111100	H8	5

Начальная популяция.



Случайным образом сформируем пары для скрещивания:

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

II. Условие. Необходимо раскрасить граф в три цвета: красный (к), синий (с), жёлтый (ж).

Решение.



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

Особенности реализации генетических алгоритмов

Кодирование параметров ГА:

· Двоичное кодирование строк.

· Использование вещественных чисел.

,

где n - количество параметров, которыми описывается объект

Каждому параметру соответствует двоичный код (вещественное число).

Хромосома H - цепочка двоичных кодов.

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

цифра	двоичный код	код Грея
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

a и b - границы отрезка, включающие в себя значения варьируемого параметра V

D(H_r) - кодирующая функция

Код Грея характеризуется значительной помехоустойчивостью, поэтому его применяют при реализации ГА.

Модификация основных параметров ГА

Модификации оператора селекции:

1. На основе рулетки.

Каждой хромосоме соответствует своя зона (сектор) рулетки.

2. На основе заданной шкалы.

Сначала вся популяция упорядочивается, затем каждой хромосоме ставится в соответствие определённое число, например, значение функции нормализованного фитнесса:

, где r - число членов популяции

3. Элитная селекция.

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

4. Турнирная селекция.

Выбирается k лучших хромосом, среди них осуществляется скрещивание.

5. Схема рекомбинации.

Заключается в использование хромосом, значительно отличающихся друг от друга.

Модификации оператора кроссинговера:

1. Многоточечный кроссинговер.

H1	0 0 1 1 0 1 0 1
H2	1 0 1 0 1 0 1 0
H1'	0 0 1 0 0 1 1 0
H2'	1 0 1 1 1 0 0 1
H1	0 0 1 1 0 1 0 1
H2	1 0 1 0 1 0 1 0
H1'	0 0 1 0 1 0 1 0
H2'	1 0 1 1 0 1 0 1

Замечание. Не рекомендуется применять большое число точек разрезания, так как это может привести к потере нужных свойств.

2. Порядковый кроссинговер.

3. Частично соответствующий кроссинговер:

1. точка кроссинговера выбирается случайно.

2. производится анализ соответствия сегментов первого и второго родителя.

4. Циклический кроссинговер.

При решении задач комбинаторной оптимизации стоит проблема нахождения допустимого решения.

H₁ 1 2 3 4 5 6 7 8 9 10

H₂ 5 3 9 1 4 8 10 2 6 7

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

I. (1,5), (5,4), (4,1)

II. (2,3), (3,9), (9,6), (6,8), (8,2)

III. (7,10), (10,7)

H^/ 5 3 9 1 4 8 10 2 6 7

5. Универсальный кроссинговер.

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

H₁ 0 1 1 0 0 1

H₂ 0 1 0 1 1 1

маска 0 1 1 0 1 0 > случайным образом с вероятностью 0.5

H₁^/ 0 0 0 0 1 1

H₂^/ 0 0 1 1 0 1

6. «Жадный» кроссинговер.

За один эксперимент находится лучшее решение:

1. для всех хромосом вычисляется значение функции фитнесса;

2. на одной из хромосом выбирается точка кроссинговера и для i-го гена (слева от ) вычисляется значение частичной функция Fit, то есть стоимость пути от i-го гена до рядом стоящего, затем - аналогично для всех хромосом;

3. от потомка берется тот ген, для которого функция Fit наилучшая.

	a	b	c	d	e
a	-	15	6	7	8
b	15	-	4	3	2
c	6	4	-	1	10
d	7	3	1	-	9
e	8	2	10	9	-

P={H₁,H₂,H₃}

H₁ = abcde

H₂ = bdeca

H₃ = ebadc

b>c H₁ Fit = 4

b>a H₁ Fit = 15

b>d H₁ Fit = 3

H₁^/=bdcae (Fit = 18)

H₂^/=28

H₃^/=25

Мобильные ГА

В мобильных ГА длина хромосома может быть переменной (имеют дело со строками переменной длины). Строки могут быть переопределены (хромосома несёт избыточную информацию) или недоопределены (хромосома другой информацией).

В мобильных ГА используются два дополнительных оператора:

· Cut (разрезание)

· Splice (сцепление)

<номер гена: значение гена>

Begin

t=0; //начальный момент времени эволюции

init_population (P_r^t); // инициализация популяции

//r - число хромосом, t - время

p^p_preparing-population; // насыщение популяции

while not termination do

p_r^p ; //селекция хромосом

p_r^cr = cut or splice (p_r^s); //разрезание

p_r^m = mutation (p_r^cr); // мутация

p^t+1=gen (p^p, p_r^cr, p_r^m);

t=t+1;

end while

Еnd.

Отличия мобильного ГА от классического ГА:

1. Используются специальные операторы cut и splice вместо оператора кроссинговера, оперирующего хромосомами фиксированной длины.

2. Возможность формирования хромосом в популяции на каждом этапе оптимизации.

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

Динамическое изменение параметров в процессе выполнения ГА

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

Схема (шаблон) - описывает набор строк (подмножество всех возможных строк) с подобными значениями в некоторых позициях. Схема представляет собой строку длиной l, состоящую из символов алфавита {0, 1, *}.

Пример: 0*10 = {0010, 0110}

Введение схемы позволяет компактно представить похожие хромосомы. Это позволяет концентрировать в области скопления похожих хромосом островки решений. Островки образуют область решений.

каждая строка, представленная схемой, называется примером схемы.

Фиксированные позиции в схеме - позиции, в которых находятся 0 или 1.

Для каждой схемы определяется два параметра:

1. порядок схемы - определяется количеством фиксированных позиций в схеме;

2. длина схемы - расстояние между самыми дальними фиксированными позициями.

=4

=6

=2

=0

=1

Теорема схем:

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

Использование оператора кроссинговера приводит к меньшему разрушению схем с малой длиной. Это позволяет сохранить представительство хромосом, соответствующих данной схеме, в следующих поколениях.

Оператор мутации реже разрушает схемы с низким порядком.

Холланд доказал, что если ГА явным образом обрабатывает n строк в каждом поколении, то в то же время не явным образом, использую строительные блоки, он обрабатывает n³ строк с высокой функцией фитнесса.

Строительные блоки - схемы с высокой функцией фитнесса, короткой длиной и малым порядком.

Запись теоремы схем в формальном виде:

m(H, t) - число представителей схемы H на шаге t.

Вычислим ожидаемое число представителей схемы H в следующем поколении (на шаге t+1) m(H, t+1):

Каждой схеме ставится в соответствие значение вероятности её выживания в следующем поколении:

где fit(H) - приспособленность данной схемы;

fit_ср - средняя приспособленность в данной популяции.

Вероятность того, что схема не будет разрушена оператором кроссинговера, равна:

, где l - количество бит в строке.

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

Схема переживёт мутацию, если выполняется условие:

.

Формальное описание теоремы схем:

.

Выводы:

Значения функций приспособленности fit(H) и fit_ср изменяются в процессе эволюции, поэтому чем больше отношение , тем больше вероятность попадания схемы в популяцию.

мера давления отбора.

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

Теорема схем даёт качественную картину функционирования ГА, снабжает разработчика знаниями о хороших способах кодирования, реализации и применении операторов ГА.

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

Разновидности ГА

I. Эволюционные алгоритмы.

Основное отличие от классического ГА заключается в том, что преобразование элементов осуществляется на уровне фенотипов.

H - генотип

A - фенотип

Для получение фенотипа из генотипа необходимо произвести соответствующее преобразование:

.

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

II. Генетическое программирование.

Под данным термином понимается применение моделей поиска оптимальных параметров к программе.

Хромосома в этом случае не обычная линейная структура, а часть программы.

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

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

Виды функции фитнесса:

1. Использование естественных ограничений при построении программ (например, точность, время).

2. Использование различных модификаций функции фитнесса:

, где - текущее значение.

Чем меньше разность, тем лучше решение

3. Модифицированная функция фитнесса:

.

4. Нормированная функция фитнесса:

, где r - размер популяции;

.

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

Операторы:

· кроссинговер;

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

Применение генетического алгоритма к обучению многослойного персептрона

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

В качестве популяций используются НС с различными весовыми коэффициентами.

,

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

Алгоритм обучения:

1. Инициализация векторов , значениями, близкими к нулю.

2. Селекция: выбираются методы, хорошо себя зарекомендовавшие при оптимизации многопараметрических задач.

3. Применение генетических операторов кроссинговера и мутации.

Существует два подхода:

1) использование операторов на уровне генотипа (хромосомы);

2) использование операторов на уровне фенотипа.

4. Определение функции ошибки сети :

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

Если для некоторой сети получили , то выбирается данная НС в качестве решения.

На четвёртом этапе при использовании операторов на уровне фенотипов для вычисления предпочтительней использовать оператор мутации.

Процедура заканчивается если:

· ;

· завершено определённое число шагов итерации. Если ошибка не получена, то переходим к НС с другой архитектурой, либо расширяем пространство поиска.

5. Тестирование НС на примерах, отличных от тех, которые используются на шаге 4.

Вычисляем ошибку обобщения .

Основное отличие данного ГА от BP:

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

Вторая задача: нахождение минимального числа слоёв НС и числа нейронов в каждом слое.

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

Для решения конкретной прикладной задачи строится своя НС. Сам тип НС, а также её архитектуру выбирает пользователь.

Желательно строить САПР НС, которая будет подбирать тип и архитектуру НС применительно к конкретной задаче.

Постановка задачи: задано количество входов НС ; известно число выходов НС (количество классов). Необходимо определить число промежуточных слоёв НС и число нейронов в каждом слое.

Для построения НС, адекватной данной задаче, вводится интегральный критерий:

,

где , - коэффициенты, определяющие вклад каждой составляющей, ;

S - суммарное количество связей.

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

Рекуррентные и рециркуляционные сети

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

Рециркуляционные сети характеризуются распространением сигнала как в прямом (feed forward), так и в обратном (back forward) направлениях.

К рекуррентным сетям (сетям с обратной связью) можно отнести следующие:

· сеть Хопфилда

· машина Больцмана

· сеть Хемминга

Впервые нейронную сеть с обратной связью предложил Джордан в 1986 году.

НС Джордана имела следующий вид:



Первый слой выполняет распределительную функцию.

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

Помимо входных нейронов в первом слое находятся контекстные нейроны, количество которых равно числу выходов НС. Через контекстные нейроны осуществляется вязь входа с выходом.

весовой коэффициент связи нейронов входного и промежуточного слоев;

весовой коэффициент связи нейронов промежуточного и выходного слоев.

Взвешенная сумма входов i-ого нейрона промежуточного слоя:

,

где весовой коэффициент связи между j-тым нейроном входного слоя и i-тым нейроном промежуточного слоя; порог i-того нейрона промежуточного слоя.

.

Сеть Джордана используется для решения задач прогнозирования и управления.

Сеть Элмана (Elman, 1991).

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

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

Сеть Хопфилда

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

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

Ассоциативной памяти человека присуще следующие особенности:

· поиск информации в памяти основывается на некоторой мере, определяющей меру сходства с ключевым образом;

· память способна хранить образы структурированных последовательностей;

· выборка информации из памяти представляет собой динамический процесс.

На основе исследования ассоциативной памяти человека был построен Ассоциатрон (Накано, Амосов, Палм).

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

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

Существует несколько разновидностей сети Хопфилда:

· сеть работает в дискретном времени, сигналы сети могут принимать только дискретные значения;

· сеть работает в дискретном времени, сигналы сети могут принимать непрерывные значения;

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

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

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

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

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

.

Аттрактор - устойчивое состояние сети, соответствующее определенной стационарной точке, некоторому образу.

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

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

1. Инициализация сети; синаптические коэффициенты устанавливаются следующим образом: ,

где i и j - индексы, предсинаптического и постсинаптического нейронов; i-тый и j-тый элементы вектора k-того образа.

2. Подача на входы сети неизвестного сигнала, его распространение непосредственно устанавливает значение выходов: .

3. Расчет новых состояний нейронов:

и новых значений выходов: , где f - ступенчатая функция активации с порогами {+1, -1}, t - номер текущей итерации.

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

Недостатки сети:

· Тенденция "стабилизации" выходного сигнала в локальном, а не в глобальном минимуме.

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

· Число запомненных образов m не должно превышать величины, приблизительно равной . В связи с данным ограничением сеть иногда не может провести распознавание и выдает на выходе несуществующий образ.

· Если два образа А и Б сильно похожи, они, возможно, будут вызывать в сети перекрестные ассоциации: предъявление сети вектора А приведет к появлению на её выходах вектора Б, и наоборот.

Применение сети Хопфилда к решению задач комбинаторной оптимизации

Рассмотрим задачу коммивояжера (классический пример NP-полной задачи):

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

Для решения этой задачи может быть использована сеть Хопфилда, состоящая из нейронов, расположенных в виде матрицы нейронов: i-я строка матрицы соответствует i-му городу (одному из A, B, C, D, E), i-й столбец соответствует i-му порядку посещения города. Выход узла сети на пересечении строки x (A, B, C, D, E) и столбца i обозначим , где x представляет город, а i - порядок посещения. Тогда один из возможных путей имеет вид:

.

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

Расстоянием между городами x и y является:, где .

Целевая функция E задачи поиска оптимального маршрута (функция энергии) может быть определена следующим образом:

(1)

, где ; - положительные константы.

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

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

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

Приведём целевую функцию к основной форме уравнения сети Хопфилда - функции Ляпунова для двумерной нейронной матрицы:

. (2)

Путём сопоставления коэффициентов уравнения (1) и (2) можно определить весовые коэффициенты:

,

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

Теперь алгоритм обучения Хебба можно заменить прямым заданием указанных весов для НС.

Сеть Хемминга

Сеть Хемминга (Hamming) - расширение сети Хопфилда. Данная сеть, по сравнению с сетью Хопфилда, характеризуется меньшими затратами на память и объемом вычислений, что очевидно из её структуры. Сеть состоит из двух слоев, каждый из которых имеет по m нейронов, где m - число образов.



Идея работы сети состоит в нахождении расстояния Хемминга от тестируемого образа до всех образов.

Расстояние Хемминга - число отличающихся битов в двух бинарных векторах.

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

Функция активации сети является пороговой линейной.

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

Алгоритм функционирования сети:

1. Инициализация сети: весовым коэффициентам первого слоя и порогу активационной присваиваются следующие значения:

Здесь i-тый элемент k-того образа.

Весовые коэффициенты тормозящих связей во втором слое принимают равными некоторой величине . Связь входа нейрона с его выходом имеет вес +1.

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

.

После этого полученными значениями инициализируются значения выходов второго слоя:

.

3. Вычисление новых состояний нейронов второго слоя:

и значения их выходов:

, где t - номер текущей итерации.

4. Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да - перейти к п.3, иначе - останов.

Преимущества сети Хемминга над сетью Хопфилда:

· сеть Хемминга способна найти минимальную погрешность, если погрешности входных бит являются случайными и независимыми;

· для функционирования сети Хемминга нужно меньшее количество нейронов;

· сеть Хемминга не страдает от неправильных классификаций;

· сеть Хемминга быстрее и точнее, чем сеть Хопфилда.

Самоорганизующиеся нейронные сети. Самоорганизация в НС

Основная цель самоорганизации в НС - создание условий выживания организмов в определённых условиях.

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

Для двухмерного пространства существует оптимальное разделение (Voronoj): правильные многоугольники, в узлах (в центре многоугольников) которых - нейроны. При подаче нового вектора на вход системы определяется расстояние между входным вектором и каждым из нейронов. При отнесении вектора к какому-либо классу точность определяется допуском.



С. Гроссбергом было доказано, что оптимальное разбиение существует только для двухмерного пространства. Также им были предложены определённые алгоритмы, с помощью которых можно разделить n-мерное пространство.

Для построения кластеров необходимо произвести обучение сети.

Различают обучение с учителем и без учителя. Ранее нами были изучены алгоритмы обучения с учителем. Рассмотрим алгоритмы обучения без учителя, которые также называются алгоритмами объективной классификации.

Для реализации алгоритмов обучения без учителя необходимо:

1. выбрать способ разбиения объектов на классы;

2. выработать правила отнесения входного образа к определённому классу.

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

Суть самообучения:

1. при обучении правильные ответы сети не сообщаются;

2. во время процедуры обучения происходит формирование кластеров на основе обобщения имеющейся входной информации, сосредоточенной в обучающей выборке;

3. обученная сеть относит новый входной вектор к одному из кластеров, руководствуясь некоторым критерием сходства.

К НС, обучающимся без учителя (НС объективной классификации или НС с самоорганизацией), можно отнести следующие нейронные сети:

· сети Кохонена

· ART-сети

· ART MAP

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

Процесс кластеризации реализуется в алгоритмах обучения без учителя.

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

Например, объекты - n-мерные векторы X=(x₁, x₂,…,x_n), в качестве меры близости двух объектов Х₁ и Х₂ можно принять:

· евклидово расстояние между ними

· максимальную разность значений компонент векторных описаний

· скалярное произведение двух векторов

Введенные меры сходства могут служить критерием для отнесения некоторого объекта к соответствующему классу.

Конкурентное обучение

Конкурентное обучение (competitive learning) НС - наиболее популярная схема реализации процедуры кластеризации без учителя. Данный метод основан на том, что нейроны конкурируют за право «стать победителем».

На рисунке представлен пример НС, имеющей три входа и четыре выхода. Все входы НС соединяются со всеми её выходами посредством связей с весовыми коэффициентами .

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

Трёхмерное входное пространство разделяется на четыре кластера. Кластерные центры, описываемые векторами, изменяются во время процедуры кластеризации на основе правил конкурентного обучения.

Входной вектор X и весовой вектор W_j, соответствующий выходу, должны быть нормализованными. Нормализация осуществляется следующим образом:

; .

Основная проблема при организации процедуры кластеризации - выбор метрики для определения меры схожести (меры различия) между векторами.

1) В качестве меры схожести выберем скалярное произведение .

Тогда величина нейронной активности выхода будет определяется по формуле:.

Весовой вектор W_ij старается повернуться на угол б, чтобы его направление совпало с направлением X_i (б0).



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

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

,

где - скорость обучения.

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

2) В качестве меры схожести выберем евклидово расстояние, тогда активность выходных нейронов определяется по формуле:

.

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

Среднеквадратическая ошибка для -го нейрона - победителя равна:

,

где - нейрон - победитель;

- входной вектор;

- центр кластера, которому принадлежит .

Для сжатия данных используется векторный квантователь (learning vector quantization), который обеспечивает преобразование векторов к некоторому эталонному вектору. Эталонный вектор (кодовый вектор) является центром кластера. Совокупность кодовых векторов - векторная книга.

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

Сеть Кохонена

Сеть Кохонена была введена Т. Кохоненом в 1982г.

Другие названия сети:

"самоорганизующаяся карта признаков" (Self-Organizing feature Maps, SOM)

KCN (Kohonen Clastering Networks)

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

Сеть Кохонена определяется картой Кохонена, которая служит для отображения нейронной активности в пространство.

Сеть Кохонена имеет один слой нейронов. Число входов каждого нейрона равно размерности входного образа. Количество нейронов в слое непосредственно определяет, сколько различных кластеров сеть может распознать.

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

Сеть Кохонена использует конкурентный алгоритм обучения.

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

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

Алгоритм обучения сети Кохонена сводится к следующей последовательности действий:

1. Инициализировать весовые вектора для всех выходных нейронов (матрицы связей ) случайной малой величиной.



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

,

где N - число примеров в обучающей выборке, j - номер нейрона, для которого расстояние dist = min.

Установить размер окрестности для выигравшего нейрона r ("радиус стимуляции").

2. Положить .

3. Подать на вход сети очередной входной вектор из обучающей выборки , где t - текущий шаг итерации.

4. Для каждого нейрона j определить его расстояние по формуле для любого j.

5. Выбрать нейрон победитель , для которого это расстояние минимально (поиск победителя ведётся по величине отклонения входного вектора от весового вектора каждого нейрона).

6. Модифицировать весовые коэффициенты выигравшего нейрона:

и тех нейронов s, которые находятся в окрестности выигравшего:

,

где ; м - скорость обучения (м<1).

7. Повторить п. 3 - 6 для всех векторов обучающей выборки.

8. Положить и вычислить по формуле .

Подсчитать . Если , где з - априорно заданная положительная пороговая величина, то перейти к п. 9, иначе положить , откорректировать м, размер окрестности и перейти к п. 2.

9. Останов.

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

Для учёта влияния эффекта латерального торможения вводится поправка в формулу : , где - расстояние между победившим и соседним нейроном, r - текущий размер окрестности.

Основные недостатки сети Кохонена:

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

2. Итоговые весовые векторы выходных нейронов обычно зависят от входной последовательности.

3. Различные начальные условия обычно порождают различные результаты.

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

Поэтому более выгодными оказываются комбинированные сети.

Алгоритмы кластеризации

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

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

1. Пороговый алгоритм

Дано:

1. множество точек во входном пространстве X

;

2. пороговая величина Т, определяет критерий принадлежности точки какому-

либо классу (кластеру).

Данный алгоритм сводится к следующей последовательности действий:

1) Выбираем случайным образом точку, соответствующую центру первого кластера. (z₁)

2) Из множества точек входного пространства X выбираем произвольную точку x_i и вычисляем расстояние от данной точки до центра первого кластера z₁. ()

3) Если выполняется неравенство , то точка x_i принадлежит кластеру с центром z₁. В противном случае, создаётся новый кластер с центром z₂= x_i.

4) Пункты 2 и 3 циклически повторяются для всех точек множества X.

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

Недостаток алгоритма: Эффективность алгоритма во многом определяется величиной

пороговой величины Т и зависит от порядка просмотра точек множества X.

2. Алгоритм максимального расстояния

Характерная особенность алгоритма - выбор наиболее удалённых кластеров.

Дано:

1. множество точек во входном пространстве X

Данный алгоритм сводится к следующей последовательности действий:

1) Выбираем случайным образом точку, соответствующую центру первого кластера. (z₁)

2) Из множества точек X выбираем такую точку, которая наиболее удалена от точки, соответствующей центру z₁, и определяем эту точку как центр второго кластера.



3) Для каждой из точек вычисляются расстояния от данной точки до всех центров кластеров , созданных на данный момент времени.

То есть для каждой точки x_j множества X определяется кластер («свой» кластер), расстояние до которого будет минимальным. Далее выбирается точка x^*, наиболее удалённая от данного («своего») кластера.

На каждом шаге алгоритма t=1,2,3,…вычисляется величина:

Если значение d составляет существенную часть (не менее половины) от величины , то тогда x^* объявляется центром нового кластера. В противном случае (значение d менее половины от величины ) процесс завершается, а все оставшиеся точки множества X разносятся по ближайшим кластерам.

Недостатки алгоритма:

2. случайный выбор начального кластера

3. увеличение уровня сложности на каждом шаге работы алгоритма

3. Алгоритм внутригруппового среднего (метод K-средних, K-means clustering, C-means clustering)

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

Дано:

1. множество точек во входном пространстве X

Алгоритм сводится к следующей последовательности действий:

1) Произвольно выбираются q центров кластеров (в качестве центров кластеров берутся точки из входного множества).

2) Все образы (точки из входного множества), не являющиеся центрами кластеров, «разносятся» по кластерам в соответствии с принципом минимального расстояния до центра кластера.

Образ х принадлежит кластеру K_j, если расстояние от точки х до центра z_j(r) данного кластера меньше расстояния от х до центра любого другого кластера (q-1). K_j определяет множество, состоящее из точек, включённых в него до r-ого шага.

, если

3) Определяются новые центры кластеров z_j(r+1), j=1… q таким образом, чтобы минимизировать показатель качества J.

В данном случае используется евклидово расстояние.

Новый центр кластера вычисляется по следующей формуле:

,

где - количество точек, включенных в пространство K_j к r-ому шагу итерации.

4) Алгоритм заканчивает свою работу, если выполняется равенство: , то есть не изменяются центры кластеров. В противном случае, переход к пункту 2.

Пример реализации алгоритма К-средних

Дано:

Х={x₁, x₂,…,x₁₀}

q=3

Положим, что Z₁ = X₁; Z₂ = X₃; Z₃ = X₄

В технике оптимизации используется приём "мультстарт": алгоритм оптимизации реализуется несколько раз из различных начальных точек, а затем из полученных решений выбирается наилучшее.

Шаг 1. Определяем минимальное расстояние от каждой точки до каждого кластера.

	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
коорд.	(2;2)	(2;4)	(3;4)	(3;8)	(4;7)	(5;9)	(6;1)	(6;8)	(7;1)	(8;1)
Z1	0	2	-	-	5,4	7,6	4,1	7,2	5,1	6,05
Z2	-	1	0	-	3,2	5,4	4,2	5	5	5,8
Z3	-	4,1	-	0	1,4	2,3	7,6	3	8,05	8,6

Шаг 2. По критерию минимального расстояния определяем, какие точки относятся к какому кластеру.

кластер	точки
1	X1, X7
2	X2, X3, X9, X10
3	X4, X5, X6, X8

Шаг 3. Пересчёт всех кластерных центров Z_i

Z₁ = (4; 1,5)

Z₂ = (5; 2,5)

Z₃ = (4,5; 8)

Шаг 4.

	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
Z11	2	3,2	2,7	6,6	5,5	7,6	2	6,8	3	4
Z21	3	3,35	2,5	5,85	4,6	6,5	1,8	5,6	2,5	3,4
Z31	3,5	4,7	4,3	1,5	1,1	1,1	7,2	1,5	7,4	7,8

Шаг 5.

кластер	точки
1	X1, X2
2	X3, X7, X9, X10
3	X4, X5, X6, X8

Шаг 6.

Z₁² = (2; 3)

Z₂² = (6; 1,75)

Z₃² = (4.5; 8)

Шаг 7.

	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
Z12	1	1	1,4	5,1	4,47	6,7	4,47	6,4	5,4	6,3
Z22	4	4,6	3,75	6,9	5,6	7,1	0,75	6,25	1,25	2,1
Z32	6,5	4,7	4,3	1,5	1,1	1,1	7,2	1,5	7,4	7,8

Шаг 8.

кластер	точки
1	X1, X2, X3
2	X7, X9, X10

Подобные документы

• Сущность искусственного интеллекта

  Искусственный интеллект – научное направление, связанное с машинным моделированием человеческих интеллектуальных функций. Черты искусственного интеллекта Развитие искусственного интеллекта, перспективные направления в его исследовании и моделировании.
  
  реферат [70,7 K], добавлен 18.11.2010
  

• Современные подходы к созданию искусственного интеллекта

  Может ли искусственный интеллект на данном уровне развития техники и технологий превзойти интеллект человека. Может ли человек при контакте распознать искусственный интеллект. Основные возможности практического применения искусственного интеллекта.
  
  презентация [511,2 K], добавлен 04.03.2013
  

• Нейронные сети и эволюционное моделирование

  Рождение искусственного интеллекта. История развития нейронных сетей, эволюционного программирования, нечеткой логики. Генетические алгоритмы, их применение. Искусственный интеллект, нейронные сети, эволюционное программирование и нечеткая логика сейчас.
  
  реферат [78,9 K], добавлен 22.01.2015
  

• Искусственный интеллект

  Агентно-ориентированный подход к исследованию искусственного интеллекта. Моделирование рассуждений, обработка естественного языка, машинное обучение, робототехника, распознание речи. Современный искусственный интеллект. Проведение теста Тьюринга.
  
  контрольная работа [123,6 K], добавлен 10.03.2015
  

• Искусственный интеллект

  История появления термина "искусственный интеллект". Приоритетные направления его применения: генерация речи, обработка визуальной информации. Нейронные, байесовы, иммунные сети, теории хаоса - примеры реализации современных интеллектуальных систем.
  
  реферат [27,2 K], добавлен 14.01.2011
  

• Введение в интеллектуальные системы

  Понятие "искусственный интеллект". Понимание механизмов восприятия, выявление способов работы мозга. Направления развития информатики. Научные проблемы. Программы решения интеллектуальных задач. Анализ изображения и идентификация его содержимого.
  
  презентация [12,2 K], добавлен 14.08.2013
  

• Моделирование рассуждений в ИИС

  Интеллектуальные системы и искусственный интеллект. Рассмотрение моделей рассуждений и целей их создания. Знания и их представление, логические, сетевые, фреймовые и продукционные модели. Моделирование рассуждений на основе прецедентов и ограничений.
  
  курсовая работа [74,0 K], добавлен 26.12.2010
  

• Сознание и искусственный интеллект

  Изучение проблемы искусственного интеллекта. Процесс переработки информации в мозге человека. Расшифровка мозговых кодов явлений субъективной реальности. Естественный интеллект как факт, обладающий субъективной реальностью с принципом инвариантности.
  
  реферат [31,1 K], добавлен 04.12.2011
  

• История и тенденции развития искусственного интеллекта

  История создания и основные направления в моделировании искусственного интеллекта. Проблемы обучения зрительному восприятию и распознаванию. Разработка элементов интеллекта роботов. Исследования в области нейронных сетей. Принцип обратной связи Винера.
  
  реферат [45,1 K], добавлен 20.11.2009
  

• Искусственный интеллект: перспективы и угрозы

  Компоненты и архитектура интеллектуального агента, его дополнение средствами обучения. Различные подходы к созданию искусственного интеллекта, перспективы его развития. Этические и моральные последствия разработки интеллектуальных машин и программ.
  
  реферат [708,9 K], добавлен 02.03.2014
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам