Содержание к диссертации
Введение
1. Анализ и исследование оптимизации структуры и управления системами обработки информации 9
1.1. Проблема создания структуры и управления системами обработки информации 9
1.2. Анализ численных методов оптимизации 13
1.3. Анализ математических моделей нейронных сетей 16
1.4. Анализ математических моделей оптимизации структуры системы обработки информации на основе генетических алгоритмов 29
1.5. Выводы 44
2. Исследование синергетической концепции управления системами обработки информации 46
2.1. Математическая модель распознавания образов в задаче управления системами обработки информации 46
2.2. Исследование структуры фазового пространства синергетической модели распознавания 50
2.3. Модель классификации образов с изменённой топологией стационарных решений 69
2.4. Выводы к разделу 2 78
3. Создание генетического алгоритма оптимизации структуры системы обработки информации 81
3.1. Многоуровневая декомпозиция системы обработки информации 81
3.2. Построение модели системы обработки информации 83
3.3. Реализация генетического алгоритма оптимизации структуры системы обработки информации 105
3.4. Выводы к разделу 3 115
4. Численное моделирование процессов распознавания и классификации 117
4.1. Численный расчёт бифуркаций в нейронной сети второго порядка 117
4.2. Моделирование распознавания и классификации 120
4.3. Выводы к разделу 4 134
5. Экспериментальная проверка генетических алгоритмов с переменной длиной хромосом на задачи оптимизации структуры системы обработки информации 135
5.1. Обобщённая форма представления СОИ 135
5.2. Описание целевых функций оптимизации структуры СОИ 138
5.3. Оценка глубины декомпозиции СОИ, описание подсистем 148
5.4. Результаты оптимизации структуры СОИ 154
5.5. Выводы к разделу 5 166
Заключение 168
Литература 172
Приложение 185
- Анализ математических моделей нейронных сетей
- Построение модели системы обработки информации
- Моделирование распознавания и классификации
- Оценка глубины декомпозиции СОИ, описание подсистем
Анализ математических моделей нейронных сетей
К настоящему моменту разработано громадное количество методов распознавания образов, каждый из которых обладает своими достоинствами и недостатками. Наиболее перспективными являются модели нейронных сетей, полученные на основе чрезвычайно разрозненных данных о функционировании мозга как системы в целом.
Искусственные нейронные сети имеют мало общего с реальными нейронными структурами и являются формальными системами, призванными не повторять морфологию мозга, а пытаться воспроизвести его характерные функциональные возможности. При этом существует некоторая аналогия между формальным и биологическим нейроном, основанная на сходстве между функционированием нейрона как системы «вход-выход» и аналогового сумматора с взвешенными входами.
Мозг состоит примерно из 100 млрд. нейронов, которые и являются функциональными единицами обработки информации. Каждый нейрон состоит из сомы, дендритов, по которым к нейрону поступают сигналы от других нейронов, и обычно одного аксона - волокна, по которому передается реакция данного нейрона к остальным (рис. 1.1).
На мембране сомы и дендритов расположены синапсы - окончания аксонов других нейронов. Сигналы характеризуются различными электрическими сопротивлениями и могут быть тормозящими и возбуждающими. Таким образом, функциональная система нейрона может выглядеть так, как показано на рисунке 1.2, где Ij - значение входных сигналов; Wj - коэффициенты передачи синапсов, Д5) - нелинейная функция, описывающая нейрон.
Совокупность нейронов и связей между ними определяют характер функционирования мозга. Особый интерес вызывают модели, имитирующие действие реальных нейронных ансамблей - моделей нейронных сетей и устройств, построенных на принципах НС - нейрокомпьютеров.
В процессе развития находится создание суперкомпьютеров для решения задач искусственного интеллекта на базе транспьютеров, т. е. однокристальных 32-х разрядных микроЭВМ с ограниченным набором команд и быстродействием порядка 10-и млн. операций в секунду. Транспьютер имеет шину с другими транспьютерами, посредством чего образуется мощный мультипроцессорный комплекс. Такие системы могут лишь повысить эффективность решения ряда задач искусственного интеллекта (ИИ), но не дать принципиально новые пути для создания интеллектуальных устройств, поскольку являются по своей архитектуре традиционными последовательными компьютерами. При этом аппаратная реализация нейронных сетей (НС) может позволить создавать системы не столь эффективные для выполнения вычислительных задач, но зато обеспечивающие технологический прорыв в тех случаях, когда требуется имитация ассоциативной памяти, обучение и интуитивный выбор решения.
Первой работой в области систематического исследования НС является статья Маккалокка и Питса, в которой была построена нейронная модель на основе схемы, показанной на рисунке 1.2, причем функция являлась пороговой, для которой выход равен 1, если вход больше заданного порогового значения, и 0 в противном случае. Соединение таких элементов путем подачи сигналов с выхода каждого нейрона на входы нескольких сумматоров представляет собой простейшую НС, получившую название перцептрона (простого или однослойного). Для каждой входной конфигурации определяется желаемая выходная, и обучение сводится к пересчету весовых коэффициентов по ошибке, рассчитываемой как разность между фактическими и желаемыми откликами для подаваемой на вход тестовой конфигурации. Процедура повторяется до тех пор, пока для любого входа не начинают воспроизводиться желаемые выходные наборы состояний нейронов.
В свое время была доказана теорема об обучении перцептронов, однако в 60-е годы выяснилось, что перцептроны не могут решать ряд простейших задач, в частности реализовать функцию «исключающее ИЛИ». Кроме того, неизвестно время обучения в каждом конкретном случае, хотя и доказано, что оно всегда конечно, а так же не определено, что распознавание перцеп-троном более эффективно, чем простой перебор весов связей входного и выходного слоев.
Затем были созданы более развитые схемы перцептронов, например, многослойный перцептрон, использующий для обучения процедуру обратного распространения ошибок, и сеть встречного распространения. В отличие от простого перцептрона, состоящего из двух слоев, многослойный объединяет в своей структуре п слоев: входной, выходной и 7V-2 скрытых. Каждый элемент соединен с элементами соседних слоев, но не соединен с элементами своего слоя. Сигнал может передаваться только от низших (входных) к высшим (выходным) слоям.
Обучение сводится к определению коэффициентов связи последовательно для всех слоев путем минимизации ошибки как функции этих коэффициентов и сигналов выходного слоя от каждой реализации. Сети встречного распространения состоят из входного слоя, слоя Кохонена и слоя Гроссберга. Слой Кохонена классифицирует входные векторы в группы схожих, причем каждая группа анализирует только один выходной нейрон, коэффициенты связи с которым слоя Гроссберга и образуют выходной вектор сети, обладая более быстрым по сравнению с процедурой обратного распространения алгоритмом обучения, сети встречного распространения обладают меньшей сферой применения, хотя и более просты в создании.
Основными недостатками перцептронных моделей считаются: во-первых, отсутствие обратной связи, что исключает динамику и сужает область применения перцептронов, т. к. они обучаются лишь однородным по смыслу образам.
Вследствие этого перцептронные сети можно использовать для построения специализированных устройств (систем распознавания речи, символов, синтеза речи по тексту, свертки изображений и т.д.), но они явно непригодны в качестве основы для универсальных систем ИИ. В моделях обратного распространения возможен паралич сети, т.е. остановка обучения, и попадания в ложный минимум. Кроме того, может потребоваться многократное предъявление обучающей выборки, что далеко не всегда удобно. Из-за указанных причин, внимание исследователей сосредоточилось на сетях Хопфилда.
Базовая модель НС Хопфилда имеет взвешенную сумму состояний N нейронов, которая подается на пороговые элементы, формирующие сигналы, вновь передаваемые на входы соответствующих нейронов, т. е. схема аналогична представленной на рисунке 1.2, за исключением того, что существует обратная связь. Состояние нейрона равно +1, выход порогового элемента равен 1 в том случае, когда указанная сумма больше порогового значения, и —1, если сумма меньше или равна пороговому значению. Обратная связь дает новые результаты: изменение нейронов возможно как синхронно, так и асинхронно, а так же наличие одношагового обучения.
Динамические свойства модели Хопфилда позволили создать методы построения НС, имеющих собственную логику. Сети Хопфилда обладают различными формами реализации:
- стандартная модель с бинарным состоянием нейронов и определенным правилом перехода;
- дискретная сеть с нейронами, состояния которых определяются целыми числами от 0 до некоторого L;
- сеть с непрерывной динамикой.
Матрица связей между нейронами составляется либо симметричной, либо асимметричной. Симметрия сети есть достаточное условие для ее устойчивости, тогда как асимметричная матрица связей позволяет расширить возможности нейронных моделей.
Алгоритм обучения сетей с детерминистской динамикой не позволяют полностью избежать вышеуказанных недостатков или свести вероятность подобного исхода к малой величине, хотя число ложных образов растет с увеличением а, при некотором а корректное распознавание вообще невозможно. Предложенная «машина Больцмана» основана на стохастической динамике, когда состояние нейронов изменяется в соответствии с некоторым распределением вероятностей, характеризующим энергию системы и абстрактной температурой, значение которой уменьшается с течением времени. В результате достигается устойчивое состояние с большей, чем для детерминированных систем, вероятностью его истинности. Стохастическая динамика увеличивает общее время распознавания и обучения, предъявляя требования к функции, определяющей вероятность переходов.
Построение модели системы обработки информации
Для удобства обозначения различных видов связей в дальнейшем будем обозначать через СР связи реализации процедур обработки информации, через СХ - связи хранения информации, через СП - связи передачи информации.
Сформулируем ряд определений и допущений, которые представляются «вполне естественными» с учётом имеющихся ограничений на рассматриваемые системы (см. разд. 1.1).
Допущение 1. Обработка информации каждым компонентом базовой подсистемы обеспечивается компонентами всех образующих её подсистем.
Определение 5. Активный компонент - это компонент, принимающий участие в обеспечении текущего объекта.
Допущение 2. Связи реализации СР между компонентами одной подсистемы характеризуются порядком их активации.
Определение 6. Связанными (СР) называются компоненты, участвующие в обеспечении соседних, последовательно идущих 00.
Для подсистемы первого уровня декомпозиции связанными (СР) являются компоненты, обеспечивающие реализацию соседних процедур. Для подсистемы второго уровня декомпозиции связанными (СР) являются компоненты, обеспечивающие связанные компоненты базовой подсистемы и т. д.
Допущение 3. В образующей подсистеме обеспечение объекта осуществляется одним и только одним её компонентом.
Поясним данное допущение. Поскольку не запрещается участие одного и того же компонента образующей подсистемы в обеспечении нескольких различных компонентов базовой подсистемы, то данным допущением мы отказываемся от рассмотрения систем, в которых допускается временное объединение нескольких устройств для параллельного обеспечения одного 00. Например, мы отказываемся от возможности создавать временно для реализации одной процедуры компьютер с несколькими процессорами или жёсткими дисками, которые после реализации будут переустановлены на другие компьютеры. Не следует путать подобное параллельное обеспечение с параллельным обеспечением нескольких компонентов базовой подсистемы различными компонентами одной образующей подсистемы, что вполне допустимо (рис. 3.2, б), а также с обеспечением одного компонента базовой подсистемы компонентами нескольких образующих подсистем (рис. 3.2, в).
Допущение 4. СР между компонентами различных подсистем одной группы образующих подсистем характеризуются взаимной активностью этих компонентов и степенью связи, т. е. количеством вовлечённых в связь подсистем.
Определение 7. Для СР 2-ой степени и выше связанными называются взаимно активные компоненты образующих подсистем.
Компоненты различных подсистем различных групп образующих подсистем также могут быть связанными между собой, но связь эта опосредованная. Говорить о взаимной активности компонентов различных групп образующих подсистем можно только ссылкой на общий ОО более высокого уровня, в обеспечении которого эти компоненты принимают участие именно в таком сочетании. Следовательно, при этом будут рассматриваться связи, о которых уже шла речь.
Определение 8. Построить способ активации f - значит перечислить все ПА соответствующего множества Q\ . В дальнейшем под способом активации или способом формирования связи будем понимать конкретную реализацию функции связи внутри подсистемы или между подсистемами.
Способ активации компонентов внутри образующей подсистемы, по сути, является способом организации связи между образующей и базовой подсистемами и может быть условно принят как способ организации связей реализации 1-ой степени.
Отметим, что если компонент а т &А[, т. е. обеспечивает некоторый объект при данном k-ош способе активации, то, в силу допущения 1, найдётся взаимно активный ему компонент aJn є AJk, обеспечивающий тот же самый объект. Обозначим через FlJ множество всех возможных способов формирования связей 2-ой степени между компонентами образующих подсистем одной группы.
Определение 9. Построить fll 2- n - способ формирования СР п-ой степени между подсистемами одной группы образующих - значит перечислить все группы взаимно активных компонентов (ГВАК) соответствующего множества QV2- n .
Для связей 3-ей степени подсистем одной группы выражение (3.11) принимает вид.
Способ организации связей хранения СХ также можно разделить по степеням.
Допущение 5. СХ информации 1-ой степени характеризуются объектом хранения (компонентом подсистемы, требующим определённого места хранения) и хранилищем (компонентом ТО). Объект хранения и хранилище образуют пару хранения (ПХ).
Определение 10. Построить f - способ формирования СХ 1-ой степени между подсистемой ТО с номером і и подсистемой с номером у, компоненты которой выступают в роли объектов хранения - значит перечислить все ПХ соответствующего множества Ql.
Допущение 6. СХ информации старших степеней характеризуются количеством объектов хранения и общностью места их хранения.
Объекты хранения с общим местом хранения образуют группу общего места хранения (ГОМХ). Как следует из допущения 5, в роли объекта хранения могут выступать компоненты различных подсистем. Введём дополнительную фиктивную подсистему с номером х, объединяющую все объекты хранения.
Допущение 7. Связи передачи информации СП характеризуются физической топологией вычислительной сети.
Подобные связи возможны только между компонентами подсистемы ТО. Среди основных видов топологии (рис. 3.3): шинной, звездообразной, кольцевой, иерархической, многосвязной и комбинированной оптимизация СП без нарушения вида топологии возможна и имеет смысл только в многосвязной сети или в комбинированной в той её части, которая имеет многосвязную топологию.
Моделирование распознавания и классификации
В соответствии с методикой, изложенной в предыдущих разделах, была построена синергетическая нейронная сеть с распознаванием и классификацией образов. Каждый образ v, состоял из ста скалярных компонент, при этом /=1,2,...,98 (7V=100, М=98), т. е. эксперименты проводились почти на границе ёмкости памяти (см. раздел 2). Каждая компонента вектора vt принимала целые значения от 0 до 15 (для НС это необязательно, однако такое ограничение диапазона было удобно при работе на персональном компьютере).
Образы были сформированы с использованием генератора случайных чисел, работающего от внутреннего таймера компьютера, который дает распределение вероятностей, близкое к равномерному. В течение всего численного эксперимента на случайно выбираемый прототип Vk накладывался вектор шумов %, образованный также с использованием генератора случайных чисел с различной дисперсией, после чего получившийся вектор q предъявлялся сети для распознавания или классификации.
Серия экспериментов с одним предъявляемым образом проводилась для различных значений р и состояла из трех этапов. На первом из них проводилось распознавание в стандартной модели из разделов 2 и 3. Затем выполнялась классификация q в модели, построенной по алгоритму, разработанному в разделе 4, для различных значений отношения мощностей множеств v=jui/ju2, менявшихся в диапазоне от 0 до 1 (соответственно v=0 означало, что подмножество W2 совпадает с Д a v=l - случай равномощных подмножеств W] и W2).
Прототип vk для формирования предъявляемого образа всегда выбирался из первого множества, таким образом успешным признавалось такое окончание динамического процесса, когда все моды, не принадлежавшие Ди релаксировали к нулю. После этого - на третьем этапе - в случае успешной классификации выполнялось распознавание в выбранном классе по схеме, аналогичной применявшейся на первом этапе, но в качестве начальных условий принимались те значения, которые имели моды множества Дх в конце классификации.
На каждом этапе был установлен контроль успешности его завершения и длительности переходного процесса в тактах. Для интегрирования системы нелинейных обыкновенных дифференциальных уравнений был использован метод Эйлера, обеспечивающий для данной системы достаточную скорость сходимости и приемлемую погрешность в случае выполнения ограничений на параметры Xh найденных в разделе 3, поскольку при распознавании в си-нергетической НС основные требования предъявляются к качественному результату.
Численное интегрирование прекращалось, когда моды, либо не соответствовавшие, либо соответствовавшие искомому прототипу (множеству) принимали значения, по абсолютной величине меньшие заданного порога. В первом случае процесс считался завершенным успешно, во втором - нет.
Было проведено несколько серий компьютерных экспериментов для различных прототипов со следующими параметрами сети: шаг разностной сетки метода Эйлера /г=0.1, =3.0, С=1.0, A\=Ai=\.0. По результатам моделирования были построены графики, характеризующие функционирование предложенной модели: зависимость качества распознавания, классификации и распознавания в выбранном классе J, а также зависимость длительности переходного процесса Т на тех же этапах от уровня шума р при различных значениях v.
Под качеством процесса понимается отношение числа успешно завершенных этапов (т. е. тех случаев, когда в результате распознавания был выбран требуемый прототип или в результате классификации - искомое подмножество) к общему числу экспериментов, попавших на некоторый интервал изменения уровня шума.
Длительность переходного процесса - это средняя длительность распознавания или классификации для успешно завершенных этапов на данном интервале изменения уровня шума. Графики изначально представляют собой кусочно-постоянные зависимости характеристик от уровня шума, последствий аппроксимированные непрерывными функциями. Ширина интервала усреднения на оси р была равной 0.2.
Оценка глубины декомпозиции СОИ, описание подсистем
Декомпозиция СОИ по видам обеспечения [27, 51] процесса обработки информации приводит к схеме, представленной на рисунке 5.4. Часть подсистем СОИ специализируется на обслуживании информационных задач какого-либо определённого этапа обработки информации (математическое, лингвистическое обеспечение и др.). Как правило [27], в СОИ ЭВМ имеются подсистемы функционально-логической и конструкторской обработки информации [52-54]. Подсистемы, представленные на рисунке 5.4, участвуют практически во всех этапах обработки информации. При этом компоненты каждой из этих подсистем призваны выполнять сходные задачи и являются частично взаимозаменяемыми. Подсистемы видов обеспечения на рисунке 5.3.1 составляют первый уровень декомпозиции СОИ. Рассмотрим более подробно каждую из этих подсистем.
Компонентами подсистемы являются АРМ. В настоящее время разработано несколько типов серийно выпускаемых АРМ [27,55,56], содержащих различные устройства. В нашем случае состав АРМ не уточняем, считаем его «типовым» и полагаем, что на данных АРМ можно выполнить любую процедуру обработки информации, если позволит конфигурация отдельных компонентов. Компоненты частично взаимозаменяемы (частично в том смысле, что не всякое ПО предназначено для реализации нескольких процедур или ПО может оказаться критичным к конфигурации ТО и компонент ТО будет не способен работать с подобным ПО).
Число активных компонентов подсистемы переменно. Т. е. часть АРМ может не участвовать в процессе обработки информации. После окончания эволюционного развития можно делать вывод о реально необходимом количестве компонентов ТО. Начальное значение имеет смысл приравнять к числу проектных процедур, по одному АРМ на каждую процедуру.
Компонентами ПО являются программно-методические комплексы (ПМК), осуществляющие обработку информации. Компоненты отличаются друг от друга по области применения, по требованиям к конфигурации компонентов ТО. В случае, когда некоторые компоненты ПО способны выполнять несколько процедур обработки информации при наличии альтернативного выбора конкретного ЭО, они становятся частично взаимозаменяемыми.
Практика показывает [41], что 5-6 ПМК обеспечивают реализацию всех процедур обработки информации. В данной задаче количество ПМК установлено равным 6. Поскольку реальных ПМК мы не рассматриваем, время реализации каждой процедуры каждым ПМК для каждого уровня быстродействия было установлено с использованием генератора случайных чисел. Для того чтобы устанавливаемые значения были корректны с точки зрения различного быстродействия компьютеров, применялся следующий алгоритм:
- для каждой процедуры случайным образом выбирается п - количество ПМК, способных обеспечивать выполнение этой процедуры;
- случайным образом выбирается п различных номеров ПМК, которые составят набор альтернативных ЭО этой процедуры;
- все ПМК, не вошедшие в состав альтернативных ЭО, получают отрицательное значение времени реализации процедуры (например, -1). Отрицательное время служит сигналом неспособности ПМК обеспечивать данную процедуру;
- для ЭО время ранжируется по уровням быстродействия АРМ. Устанавливается предельное время реализации (100 условных единиц). Время t0 для уровня 0 случайным образом выбирается из диапазона от 1 до 100, t\ для уровня 1 выбирается из диапазона от 1 до t0 (т. е. процедура будет выполнена за время, не превышающее времени реализации этой же процедуры на АРМ с уровнем быстродействия 0) и т. д.
Компонентами подсистемы являются блоки данных, используемые для реализации тех или иных процедур. Формы хранения, а также место хранения разных блоков данных различна. При наличии альтернативы в выборе блока в качестве поставщика исходных данных возможна частичная взаимозаменяемость компонентов этой подсистемы. Форма хранения и доступа к данным предъявляет определённые требования к конфигурации компонентов подсистемы ТО.
Поскольку реальных блоков данных не рассматриваются, то время доступа к каждому блоку каждого способа хранения для каждого уровня быстродействия было установлено с использованием генератора случайных чисел. Количество блоков данных установим равным 22. Для того чтобы устанавливаемое время доступа было корректно с точки зрения различного быстродействия компьютеров, применялся следующий алгоритм:
- для каждого способа хранения (прямой доступ, удалённый доступ, перерасчёт) выставляется порядок времени доступа (1, 10 и 100 условных единиц времени соответственно);
- время прямого доступа tp устанавливается минимальным - одна условная единица для каждого уровня быстродействия;
- время удалённого доступа tu выбирается из диапазона от tp до 10, нижняя граница корректируется: время доступа для АРМ с высшим уровнем не превышает времени для АРМ с низшим уровнем;
- время перерасчёта tr выбирается из диапазона от tu до 100, нижняя граница корректируется: время доступа для АРМ с высшим уровнем не превышает времени для АРМ с низшим уровнем, но выше времени удалённого доступа.
Кроме этих данных имеется информация о допустимости использования каждого блока данных в качестве исходного для каждой процедуры. Таблица формируется по следующему алгоритму:
- случайным образом выбирается п - количество пригодных блоков данных;
- случайным образом выбирается п различных номеров блоков данных, в таблице соответствующим элементам присваивается значение 1;
- элементам таблицы, соответствующим невыбранным блокам данных, присваивается 0.
Значение 0 сигнализирует о том, что текущий блок данных не может быть использован при реализации текущей процедуры, а значение 1 сигнализирует об обратном.
