Методы синтеза элементов и анализа дискретных и нечетких иерархических систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Лебедев, Анатолий Анатольевич

• Лебедев, Анатолий Анатольевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Лебедев, Анатолий Анатольевич

5

ГЛАВА 1. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ И АНАЛИЗ

ОСНОВНЫХ ПОДХОДОВ К ЕЕ РЕШЕНИЮ

1.1. Содержательная постановка задачи

1.2. Обзор основных подходов

1.2.1. Исследование операций

1.2.2. Имитационное моделирование

1.2.3. Экспертные системы

1.2.4. Системы поддержки принятия решений

1.2.5. Анализ иерархий

1.3. Технология информационного мониторинга

1.3.1. Основные этапы разработки и использования систем информационного мониторинга

1.3.2. Пример использования системы информационного мониторинга-Система мониторинга ядерных технологий

1.3.3. Пример использования системы информационного мониторинга -Прогнозирование риска развития сердечно-сосудистых заболеваний

1.3.4. Формализация и обозначения

1.4. Выводы

ГЛАВА 2. СИНТЕЗ ЭЛЕМЕНТОВ СИСТЕМ МОНИТОРИНГА

2.1. Синтез операторов агрегирования информации по экспертным описаниям

2.1.1. Постановка задачи и формулировка результатов

2.1.2. Труднорешаемость задачи выбора оптимальной функции

2.1.3. Примеры условий

2.1.4. Полиномиально разрешимые случаи

2.1.5. Пример

2.2. Выводы

ГЛАВА 3. АНАЛИЗ СИСТЕМ МОНИТОРИНГА

3.1. Задача проверки устойчивости

3.1.1. Формализация и труднорешаемость

3.1.2. Полиномиально разрешимый случай

3.2. Задача оптимального распределения ресурсов

3.2.1. Формализация и труднорешаемость

3.2.2. Полиномиально разрешимые случаи

3.3. Более общий полиномиально разрешимый случай для обеих задач

3.3.1. Определения и формулировка результатов

3.3.2. Алгоритм поиска сверхдоминаторов

3.3.3. Алгоритмы решения задач проверки устойчивости и оптимального распределения ресурсов

3.4. Оценка распространения погрешности в нечетком случае

3.4.1. Локальный подход

3.4.2. Дискретный подход

3.5. Выводы

ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ СИСТЕМЫ ИНФОРМАЦИОННОГО МОНИТОРИНГА

4.1. Оценка и мониторинг проектов разработки высокотехнологичных изделий

4.1.1. Cadence VCAD

4.1.2. Создание структурной модели

4.1.3. Создание поведенческой модели

4.1.4. Инициализация

4.1.5. Графический интерфейс

4.1.6. Результаты

4.2. Возможные области применения технологии информационного мониторинга

Введение диссертации (часть автореферата) на тему «Методы синтеза элементов и анализа дискретных и нечетких иерархических систем»

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

В 30-40 годы XX века А. Тьюрингом был предложен подход к моделированию поведения вычислительных систем, а также созданы предпосылки для возникновения соответствующей теории. Подобные системы быстро нашли применение, и интенсивная работа в этом направлении в итоге привела к возникновению новой науки - кибернетики. Основной вклад в ее создание внесли К. Шеннон и А. Тьюринг. В развитии кибернетики важную роль также сыграли Дж. фон Нейман, Н. Винер, A.A. Ляпунов, А.Н. Колмогоров, C.B. Яблонский, О.Б. Лупанов, Ю.И. Журавлев, В.Б. Кудрявцев и другие ученые. С развитием техники и математического аппарата задачи, решаемые машинами, усложнялись. Помимо чисто вычислительных задач, перед ними ставились все более интеллектуальные проблемы, такие как распознавание образов, управление сложными процессами и т.п. В результате в кибернетике возникло и со временем заняло одну из ведущих ролей понятие интеллектуальной системы [6].

В 70-е годы в этом направлении, помимо прочих, обозначились такие разделы, как системы поддержки принятия решений [51], экспертные системы [34]. Они накапливали знания о некоторой конкретной предметной области и могли принимать решения о поведении в различных ситуациях в рамках этой области, заменяя собой человека-эксперта.

Со временем возможности систем подобного рода расширялись за счет более совершенного аппаратного, программного и алгоритмического обеспечения — им становились доступны все более сложные, слаборегламентированные предметные области и задачи.

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

