автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ и разработка алгоритмов эффективного управления системами обработки информации

ВВЕДЕНИЕ.

1. АНАЛИЗ И ИССЛЕДОВАНИЕ ОПТИМИЗАЦИИ СТРУКТУРЫ

И УПРАВЛЕНИЯ СИСТЕМАМИ ОБРАБОТКИ ИНФОРМАЦИИ.

1.1. Проблема создания структуры и управления системами обработки информации.

1.2. Анализ численных методов оптимизации.

1.3. Анализ математических моделей нейронных сетей.

1.4. Анализ математических моделей оптимизации структуры системы обработки информации на основе генетических алгоритмов.

1.5. Выводы.

2. ИССЛЕДОВАНИЕ СИНЕРГЕТИЧЕСКОЙ КОНЦЕПЦИИ УПРАВЛЕНИЯ СИСТЕМАМИ ОБРАБОТКИ ИНФОРМАЦИИ.

2.1. Математическая модель распознавания образов в задаче управления системами обработки информации.

2.2. Исследование структуры фазового пространства синергетической модели распознавания.

2.3. Модель классификации образов с изменённой топологией стационарных решений.

2.4. Выводы к разделу 2.

3. СОЗДАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ОПТИМИЗАЦИИ СТРУКТУРЫ СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ.

3.1. Многоуровневая декомпозиция системы обработки информации.

3.2. Построение модели системы обработки информации.

3.3. Реализация генетического алгоритма оптимизации структуры системы обработки информации.

3.4. Выводы к разделу 3.

4. ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ РАСПОЗНАВАНИЯ И КЛАССИФИКАЦИИ.

4.1. Численный расчёт бифуркаций в нейронной сети второго порядка

4.2. Моделирование распознавания и классификации.

4.3. Выводы к разделу 4.

5. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С ПЕРЕМЕННОЙ ДЛИНОЙ ХРОМОСОМ НА ЗАДАЧИ ОПТИМИЗАЦИИ СТРУКТУРЫ СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ.

5Л. Обобщённая форма представления СОИ.

5.2. Описание целевых функций оптимизации структуры СОИ.

5.3. Оценка глубины декомпозиции СОИ, описание подсистем.

5.4. Результаты оптимизации структуры СОИ.

5.5. Выводы к разделу 5.

Актуальность темы. В последнее время наблюдается внедрение систем обработки информации (СОИ) практически во все области человеческой деятельности. Помимо увеличения состава СОИ (кроме традиционных САПР, АСУ и АСУ ТП появились различные банковские системы, системы управления транспортом, предприятиями, складами, всевозможные виды САПР, вычислительные сети и т. д.) изменились основные подходы к их управлению. Традиционно на управление выделялось столько средств, сколько требовалось, поскольку исследования в конкретной области имели приоритетный характер. Для каждой новой СОИ создавалось уникальное программное обеспечение (ПО). В таких условиях эффективность систем вызывала интерес лишь с научной точки зрения. На сегодняшний день возник обширный рынок унифицированного ПО, различные программные комплексы (ПК) способны решать сходные задачи, имеется широкий выбор информационной поддержки. Одновременно с возможностью выбора средств реализации, ставятся существенные ограничения на финансирование. Поэтому задача эффективности управления СОИ, рассматриваемой в обобщённой форме, является актуальной задачей, имеющей прикладное практическое значение, что подтверждается постоянно высоким числом научных работ, посвящённых проблеме эффективности управления систем обработки информации.

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

Задачи эффективности управления СОИ характеризуются большим удельным весом задач динамического расчёта, связанных с выбором структуры и обеспечивающих заданное качество функционирования по выбранному целевому функционалу (критерию).

Структура системы допускает декомпозицию системы по видам обеспечения процесса обработки информации. Анализ структуры проводится с помощью синергетической модели распознавания на основе нейронных сетей (НС).

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

Задача эффективности управления процессами обработки информации относится к задачам оптимизации структуры СОИ, для численного решения которых разработано множество методов. Однако СОИ включает в себя несколько классов подсистем, свойства и особенности обработки информации которых различны, поэтому выбор методов оптимизации структуры СОИ в общем случае является трудоёмкой и неоднозначной задачей. Анализ показывает весьма ограниченную возможность существующих традиционных методов и алгоритмов оптимизации. Следовательно, важной и актуальной задачей является разработка алгоритма, допускающего многокритериальную оптимизацию, инвариантного к виду и количеству целевых функций и не зависящего от конкретных особенностей рассматриваемой СОИ. Предлагаемый алгоритм оптимизации структуры СОИ основан на эволюционно-генетическом подходе моделирования биологических механизмов популяци-онной генетики и является расширением метода, известного под названием «генетические алгоритмы» (ГА).

