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

На правах рукописи

С . - /г. - •■<

и I... ■

КОРЛЯКОВА Мария Олеговна

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ПРИОБРЕТЕНИЯ ЭМПИРИЧЕСКИХ ЗНАНИЙ В ПОИСКОВОМ ПРОЕКТИРОВАНИИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Специальность: 05.13.13

Вычислительные машины, комплексы, системы и сети

АВТОРЕФЕРАТ диссертации яа соискание ученой степени кандидата технических наук

Москва - 1998

Работа выполнена в Московском энергетическом институте

(Техническом Университете) на каф. Вычислительные машины, системы и сети

Научный руковдитель д.т.н., доц. Дзегеленок И.И.

Официальные оппоненты: д.т.н, проф. Вагин В.Н.

к.т.н, с.н.с. Фоминых И.Б.

Ведущая организация:

Научно Исследовательский Институт Вычислительных Комплексов им.М.А. Карцева

Защита состоится "24 " Я/ЗрА^Я______199<3г. в /6 часов, в

аудитории / ~ 3 !Она заседании диссертационного Совета К-053.16.09 в Московском энергетическом институте (Техническом университете). С диссертацией можно ознакомиться в библиотеке МЭИ(ТУ) по адресу г. Москва, ул. Красноказарменная, д. 13.

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, Москва, Красноказарменная ул., д.14, Ученый Совет МЭИ(ТУ).

Автореферат разослан

■■ /9" (ЧсхрТС}_199&г.

Ученый секретарь диссертационного

Совета * ^^гаГ к.т.н., доц. Дорошенко А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Под проектированием ВС будем понимать поиск эффективных вариантов их организации и применения, а так же оценку полученных и имевшихся ранее решений. Помочь могут экспертные системы (ЭС), но при их разработке возникает задача приобретения эмпирического знания, которая осложняет создание необходимого инструментария для проектирования ВС. Кроме топ», ЭС станут действительно интеллектуальными только тогда, когда они будут помогать создавать новое знание. Приобретение эмпирического знания процесс - предъявляющий высокие требования к инженеру-по-знаниям и эксперту в проблемной области, и даже самые квалифицированные специалисты нуждаются в методах и средствах приобретения знаний. Выделим два типа задач приобретения знаний в приложении к поисковой области "вычислительные системы":

• для существующих моделей рабочих станций, персональных компьютеров и других видов ВС важно получение правила приоритетного оценивания но обобщенному показателю качества;

• новые, развивающиеся направления ( например, кластеры рабочих станций, Параллельные Мультикомпьютерные сети (ПМК-сети)) требуют создания методов перехода к новому знанию.

Оба направления приобретения знания характеризуются высокой сложностью объектов, разнообразием целей поиска, а так же постоянным изменением мира, в котором осуществляется поиск. Существующие системы, предназначенные для приобретения эмпирического знания (ТЕП1Е31А8, ЕМУСШ, КАБ, С2, ЕхреПЕАвУ, ЕиШБСО, ШБиБЕ/г, Ро1уАпа1ук1 и др.), обеспечивают формирование непротиворечивой предметной области, при стремлении к изначально полному описанию решаемых задач и целей. Однако постоянные изменения в мире ВС обращают внимание на иной подход к получению знаний, связанный с Открытыми мирами и Открытыми Задачами. Последние не предъявляют жестких требований к завершенности моделей принятия решений и выявлению новых областей знания. Однако Открытые задачи не обеспечены пока методами повышения их содержательной емкости и достижения сложных целей.

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

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

Для достижения поставленной цели решаются следующие задачи'.

• преобразование поискового пространства в процессе постановки и решения открытой задачи;

• формирование эмпирического знания в виде нелинейного правила выбора;

• изучение эффекта перехода к новым, ранее не изученным подвидам ВС;

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

• постановка и решение прикладных задач проектирования вычислительных систем.

Методы Исследования. Работа основана на использовании разработанных в МЭИ теоретических основ постановки и решения Открытых задач поискового проектирования и опирается на использование понятий высшей алгебры, алгебры логики, теории графов, теории искусственного интеллекта и методологии имитационного моделирования.

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

• сокращение числа фчзически невозможных вариантов с помощью механизма переинтерпретации;

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

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

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

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

• Удалось сократить временя выполнения расчетных задач в 1.27 раза, по сравнению с первым предложенным вариантом Параллельной мульти-компьютерной сети для данного класса задач.

