Диссертация (1137070), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Глава содержитподробное описание предложенного диссертантом способа конструированияНСХ и формулирование решаемой задачи в терминах ИНС,.Решение поставленной задачи (1) разделено на два этапа. Для каждого изних строится своя модель НСХ.Для представления задачи в терминах ИНС каждый нейрон снабжен двумяиндексами, которые соответствуют группе данных и номеру ЛЗ – для этапа 1, иномеру ЛЗ и номеру узла ВС – для этапа 2.

Значение аксона нейрона OUTxi= 1 наэтапе 1 показывает, что группа данных x будет включена в i-ый тип ЛЗ. Всевыходы OUTxi имеют бинарную природу.Диссертантом предложена инженерная идея оценки степени учетасинтезированными типами ЛЗ семантической смежности групп данных, ихсоставляющих, которую известные методы во внимание не принимают. Группыданных семантически смежны, если при анализе предметной области междуними выявляется такое отношение, что одна группа данных определеннымобразом характеризует (дополняет, расширяет и т.д.) смысловое значениедругой.

Семантическая смежность отражает семантические связи междуэлементами предметной области и позволяет выделить подмножества группданных, использующихся в близких или одних и тех же запросах. Диссертантомвведен дополнительный критерий, способствующий повышению качества ЛС:ISq  i 1II  OUT   OUTxix 12yi axyg   min .(9)y 1y xНа этапе 1 осуществляется синтез типов ЛЗ с учетом матрицысемантической смежности групп данных и ограничений (2), (3), (7).Диссертантом предложена модель НСХ для этапа 1 с функцией энергии, равной1 IE   2 i 1IIIj 1x 1y 1  A1   xy  1  ij   B1  ij  1   xy    2  axyg  1  D1  ij I  incomp _ grxy  incomp _ gryx    OUTxi  OUTyj  i 114, гдеI2BCg 1   a   1   OUTxyxi2 2  Fi x 1y 1yxI(10)1)матрица весовых коэффициентовW  w  :wxi , yj   A1   xy  1  ij   B1 xi , yjI 2 I 2ij  1   xy    2  axyg  1  D1  ij   incomp _ grxy  incomp _ gryx  , где ij – символ Кронекера;2B ICпорог нейрона xi : Txi   1    axyg   12  Fi 2 yy 1x2).Результатом решения этапа 1 является матрица X .(I  T )На этапе 2 осуществляется безызбыточное размещение синтезированныхтипов ЛЗ в узлах ВС с учетом ограничений (4) – (6), (8).

Диссертантомпредложена модель НСХ для этапа 2 с функцией энергии, равной1 R0E   2 r1 1IR0Tr2 1t1 1t 2 1i 1R0T  A2  t t  1   r r   OUTt r  OUTt r  121 2 112 2r 1t1 11I xit1  i 1)TD C2 2 EMD0  2  hr1 2  r1i 1    x  iiE2  trsrh tr11it12матрица весовых коэффициентовW ( T R0 )( T R0 )  SN pt1p 1  T pP0 B2   0 2  t1r1, где   OUTt1r1 (11) wt1r1 ,t2r2 : wt1r1 ,t2r2   A2   t1t2  1   r1r2 ,где t t – символ Кронекера;122)порогE2  trsrh tr112нейрона SN pt1p1  TpP0t1r1 :Tt1r1 IB2   0 ICD   xit1 i  2  2 EMD0  2  t1r1 i12  hr1 2  r1i 1    x  iiit1 .Результатом решения этапа 2 является матрица (T Y R ) .0Построенный НС-алгоритм в качестве исходных данных принимает нетолько формализованные характеристики РБД, но и два вектора весовыхкоэффициентов C1   A1 , B1 , C1 , D1  и C2   A2 , B2 , C2 , D2 , E2  для построения функцийэнергии ИНС этапов 1 и 2 соответственно.

Систематического способаопределения векторов C1 и C2 не существует. Необходимо найти такие вектораC1 и C2 , при которых НС-алгоритм дает квазиоптимальное решение задачи. Длянахождения C1 оптим. и C2 оптим. диссертантом предложено использование ГА.15При реализации ГА НС-алгоритм используется как «черный ящик»,осуществляющий отображение особи Ai  Bi  Ci  ... в соответствующую ейматрицу, по которой определяется фенотип особи: Ai  Bi  Ci  ...   X  Y  . ( I  T ) (T  R ) 0Во второй главе дано подробное описание использования ГА для решениязадачи, включая конструирование функций приспособленности для обоихэтапов с учетом целевой функции и ограничений задачи.В созданном НС-ГА-алгоритме можно выделить следующие роли. НСчасть отвечает за выполнение ограничений задачи и минимизацию S q .

Так как вобщем случае полный учет семантической смежности и ограничения задачимогут быть несовместны, то приоритет отдается выполнению ограничений. ГАчасть отвечает за минимизацию целевой функции (1).Использование ТМ предлагается диссертантом в качестве альтернативыпостроенному НС-ГА-алгоритму. Поскольку ТМ не обладает недостатком НСХстабилизироваться в локальном минимуме функции энергии НС, то в случае ееприменения отпадает необходимость в использовании ГА-оболочки длянейросетевого ядра.