Таким образом, с учётом вышесказанного, тема работы, посвящённая анализу и эффективности управления СОИ, является актуальной как в научном, так и в прикладном аспекте.

Объектами исследования являются параметры, структура СОИ и алгоритмы повышения эффективности управления обработкой информацией.

Целью работы является анализ и разработка машинно-ориентированных алгоритмов параметрического анализа на основе применения синергетической модели ассоциативной НС и структурной оптимизации СОИ с помощью ГА с переменной длиной хромосом.

Поставленная цель потребовала решения следующих задач:

1. Системный анализ проблем, принципов и особенностей эффективности управления СОИ; исследование и постановка задачи разработки алгоритмов параметрического анализа и структурной оптимизации СОИ.

2. Разработка математической модели классификации образов на основе синергетической концепции и исследование структуры фазового пространства НС.

3. Формальное представление структуры СОИ в виде модели связей; разработка машинно-ориентированных алгоритмов структурной оптимизации СОИ с помощью ГА с переменной длиной хромосом.

4. Численное моделирование НС для задач параметрического анализа и структурной оптимизации СОИ.

5. Разработка программного комплекса и экспериментальная проверка ГА на примере оптимизации структуры СОИ промышленного объекта.

Методы исследований. Для теоретических исследований применялись методы теорий нейронных сетей, синергетики, генетических алгоритмов, графов, множеств, вероятностей. Исследование свойств НС производилось на основе методов теории обыкновенных дифференциальных уравнений, теории устойчивости в линейном приближении с использованием аппарата линейной алгебры.

Научная новизна работы:

1. На основе известной синергетической концепции математической модели НС распознавания образов создана модель НС классификации с пересекающимися и непересекающимися подмножествами эталонов.

2. Наряду с количественными оценками эффективности альтернативных структур СОИ принимают участие результаты качественного сравнения в виде ряда предпочтений с использованием многослойной искусственной НС.

3. На основе обобщения и систематизации накопленного опыта оптимизации структуры системы и особенностей её реализации разработаны логические и эволюционные правила и стратегия их использования в процессе автоматизированного синтеза оптимальных вариантов структуры СОИ.

4. Разработан и реализован машинно-ориентированный ГА структурной оптимизации СОИ, использующий представление допустимых решений в виде хромосом с переменной длиной, и не зависящий от особенностей обработки информации конкретной системы, вида и количества целевых функций, ограничений на внутренние параметры системы.

Практическая ценность работы.

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

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

3. Разработанные инженерные методики и программный комплекс выполнены в рамках научно-технической программы РФ «Научные направления высшей школы по приоритетным направлениям науки и техники» на 2001-2002 годы, подпрограмма 201. Производственные технологии, раздел 201.06. Интеллектуальные системы автоматизированного проектирования и управления производством, проект 06.01.075. Моделирование теплового режима и помехозащищённости эволюционирующей конструкции ЭВМ в условиях развивающихся интеллектуальных систем автоматизированного проектирования и управления производством.

4. Результаты проведённых исследований анализа сложных технических систем управления в форме методических указаний используются в учебном процессе в ЮРГТУ (ИЛИ) при подготовки специалистов в области вычислительных машин, комплексов, систем и сетей.

Внедрение результатов работы. Результаты диссертационной работы внедрены:

- в промышленности ОАО «Ростовуголь» с годовым экономическим эффектом шесть миллионов рублей;

- в учебном процессе кафедры ЭВМ Южно-Российского государственного технического университета (Новочеркасского политехнического института).

Обоснованность и достоверность научных положений и выводов подтверждается:

- результатами вычислительных экспериментов;

- результатами экспериментальных исследований;

- соответствием теоретических и экспериментальных исследований;

- работоспособностью разработанных подсистем автоматизированного параметрического анализа и структурной оптимизации СОИ.

5.5. Выводы по разделу 5