Реализация результатов работы. Представленные в диссертации разработки получены в результате выполнения хоздоговорных НИР, которые велись в течении 1992-1997 года в МЭИ на кафедре "Вычислительные машины, системы и сети". НИР выполнялись в целях дальнейшего совершенствования инструментальных средств поискового проектирования и расширения сферы их практического применения. В рамках межвузовской научно-технической программы "Перспективные информационные технологии в Высшей школе" по грантам РосНИИ информационных систем ( тема №23-ИО/94, научный руководитель И.И.Дзегеленок, отв. исполнитель М.О.Корлякова) разработана: экспериментальная технология оценки качества программных средств учебного назначения, для которой использовалась Проблемно-Настраиваемая Экспертная система В рамках госбюджетной темы (Гос.регистр.№01910022602, 1991-1995г.г.) при отработке механизмов постановки и решения Открытых задач были созданы экспериментальная технология оценки рабочих станций для полиграфии и технология образования конфигураций ПМК-сетей. Указанные разработки переданы ряду организаций (РосНИИ информационных систем, Исследовательскому центру проблем качества подготовки специалистов Госкомвуза РФ, МГГУ, ОАО "Калужский Турбинный Завод" (г.Калуга) и др) и использовались в их практической деятельности.

Апробация работы. Результаты исследований, составляющих содержание работы, докладывались и обсуждались на Международных форумах информатизации по программе конференции "Информационные средства и технологии" (Москва, 1994, 1995, 1997), а также на 6-ом симпозиуме

(l

"Квалимстрил человека и образовании: методология и практика" (Москва, 1997). Инструментальный комплекс поискового пдхм кщроиании экспонировался на выставке "ИНТЕЛЛЕКТ-СОФТ 9ti" (Москва, 199В) и международной выставке "Softool-97" (Москнл, 1997).

ЩОЛЧКНЧИИ П<> теме диссертации опуб.ииконаио 4 работы.

Состав работы. Работа состоит из введения, четырех глав, заключения, литературы по главам (всего 85 наименований) и приложений. Основной текст работы на 120 ст|>, пключаст М рисупока, 26 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Ul> 11ИСДСИИИ 1)Ги1см>1М|.|||,н"1Ч'|| актуальность проблемы, определяется подход к ее решению, дается общая характеристика диссертации. Отмечаются отсч(Ч"т|»'1|н|.н' и л:|руГм-жиы<' ученые, окамамшис определенное влияние на развитие формируемого направления исследований. Среди которых: Д А. Поспелов, В.Н. Вагин, В.К. Финн. Е. Hunt, С. Hewitt(ClUA) и И.И. Дзеге-ленок (руководитель данного направления).

Глава 1. ПРОБЛЕМА ПОИСКОВОГО ПРОЕКТИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ПОДХОД К ПРИОБРЕТЕНИЮ ЭМПИРИЧЕСКИХ ЗНАНИЙ

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

Под рабочими станциями-WS будем понимать совокупность характеристик следующих элементов:

WS = <Р, Mo, Mh, A, Bi, Be. D, Mn, S>, где P -процессорный элемент; Mo - оперативная память; Mh -дисковая память; I) - дополнительные устройства хранения и записи информации; А -акселераторы; Bi - внутренних шины; Be -внешние шины; Мп -монитор; S -операционная система.

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

Другой объект Программные Средства учебного назначения (ПС) могут быть представлены совокупностью своих основных свойств: Р = < Т, I. Е, М>,

где Т - технические характеристики аппаратной части и операционной системы ЭВМ; I -свойства и особенности интерфейса; Е - психологические и эргономические характеристики; М - методические характеристики.

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

Третий объект из области "вычислительные системы" - ПМК-сети (связаны как с традиционными сетями ЭВМ, так и с параллельными вычислительными системами) - для которых определена конкретная задача (расчет схемы тепловой установки) и принято следующее описание:

РМС = <{ПЭ}, РП8МЯТЬ, Ксеть, РОС, Имашина>,

где {ПЭ} - взаимодействующие в сети компьютеры, имеющие Рпамять -распределенную память (оперативная и внмнняя память ПЭ с возможным выделением общей памяти для всех ПЭ) и объединяемые через Ксеть - коммутационную сеть посредством каналов или линий связи. Сеть функционирует под управлением РОС - распределенная операционная система, а прикладные программы формируются с помощью Имашина - инструментальной машины. Устоявшихся методов проектирования ПМК-сетей не существует, а значит необходимо сформировать правило образования эффективной конфигурации ПМК-сети для указанной задачи.