Системы информационного мониторинга можно отнести к классу иерархических нечетких дискретных динамических систем. Теоретическую основу такого класса систем составляет теория автоматов, теория нечетких множеств, дискретная математика, методы анализа иерархий, которые были разработаны в работах Саати (T.L. Saaty, США) [19], Месаровича (M.D. Messarovich, США) [43], Заде (L.A. Zadeh, США) [52], Яблонского C.B. [23], Кудрявцева В.Б. [7] и других ученых. Системы, разработанные на базе этой технологии, позволяют иметь развивающуюся во времени модель проблемы на основе оценок аналитиков, подкрепленную ссылками на все информационные материалы, выбранные ими, с общими и частными оценками состояния проблемы и/или ее аспектов. Использование времени как параметра системы позволяет проводить как ретроспективный анализ, так и строить прогнозы развития проблемы (отвечать на вопросы типа «Что будет, если . ?»). В последнем случае также возникает возможность выделения «критических путей» - таких элементов (или наборов элементов) модели, небольшое изменение которых может вызвать заметные изменения в состоянии всей проблемы. Знание таких элементов имеет большое практическое значение и позволяет выявить «слабые места» вп роблеме на текущий момент времени, разработать мероприятия по блокированию нежелательных ситуаций или провоцированию желательных, т.е. в некоторой степени управлять развитием проблемы в интересах организации, ее отслеживающей.

Актуальность

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

Цели и задачи работы

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

• В теоретической части:

- Проблема выбора операторов агрегирования информации в иерархических системах по описанию эксперта средствами теории функций £-значной логики;

- Теоретические оценки качества работы нечеткого оператора агрегирования информации как элемента Схемы Функциональных Элементов (СФЭ) и СФЭ в целом;

- Обратная задача (задача оптимального распределения ресурсов) для дискретных СФЭ.

• В прикладной части:

- Разработка прикладной системы оценки и мониторинга (в качестве контролируемых процессов были выбраны проекты разработки изделий микроэлектроники).

Структура и краткое содержание работы

Диссертационная работы состоит из введения, четырех глав, списка литературы, заключения и приложений.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Лебедев, Анатолий Анатольевич

Основные результаты диссертационной работы заключаются в следующем:

• Предложена формализация технологии информационного мониторинга в терминах теории схем функциональных элементов.

• Сформулирована и решена задача выбора операторов агрегирования в дискретных иерархических системах по экспертным описаниям.

• Сформулирована и решена проблема проверки устойчивости для схем функциональных элементов в дискретном и нечетком случаях.

• Сформулирована и решена задача оптимального распределения ресурсов для схем функциональных элементов в различных метриках.

• Полученные результаты применены для решения практической задачи -построения системы оценки и мониторинга проектов разработки изделий микроэлектроники.

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Лебедев, Анатолий Анатольевич, 2010 год

1. Вачнадзе Р.Г., Гибрадзе Т.А., Карчаеа М.О., Маркозашвили С.Г. Методика оценки эффективности лекарственных средств на основе экспериментальных морфологических данных. // Вестник JI.MH СССР. 1988. №7, сс. 80-83.

2. Вентцелъ Е.С. Исследование операций. — М.: Советское радио, 1972, 552 с.

3. Заде Л.А. Понятие лингвистической переменной и его применение к принятию приблизительных решений. — М.:Мир, 1976. 165с.

4. Козлов М.А., Тарасов С.П., Хачиян Л.Г. Полиномиальная разрешимость выпуклого квадратичного программирования // Журнал вычислительной математики и математической физики, 1980, Том 20, № 5, сс. 1319-1323.

5. Кудрявцев В.Б. Функциональные Системы. — М., Издательство Московского Университета, 1982. 158с.

6. Лебедев A.A. О задачах оптимального распределения ресурсов и проверки устойчивости для схем функциональных элементов в k-значной логике (готовится к печати).

7. Лебедев A.A. Синтез операторов агрегирования информации по экспертным описаниям (готовится к печати).

8. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологических изделий микроэлектроники. //Известия ТРТУ, Тематический выпуск "Интеллектуальные САПР", ISBN 5-8327-0249-2, 2006, № 8 с.93-99.

9. Лебедев A.A., Рыжов А.П. Оценка и мониторинг проектов разработки высокотехнологичных изделий на примере микроэлектроники // Интеллектуальные системы, Том 11, выпуск 1-4, 2008 г., с. 55-82.

10. Подколзин A.C. Компьютерное моделирование логических процессов (монография). — М., Физматлит. 2008г. 1024 с.

11. Рогожин C.B., Рыжов А.П. О нечетко заданных классах функций k-значной логики. // V Всероссийская конференция «Нейрокомпьютеры и их применение». Москва, 17-19 февраля 1999 года. Сборник докладов, с.460-463

12. Рыжов А.П. Об агрегировании информации в нечетких иерархических системах. //Интеллектуальные системы, Том 6, выпуск 1-4, 2001, с. 341-364.

13. Рыжов А.П. О степени нечеткости размытых характеристик. // Математическая кибернетика и ее приложения в биологии. Под редакцией Л.В.Крушинского, С.В.Яблонского, О.Б.Лупанова. — М., Издательство МГУ, 1987, с. 60-77.

14. Рыжов А.П. Оценка степени нечеткости ие е применение в системах искусственного интеллекта. //Интеллектуальные системы. Т.1, Вып. 1-4, Москва, МНЦ КИТ, 1996, с. 95-102.

15. Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. — М., Диалог-МГУ, 1998, 116с.

16. Саати Т. Анализ иерархических процессов. — М.: Радио и связь, 1993. 315с.