Имея результаты оптимизации по всем трём направлениям, можно дать следующие рекомендации для получения хороших результатов оптимизации структуры данной СОИ:

1. Численность популяции следует устанавливать не ниже 100.

2. Увеличение числа мутантов в общем случае не приводит к улучшению результатов; имеет смысл остановиться на 5% (поскольку качественные мутации всё-таки имеют место, определённый процент мутантов в популяции желателен).

3. Выбор приоритетов ЦФ во многом определяет будущие результаты. В зависимости от того, что нам необходимо, высокая производительность или низкая стоимость, и следует устанавливать приоритеты.

На основе этих рекомендаций был проведён ряд опытов, которые дали лучшие показатели качества (см. приложение 2), нежели исследования, описанные выше.

До разработки ГАПДХ поставленная задача решалась с применением алгоритма пошагового устранения «узких мест» системы на основе аналитической модели СОИ. Расчёты проводились с помощью программы «Эволюция» [5]. При выполнении процедуры оптимизации использовались следующие вариации исходных параметров системы:

- изменение распределения потока заявок между различными способами выполнения процедур;

- изменение интенсивности входного потока заявок;

- изменение компонентов системы, на которых выполняется процедура обработки информации;

- изменение времён выполнения операций обработки информации.

Этот метод обладал двумя основными недостатками:

- выбор метода поиска «узкого места» системы на каждом шаге определялся экспертом, т. е. носил интуитивный характер;

- в программе «Эволюция» не учитываются стоимостные показатели качества.

В ПК «Путь» эти недостатки отсутствуют, поиск и устранение «узких мест» автоматизированы, эксперт влияет на процесс оптимизации только на этапе описания исходных характеристики процесса и популяции, имеется возможность ввести любую необходимую ЦФ, ограничения на ЦФ только количественные (общее число не должно превышать 128).

Итак, можно сделать вывод о том, что ГАПДХ оптимизации структуры СОИ, реализованные в ПК «Путь», вполне работоспособны и обладают рядом преимуществ перед использовавшимися до него методами решения подобных задач.

ЗАКЛЮЧЕНИЕ

Описан формализм синергетической модели НС Хакена, которая лежит в основе данного исследования, выявлена общая характеристика динамики этой модели. Выполнен анализ динамики СОИ, которая в общем случае до сих пор не исследована, а также предложены методы расширения возможностей модели с конкуренцией мод для решения задач классификации образов и структурной идентификации технологических объектов управления.

Обоснован выбор описания нейронной сети в форме уравнений с конкуренцией. Доказано, что при выполнении ряда ограничений на управляющие параметры, в нейронной сети существуют стационарные решения строго определенных видов. На примере НС с ортонормированными прототипами аналитически исследована иерархия бифуркаций в фазовом пространстве размерности М с числом управляющих параметров, не превышающим М, что графически проиллюстрировано для модели третьего порядка. Исследованы особенности изменения структуры фазового пространства при запоминании нейронной сети эталонов, обладающих высокой степенью корреляции между собой. Анализ, предложенный в данном разделе, дает основу для создания реальных синергетических сетей распознавания образов, в которых имеются возможности селективного распознавания коррекции качества с помощью управляющих коэффициентов и даже задание маршрутов фазовых траекторий с их прохождением вблизи требуемых точек £>(1). Все это повышает способности систем искусственного интеллекта, создаваемых на основе предложенной методики.

В СОИ, включающих в себя устройство, производящее структурную идентификацию объекта, конечно, наиболее применима классификация по признакам сходства, позволяющая разделять типовые звенья на множества по виду переходного процесса. Для построенной модели классификации остаются в силе ограничения на функции, накладываемые на показатели притяжения множеств, в данном случае определяющие устойчивость не только точечных аттракторов, но и поверхностей, образующих континуум таких точек.

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

В диссертационной работе исследована возможность представления структуры СОИ в виде модели связей компонентов подсистем, полученных в результате декомпозиции системы.

Теоретическое обоснование возможности упрощения модели связей (т. е. сокращения числа рассматриваемых связей) для СОИ, удовлетворяющих ограничениям, описанным в 1.1, позволило разработать методику построения минимальной модели, достаточной для корректного представления структуры системы.