Получение обоснованной оценки Рабочих Станций и ПС или выделение лучшей конфигурации ПМК-сети затрудняется тем, что области, в которых должна осуществляться работа, не полностью известны. Процесс формирования и уточнения представления (знания) об объекте может идти все время Человеку в трудном деле приобретения эмпирических знаний могут помочь интеллектуальные системы.

Под эмпирическим знанием будем понимать совокупность элементов: ErnKn = <0, ф. G, М(0,Ф), Y(M,G)> где 0=(х,( - известные объекты;

Ф=(ф|} - известные законы, существующие для О;

G=(gi) - цели, определяющие существование О; приобретение эмпирического знания (EmKn) требует:

- создать М(О.Ф) - описание предметной области;

- по М и G определить Y(M,G)-3aKOH образования новых о< и ф| (нового эмпирического знания).

В данном случае рассматривается процесс постановки и решения Открытой задачи, который заставляет эксперта передавать знания в два этапа:

- первичное представление предметной области как признакового описания;

- разделение, предлагаемых вариантов на "удачи" и "неудачи".

Подход к приобретению эмпирических знаний, связанный с решением Открытых задач поискового проектирования определяет их как механизм <D", Ф. <T[uJ,F[uI>, Р(Х), у(Х), R{X„}> , направленный на восстановление зависимости у(Х) в пространстве переменных D" с учетом возможной совокупности физически нереализуемых вариантов ХеФ, на основе индуктивного обобщения примеров <TU-"удач",Ри-"неудач">, где и номер сеанса приобретения знаний и примене-

ния оценочного правила Р(Х) для решений Х„ образованных механизмом выдвижения гипотез К{Х,,).

Решение Открытых задач идет по схеме: обучение и экзамен, которая повторяется до тех пор, пога возможно выдвижение новых гипотез.

Свойства объекта X будем отображать как множества предметных переменных х|={х,1,х12,..,хд,.., х,|,|}, где х^ - значение ¡-ой переменной, а ]=1,..,к1, 1=1,..,п. Любой вариант объекта проектирования представляем в виде вектора Х={х1,..,хп} - упорядоченного набора значений переменных Х|, где ¡=1,..,п. Вся совокупность вариантов, образуемых вариациями переменных Х|, задает пространство О" (пространство предметных переменных)

Внесение новых переменных хотя и детализирует предметную область, но одновременно поиск в пространстве большей размерности резко усложняется. Практически всегда для любого описания поискового пространства, сделанного человеком, можно обнаружить целый ряд сочетаний значений, которые определяют невозможные комбинации (например при описании портативных компьютеров для неременных "тип процессора" и "частота процессора" невозможны сочетания "тин ОХ4 - частота КШМН?."). Количество невозможных решений может превосходить число физически реализуемых вариантов

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

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

Для разделения решений в пространстве И" на "удачи" и "неудачи", вводится качественная оценка Р(Х) вариантов X. Это может быть либо совокупность внешних показателей качества Е(Х)={( 1(Х),..Дк(Х)), либо решение эксперта (где П(Х) - частный показатель качества для пространства О"). На основе правила Р(Х) в пространстве Б" задают факты (множества Т, Г -"удач" и "неудач" соответственно).

Возможность решения Открытых задач постулируется следующим допущением:

