1 АНАЛИТИЧЕСКАЯ ЧАСТЬ
1.1АРХИТЕКТУРА НЕЙРОННЫХ СЕТЕЙ
В настоящие время существует огромное количество нейронных сетей и не перестают появляться новые. Проанализируем особенно часто распространённые архитектуру сетей.
Персептрон – это очевидный тип нейросети, состоящий всего лишь из одного нейрона. Нейрон зачастую владеет случайным количеством входов, но один точно должен быть тождественно равен 1. Данный особенный вход обозначают смешанным, его использование в некоторых случаях бывает, как следует удобным. Тот или иной вход рассчитывает свой собственный вес. Когда в нейрон поступает импульс, происходит расчёт общих итогов сигналов, после чего к потоку применяется функция активации и в конце сигнал поправляется на выход.
Рисунок 1 – Архитектура простейшей персептроной сети
Такая простая на первый взгляд сеть, представлена на рисунке 1, состоящая только из единственного нейрона, всё же может выполнять следующий список задач:
? выполнять простой анализ событий;
? выполняет регрессионный анализ данных;
? выполнять элементарные.
Важным аспектом для работы нейронной сети является линейная разделимость данных. В пример можно привести некоторые функции из математической логики, такие как логическое И(?) и логическое ИЛИ(?).
Рисунок 2 – Логические операции конъюнкции и дизъюнкции
Для таких функций постоянно возможно проложить прямую (или гиперплоскость в многомерном пространстве), отделяющие 0 значения от 1.
Это и называют линейной разделимостью объектов. Тогда аналогичная модель может решить определенную задачу систематизации и сформировать базисный логичный элемент. В случаи, когда данные невозможно разделить, то сеть состоящая из одного нейрона не справиться с поставленной задачей. Для таких задач существует более сложные структуры нейронных сетей, состоящие из большого количества таких персептронов, которые соединиться в слои.
Многослойный персептрон. В данном представлении слои – это цепочка нейронов, представленная на схемах, как нейроны расположение в одной вертикальной линии, в некоторых представлениях схему могут поворачивать, и такая линия будет уже горизонтальная.
Многослойный персептрон представляет собой обобщенный вид однослойного персептрона. Он состоит из некоторого множества входных узлов, некоторых сокрытых слоев вычислительных нейронов и выходящего слоя.
Основные свойства многослойного персептрона:
– каждый нейрон имеет нелинейную функцию активации, которая должна быть дифференцированной;
– сеть достигает высочайшей степени связности при поддержке синаптических соединений;
– сеть имеет один и более спрятанных слоев.
Рисунок 3 – Архитектура многослойной персептроной сети
Подобные многослойные сети также называться глубокими. Такая сеть нужна для выполнения задач, с которыми не справится персептрон. В частности, линейно единых задач. Из следствия теоремы Колмогорова можно прийти к выводу, что лишь многослойный персептрон является единой многоцелевой нейронной сетью, а также универсального аппроксиматора, который может разрешить каждую задачу. Возможно, не самым действенным способом, который могли бы гарантировать сильнее узкопрофильные нейросети, но все же решить. собственно поэтому, когда исследователь не уверен, нейросеть какого варианта годится для решения стоящей пред ним задачи, он выбирает первоначально многослойный персептрон.
Сверточная нейронная сеть – сеть, ключевой особенностью которой является обработка и передача данных не полностью, а частями. Поступающая информация поочередно обрабатывается и отправляется в следующие слои. Сверточные нейронные сети содержат в себе несколько слоёв, такие каксверточный слой, субдискретизирующий слой, слой полносвязной сети.
Слои свертки и под выборки (субдискретизации) следуют друг за другом и пары таких слоёв могут встречается некоторое количество раз. К выходному слою добавляется персептроны, для обработки вычисленных данных на предыдущих этапах.
Рисунок 4 – Архитектура сверточной нейронной сети
Сеть имеет такое название из-за функции свёртки, принцип работы которой заключается в том, что каждый элемент картинки умножается на ядро свертки по фрагментам, а полученный итог переходит на следующий слой в той же позиции. Данная функция применяться для ухода от определенных свойств изображения к более абстрактным мелочам, а последующий слой к ещё более абстрактным, и продолжается это до того момента пока на изображении находится упомянутые объекты.
Такая нейронная сеть нужна для решения следующих задач, таких как:
– распознавания изображения и что изображено на нём;
–определяет объект и его место нахождение на изображении;
–распознаёт принадлежность каждого пикселя.
Приведенные выше нейронные сети относятся к сетям прямого распространения. Так же существуют другие нейронные сети, архитектура которых строиться из принципа связи возвращения сигнала назад. Пример такой нейронной сети является рекуррентная.
Рекуррентная нейронная сеть можно представить как ориентированный цикл, где выходные нейроны соединены с входными. В такой нейронной сети информация подается со всех слоёв, но с предыдущих она будет поступать с задержкой.
Характеристики сети:
–все ребра соединяющие нейроны имеют свой вес, которые также является его приоритетом;
– разделяют два типа узлов в сети: входные и скрытые;
–на любой части нейронной сети информация передаётся.
Рисунок 5 – Архитектура рекуррентной нейронной сети
Такие сети еще называют «памятью». Если подать данной сети на вход некие «образцы» – последовательности кодов (к примеру, 1000001, 0111110 и 0110110) — и обучить ее на запоминание этих образцов, настроив веса синапсов сети определенным образом при помощи правила Хебба, то затем, в процессе функционирования, сеть сможет «узнавать» запомненные образы и выдавать их на выход, в том числе исправляя искаженные поданные на вход образы. К примеру, если после обучения такой сети я подам на вход 1001001, то сеть узнает и исправит запомненный образец, выдав на выходе 1000001. Правда, эта нейронная сеть не толерантна к поворотам и сдвигам образов, и все же для первой нейронной сети своего класса сеть весьма интересна.
В. И. Ширяев рассматривает архитектуру нейронных сетей. Для составления нейронных сетей используется обычно несколько стандартных архитектур, из которых путем исключения лишнего или добавления строят большинство используемых сетей.
Автор выделяет две базовые архитектору - слоистые и полносвязные сети. Слоистые сети: нейроны расположены в несколько слоев. Нейроны первого слоя получают входные сигналы, преобразуют их и через точки ветвления передают нейронам второго слоя и т.д. Число нейронов в каждом слое может быть любым и никак заранее не связано с количеством нейронов в других слоях. Полносвязные сети: каждый нейрон передаёт свои выходной сигнал остальным нейронам, включая себя. Выходными сигналами сети могут быть все или некоторые выходные сигналы нейронов после нескольких тактов функционирования сети. Все входные сигналы подаются всем нейронам.
Очень важно согласовывать работу различных нейронов во времени. Как только в системе возникает более одного элемента, встает вопрос о синхронности их функционирования. Но для программных имитаторов нейронных сетей на цифровых ЭВМ такого вопроса нет в силу свойств основного компьютера, на котором реализуются нейронные сети. Для других способов реализации такой вопрос весьма важен. Здесь и далее будут рассматриваются только нейронные сети, синхронно функционирующие в дискретные моменты времени: все нейроны срабатывают «разом».
Элементы слоистых и полносвязных сетей могут выбираться по- разному. Существует, впрочем, стандартный выбор- нейрон с адаптивным неоднородным линейным сумматором на входе. Для полносвязной сети входной сумматор нейрона фактически распадается на два: первый вычисляет линейную функцию от входных сигналов сети, второй -линейную функцию от выходных сигналов других нейронов, полученных на предыдущем шаге. Функция активации нейронов (характеристическая функция) — нелинейный преобразователь, преобразующий выходной сигнал сумматора, может быть, одной и той же для всех нейронов сети. В этом случае сеть называют однородной (гомогенной). Если же зависит еще от одного или нескольких параметров, значения которых меняются от нейрона к нейрону, то сеть называют неоднородной (гетерогенной). Составление сети из нейронов стандартного вида не является обязательным. Слоистая или полносвязная архитектуры не налагают существенных ограничений на участвующих в них элементы. Единственное жесткое требование, предъявляемое архитектурой к элементам сети, это соответствие размерности вектора входных сигналов элемента (она определяется архитектурой) числу его входов. Если полносвязная сеть функционирует до получения ответа заданное число тактов k, то ее можно представить как частный случай k-слойной сети, все слои которой одинаковы и каждый из них соответствует такту функционирования полносвязной сети. Существенное различие между полносвязной и слоистой сетями возникает тогда, когда число тактов функционирования заранее не ограничено слоистая сеть так работать не может.
1.2 ТОПОЛОГИЯ СЕТЕЙ
Как отмечают большинство исследователей, центральной точкой любого метода эволюционного построения нейронных сетей является выбор генетического представления (т.е. схемы кодирования и соответствующего декодирования). Выбор представления определяет класс сетей, которые могут быть построены с помощью данного метода. Кроме того, от них зависит эффективность метода по всем параметрам.
В настоящее время обычно выделяют два больших класса способов кодирования: прямое кодирования (direct encoding) и косвенное кодирование (indirect encoding).
Прямое кодирование оперирует хромосомами, представляющими некоторое линейное представление ИНС, в котором в явном виде указаны все нейроны, веса и связи ИНС. Таким образом, всегда можно построить взаимно-однозначное соответствие между структурными элементами ИНС (нейронами, связями, весами и пр.), т.е. фенотипом, и соответствующими участками хромосомы, т.е. генотипом.
Этот способ представления нейронной сети является наиболее простым и интуитивным, а также позволяет применять к полученным хромосомам уже имеющийся аппарат генетического поиска (например, операторы кроссинговера и мутации). Из наиболее очевидных минусов такой схемы кодирования можно отметить «распухание» генотипа при увеличении количества нейронов и связей ИНС и, как следствие, низкую эффективность за счет значительного увеличения пространства поиска.
Косвенное кодирование (в некоторых источниках также используется термин weak — слабые, имея в виду слабосвязанные) исповедует более «биологичный» принцип — в генотипе кодируется не сам фенотип, но правила его построения (условно говоря, некая программа). При декодировании генотипа эти правила применяются в определенной последовательности (зачастую, рекурсивно и, зачастую, применимость правил зависит от текущего контекста), в результате чего и строится нейронная сеть.
При использовании косвенных методов кодирования генетическое представление (а, соответственно, и пространство поиска для генетических алгоритмов) получается более компактным, а сам генотип позволяет кодировать модульные структуры, что дает в определенных условиях преимущества в адаптивности полученных результатов. Взамен же мы получаем практическую невозможность проследить, какие изменения в генотипе привели к заданным изменениям в фенотипе, а также множество трудностей с подбором генетических операторов, сходимостью и производительностью.
Исторически, прямое кодирование было исследовано раньше и глубже, однако ряд минусов этого подхода заставляют исследователей все более пристально присматриваться к косвенным методам кодирования. Однако по своей сути косвенные методы весьма сложны для анализа. Например, одна и та же мутация правила, расположенного в начале «программы», оказывает колоссальный эффект, а примененная к «концевым» правилам — эффекта не оказывает вовсе, а в результате — генетический поиск имеет сильную тенденцию к преждевременной сходимости. Подбор операторов кроссинговера также является нетривиальной задачей, т.к. использование стандартных бинарных операторов, как правило, приводит к частому появлению нежизнеспособных решений.
1.3 ОБУЧЕНИЕ НЕЙРОННОЙ СЕТИ
Процесс, в котором характеристики нейронной сети настраиваются путем прогнозирования среды, в которую эта сеть встроена. Тип обучения обусловливается методом подстройки параметров. отличают алгоритмы обучения с учителем и без учителя.
Для того, чтобы нейронная сети была способна реализовать установленную задачу, ее необходимо обучить. распознают методы обучения с учителем и без учителя.
Процесс преподавания с учителем представляет собой представление сети подборки обучающих примеров. любой образец подается на входы сети, потом проходит обрабатывание внутри структуры НС, рассчитывается выходящий сигнал сети, который сравнивается с соответствующим значением целевого вектора, представляющего собой требуемый выход сети. потом по поставленному правилу вычисляется ошибка, и происходит поправка весовых коэффициентов связей внутри сети в зависимости от выбранного алгоритма. Векторы обучающего множества предъявляются последовательно, вычисляются погрешности и веса подстраиваются для каждого вектора до тех пор, пока погрешность по всему обучающему массиву не достигнет приемлемо невысокого уровня.
При обучении без учителя обучающее множество складывается только из входных векторов. Обучающий метод подстраивает веса сети так, чтобы получались согласованные выходящие векторы, т. чтобы представление довольно тесных входных векторов подавало одинаковые выходы. Процесс обучения, следовательно, выделяет статистические характеристики обучающего множества и группирует сходственные векторы в классы. Предъявление на вход вектора из данного класса предоставит назначенный выходящий вектор, однако до обучения нельзя предсказать, какой вывод будет вырабатываться данным классом входных векторов. Следовательно, выходы подобной сети обязаны модифицироваться в некоторую ясную форму, обусловленную процессом обучения. Это не является серьезной проблемой. естественно не трудно идентифицировать отношение между входом и выходом, поставленную сетью. Для обучения нейронных сетей без учителя приспосабливаются сигнальный прием обучения Хебба и Ойа.
Математически процесс изучения возможно описать последующим образом. В процессе функционирования нейронная сеть вырабатывает выходящий сигнал Y, реализуя определенную функцию Y = G(X). когда архитектура сети задана, то вид функции G определяется значениями синаптических весов и смещенной сети.
Пусть выводом определенной задачи является значение Y = F(X), данная параметрами входных-выходных данных (X1, Y1), (X2, Y2), …, (XN, YN), для которых Yk = F(Xk) (k = 1, 2, …, N).
Обучение складывается в поиске (синтезе) функции G, близкой к F в смысле некторой функции погрешности E.
когда подобрано множество обучающих примеров – пар (XN, YN) (где k = 1, 2, …, N) и способ вычисления функции погрешности E, то обучение нейронной сети преобразовывается в задачу многомерной оптимизации, обладающую сильно огромную размерность, при этом, поскольку значение E возможно владеть свободный вид обучения в общем случае – многоэкстремальная невыпуклая проблема оптимизации.
1.3.1 ЭТАПЫ ЭВОЛЮЧИИ НЕЙРОННОЙ СЕТИ
? Создание новой популяции. На этом шаге создается начальная популяция, которая, вполне возможно, окажется не кошерной, однако велика вероятность, что алгоритм эту проблему исправит. Главное, чтобы они соответствовали «формату» и были «приспособлены к размножению».
? Размножение. Ну тут все как у людей, для получения потомка требуется два родителя. Главное, чтобы потомок (ребенок) мог унаследовать у родителей их черты. При это размножаются все, а не только выжившие (эта фраза особенно абсурдна, но так как у нас все в сферическом вакууме, то можно все), в противном случае выделится один альфа-самец, гены которого перекроют всех остальных, а нам это принципиально не приемлемо.
? Мутации. Мутации схожи с размножением, из мутантов выбирают некое количество особей и изменяют их в соответствии с заранее определенными операциями.
? Отбор. Тут начинается самое сладкое, мы начинаем выбирать из популяции долю тех, кто «пойдет дальше». При этом долю «выживших» после нашего отбора мы определяем заранее руками, указывая в виде параметра. Как ни печально, остальные особи должны погибнуть.
1.4 СРАВНЕНИЕ ХАРАКТЕРИСТЕК НЕЙРОПОКЕТОВ
В настоящее время известно большое количество нейропакетов, выпускаемых рядом фирм и отдельными исследователями и позволяющих конструировать, обучать и использовать нейронные сети для решения практических задач.
Рассмотрим несколько нейропакетов, предназначенных для реализации на персональных компьютерах в различных операционных средах, по степени их универсальности, а также с точки зрения простоты использования и наглядности представления информации в таблице 1.
Таблица 1. Виды нейропокетов
Производительность Наименование продукта Платформа Функциональные характеристики
AbTech (Шалетсвилл шт Вайоминг США) http //www abtech com/MQ1 HTM ModelQuest Windows Интегральная среда для прогнозирования принятия решений и управления В основе лежит концепция «статистических сетей» (Statistical Networks) как сплава НС и статистических методов обработки
AlWare Inc Process Advisor Windows Нейропакет для решения задач управления динамическими процессами
Attar Software (Ланкашир, Великобритания) XpertRule Analyser Windows Пакет для построения моделей данных и выявления скрытых закономерностей на основе вероятностных правил, генетических алгоритмов или НС
BioComp Systems (Редмонд шт Вашингтон, США), NeuroGenetic Optimizer (NGO) Windows Инструментальная среда для оптимизации входных сигналов и структуры НС на основе генетических алгоритмов
California Scientific Software (Невада-Сити, шт Калифорния США), BrainMaker
Windows
Macintosh Инструментальная среда для разработки приложений на основе НС для распознавания образов, прогнозирования и нейросетевой памяти
Megaputer Intelligence (Москва, Россия) PolyAnalyst OS/2 Warp Windows Объектно-ориентированная среда для анализа данных, поиска закономерностей и представления их в символическом виде
АОЗТ «Альфа Систем» (ЛЭТИ, С - Петербург) Neuro Office Windows Пакет для проектирования интеллектуальных программных модулей на основе НС с ядерной организацией
Институт вычислительного моделирования СО РАН, Красноярск, Россия, Царегородцев В. Г. NeuroPro Windows Нейропакет для извлечения знаний из таблиц данных
OOO «НейрОК» (МГУ, Москва, Россия) Excel Neural Package Windows Нейропакет для статистического прогнозирования и анализа многомерных данных
НейроКомп (ВЦ СО РАН, Красноярск, Россия) Глаз Windows
Распознавание визуальных образов используется для обработки аэрокосмической информации
2 ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1 ПРАВИЛА ИГРЫ
Игра начинается на доске 8?8 клеток, поделенной на равные квадратные поля. Поля имеют два цвета: чёрный и белый, так, что соседние по вертикали и горизонтали поля раскрашены в противоположные цвета. Начальное положение фигур. У игроков в начале игры имеется одинаковое количество фигур, у одного из игроков белые, а у другого – чёрные. Всего у каждого игрока шестнадцать фигур: восемь пешек, два слона, два коня, две ладьи, ферзь и король. У каждого из цветов в начальной позиции фигуры определенное расположение. Белые занимают первую и вторую горизонтали, чёрные – седьмую и восьмую, горизонтальные ряды подписаны цифрами от одного до восьми снизу-вверх, а вертикальные ряды латинскими буквами от, а до h слева направо. Ряды пешек белых расположены на второй горизонтали и черные на седьмой. На углах доски стоят ладьи, на первой и восьмой горизонтали, рядом с ладьями – кони, рядом с конями – слоны. Расположение ферзя легко запомнить по выражению «ферзь любит свой цвет», белый ферзь стоит на белом поле, а чёрный на чёрном. На оставшейся клетки располагается король. Игра по этапная заключается в том, что сначала свои ходы делают белые, а потом черные. Пешка может ходить вперед перед собой на свободное поле, или если это первое перемещение пешка с исходной позиции может передвинуться на два поля вперед. Слон может ходить, если на диагоналях перед ним нет фигуры на любое поле по диагонали. Ладья может ходить на любое поле по вертикали или горизонтали, на которых она стоит, если перед фигурой свободно. Конь ходит на поле, находящееся на расстоянии 2 по вертикали и 1 по горизонтали или 1 по вертикали и 2 по горизонтали от текущего положения. Ферзь может ходит на любое поле по диагонали вертикали и горизонтали, на которых он стоит. Король может перемещаться двумя различными путями: ходить на любое рядом находящиеся поле. «Рокировка» — это перемещение короля и одной из ладей того же цвета по крайней горизонтали считающееся одним ходом короля и выполняющееся следующим образом: король перемещается с его исходного поля на два поля по направлению к ладье, затем ладья переставляется через короля на последнее поле, которое только что пересек король.
Рокировка становится невозможной: если король уже ходил, или с ладьей, которая уже ходила.
Рокировка временно невозможна: если поле, на котором стоит король, или поле, которое он должен пересечь, или поле, которое он должен занять, атаковано одной из фигур партнера; если между королем и ладьей, с которой должна быть произведена рокировка, находится какая-либо фигура.
Взятие на проходе – когда пешка совершает ход на две клетки через битое поле, находящееся под ударом пешки противника, то ответным ходом она может быть взята этой пешкой противника. При этом пешка противника перемещается на битое поле, а сбитая пешка снимается с доски. Взятие на проходе возможно только непосредственно в ответ на ход пешки через битое поле, на следующих ходах оно уже не разрешено.
Считается, что король находится «под шахом», если он атакован хотя бы одной фигурой партнера, даже если она не может сделать ход из-за того, что её собственный король остается под шахом или под него попадает. Ни одна из фигур не может сделать ход, который ставит или оставляет своего короля под шахом.
Ни одна из фигур не может быть перемещена на поле, занятое фигурой того же цвета. Если фигура переходит на поле, занимаемое фигурой партнера, последняя считается взятой и убирается с шахматной доски как часть того же самого хода. О фигуре говорят, что она атакует фигуру партнера, если эта фигура может произвести взятие на этом поле. Фигура, считается атакующей поле, даже если она не может на него пойти из-за того, что её собственный король остается под шахом или под него попадает.
Партия считается выигранной:
– кто первый ставит мат королю;
–когда противник сдаётся;
– если у противника закончилось время в том случае, признаётся проигравшим, иначе назначается ничья;
– если противник нарушил правила игры.
Партия заканчивается вничью:
– в «мёртвой позиции» положении, когда король остался против короля;
– если оба игрока согласны на ничью;
– правило 50 ходов.
2.2 ВЫБОР СРЕДСТВ ДЛЯ РЕАЛИЗАЦИИ ПРОГРАММЫ
В данный момент существует огромное разнообразие различных языков программирования. От функциональных до объектно-ориентированных. Для реализации нейронных сетей наиболее актуальными являются Python, Java, С++.
В данной работе был выбран язык программирования Python, который обладает следующими преимуществами перед остальными подобными языками:
? простота использования — данный язык является одним из самых простых в освоении и использовании;
? понятность — в этом языке наиболее простая семантика, что помогает в работе с легаси кодом, а также простыми названиями функций;
? наличие необходимых библиотек разработки;
? высокая скорость выполнения — большинство библиотек в Python написано на более низкоуровневом языке С++, что позволило добиться высокого быстродействия;
? мультиплатформеность — данный язык может использоваться на большом количестве систем, от Windows и Linux до Android и iOS.
В игре шахматах предусмотрены два режима игры: PvP (Player versus Player) и PvE (Player versus Environment)
Особенности режима PVP – это игра против других игроков, где ты не можешь предугадать ход противника и от этого становится больше поля для размышления ходов. В этом режиме можно также сыграть с другом проверить на что вы способны. Или сыграть с более сильным противником, чтобы научиться у него чему-нибудь новому для себя.
Особенности режима PVE – можно выбрать уровень сложности компьютера, против которого играть. Если ты в игре новичок, то в этом режиме можно ознакомится с игрой, её механиками. Игры могут быть однотипными против бота, но ты можешь использовать каждый раз разные стратегии игры.
2.3 СТРУКТУРА СИСТЕМЫ
Обратим внимание на тот факт, что функция, которую мы обучаем, не имеет представления о правилах игры в шахматы. Мы даже не обучаем ее тому, как ходит каждая фигура. Модель способна генерировать соответствующие правилам ходы, но мы не передаем ей никакой информации о самой игре. Модель извлекает эти знания, обрабатывая огромное количество сыгранных партий.
Генетические алгоритмы (ГА) – это адаптивные методы поиска, которые в последнее время используются для реш
