Нейронные сети Лаба 5 (генетика)

1

ЛАБОРАТОРНАЯ РАБОТА 5 ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

ДЛЯ НАСТРОЙКИ НЕЙРОННЫХ СЕТЕЙ.

5.1 Цель работы

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

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

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

5.2.1 Генетические алгоритмы

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

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

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

Именно такой задачей является задача настройки многослойной нейронной сети. Рассмотрим еѐ подробнее.

5.2.2 Задача эволюционной постройки нейронной сети

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

2

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

В настоящее время обычно выделяют два больших класса способов кодирования: прямое кодирования (direct encoding) и косвенное кодирование (indirect encoding). Прямое кодирование оперирует хромосомами, представляющими некоторое линейное представление ИНС, в котором в явном виде указаны все нейроны, веса и связи ИНС. Таким образом, всегда можно построить взаимно-однозначное соответствие между структурными элементами ИНС (нейронами, связями, весами и пр.)

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

5.2.3 Эволюционная настройка ИНС с прямым кодированием

Пакет Neurolab позволяет очень легко оперировать прямым кодированием нейронной сети с помощью команд tool.np_get и tool.np_set.

Создадим многослойный персептрон с линейным выходом с произвольным числом нейронов, например

import neurolab as nl import numpy as np

net = nl.net.newff(((-3, 3),), [10, 1]) #двуслойный персептрон с одним входом, 1 выходом и 10 нейронами скрытого слоя

net.layers[-1].transf = nl.trans.PureLin() #передаточная функция последнего слоя - линейная, остальных тангенциальная (по умолчанию)

net.init() #инициализация сети

Используя команду vec = nl.tool.np_get(net) можно получить все веса и сдвиги сети net в виде вектора vec, а с помощью команды nl.tool.np_set(net, vec) – проинициализировать сеть net вектором весов и сдвигов vec. Именно этот вектор мы будем использовать в качестве хромосомы. Особь в нашем случае будет для простоты состоять из одной этой хромосомы. При желании, другими хромосомами, задающими особь, могут быть число слоѐв и нейронов в них, связность, функции активации и прочее.

initial_chromosome = nl.tool.np_get(net) # хромосома - вектор параметров сети

# популяция - множество хромосом population_size = 10 #величина популяции

#размерность матрицы, которая задаёт популяцию population_shape = (population_size, len(initial_chromosome))

#начальная популяция случайных хромосом в диапазоне -3, 3 initial_population = np.random.uniform(-3, 3, population_shape)

3

Зададим два простейших генетических оператора – мутацию и селекцию.

def mutate(population, mutability):

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

for i, chromosome in enumerate(population): #для каждой хромосомы в популяции

# каждый параметр отклоняется на величину, пропорциональную мутабельности

chromosome = [gene + (np.random.random()- 0.5)*2*mutability for gene in chromosome] population[i] = chromosome

return population

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

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

x = np.linspace(-3, 3) #область определения y = np.cos(2 * x) - np.sin(x) #значения size = len(x)

P = x.reshape(size,1) #входные данные T = y.reshape(size,1) #обучающий сигнал

Теперь опишем функцию селекции:

def select(population):

""" Функция селекции выбирает наиболее приспособленных особей из популяции"""

def fitness_function(x):

""" Для простоты определим функцию приспособленности как функцию, обратную квадрату ошибки """

return 1 / np.sum(np.square(x)) * 100 #множитель просто для удобства восприятия

fitness = np.zeros(len(population)) #массив для хранения значения приспособленности каждой хромосомы

for i, chromosome in enumerate(population): #для каждой хромосомы в популяции nl.tool.np_set(net, chromosome) #сеть инициализируется тестируемой хромосомой fitness[i] = fitness_function(T - net.sim(P)) #вычисляется приспособленность как

функция ошибки сети

population = population[fitness.argsort()[::-1]] #популяция отсортирована в порядке уменьшения приспособленности

fitness.sort()

fitness = fitness[::-1] #значения приспособленности отсортированы по уменьшению #print (np.average(fitness)) #выводим среднюю ошибку по популяции