- гипотеза представительности (исходное пространство Р" переменных Х^-Хд, где х,е(хц.х12,...х^). ¡=1.п, и правило Р(Х), таковы, что существует ограниченное число решений ХдбТц,ХдеГд, котор множества Т.Г и их границу у(Х)=0 в данном классе

Один из основных процессов решения Открытых задач - индуктивное обобщение имеющихся фактов. Результат обобщенная скалярная функция выбора у(Х). Для всех элементов множеств Т, F, в идеале, справедливо I >= 0, если ХеТ, Р(Х)=1 У(Х)= "! (1)

I < 0, если XeF, Р(Х)=0 Функцию выбора (ФВ) ищем в виде квазилинейного многочлена;

у(Х)= у(Х,С)-С„ , где у(Х,С) = ,

xjj- j-e значение i-й предметной переменной, C={cii.Ci2.-,C|M,..,cnj,cn2...,cni<n} - весовые коэффициенты, к, - число значений по i-й координате, п - число переменных.

Формирование у(Х) соответствует определению набора коэффициентов С и порога Сд. посредством решения открытой системы неравенств (1). С увеличением обучающей выборки увеличивается достоверность разделения. Переход к следующему уровню приобретения знаний и+1 связан с выделением множества гипотез целенаправленного порождения знаний R{Xg}, где Хо-эмпирические гипотезы, и оценки гипотез по правилу Р(Х0). Из решений Х(]-опорных выделяют решения Хо<ёТ, X0eF, и эти множества есть множества опорных гипотез Тп и Fn.

Для пространства предметных переменных введены отношения доминирования и дальнего соседства.

Отношение дальнего соседства (Ха[--[ХЬ) существует для Х3 и Х^, которые отличаются значением только одной переменной

Отношением доминирования Ха I —»Х^ во множестве Т, существует для Х3. Xij у которых vfXa)<v(Xb). где Ха.ХьеТ и Ха|—|ХЬ. Для множества F Ха 1->Х>, установлено для у(Ха1>у(Хь), где Xa,XbeF.

Для отношения доминирования и отношения дальнего соседства строят ориентированные графы Gt - граф "удач", Gf - граф "неудач" )на множествах Т, F соответственно. Каждому отношению | —> сопоставим дугу графа, а каждому элементу множества T(F) -вершину и ее оценку у(Х). Введение отношения доминирования позволяет определить опорные решения как минимальные элементы графа доминирования, а локальными максимумами для графа удач назовем максимальные элементы Gt (аналогично для Gf - локальные минимумы).

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

Линейный характер ФВ не позволяет работать с задачами реальной сложности (такими как получение правила приоритетного оценивания рабочих станций или ПС), которые имеют несколько областей удачных решений, что трудно описать квазилинейной ФВ. Необходимо ввести в ФВ нелинейные составляющие, которые опишут отклонения от Гранины квазилинейного

разделения пространства, в котором осуществляется поисковое проектирование ВС.

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

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

Глава 2. РАЗРАБОТКА И ОБОСНОВАНИЕ МЕХАНИЗМОВ ПРИОБРЕТЕНИЯ ЭМПИРИЧЕСКОГО ЗНАНИЯ.

Будем называть невозможные сочетания значений неременных физически-нереализуемыми компонентами (ФНК). Для упрощения будем рассматривать только случай двухместного ФНК. Эксперт, описавший объект, сможет перечислить ФНК для пар координат. Определим вид ФНК:

Ф* - множество запрещенных фигур или ФНК. Каждый элемент множества Ф* задаем как Ф^ - <х^р ..., х^т>. где хц - j-e значение предметной переменной х. Все варианты Х-решений из пространства предметных переменных, содержащие элементы из Ф*. относятся к недопустимым. Эти решения X составляют множество Ф.

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

Предлагается для пар предметных переменных с ФНК провести процесс переинтерпретации. Цель переинтерпретации - уменьшение числа невозможных вариантов. Смысл переинтерпретации состоит в получении декартового произведения множеств значений переменных из пары, "очистки"

внесения смысла в новую координату. Пространство переходит от D" к D*""1'. Критерием выбора <Эвыг, пары переменных для обработки служит число вариантов из пространства, содержащих ФНК, образованные этой парой:

QbuS = max F(i,j) , где F(i,j) -число невозможных решений из D" для переменных i,j, и i=l.kj, j=l.kj и

Преобразовав этот критерий к виду, который легче вычислять получим:

Q,.ur. = max СI <t»,j I /(k| * kj)), где i = 1, kj, j = 1, kj и IФ^ I- число ФНК для переменных i, i; k| - число значений 1-й переменной.

Исходя из практических соображений решено сокращать пространство не более чем в два раза. Решение о проведении переинтерпретации принимает эксперт на основе величины критерия QBljr, для нар неременных.

Некоторые переменные могут быть несущественными для данного объекта проектирования. Рассмотрение ФВ, позволит определить несущественные предметные переменные. Для этого построим таблицу W, в которой каждый элемент Wjj=Cjj, где j-номер значения i-й переменной, Cij - коэффициент ФВ для j-ro значения i-ii переменной. Для каждой предметной переменной определяется разница между максимальным и минимальным из коэффициентов ФВ этой координаты

d, = | шах С^ - min Су |*k|, где kr число значений i-й переменной. j= 1 ki j-1 k\

Cy - коэффициент j-го значения i-й переменной, i-номер переменной. На основе экспериментов было определено пороговое значение

dnop = (S d; ) / (3*п). где п - число координат-переменных, i=l.n

Переменные, имеющие d, ниже dnop в пространстве, будем считать несущественными. Такую предметную переменную можно удалить. Решение об удалении принимает эксперт.

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

dnopi = ( I I |СЦ - C,k|)/((kj2-kj)/2).

j = l n k=l.n, k*j

где n -число переменных, i-номер переменной, а j,k -номера i-ro значения, kj -число значений i-ой переменной. Пары значений переменной i, для которых |C,J-Clk|<dnopi, могут быть объединены. Решение о соединении несущественных значений принимает эксперт на основе анализа пар значений на условие |C,J-Clk|<dn(ipi.

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

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

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

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

Хотя для обучающей выборки, в идеале, правило у(Х) должно давать полное разделение, модель у (С, X) может иметь определенную зону ошибок Г1 ={Х | у(Х)>=0, ХеР}#0. Это говорит о необходимости усложнить ФВ.

Предлагается трансформировать у(С,Х) в у(С, X, Н, Z) так, чтобы при сохранении мерного рамде.лешш X на Т и К\К1 зима ошибок уменьшились. Будем рассматривать модели вида

у(С,Х,Н,г )=(С,Х)- С» , где

Zv - м-п нелинейная компонента; -весовой коэффициент при Zv, ЬуеК.

Определим вид компоненты Zv ранга ш, формируемой на б-ом шаге и-го цикла. Нелинейная компонентаШК) - логическое произведение из ш элементов, представляющих собой значения х^- координат из Р". Для определения вида Zv построим матрицу V/ - степени вхождения значений в зону ошибок Г1. Элемент матрицы является степенью вхождения ¿-го

значения ¡-й переменной в . Формирование Zv основано на реализации принципа выделения предельных покрытий. Покрытием множества Г+ нелинейной компонентой Zv назовем множество Г+"={ X |

Для каждого ХеГ+ проверим значения по всем п координатам и увеличим на 1 соответствующие элементы и^ = |х; = X; * ац},