Дополнительным аргументом в пользу применения табупоиска является тот факт, что подбор ГА-оболочкой весовых коэффициентовтермов функции энергии НС значительно увеличивает процессорное времярешения задачи, снижая эффективность такого подхода.Для оценки возможностей и преимуществ табу-поиска был построеноснованный на нем ТМ-алгоритм для решения задачи. Текст диссертациисодержит подробное описание ТМ-алгоритма и предложения диссертанта поусовершенствованию табу-поиска для каждого из этапов решения задачи сцелью улучшения качества решения и производительности ТМ-алгоритма.Для повышения эффективности работы ТМ-алгоритма предложена идеяперехода от последовательной к параллельной модели работы механизма табупоиска. Разработанная модель распределенной ТМ (РТМ) представляет собойобъединение Табу под-машин, структура которых определяется динамически изависит от количества процессоров, на которых функционирует РТМ.16Вовторойглаветекстадиссертацииприведенодоказательствоутверждения о том, что для предложенного диссертантом метода разбиения ТМэнергия полной ТМ аддитивна по энергиям Табу под-машин, составляющихP 1РТМ: E  E0  E1  ...

 EP 1   E p , где P – количество процессоров.p 0Третьяглавапосвященарассмотрениюособенностейчисленныхреализаций разработанных алгоритмов, параллельного механизма табу-поиска,определению пользовательских операций приведения.Диссертантом были определены две операции приведения.

Первая – длявыбора нейрона-победителя в процессе обработки соседних состояний. Вторая –для выбора нейрона-победителя в процессе обработки удаленных состояний.Обе операции коммутативны и имеют два операнда. Результатом выполнениякаждой из операций приведения является тот из операндов, который в большейстепени удовлетворяет правилам данной операции.В программной реализации РТМ-алгоритма степень учета семантическойсмежности групп данных при изменении состояния Табу-машины считается поупрощенной формуле, преложенной диссертантом в главе 2, на том процессоре,которому принадлежит нейрон, изменяющий свое состояние.

Результатвычисления, полученный на одном процессоре, рассылается на все остальныепроцессоры. Процедура проверки «критерия желания» РТМ была реализованапараллельно на каждом из процессоров. Аналогичный подход был использовани для подсчета значения целевой функции задачи.В четвертой главе рассматриваются методики апробации алгоритмов иописаны результаты практического применения предлагаемых методов. Вкачестве базы данных примеров рассматриваются три модельные задачиразличной размерности и задача синтеза ОЛС реальной БД ERP-системы HumanResource Management Tool (HRMT), используемой в международной ITкомпании ООО «Датавижн НН».Для определения влияния параметров ТМ / РТМ на качество решения ивремя его нахождения были проведены серии экспериментов по решениюэтапов 1 и 2 задачи при различных значениях параметров ТМ: табу-размера l,17количества циклов обработки удаленных состояний C, количества цикловобработки соседних состояний β.

Для каждой из модельных задач былополучено 372 пробных решения этапа 1 и 372 решения этапа 2 для каждого изразличных решений этапа 1.Декомпозиция проводилась на модельных задачах с помощью ЭМСО, НСГА-алгоритма и ТМ / РТМ. В качестве относительной метрики оценки качествадекомпозиции групп данных диссертантом взята степень неучета семантическойсмежности групп данных как характеристика полученного на этапе 1 множестваЛЗ: N q SqN N100% , где N – это число нейронов в НСХ. Значение данногопоказателя для модельных задач разной размерности сведены в Таб.2.

Рис.1показывает значение процессорного времени, потраченного на декомпозициюНС-ГА- и ТМ-алгоритмами, для модельной задачи с N  1600 .Таб. 2. Значение показателя N q на модельных задачахСтепень неучета N q семантической смежности групп данных, %N  100N  400ЭМСО36,8НС-ГА-алгоритм31,6ТМ / РТМ36,328,434,815,62,235,64,416,1Максимальный %Минимальный %Средний %4000N  160018,316,312,612,212,5Процессорное время, потраченное на декомпозицию групп данных3917,2350030002500Процессорноевремя2000(сек )15001000768,5392,2500164,20НС-ГА-алгоритмТМ: максимумТМ: среднееТМ: минимумРис. 1. Процессорное время, потраченное на декомпозицию данных при N  160018Впроцессеэкспериментальныхисследованийбылинайденыоптимальные безызбыточные размещения синтезированных типов ЛЗ по узламВС.

На Рис.2 представлен сравнительный анализ качества полученных решенийдля модельной задачи с N  1600 . Средние результаты, полученные с помощьюТМ / РТМ на модельной задаче большей размерности, качественнопревосходят результаты, полученные с помощью НС-ГА-алгоритма, на 8,7%, арезультаты, полученные с помощью ЭМСО, – на 23,6%.Значение целевой функции на решениях модельной задачи с N=16000,050,04950,04140,0450,040,03780,040,03680,0350,03Значение целевой0,025функции0,020,0150,010,0050ЭМСОНС-ГАалгоритмТМ / РТМ:максимумТМ / РТМ:среднееТМ / РТМ:минимумРис. 2. Значения целевой функции на решениях модельной задачи с N  1600 ,полученных с помощью ЭМСО, НС-ГА-алгоритма и ТМ / РТМАнализ результатов серий экспериментов позволил дать рекомендациипо выбору оптимальных значений тройки параметров ТМ / РТМ для решенияэтапа 2 задачи: l  T ; I  ,    0,5; 1 , C  20 .Все серии экспериментов по решению задач с использованием РТМпроводились на вычислительном кластере. Использование РТМ дает линейноеускорение.

Характеристики

Список файлов диссертации