Диссертация (Методы и алгоритмы интеллектуализации принятия решений в условиях неопределенности на базе аппарата нейронных сетей и эволюционного моделирования), страница 5

Однако вметоде ENS3 не реализован оператор кроссинговера, что необходимо посчитатьего недостатком, так как при должной реализации кроссинговер способенсущественно сократить время эволюции и ускорить формирование оптимальнойособи. Метод ENS3 также не допускает модификацию вида функций активациинейронов. Кроме того, фиксированные вероятности мутации для нейронов исвязей сокращают пространство поиска: многие эффективные конфигурации ИНСне могут быть сформированы в связи с низкой вероятностью изменения всоответствующих узлах ИНС текущей популяции.1.3.2 Нейроэволюционный метод расширения топологийNEAT (Neuro-Evolution by Augmenting Topologies, нейроэволюционныйметод расширения топологий) – метод, оптимизирующий веса и последовательноусложняющий структуру ИНС [77, 120].

Метод был разработан в 2002 году КеномСтэнли в Университете Техаса, Остин. Исходная популяция генерируется изполносвязных нейросетей, состоящих из входного и выходного слоев, количествонейронов в которых определяется заранее. За основу структуры генотипа в методевзят список синапсов. Каждый синапс хранит индексы двух нейронов (источникаи получателя сигнала), вес связи, бит активности, указывающий, активен ли24данный синапс, и инновационное число для определения аналогичных генов прикроссинговере [78].

Таким образом, в методе используется прямая схемакодирования. Метод NEAT реализует два оператора мутации для раздельноймодификациивесов и структуры; для каждого весового коэффициентавероятность мутации фиксирована. Структурные мутации увеличивают размергенотипа за счет добавления новых генов. Они добавляют либо связь для двухранее не соединенных нейронов, либо новый нейрон: при этом существующаясвязь разбивается на две – вход и выход нового нейрона. Замещаемая связьпомечается как не активная; вес входящей связи задается равным единице, а весисходящей приравнивается к весу замещаемой связи.Операторкроссинговерабазируетсягомологичныхгенов (аллелей) и процессагомологичныхгеновпереднакроссинговером.биологическихсинапсисаМетодпонятиях— выравниванияNEATиспользуетинновационные числа - исторические маркеры, связанные с каждым геном дляотслеживания хронологии вносимых в него изменений.

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

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

Для кластеризации на отдельные виды вводится расстояние междухромосомами – линейная комбинация количества E добавочных генов, количества̅:D обособленных генов и средней разности весов совпадающих генов =1 +2 ̅ ,+ 3 (1.4)где – количество генов в генотипе большей длины, необходимое длянормализации; 1 , 2 , 3 – заданные заранее коэффициенты.Разбиение на виды на основании метрики позволяет решить проблемунезащищенности инноваций. Алгоритм кластеризации популяции P на видысостоит из шагов:1.

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

Вычисление в эпоху для каждого генотипа ∈ расстояния допредставителей классов и создание при необходимости новых видов.Внутривидовая приспособленность особи рассчитывается исходя из общегозначения ее приспособленности и расстояния до других особей:′ =∑=1 ((,)),(1.5)где B – функция принадлежности к виду:1, (, ) ≥ ((, )) = {.0, (, ) < (1.6)В зависимости от суммы значений приспособленности ′ особей внутривида определяется потенциально возможное количество потомков ,принадлежащих данному виду: =̅̅̅̅̅̅̅̅,(1.7)26где ̅̅̅ – средняя приспособленность внутри вида k; ̅̅̅ = ∑ ̅̅̅ – сумма среднихприспособленностей всех видов; – размер популяции.Такимобразомопределяетсявнутривидовоеразделениеприспособленности. Виды с наименьшей приспособленностью не переходят наследующую эпоху; внутри оставшихся видов выбираются случайным образомособи для создания новой популяции. Особи с наилучшей внутривидовойприспособленностью переходят в следующее поколение, а при отсутствии такихособей предыдущее поколение полностью замещается.У метода есть несколько модификаций, к наиболее удачным из которыхотносятся: rtNEAT (real-time NEAT), Phased Pruning (Поэтапное упрощение),cgNEAT (Content-Generating NEAT), HyperNEAT (Hypercube-based NEAT) –метод, использующий косвенное кодирование для настройки параметровполносвязной ИНС при фиксированной структуре [50].К достоинствам метода NEAT относятся защита инноваций историческимимаркерами и поддержание разнообразия популяции за счет специализации.

Этидва подхода решают проблемы преждевременной сходимости и незащищенностиинноваций. Тем не менее, эволюция путем последовательного усложнения,реализованная в методе, является причиной таких недостатков как ограничениепространства поиска и высокая ресурсоемкость.1.3.3 Метод эволюционной модификации топологии нейронных сетейEANT (Evolutionary Acquisition of Neural Topologies, эволюционноемодифицированиетопологий нейронныхсетей) – метод, использующийгибридную схему кодирования CGE (common genetic encoding, обобщенная схемакодирования генов) [76].

Метод был разработан в 2005 году Йохансом Кассауноми Джеральдом Соммером в Университете имени Кристиана Альбрехтса, Киль,Германия. Схема CGE предназначена для раздельного модифицированияструктуры и параметров ИНС.Она обладает двумя важными свойствами:27полнотой и замкнутостью. Благодаря использованию CGE в методе EANTудалось избежать этапа декодирования хромосом.

Схема CGE определяет генотипИНС как линейную последовательность генов, способных принимать одну из трехразличные форм (аллелей) [118]: вход, узел или джампер. Вход – это ген,обозначающий входной нейрон. Узел – это ген, обозначающий нейрон, которомусоотнесены четыре параметра: весовой коэффициент, текущее значение функцииактивации, глобальный уникальный идентификатор GUID (Global UniqueIDentifier) и количество входных связей. Джампер – ген синаптической связи,хранящий ссылки на два узла, соединенных данной связью, и GUID нейрона, скоторым соединен джампер.

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

Процесс расчета выходных значений фенотипов нетребует их декодирования в генотипы и состоит из следующих шагов:1. Инициализация. Процесс вычисления выходов нейронов идет справаналево; на начальном этапе определяется самый правый элемент линейногогенома.2. Проход справа налево по генотипу. Для каждого элемента генотипавыполняются правила: если текущий элемент – это вход, его текущее значение ивес заносятся в стек; если текущий элемент – это нейрон, из стека извлекаются lсвязанных с ним входных значений и их весовые коэффициенты.

Результатвычисления функции активации нейрона и вес заносятся обратно в стек. Еслитекущий элемент – это джампер, то для него определяется последнее значениенейрона, чей GUID совпадает со значением GUID джампера. Значение веса,хранящееся в джампере, заносится в стек. Если джампер представляет собой28прямую, а не рекуррентную связь, сначала происходит копирование участканейросети начиная с нейрона, чей GUID совпадает с GUID джампера.

Дляопределенной таким образом подсети вычисляется значение выхода. Данноезначение и соответствующий ему вес заносятся в стек.3. Формирование выходного вектора ИНС. После полного прохода справаналево по генотипу из стека последовательно извлекаются значения вычислений,количество которых совпадает с количеством выходов ИНС.