где X; -значение 1-й переменной, ау - ¿-е значение 1-й переменной. Из всех УУу выбираем наибольшие элементы по каждой переменной и упорядочиваем их по величине. Для увеличения ранга к существующей НК присоединяем х^ такое, что 1 отлично от номеров переменных уже введенных в г, и это наибольшее из оставшихся По новой Ъч определяем текущее значение веса Ьу=тах у(Х)+1, ХеГк. Увеличение ранга НК идет до тех пор, пока кроме покрывает ХеТ так, что при введении поправки

И„ получаем у(ХеТ)<0.

Прежде чем начинать формирование новой НК, следует вывести из К+ все элементы множества Ги = {Х^у=1, ХеК), а в их вес внести поправку Ьу. Процесс формирования НК необходимо продолжать до тех пор, пока не выполнится условие Г+ = 0.

Нелинейная компонента может содержать от двух до п переменных в пространстве О". Чем короче тем большее число вариантов она охватит и тем больший смысл в ней заключен. Среди НК могут быть такие, что будет открыта новая закономерность получения удачных решений, а это не менее важно, чем получение верного разделения обучающей выборки.

После переинтерпретации все оставшиеся ФНК следует превратить в изначально заданные нелинейные компоненты^а11р, которые имеют вид, аналогичный НК, сформированным в процессе определения ФВ. Вопрос состоит в определении веса для Za,1p на каждом шаге и. Вес Ьапр априорной

нелинейной компоненты зависит от величины" у(Х*) ""для" X*"покрываемых " 28Пр и определяется по следующему правилу