Разработана методика перехода от модели связей к модели структуры СОИ с переменной длиной хромосом. Разработаны генетические алгоритмы с переменной длиной хромосом (ГАПДХ) оптимизации структуры СОИ. Разработан алгоритм оценки степени приспособленности особи на основании значений критериев оптимизации. Проведён анализ взаимного влияния хромосом друг на друга в процессе оптимизации.

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

Взаимное воздействие связей одного вида в неизбыточной модели проявляется только на этапе расчёта значений ЦФ, любое решение, полученное для подобной модели, будет непротиворечивым, и о жизнеспособности и конкурентоспособности особи можно будет судить только после анализа значений ЦФ.

В результате введённых ограничений на свойства рассматриваемых

СОИ:

- избавились от избыточности в модели связей СОИ;

- свели к нулю взаимное влияние связей, рассматриваемых в решении;

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

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

171

Построена теоретическая база для практической реализации ГАПДХ оптимизации структуры СОИ. Создан инструмент (программный комплекс (ПК) «Путь»), реализующий предлагаемый метод оптимизации структуры СОИ, разработанная технология моделирования позволяет строить модели СОИ различных видов.

ГАПДХ могут применяться при оптимизации с различными критериями, поскольку способ получения решения не зависит ни от характера целевых функций (ЦФ), ни от их количества.

Универсальность ПК «Путь» (в том смысле, что он выполняет весь комплекс типовых генетических операций (ГО), оставляя пользователю право выбирать цели оптимизации и организовывать расчёт значений критериев) позволяет использовать его для решения различных сложных задач переборного типа.

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

1. Айала Ф. Введение в популяционную и эволюционную генетику. - М.: Мир, 1984.

2. Андриевский Б.Р., Фрадков А.Л. Избранные главы теории автоматического управления с примерами на языке MATLAB. СПб.: Наука, 1999.

3. Анохин П.К. Очерки по физиологии функциональных систем. М.: Медицина, 1975.

4. Афонин П.В. Исследование эффективности модифицированных генетических операторов. //Радиоэлектроника, электротехника и энергетика. Седьмая междунар. науч.-техн. конф. студентов и аспирантов. Тез. докл. в 3-х т., т. 1. М.: изд-во МЭИ, 2001.

5. Ахметов К. Windows 95 не для всех. М.: Компьютер пресс, 1997.

6. Баталов Б.В., Назарьян А.Р., Руденко A.A. Направления и перспективы автоматизации проектирования изделий электронной техники. «Электронная промышленность», № 4, с. 3-11, 1979.

7. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Учебное пособие. Воронеж: ВГТУ, 1995.

8. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

9. Батищев Д.И. Поисковые методы оптимального проектирования. М.: «Советское радио», 1975.

10. Батищев Д.И., Власов С.Е. Применение генетических алгоритмов для трассировки нерегулярных структур с однослойной коммутацией. Сб. научных трудов «Оптимизация и моделирование в автоматизированных системах». Воронеж: Воронежский гос. техн. ун-т, 1995.

11. Батищев Д.И., Скидкина JI.H., Трапезникова Н.В. Глобальная оптимизация с помощью эволюционно-генетических алгоритмов. Сб. научных трудов «Оптимизация и моделирование в автоматизированных системах». Воронеж: Воронежский гос. техн. ун-т, 1994.

12. Беллман Р. Динамическое программирование. М.: иностр. литература, 1960.

13. Берштейн JI.C., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных интеллектуальных системах. Ростов н/Д.: изд-во РГУ, 1999.

14. Биллинг В.А., Мусикаев И.Х. Visual С++4. Книга для программистов. -М.: «Channel Trading Ltd», «Русская редакция», 1996.

15. Борель Э. Вероятность и достоверность. М.: Наука, 1969.

16. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. М.: Наука, 1986.

17. Букатова И.Л. и др. Эвоинформатика. Теория и практика эволюционного моделирования. М.: Наука, 1991.

18. Букатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979.

19. Вазан М. Стохастическая аппроксимация. М.: Мир, 1972.

20. Ведерникова О.Г. Разработка и исследование комбинированного генетического алгоритма генетического поиска и имитации отжига для задачи размещения элементов СБИС. Дис. к.т.н. Ростов н/Д: РГА сельхозмашиностроения, 1999.

21. Вейль Г. Математическое мышление. //Перевод с англ. М.: Наука, 1989.

22. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные