Введение к работе
Актуальность теш. Разработка и совершенствование методов at.'матизации процессов проектирования, планирования и управления на основе использования новейших достижений научных исследований, современных информационных технологий.. широкого применения современной вычислительной техники является одним из важнейших факторов повышения эффективности производства и.ускорения научно-технического прогресса. В этой связи задачи автоматизации выбора и принятия оптимальных решений при управлении различными организационными и технологическими системами и процессами на основе использования оптимизационных моделей, методов, и средств, их программной и аппаратной поддержки приобретают особую актуальность.
Наряду с поиском и внедрением оптимальных методов проектирования, планирования и управления большое внимание уделяется развитию и использованию новых технологий проектирования и управления на основе повышения уровня интеллектуальности используемых моделей и перевода слабоструктурируемого творческого.процесса вы-.. бора и принятия решений из полуинтуитивной, области в область формальных, строго обоснованных решений. С этой целью активно ведутся работы по созданию и развитию новых математических моделей. методов и аппаратных средств, предназначенных для представления и обработки данных и знаний, выраженных как в четкой количественной форме, так и в чечеткой качественной'форме и представленных в ри-v де высказываний, разъяснений и пожеланий специалистов - экспертов б данной предметной области.
Методы искусственного интеллекта из области теоретических исследований и разработок все шире внедряются в производство и практику. Быстрыми темпами растет объем комбинаторных вычислений. что связано с повышением уровня интеллектуальности различного рч-дг автоматизированных информационно-поисковых и советующих систем, а также с широким внедрением средств вычислительной техшікн и обработки информации в производство и повседневную деятельно-; ть человека, где решения принимаются на -cwv комбинаторного оценивания, прогнозирования, анализа и перь-оорч вариантов. Сложи*> ть задач связанных с выработкой и принятии: н.учь; обоснованных решений непрерывно возрастает. Все ьто- :№:;;>: н^'О-ходимость далі нейшей разработки и исследования теории и.средств поддержки комбинаторных моделей поиска' и принятия решений.
В связи с тем» что многие задачи выбора и принятия решении вносятся к классу труднорешаемых комбинаторных задач . возникает проблема понижения сложности их решения. Эта проблема является центральной не только в теории моделирования и дискретной оптимизации, но также и в теории искусственного интеллекта, и имеет не только математическое, но и глубокое познавательное значение.
Поскольку информация, используемая в процессах принятия решений часто является нечеткой т.е. неточной, неполной и зачастую носит качественный расплывчатый характер, что относится и к знаниям экспертов, то важно иметь адекватный математический аппарат для формального представления и обработки зтой информации.-Осноеы такого математического аппарата были заложены в работах Л.Заде по. теории нечетких множеств и нечёткой логики к развиты в дальнейшем многими исследователями как в России, так и за рубежом. Значительный вклад в развитие аппарата теории нечётких множеств, нечеткой логики и его прикладного аспекта внесли: Аверкин А.Н.. Алексеев А.В., Алиев Р.А., Борисов А.Н. .Блишун А.Ф., Батыршин И. 3., Берштейн Л. С.. Дюбуа Д., Ежкова И. В., Куковин В. Е., Кофман А.. Кузьмин В.Б., Каня А.А., Мамдани Е.Н., Мелихов А.Н.. Мицумото М.. Негойце К.В., Орловский С. А., Поспелов Д. А.. Прад А.. Сшюв В.Б.. Тарасов В.Б.. Ульянов СВ.,- Церковный А.Э., Шапиро Д.И., Ягер P.P. и многие другие учёные.
Применение нечеткой логики для представления знаний эксперта позволяет более адекватно отображать щ в памяти экспертной системы и более гибко и адекватно по сравнении с системами, использующими для представления знаний классическую чёткую логику, осуществлять вывод решений. Однако методы представления и обработки данных и знаний, описанных на языке нечетких множеств и преобразуемых по правилам нечёткой логики, имеют существенные особенности и отличия от традиционных четких методов. В этой связи актуальными являются исследование и дальнейшая разработка моделей представления нечетких знаний, а также разработка моделей и алгоритмов принятия решений на основе использования нечётких отношений и нечеткой логики.
В связи с бурным, развитием к интр.-:;.явным внедрением в сферу прикладных научных исследований у в практику проектировании, управления и производства кетг,;\с . «^чь. ;„ знаний и искусственного интеллекта, позволявших .эд^р.^иать процессы принятия решений как в условиях четкой, так и нечеткой исходной информации, особую
значимость и актуальность приобретают вопросы созданий ссс'тве.с-твующих средств аппаратной поддержки .сложных комбинаторных моделей выработки и принятия решений. Это объясняется тем, что су-' шествующие ЭВМ с традиционной архитектурой и последовательным характером вычислений плохо приспособлены для реализации комбинаторных вычислений и к работе с нечеткими данными.
В диссертационной работе обобщаются результаты теоретических и экспериментальных исследований в области построения коибинатор-ных моделей и алгоритмов выработки и- принятия решений в условиях как четкой, так и нечеткой исходной информации и средств их программной и аппаратной поддержки.
Указанный комплекс- исследований был проведен в 1973 - 1995 годах, при непосредственном участии' автора, на кафедре математического обеспечения и применения ЭВМ ТРТУ.
Целью диссертационной работы является развитие, теории, исследование и совершенствование математических методов, моделей и алгоритмов выработки.и принятия решений при автоматизации проектирования, планирования и управления в условиях четкой и нечеткой исходной информации, а также разработка элементов и устройств вычислительной техники а систем-управления в качестве средств аппа7 ратной поддержки четких и нечетких моделей принятия решений.
Поставленная цель определяет следующие основные задачи дис
сертационной работы: .
исследовать способы представления данных и знаний з системах принятия решений и разработать оптимизационные комбинаторные модели, методы и алгоритмы выработки решений сложных задач, возникающих при автоматизации проектирования, планирования и управления, и представленных на языке графов гилерграФов и лсевдобу-левьг/. функций при четкой исходной информации;
исследовать существующие и разработать новые, более эффективные методы и алгоритмы распознавания изоморфизма и ..изоморфного вложения графов.' ' гиперграфов' .и нечетких графов, с целью создания эффективных методов и алгоритмов выработки решения и"' получения вывода на основе распознавания сходства формальных представлений задач, данных и знаний с образцами; .
разработать нечеткие композиционные и классификационные модели и алгоритмы принятия решений на основе нечётких отношений. нечеткой логики при. различном уровне полноты-и достоверности экспертной информации; .- . "'
разработать элементы и устройства параллельных структур для реализации методов нечёткого вывода на основе композиции нечётких отношений и распознаваниЯ'Неябткого сходства ситуаций;
разработать элементы вычислительных структур и специализированные устройства для реализации операций нечеткой логики и обработки данных, а также аппаратные средства поиска и преобразования данных в системах принятия решений.
Объектом исследования диссертации являются комбинаторные математические модели, методы и алгоритмы выработки решений в условиях чет-кой и нечеткой исходной информации и способы построения элементов и устройств вычислительной техники и систем управления для реализации операций нечеткой логики, композиционного вывода и преобразования данных.
Методы исследования базируются на аппарате теории четких и нечетких'множеств И нечеткой логики, теории графов и гиперграфов, на использовании методов комбинаторного, целочисленного и бивалентного нелинейного программирования, теории искусственного интеллекта, теории построения автоматных моделей и моделей сложных систем, системного анализа, арифметических и логических сенов вычислительной техники и теории однородных вычислительных структур. Цель диссертации, основные задачи работы, методы исследования создали предпосылки для получения новых научных рэзультатов в области математических методов И моделей выработки решений сложных комбинаторных задач автоматизации проектирования, планирования; управления в условиях как четкой, так и нечеткой исходной информации, а также в области создания новых аппаратных средств поддержки систем принятия решений.
Научная новизна работы заключается в обосновании, разработке, аналитическом и экспериментальном исследовании-математических моделей, методов и аппаратных средств, ориентированных на использование в интеллектуальных системах выработки и принятия решений в условиях как четкой, так и нечеткой исходной информации. В частности:
проведены исследования по разработке и теоретическому обоснованию оптимизационных моделей, методов и алгоритмов решения сложных комбинаторных задач, представленных-на языке графов, гиперграфов и псевдобулевых функций;
разработаны и теоретически обоснованы оптимизационные комбинаторные модели и алгоритмы решения задач распределения и пере-
распределения, выбора лучших представителей, позволяющие оцениг взть близость полученного решения к оптимальному;
разработаны аппаратные модели раскраски вершин графа в заданное число красок, реализующие зерятностный и детерминированный алгоритмы направленного перебора;
на основе проведенных исследований разработаны, теоретически и экспериментально обоснованы новые эффективные алгоритмы распознавания изоморфизма неориентированных графов и гиперграфов;
-' разработаны и экспериментально исследованы алгоритмы рас
познавания изоморфного вложения четких и нечетких графов, а также
способы аппаратной поддержки задач распознавания изоморфизма и
изоморфного вложения графов; .
- проведены исследования по разработке композиционных моде
лей принятия решений при нечеткой исходной информации, основанных
как на нечетком.варианте дедуктивного вывода.' гак и'на композиции
функций нечеткой логики, допускающих, естественное обобщение ні
случай формализации высказываний произвольной сложности; .
. - проведены исследования по разработке нечетких классификационных моделей принятия решений при различном уровне полноты и достоверности экспертной информации;
- проведены исследования по разработке классификационного
метода вывода на основе распознавания сходства ситуаций и разра
ботаны методы и аппаратные средства' поддержки процедур получения"
классификационного вывода;
- - разработаны элементы специализированных процессоров и вычислительных структур для обработки нечеткой информации, устройства для реализации операций нечеткой логики, работающие с данными, представленными как в двоичном коде, так и в унитарном. также устройства, поиска и преобразования данных в системах принятия решений.
Математические исследования и разрабатываемые . методы соответствуют требованиям программной1 и технической реализации.
' Практическая ценность работы состоит в том,' .что предложенные комбинаторные модели, оптимизационные методы и алгоритмы используют современный математический аппарат, позволяющий наиболее адекватно отображать поставленные задачи и осуществлять решение, с точностью, определяемой лишь материальными и временными ресурсами. Разработанные графовые и гиперграфозые подели и алгоритмы получили . применение прй'решении задач автоматизации проектирования
- 8 - .,
дискретных устройств-, а модели и алгоритмы выработки и принятия решений на основе установления сходства описаний ситуаций, использования нечетких отношений, '.систем продукций и классификационных схем позволяют автоматизировать процедуру получения решений аналогичных тем, которые принимает опытный оператор на основе четкой и нечеткой качественной информации. Эти модели позволили с высокой степенью достоверности имитировать операторскую деятельность при построении моделей функционирования сложных человеко-машинных комплексов.- Использование разработанных моделей и алгоритмов способствует повышений: интеллектуальности систем обработки информации и принятия решений, а их аппаратная реализация при помощи разработанных г- йциализированных устройств и структур позволяет на порядок и более повысить быстродействие систем принятия решений по сравнению с использованием традиционных ЭВМ.
Достоверность ч обоснованность научных положений, выводов и рекомендации, сформулированных в диссертации, подтверждается вычислительным экспериментом и данными, полученными как на имитационных моделях* так И макетированием отдельных блоков спецустройств, апробацией работы на ряде всесоюзных и региональных конференций, прохождением предложенных в диссертации технических решений через экспертизу Госкомитата по делам открытий и изобретений, а также результатами практического использования предложенных в диссертации моделей, методов и средств, подтвержденных ак-' тами об использований и внедрении.
Новизна и оригинальность разработанных аппаратных средств поддержки предложенных комбинаторных моделей выработки и принятия решений подтверждается 30 авторскими свидетельствами на изобретения и тремя патентами. - '
Реализация результатов работы. Результаты, 'полученные автором, использовались в 14 НИР, выполненных в рамках госбюджетной и хоздоговорной тематики в соответствии с постановлением Госкомитета СМ СССР по науке И технике №500 от 21.11.1975 т.. постановлением СМ РСФСР №610 от 12.11.1976 Г;, по планам работы секции радиоэлектроники и приборостроения Программы САПР Минвуза РСФСР, по координационному плану АН СССР по комплексной проблеме "Кибернетика" за 1981-1985 г.г., по координационному плану работ Минвуза СССР на '1981-1990 г.г., по планам НИК ЕЭС. по единому заказу-наряду ТРТУ на 1993-1994 r.r.v по Межвузовской программе " Интеллектуальные системы На базе нечетких компьютеров", выполняемой
. ' " 9"" . . кафедрой МОП ЭВМ ТРТУ в рамках Программы " Университеты России".
Научные и практические результаты диссертации использованы и внедрены в НИИ многопроцессорных вычислительных систем г.Таганрога" ОКБ "Миус" г.Таганрога, НПО ''Кузробот", г.Таганрога, ОКБ "Ритм" г.Таганрога, Научно-производственное предприятие "Инфо-комп" при ТРТУ, на кафедре математического обеспечения и применения .ЭВМ ТРТУ (учебный процесс).
. Акты внедрения h использования научных результатов прилагаются к диссертации.
Апробация работы. Основные результаты работы докладывались и обсуждались на Республиканской конференции молодых учёных и специалистов (г.Киев, 1973г.)/ на 3 и 4 Всесоюзных конференциях по однородным вычислительным системам и средам (г:Таганрог, 197?г., г.Киев, 1975г.).. на Региональной научно-технической конференции по использованию вычислительной техники (г.Ростов. 1973г.), на конференциях и семинарах по методам машинного проектирования вычислительных устройств (г.Ленинград, І976г. .г.Запорожье, 1978г.,г.Харьков,1978г.) на семинарах по теории графов и дискретной оптимизаций, по автоматизации проектирования устройств цифровой техники (г.Ильменау, ГДР,1983г.. г. Берлин, ГДР. 1983г., Г.Дрезден, ГДР,1983г.). на Всесоюзной научно-технической конференции по проблеме создания и развития интегрированных автоматизированных систем в проектировании и производстве (г.Могк-4 ва,1987г.), на Всероссийской конференции "Медицинские информации онные системы"(г.Таганрог.1993г.), на Всероссийской с международ: ным участием конференции "Интеллектуальные САПР" (г.Геленджик, 1993г.), на Всероссийской с международным участием конференции " Персональные исследовательские комплексы и АРМ-94" (г.Таганрог, 1994г.), на научно-технической и научно-методической конференции профессоро-преподавательского состава и сотрудников ТРТУ, ежегодно с 1972 по.1995г. в г.Таганроге.
Публикации. По теме диссертации опубликовано 79 работ, в том числе 49 статей в центральных изданиях, междуведомственных и межвузовских, сборниках научных трудов, тезисов докладов Всесоюзных и Республиканских конференций, получено 30 азторских свидетельств на изобретения. Кроме того, отдельные положения диссертации нашли отражение в .14 зарегистрированных в ВНИТЦ отчетах-по НИР, в трёх учебных пособиях, изданных по планам Минвуза и в нескольких учебно-методических пособиях и руководствах к лабораторным и практи-
- 10 -
ческим занятиям. .
Структура и объем диссертационной работы. Диссертация состоит из введения, 7 глав, заключения,, списка использованной литературы и трёх приложений. Общий объём диссертации - 333 стр., основного текста 315 стр., . включая 40 стр. рисунков и 20 стр. список литературы из 258 наименований. Имеется три приложения на 18 стр., куда вынесены способы формализации некоторых задач и наиболее трудоёмкие доказательства теорем, а также акты сб использовании и внедрении результатов диссертационной работы.