Ь»пр= та* у(Х')+1, где X* - такие варианты покрываемые 2апр, что у(Х*еГ)>=0. В случае, когда все покрываемые 7.апр варианты не выходят из Т", то Ьа!|р=0.

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

Для ФВ с нелинейными составляющими организовать выдвижение гипотез и поиск локальных максимумов.

ную составляющую Ъ. то для существования локальных максимумов I' необходимо и достаточно выполнение системы уравнений:

I Зу(Х,С) I _,

с*1Ч = шах I---------- I для всех 1 = 1.п,

I

дХп

I Х=Х*

где с*,ч -вес при вспомогательной переменной х*;ч вектора (Х*,С).

Локальные максимумы находятся через взятие частных производных ФВ у(Х,С,Н,2). Необходимо представить эквивалент частной производной в случае функции у(Х,С,Н,2) в дискретном пространстве

Определим частные производные для решения Х={х1а, х2[),..., х3с) из нростринстпи О".

д у э т

{ С;) + £ Ьк гк - СМ - 1. Ик 7.к' } ,

Л х„

к=1

к=1

где т - число гк'-НК покрывавших X, но не покрывающих вариацию от X по значению ху , в - число г^-НК не покрывавших X, но покрывающих вариацию X в направлении х^ ; СМ - коэффициент ФВ для ¡-го значения X.

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

¿У 5 т

Си + Е Ьк гц -С1 -I Ик гк', т = гпц , .ч=вц

(Эх

11

"12

кп

т = т12, 5=я12

к=1 к=1 С12 + 1^2,, -С2 -I Ьк2к'

к-I к = 1

с„ кп +£ гк -Сп -I Ьк гк', т = тп кп, 8=вп кп к~1

Эта таблица дает информацию о поведении у(Х,С,Н^) аналогично тому, как производная дает эту информацию в случае дифференцируемых функций. Для поиска локального максимума предлагается использовать подъем по графу от вершин Х°ч , являющихся нижней оценкой веса локального максимума, к самому 1° - локальному максимуму. Для получения

нижней оценки Хоц из частных производных набираем вектор X011 ={ xj, х2, ... , хп ), для значений которого выполнены следующие условия:

dy(X)/3x,j=cost, где хуеХ"« и

Xj = шах Xjmt где для X|m выполнено первое условие m=l.ki

Если такой вектор набрать не удалось, то удаляем из списка НК, имеющую самый большой ранг и повторяем еще раз. Может быть несколько векторов Хоц, так как у ФВ может быть несколько коэффициентов равной величины для одной переменной. Организуем подъем по графу "удач" от Xj04 в направлении увеличения у(Х"), которое определяется через частные производные дy/<5x,j>0 (где Х'-вариант получаемый через внесение вариаций в Х;"ц). Если нарпацнН, удовлетворяющих Ру(Х*)/<~> x,j >0 нет, то текущий вектор X* - локальный максимум.

Поиск локальных максимумов имеет важное самостоятельное значение. Локальные максимумы "лидеры" в своей предметной области. Однако, не менее важны они при поиске опорных решений.

Предлагается для опорных решений применить алгоритм построенный на чередовании спусков к минимумам и подъемам к точкам локальных максимумов. Представим алгоритм для множества Т.

Устанавливаем список локальных максимумов в виде массива {t°i,t°2, ...,t°Lmaxlb где LmaxI- число локальных максимумов, a t° ¡-вектор локального максимума. Устапшмшнаем картируемый вариант X* в t" ¡. Строим матрицу W-частных производных для X*. w,j- элемент W соответствующий частной производной в направлении Xjj, где i-номер неременной, a j- номер значения этой переменной. Выбираем такое направление Xjj из еще не обойденных для данной вершины X* графа Gt, что хд соответствует наименьшему wy из тех, которые уменьшают у(Х"), но не переводят X* из области Т в область F. Направление, в котором осуществляют спуск, помечают как обойденное и возвращаются к определению частных производных на новом уровне. Если из текущей вершины X* нет ни одной вариации, то это опорное решение.

Полученное Опорное Решение заносим в список Опорных Гипотез, если его еще не было ни среди Гипотез, ни среди множеств Т и F. Недостаток алгоритма состоит в том, что большое количество вычислений уходит на спуск в уже найденные опорные решения. Поэтому вводится счетчик прерывающий работу над текущим локальным максимумом, так как нет необходимости указать абсолютно все опорные решения и от эксперта не требуется оценка абсолютно всех гипотез.

Решение эксперта не всегда совпадает с предположением ФВ, но гипотезы-противоречия являются самыми важными с точки зрения образования решающего правила, так как они исправляют явные просчеты сформированной ФВ.

Механизмы формирования поискового пространства и построения в нем нелинейной ФВ позволяют получать решение Открытых задач для пространств с несколькими областями удачных вариантов, что было показано на примере выбора конфигурации портативного компьютера.

- создан метод сокращения пространства предметных переменных:

- разработан механизм построения нелинейных составляющих ФВ:

- создан механизм выдвижения эмпирических гипотез для ФВ с НК.

Наполнение обучающей выборки через механизм выдвижения гипотез

позволяет с минимальными затратами осуществить формирование ФВ с НК Для модельной задачи "поисковое проектирование портативных компьютеров" обучающая выборка составляет 377 примеров. Это составляет 0.017% от полного перебора. Тем не менее достоверность разделения составила 96% ( 24 решения из 25) при проверке работы сформированной ФВ на реальных вариантах ноутбуков

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

Анализ эффекта "открытия" показал, что он проявляется в случае формирования функции выбора с нелинейными составляющими, несущими реальный семантический смысл.

Можно предположить, что программный комплекс для постановки и решения Открытых задач, который будет использовать созданные методы формирования пространства предметных переменных, а так же построение нелинейной ФВ (и работы с такой ФВ), позволит перейти в дальнейшем к решении» задач реальной размерности и сложности.

Глава 3. РАЗРАБОТКА ПРОБЛЕМНО НАСТРАИВАЕМОЙ ЭКСПЕРТНОЙ СИСТЕМЫ С НЕЛИНЕЙНОЙ ФУНКЦИЕЙ ВЫБОРА.

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

При разработке Проблемно-Настраиваемой ЭС применена алгоритмическая декомпозиция для всей системы в целом и объектно-ориентированный подход, объектные языки и средства визуализации для построения некоторых частей. Архитектура Проблемно-Настраиваемой инструментальной ЭС приведена на Рис.1.

э к

с п

Е Р

Т «

П

О Л Ь 3 о

В -

л

т.

ФНК невозможные компоненты_

у

1)п пространство \ переменных /

I ..—......

в водится

начальный набор фактов Т, Г

1)п -1 переинтерпретация