17. ТахаХ.А. Введение в исследование операций — М.: «Вильяме», 2007. ISBN 0-13-032374-8. 912 с.

18. Форрестпер Д. Мировая динамика. — М., ACT, 2003

19. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS. — СПб.: БХВ-Петербург, 2003. 608с. ISBN 5-94157-248-4

20. Яблонский С.В. Основные понятия кибернетики // Проблемы кибернетики. 1959. Вып. 2. с.7-38.

21. Aspvall В., Plass M.F, Tarjan R.E. A linear-time algorithm for testing the truth of certain quantified boolean formulas. // Information Processing Letters 8 (3), 1979, pp. 121-123

22. Banks J., Carson J., Nelson В., Nicol D. Discrete-event system simulation. — Pearson, 2005.

23. Berner, E.S., ed. Clinical Decision Support Systems. — NY: Springer, 2007, ISBN 0387339140. 281 p.

24. O'Brien, J.A., Marakas, G.M. Management information systems (9th ed.). Boston, MA: McGraw-Hill/Irwin. 2009

25. Buchanan B.G., Shortliffe E.H. (eds.). Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project. — The Addison-Wesley series in artificial intelligence, 1984.

26. Cocke J. Global common subexpression elimination. // ACM SIGPLAN Notices 5:7. 1970, pp 20-24

27. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. // 1976, SIAM J: Comput. 5, pp 691-703

28. Fayyad U.M. (Ed.). Advances in Knowledge Discovery and Data Mining.— MIT Press, 1996. 560p.

29. Garey, M.R.; Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — New York: W.H. Freeman. 1979. ISBN 0-7167-1045-5

30. Gholam-Nezhad H., Kathawala Yu. Risk Assessment for International Investment.//Management Research News, 1990, Vol. 13, Iss. l,pp 1-8.

31. Jackson P. Introduction to expert systems — Addison-Wesley, 1999, ISBN 0-201-87686-8, 542pp.

32. Jintrawet A. A Decision Support System for Rapid Assessment of Lowland Rice-based Cropping Alternatives in Thailand. // Agricultural Systems, 1995, Vol. 47, pp 245-258.

33. Kaplan R.S., Norton D.P. The balanced scorecard: measures that drive performance. // Harvard Business Review Jan — Feb 1992 pp. 71-80.

34. Karp R.M. Reducibility among combinatorial problems // Complexity of computer computations, 1974, Plenum Press, NY, pp 85-103

35. Libecap G.D. University entrepreneurship and technology transfer: process, design, and intellectual property. — ELSEVIER, 2005. 31 lp.

36. Mamdani E.A. Application of fuzzy logic to approximate reasoning using linguistic synthesis. // IEEE Trans. Computers, 1977, Vol. C26, N12, pp. 1182-1191.

37. Martin Michael J.C. Managing innovation and entrepreneurship in technology based firms. — NY: John Wiley & Sins, Inc., 1994. 402p.

38. Matsatsinis N.F., Siskos Y. Intelligent support systems for marketing decisions. — Kluwer Academic Publishers, 2002.

39. Matzke W.E., Strube G„ Schmidt-Habich H., Drenan L. VCAD a virtual enterprise collaboration model impacting the semiconductor industry. // IASTED International Conference on Knowledge Sharing & Collaborative Engineering (KSCE 2004).

40. Messarovich M.D., Macko D., Takahara Y. Theory of hierarchical multilevel systems. — Academic Press, N.Y. London, 1970. 344p.

41. Pardalos P.M., Vavasis S.A. Quadratic programming with one negative eigenvalue is NP-hard. //Journal of Global Optimization, Vol. 1, Number 1, 1991, pp.15-22.

42. Ryjov A. Basic principles and foundations of information monitoring systems. // Monitoring, Security, and Rescue Techniques in Multi-agent Systems. Springer, 2005. pp. 147-160.

43. Ryjov A., Belenki A., Hooper R., Pouchkarev V., Fattah A., Zadeh, L.A. Development of an Intelligent System for Monitoring and Evaluation of Peaceful Nuclear Activities (DISNA) //IAEA, STR-310. Vienna, 1998. 122p.

44. Saaty T. Theory and Applications of the Analytical Network Process: Decision Making with Benefits, Opportunities, Costs and Risks. — RWS Publications, 2005, ISBN 1-888603-06-2. 352 pp.

45. Shoham Y., Ley ton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009.

46. Tarjan R. Finding dominators in directed graphs. // SIAM J Computing, 1974, 3, №1, pp. 62-89

47. Turban E., Aronson J.E., Liang T.-P., Sharda R. Decision Support Systems and Intelligent Systems. — Prentice-Hall, Inc. Upper Saddle River, NJ, USA, 2006, ISBN 0131986600, 850 p.

48. Zadeh L.A. Fuzzy sets. // Information and Control, 1965, v.8, pp. 338-353.

49. Zeigler B.P., Praehofer H., Kim T.G. Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems 2nd edition. — Academic Press, 2000.