Представления знаний в информационных системах

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) = 1x ; 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