у(Х)функция ( выбора

Н(Хо} порождение гипотез *

оценка Р(Хо) гипотез РЕШАТЕЛЬ

СКГНИСНОЕ ОБСЛУЖИНА1 ГИК

БЗ (у(Х), Г Т, Оп,ФНК)

Рис.1. Архитектура Проблемно-Настраиваемой Экспертной Системы.

Можно выделить три основных блока, исполняющих самостоятельные функции и связанных друг с другом через Базу Знаний: - блок РЕДАКТОР БАЗЫ ЗНАНИЙ (создание и редактирование базы знаний); - блок обуче-ния-РЕШАТЕЛЬ (создает решающую модель); - блок СЕРВИСНОГО ОБСЛУЖИВАНИЯ решения (ведение БЗ, отчетов, пробная работа с моделью).

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

Общий интерфейс Инструментальной Системы приведен на Рис.2.

ОБЩИЙ ОКОННЫЙ ИНТЕРФЕЙС

главное управляющее окно

редик! >рм формироШНПН» ФВ иЫД11ИЖ«МИ<- 1И1ЮГ е -риИСНМс функции

1еремен фактов ФНК Ко:)ф. ПК оценка локальные созд. БЗ для от- сохране-

ных ФВ гипотез максимум ы Инф. Сис. чет ние БЗ

Ваза Знаний

открытие БЗ формиро~ вание ФВ

