Представление знаний

i =1

z → min .

Параметр n задает количество переменных функции z. Необходимо найти такие значения переменных xi , при которых функция z прини-

111

мает наименьшее значение. Будем использовать общую схему решения

(рис. 5.8):

1.Определение неизвестных переменных задачи. По условию

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

вать значения xi. Таким образом, каждый i-й ген хромосомы будет соответствовать i-й переменной функции z.

2.Задание функции приспособленности. Будем определять при-

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

приспособленнее особь. Приспособленность i-й особи fi будем определять по следующей формуле:

fi = zi ,

где zi – значение функции z в точке, соответствующей i-й особи.

Рис. 5.8. Общая схема решения задачи с использованием ГА

112

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

сточностью кодирования параметров 0,01. Тогда в имеющемся по условию задачи диапазоне изменения значений параметров [–5,12; 5,11] можно закодировать (5,12 – (-5,11))/0,01 + 1 = 1024 различных значений переменной. Единица прибавляется, так как значение переменной равное 0 также учитывается.

Для того чтобы представить 1024 различных значений перемен-

ной, достаточно использовать log21024 = 10 бит на каждую переменную. Таким образом, будет использоваться целочисленное кодирование с 10разрядными генами.

4.Определение параметров ГА. Для решения задачи рассмотрим популяцию из 20 особей. При отборе особей для скрещивания будем использовать турнирную селекцию с бинарным турниром. В качестве генетических операторов будем использовать 1-точечный кроссинговер и битовую мутацию. Вероятности применения операторов скрещивания и мутации установим равными 0,7 и 0,05, соответственно. Новое поколение будем формировать только из особей-потомков, т.е. величина разрыва поколений T равна 1.

Результат работы генетического алгоритма с выбранными параметрами представлен на рис. 5.9. Показаны зависимости изменения

среднего <z> и наименьшего zmin в популяции значения функции z от номера поколения t. Данные усреднены по 100 независимым запускам.

По данным рис. 5.9 видно, что после 20-го поколения значение

zmin колеблется в достаточно большом диапазоне. Из этого следует, что потери хороших особей в результате мутации велики, и следует уменьшить вероятность мутации. Установим значение этого параметра равным L-1 = 0,01, где L – длина хромосомы в битах, в данном случае L = 100. Результаты работы ГА с измененным значением вероятности мутации показаны на рис. 5.10.

113

114

Из сравнения графиков на рис 5.9 и 5.10 следует, что уменьшение вероятности мутации улучшило результат работы ГА. Также отметим, что теперь эволюционный процесс стабилизировался значительно позднее, примерно после 60-го поколения. Усредненное по всем запускам минимальное значение функции z, достигнутое за первые 100 поколений, равно ~1,016. Чтобы улучшить результат, увеличим давление селекции путем увеличения размера турнира до 4. Результат представлен на рис. 5.11.

Увеличение давления селекции привело к ускорению эволюционного поиска за счет удаления из популяции особей со средней и плохой приспособленностью. В результате стабилизация наступила после 40-го поколения, а усредненное по всем запускам минимальное полученное значение функции z равно ~0,013. Наименьшее значение функции z достигается в точке xi = 0, i = 1,2,…,10 и равно 0. В случае поиска минимума функции z с точностью 0,01, для ГА с параметрами, соответствующими графикам на рис. 5.11, решение было найдено в 69 запусках из 100. При этом в среднем было использовано 1698,68 вычислений целевой функции.

115

Табл. 5.2. Варианты реализации компонентов ГА

117

Приведенный в табл. 5.2 способ реализации генетического алгоритма не является эталонным и, вполне возможно, далек от идеала. Данные в табл. 5.2 могут служить в качестве «опорных» для конкретной реализации генетического алгоритма. Отметим, что бó льшую гибкость и расширяемость программной реализации не только генетического алгоритма, но и любого другого алгоритма и системы вообще можно достичь, используя компонентно-ориентированный подход и паттерны проектирования [35].

5.8.Задания для лабораторных работ

1.Аппроксимировать набор точек линейной функцией:

y(x) = a × x + b .

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

2. Аппроксимировать набор точек экспоненциальной функцией: y(x) = a × exp(b × x) .

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

3. Найти минимум функции:

y( x) = x2 + 4.

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

4. Найти максимум функции:

y(x) = 1 x ; x [– 4; 0).

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

5. Найти точку перегиба функции:

f(х) = (x–1.5) 3 + 3.

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

6. Найти точку пересечения функции с осью Ох.

f(х) = ln (x+1) – 2,25, x > –1.

Вариант А) Использовать целочисленное кодирование. Вариант Б) Использовать вещественное кодирование.

7. Сгенерировать с помощью генетического алгоритма слово

“ МИР”.

8.Найти с помощью генетического алгоритма особь, гены которой соответствуют, в формате RGB, фиолетовому цвету (96, 96, 159).

118

Глава 6 ИСКУССТВЕННЫЕ НЕЙРОННЫЕ СЕТИ

Вданной главе описываются искусственные нейронные сети (ИНС) – современное средство решения задач классификации, аппроксимации и кластеризации. Глава организована следующим образом. Раздел 6.1 дает краткое представление об устройстве биологических нейронных сетей.

Вразделе 6.2. представлен формальный нейрон – основная структурная единица искусственных нейронных сетей. Понятие искусственной ней-

ронной сети и описание основных архитектур представлены в разделе 6.3. Раздел 6.4 описывает обучение ИНС в общем виде, а в разделе 6.5 изложен алгоритм обратного распространения ошибки и одна из его модификаций. В разделе 6.6 представлены общие принципы функционирования ИНС прямого распространения и дается общее представление об ИНС с радиально-базисными функциями активации. Пример работы ИНС и описание одного шага обучения даны в разделе 6.7. В разделе 6.8 представлены краткие рекомендации к программной реализации нейронных сетей для выполнения лабораторных работ. Задания на лабораторные работы приведены в разделе 6.9.

6.1. Биологические нейронные сети

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

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

Кора головного мозга человека является протяженной, образованной нейронами в слое толщиной 2–3 мм с площадью около 2200 см2

119

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

личины до одного метра и более. Каждый нейрон связан с 103 −104 другими нейронами. Существует гипотеза, что степень умственного развития человека определяется не только числом нейронов, но главным образом количеством связей между ними.

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

6.2. Формальный нейрон

Искусственные нейронные сети появились в результате применения математического аппарата к исследованию функционирования нервной системы [18]. Полученные при этом результаты успешно применяются при решении проблем распознавания образов, моделирования, прогнозирования, оптимизации и управления [18, 38].

Основной структурной и функциональной частью нейронной сети

ной сигнал нейрона.

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

120