#худшая половина популяции отсекается, лучшая дублируется population = np.concatenate((population[:population_size/2],

population[:population_size/2]))

#возвращаем среднее значение ошибки и новую популяцию return population

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

4

def generation(population):

"""Одно поколение эволюции"""

population = mutate(population, mutability = 0.1) # мутируем принятую популяцию population = select(population) # формируем новую популяцию на основе селекции nl.tool.set = (net, population[ 0]) # инициализируем сеть лучшей особью

return population # возвращаем популяцию

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

Рисунок 5.1 Выходы случайно инициализированных сетей и результат отбора после первого поколения (обозначен ромбами)

Приведеная выше функция generation принимает в качестве аргумента популяцию и возвращает популяцию такого же размера, но с хромосомами, более близкими к оптимальным. Ясно, что если повторить ту же процедуру над популяцией, полученной на предыдущем шаге, то результат будет ещѐ лучше. В этом и заключается основной цикл генетического алгоритма. Проведѐм эксперимент, запустив в цикле population = generation(population) и собрав данные о значениях ошибки и приспособленности.

6

а) б)

Рисунок 5.4 – Приспособленность особей: а) средняя по поколению, б) максимальная из поколения

Проинтерпретируем результаты. По графику ошибки видно, что хотя результат монотонно улучшается, лучший результат в поколении закрепляется далеко не сразу. Момент закрепления удачной особи хорошо виден на рисунке 5.3б резкими падениями ошибки около 25 и 125 эпохи. Видно, что хотя отдельные особи в прошлом и достигали такого же или даже лучшего уровня, только после этого момента большинство результатов стало не хуже. Очевидно, что важно, чтобы система чѐтче реагировала на хорошие результаты и быстрее закрепляла их.

То же видно и по графикам приспособленности. Хотя средняя приспособленность по популяции (рисунок 5.4а) показывает общий тренд роста, все участки сильно зашумлены, что тоже демонстрирует слабую способность к отсечению плохих особей и закреплению хороших, вплоть до потери удачного наследственного материала примерно после тысячного поколения. По рисунку 5.4б видно, что лучшие особи популяций на протяжении первых 1000 поколений стабильно демонстрируют уровень приспособленности, в 2-3 раза выше, чем средний даже после 5000 поколений. Это также демонстрирует, что успешные особи были слабо использованы.

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

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

7

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

Другой важный принцип сохранения генетического материала – введение какойлибо формы скрещивания (crossover). Это подразумевает обмен материалом между самыми приспособленными особями (копирование некоторой части хромосомы одной особи и замещение еѐ аналогичным участком другой). Этот подход хорошо дополняет операцию мутации, сохраняя изменчивость, но повышая еѐ результативность. Вероятность оставить потомство и число потомков обычно тоже зависит от приспособленности особи. Кроме того, в скрещивании не обязательно должно участвовать только две особи (более того, доказана довольно низкая эффективность именно такого числа родителей).

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

Задание 1.

Предложите несколько вариантов митоза и реализуйте какой-либо из них.

Задание 2 Предложите несколько вариантов оператора скрещивания и реализуйте какой-либо из них.