закрытие БЗ 1Т1(|(!По<П гхг

Локальные максимумы

генерация

сипоте:»

переинтер-риретация

модули для для редактор

Skleiv.exe

DelZnac.exe Oelpar.exe

сервис модули

OpenBase.exe СЬвЬаяе ехс

1ок тпх ехе;1ок_т'т.ехе Оепег^1.ехе;Сепег_П.ехе

оценочные модули <имя>.ехе

ВНЕШНИМ МОДУЛИ

Рис.2. Общий интерфейс Проблемно-Настраиваемой Экспертной Системы.

Приведем более подробное описание этих свойств данной системы.---------------

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

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

Обеспечен вход из системы во внешние модули, лаюшие оценку выдвинутым опорным гипотезам. Это позволяет проявлять использовать не только мнение эксперта, но и вычисляемые внешние критерии качества, а так же имитационные модели.

Обеспечена возможность решения Открытых, .задач как набора подзадач и создания объединенной БЗ. Это позволяет увеличить размеры решаемых задач и детальность описания предметной области.

Информационно-справочная подсистема "Прогноз" предназначена для

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

Задачи, которые могут быть решены с помощью, Проблемно-Настраиваемой ЭС охватывают не только известные объекты, но и новые развивающиеся области знания. Система позволяет ставить и решать Открытые задачи с 20 переменными, в каждой из которых будет 25 значений.

Глава 4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ ИНСТРУМЕНТАЛЬНЫХ

СРЕДСТВ

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

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

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

Случай определения конфигурации ПМК-сети демонстрирует возможности инструментальной системы в части поиска новых решений. В качестве

оценочного правила будет применена имитационная модель ПМК-сети, разработанная на каф. ВМСС (МЭИ) и критерии, величину которых определяем на основе имитационного моделирования вариантов-гипотез.

Использование разработанных инструментальных средств дало следующие результаты:

Правило приоритетного оценивания рабочих станций. Сформировано общее правило оценки конфигураций рабочих станций для полиграфии без учета стоимостных критериев. Это правило позволило выделить лучшие варианты универсальных рабочих станций для решения задач, стоящих перед небольшим полиграфическим производством. Лучшее решение принадлежит классу компьютеров типа Pentium и PowerPC в силу их широкого распространения в России и больших возможностей обслуживания и модернизации. Кроме того, все рассматриваемые примеры из подгрупп Pentium, DEC, SPARC и PowerPC, образовали иерархию соответствующую частным правилам выбора, которые были построены па предварительном этапе. Это свидетельствует о правомерности использования общего правила оценки конфигураций для всех подгрупп рабочих станций.

Правило приоритетного оценивания ПС. Было сформировано пространство предметных переменных для проведения оценки ПС. Это пространство в 2.5 раза меньше исходного, которое определили на основе ГОСТ 28195-89, задающего метод оценки программных продуктов. Однако сокращение числа ФНК производилось с помощью механизма переинтерпретации, что позволило сохранить всю существенную часть описания ПС. С помощью правила оценки ПС был образован идеальный вариант обучаюхцей программы. Кроме того, из нелинейных составляющих функции выбора выделили информацию о повышенных требованиях к качеству интерфейса с обучаемым и описанию программного продукта.

Поиск конфигурации ПМК-сети. Использование имитационной модели при поиске архитектурного решения позволило образовать лучшее решение на базе 4-х вычислителей в параллельной сети. Эта конфигурация ПМК-сети дает ускорение расчетов в 3.81 раза по сравнению с последовательной программной и в 1.27 раз по сравнению с предложенной первоначально конвейерной схемой расчета на 4-х вычислителях. Нелинейные составляющие ФВ, сформированной для IIMK-ссти, показали перспективность изменяемой архитектуры ПМК-сети.

ЗАКЛЮЧЕНИЕ

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

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

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

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

• организация сокращения пространства предметных переменных;

• организация решения Открытой Задачи для предметных областей, которые не поддаются разделению квазилинейной функцией выбора.

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

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

5. На основе объединения механизмов образования нелинейной функции выбора н выдвижения для нее эмпирических гипотез, а также механизма переинтерпретации пар переменных, разработана опытная версия Про-

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

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

;. Созданная инструментальная

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

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

• Образовано правило поиска конфигурации ПМК-сети. Правило выбора конфигураций выделило два решения, которые позволят решать на ПМК-сети расчетную задачу наиболее эффективно. Одно из решений является лидером но результатам формирования функции выбора, а второе решение было найдено в результате оценки нескольких хороших решений и их объединения в виде динамической структуры ПМК-сети.

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

Основные результаты диссертации опубликованы в следующих работах:

1. Дзегеленок И.И., Мильман М.О. Экспертная поддержка "усилителей интеллекта"// XI конф. "Информационные средства и технологии" Межд.форума информатизации: Тез. докладов. - М., 1994 - С.34-35.

2. Корлякова М.О. О построении обобщенного показателя качества для рабочих станций.// XII конф. "Информационные средства и технологии" Межд.форума информатизации.: Тез. докладов. -М., 1995 - С.32-33.

3. Корлякова М.О. Открытые Задачи с нелинейной функцией выбора для поддержки поискового проектирования вычислительных систем.// XIV конф. "Информационные средства и технологии" Межд. форума информатизации: Тез. докладов. - М., 1995 - С.104-109.

4. Дзегеленок И.И., Корлякова М.О. Метод переинтерпретации оценочных шкал в "усилителях интеллекта".// 6-й симпозиум "Квалиметрия человека и образования: методология и практика." Проблемы создания комплексного мониторинга качества образования в России.: Тез. докладов., Кн.П, ч.2 -М., 1997,- С.8-11.

11еч. .1. /',2 5 Тираж- Заказ /^О

Типография МЭН, Красноказарменная, 13.