аналогичную серию экспериментов, выявив зависимость от некоторых из следующих параметров: мутабельности mutability (целесообразно устанавливать его значения от 0.1 до 1, кроме

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

5.2.4 Некоторые выводы о генетических алгоритмах

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

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

8

генетического алгоритма, в то время как для нейронной сети это ключевой фактор сложности.

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

Кроме того, важно понимать, что генетический алгоритм изначально ведѐт поиск в пространстве намного большей размерности. Если задача нейронной сети (в нашем случае) преобразовать одномерный сигнал в одномерный сигнал, то размерность задачи генетического алгоритма задана длиной хромосомы (или, в более общем случае, особи), что всегда на много порядков больше. Например, размерность пространства, в котором осуществляется поиск при эволюционной оптимизации двуслойной сети с 10 нейронами в скрытом слое, равна 32, и растѐт экспоненциально с увеличением числа слоѐв.

Из этого можно предположить, в частности, что уменьшение пространства признаков теоретически способно значительно увеличить эффективность генетических алгоритмов. Это возможно, лишь отказавшись от прямого кодирования всех параметров сети в пользу косвенного кодирования.

5.2.5 Эволюционная генерация ИНС с косвенным кодированием

Косвенное (indirect или weak) кодирование подразумевает подход, более похожий на биологический. В этом случае генотип не жѐстко задаѐт схему ИНС, а лишь определяет некоторые ключевые моменты еѐ построения, конкретные же параметры задаются по общим или контекстным правилам.

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

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

Однако минусы тоже налицо: значительно сложнее проследить, как изменения в генотипе влияют на результативность отбора, кроме того, велика ответственность при определении генетических операторов и правил кодирования-декодирования: практически всегда остаѐтся вероятность появления полностью нежизнеспособных

9

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

Рисунок 5.5. Выход сети, полученной после 50 поколений эволюции. Состоит из 4 слоѐв с числом нейронов 10-9-9-1 и функциями активациями SatLin, SatLin, TanSig, PureLin. Длина хромосомы при прямом кодировании равна 219, при косвенном 8.

В приложении вы найдѐте простой скрип эволюционной настройки нейронных сетей с косвенным кодированием. Изучите его. Задав произвольный сигнал, проведите исследование, аналогичное представленному на страницах 5-6. Попробуйте включить операторы скрещивания и митоза в данный алгоритм, опишите сложности, с которыми вы столкнулись и методы их преодоления.

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

10

Приложение 5.1. Алгоритм эволюционной настройки нейронной сети с косвенным кодированием.

import neurolab as nl import numpy as np

import matplotlib.pylab as pl #===============================================================================

#Постановка задачи

#=============================================================================== X = np.linspace(-5, 5, 100)

Y = np.cos(X) - np.sin(5*X) * np.cos(.5*X) size = len(X)

P = X.reshape(size,1) T = Y.reshape(size,1)

#Параметры сети, определяемые задачей ci = 1 #число входов сети

co = 1 #число выходов сети

#===============================================================================

#Косвенное кодирование

#===============================================================================

#варианты функций активации

trans = [nl.trans.PureLin(), nl.trans.TanSig(), nl.trans.SatLin(), nl.trans.SatLins(), nl.trans.TanSig(), nl.trans.LogSig()]

def generate_chromosome():

""" Полностью случайная генерация хромосомы """

layers_number = np.random.randint(1,5) #количество слоёв

neurons = np.random.randint(1,15,layers_number) #число нейронов в каждом слое

#число нейронов должно убывать от слоя к слою neurons.sort()

neurons = neurons[::-1]

neurons[-1] = co #число нейронов выходного слоя определяется задачей.

#активационные функции для каждого слоя (генерируем номер в списке trans) transfers = np.random.randint( 0,len(trans),layers_number)

transfers[-1] = 0 #наиболее эффективная активационная функция выходного слоя - линейная

# в генотипе особи задано только число нейронов в каждом слое и активационные функции chromosome = np.array([neurons, transfers])

return chromosome

def generate_population(size):

""" Генерация случайной популяции заданного размера """

pop = []

for i in range(size):

pop.append( generate_chromosome()) return np.array(pop)

def generate_net(chromosome):

"""Восстановление сети по генотипу """

layers = []

neurons = chromosome[ 0] functions = chromosome[1]

for i, nn in enumerate(neurons):

#число входов слоя определяется числом нейроном предшествующего слоя layer_ci = neurons[i - 1] if i > 0 else ci

#формируем объект слоя, задавая число входов, число нейронов и активационную функцию l = nl.layer.Perceptron(layer_ci, nn, trans[functions[i]])

layers.append(l) #добавляем слой к списку слоёв

#формируем схему соединения слоёв - в данном случае с прямой передачей сигнала connect = [[i - 1] for i in range(len(layers) + 1)]