close

Вход

Забыли?

вход по аккаунту

?

Учебное пособие к выполнению КР

код для вставкиСкачать
Федеральное государственное бюджетное образовательное
учреждение
высшего профессионального образования
Национальный исследовательский университет «МЭИ»
________________________________________________________
И.И.Дзегеленок, Кондратьев М.А._Аляева Ю.В.
ПРИМЕНЕНИЕ РЕШАТЕЛЯ ОТКРЫТЫХ ЗАДАЧ
Методическое пособие
по курсу
«Поисковое проектирование вычислительных систем»
для студентов, обучающихся по направлению
«Информатика и вычислительная техника»
Москва
Издательский дом МЭИ
2012
УДК
621.398
М 545
Утверждено учебным управлением МЭИ (ТУ)
Подготовлено на кафедре вычислительных машин, систем и сетей
Рецензент: профессор И.И. Ладыгин
Дзегеленок И. И., Кондратьев М.А._Аляева Ю.В.
Применение решателя открытых задач: методические указания по курсу
«Поисковое проектирование вычислительных систем» / Дзегеленок И.И.,
Кондратьев К.А._Аляева Ю.В.— М.: Издательство МЭИ, 2012—50 с.
Излагается методика и даются методические рекомендации
к
практической реализации и применению в учебном процессе разработанной в МЭИ
оригинальной информационной технологии, обеспечивающей формирование
причинно- следственного знания в области поискового проектирования
вычислительных систем. Данное пособие предназначено для студентов специальности
22.0100, выполняющих курсовую работу по дисциплине «Поисковое проектирование
вычислительных систем». Пособие может быть также полезно для организации
самостоятельной работы студентов родственных специальностей с целью развития
навыков инженерного проектирования малоизученных средств вычислительной
техники и технических систем новых поколений.
Московский энергетический институт, 2012
2
ВВЕДЕНИЕ
Данное пособие посвящено практической реализации и
применению в учебном процессе разработанной в МЭИ при участии
авторов оригинальной информационной технологии, обеспечивающей
формирование причинно- следственного знания в области поискового
проектирования вычислительных систем (ППВС).
Успех применения данной технологии предопределяется
качественно новыми возможностями решения так называемых
открытых задач, когда внешние показатели качества до конца не ясны,
поскольку объект проектирования малоизучен, а его внутренние
параметры определяются предметными переменными с именными
значениями.
Основное звено технологии – решатель открытых задач.
Открытость и свобода в постановке задач указывает на широкую
область применения реализуемой технологии ППВС. Вместе с тем,
наиболее сложный момент, затрудняющий полную автоматизацию, –
блок качественной оценки (БКО) порождаемых решателем гипотез.
Опыт преподавания одноименной дисциплины «ППВС» в
рамках дисциплин ученого совета АВТИ показывает, что выполнение
студентами 5-го курса запланированной курсовой работы во многом
затруднено из-за отсутствия каких-либо ранее изданных методических
указаний.
Обобщение принципов, приемов и способов воссоздания БКО
как раз и составляет основную цель в изложении данного пособия,
состоящего из 3-х глав. Первая содержит минимум необходимых
сведений по определению особенностей практической реализации
собственно технологии поискового проектирования. Основу пособия
составляет содержание второй главы по определению способов
практического осуществления БКО. Результирующая часть пособия –
третья глава, в которой представлена техника стыковки решателя с
БКО, что существенно повышает уровень автоматизации реализуемой
технологии.
Приложение содержит
перечень решенных открытых задач,
подтверждающий большую свободу творчества студентов при выборе
тематики курсовой работы.
3
1. ТЕХНОЛОГИЯ ПОИСКОВОГО ПРОЕКТИРОВАНИЯ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
1.1. Укрупнённая технологическая схема
Появление новых направлений в развитии вычислительных систем
требует формирования правил и подходов к их проектированию и
нахождению новых проектных решений.
Для проектировщика важно получить единую закономерность
образования конкурентоспособных решений с целью обнаружить среди
них лучшие или оптимальные, а также удачные сочетания значений
параметров проектируемого объекта. При этом возможно, что решения
этих вопросов будут найдены за пределами первоначальных
представлений
о
возможных
вариантах
структуры
объекта
проектирования.
В области приобретения знаний к настоящему времени разработано
значительное число подходов, стратегий, методов и процедур работы с
экспертами, предложены различные способы обработки полученных
результатов, а также создан целый ряд программных средств,
автоматизирующих процессы извлечения знаний из экспертов,
специальных текстов и баз данных.
Однако, как показывает анализ отечественных и зарубежных работ
по проблемам приобретения знаний, практически малоисследованными
остаются
вопросы
приобретения
знаний
при
формировании
непротиворечивых баз знаний (БЗ) с так называемыми «НЕфакторами»[2]:
 Нечеткость;
 Неопределенность;
 Неточность;
 Недоопределенность;
 Неполнота;
Эти вопросы имеют важное значение, поскольку знания,
извлеченные из экспертов, как правило, содержат различные виды «НЕфакторов», в связи с чем соответствующие методы и процедуры
приобретения знаний должны обеспечивать возможность извлечения и
обработки не полностью известной информации. В целом решением
проблем, связанных с представлением и обработкой каждого из «НЕфакторов», занимаются самостоятельные направления исследований, где
для этих целей создаются специальные математические аппараты и
формализмы, наиболее известными из которых являются аппарат нечетких
множеств[3] и методы не доопределенных моделей[4], на основе которых
существует целый ряд конкретных подходов.
4
Одним из возможных к решению проблемы формирования
эмпирических знаний о качестве создаваемых МКС является
разработанный на кафедре ВМСиС теоретический аппарат индуктивного
обобщения фактов[5], предусматривающий выдвижение эмпирических
гипотез для повышения достоверности эмпирического знания.
Технологию поискового проектирования вычислительных систем
(ППВС)[5-7] можно представить в виде следующей упрощенной блоксхемы (Рис.1.1).
Рис.1 .1. Технология поискового проектирования вычислительных систем
 «Концептуализация» – выработка общих представлений о классах
вычислительных систем (ВС) и дальнейшей цели их
совершенствования включая внешние показатели качества с
техническим
заданием
пользователей
или
группы
лиц,
заинтересованных в разработке и применения ВС.
 «Структуризация» – максимально возможное уточнение
архитектуры ВС, ее сопоставление с другими возможными
вариантами построения ВС. Определение внешних показателей
качества и по возможности их пороговых значений.
 «Характеризация»
– определение характерных свойств.
Формирование поискового пространства, предметных переменных
именных значений.
 «Аргументация» – ранжирование предметных переменных, по
степени влияния на цель проектирования, расширение вариантов
реализации ВС, локальные экстремумы[1,5-8].
5
Особенности поискового проектирования вычислительных систем[5,
7]:
а) Переменные имеют именные значения;
б) Расплывчато представление о цели и области допустимых
решений;
в) Генерация гипотез
г) Наличие нелинейных составляющих;
д) Запрещенные фигуры [1, 5-8], т.е. недопустимые сочетания
значений ряда параметров;
е) Необходимость прогнозирования условных экстремумов;
Большая часть этих особенностей (а-д) были частично учтены при
реализации программного комплекса «Решатель открытых задач»
в работе [9].
1.2. Решатель открытых задач как инструмент
формирования эмпирического знания
на основе выдвижения гипотез
В поисковом проектировании ВС большое значение имеет степень
важности параметров проектируемого объекта. С увеличением числа
параметров проектирования, становится сложнее определять или
переопределять их важность. Следовательно, нужны специальные методы
и средства извлечения знаний о предмете проектирования из опыта
эксперта. Указанная задача также относится к функциям экспертных
систем (ЭС).
Приобретение знаний экспертной системой состоит в выявлении их в
источнике, преобразовании в свое внутреннее представление, а затем
перенос в базу знаний. Знание может быть экспертным и эмпирическим.
Экспертное знание ЭС может получить непосредственно от эксперта.
Эмпирическое знание может добываться ЭС через наблюдение за
«окружающей средой». В качестве «окружающей среды» могут выступать
не только результаты измерений, полученные от датчиков, но ответы
эксперта на вопросы, сгенерированные самой системой, на основе
существующих у нее знаний, или результаты моделирования.
Эмпирическое знание формируется в процессе обучения экспертной
системы из расширения представлений о предметной области.
Следовательно, должен существовать специальный механизм пополнения
базы знаний экспертной системы. Формирование эмпирического знания
требует от ЭС «умения задавать вопросы» эксперту по ходу работы. Тогда
появится возможность ставить и решать не полностью определенные
задачи, а также осуществлять поиск закономерностей проектирования
новых объектов. Такого рода задачи называются «открытыми задачами
поискового проектирования»[5-7].
6
Предметная область может быть описана набором параметров x1,…,
xn, каждый из которых имеет несколько значений: xi  ai1,ai2 ,, aik  , где i –
номер параметра, ki—число значений i–го параметра, n – общее число
параметров. Шкала значений каждого параметра может быть различной –
интервальной, дискретной, вербальной и т.д. Таким образом, объекты
исследуемой предметной области представляются перечислением
значений описывающих ее параметров. Формально такие объекты можно
представить в виде вектора x = (x1, x2, … ,xn) состоящего из набора
значений параметров xi, i  1, n . Исследуемую предметную область, в
дальнейшем именуемую поисковым пространством, будем обозначать Dn,
где n – число описывающих его параметров. Общее число решений,
i
n
которые могут существовать в пространстве Dn, составляет    ki .
i 1
Как уже было отмечено ранее, в МЭИ на кафедре ВМСиС разработан
программный комплекс «Решатель открытых задач» (РОЗ), позволяющая
ставить и решать плохоформализуемые задачи. В основу этой системы
(Рис.1 .2) положен механизм активного пополнения базы фактов (БФ).
Пополнение знаний реализуется с использованием методов индуктивного
обобщения фактов и построения эмпирического знания в виде
закономерностей «удачи» – обобщенной скалярной функции выбора g(x)
[5].
Рис.1 .2. Структурная схема решателя открытых задач.
Наиболее существенной интеллектуальной компонентой построения
ФВ является блок выдвижения эмпирических гипотез x0. Именно этот блок
7
обеспечивает процесс обучения, пополнения обучающей выборки.
Выдвижение гипотез x0 связано с необходимостью повышения
достоверности искомого эмпирического знания на расширенной области
поиска лучших решений. Процесс выдвижения эмпирических гипотез
начинается с определения всех опорных решений. Затем из полученного
набора выделяются только те решения, которых на данный момент нет в
обучающей выборке. Полученный набор – это опорные гипотезы xo, на их
основе будет формироваться список эмпирических гипотез x', требующих
качественной оценки по правилу P(x') со стороны эксперта. Гипотезы,
получившие оценку эксперта, пополняют обучающую выборку. В
результате знание РОЗ о данном поисковом пространстве корректируется,
что приближает к решению поставленной открытой задачи. Процесс
обучения считается завершенным, если достигнут необходимый уровень
знаний. Такое решение принимает эксперт на основе изучения вида
текущей ФВ.
Существующая версия решателя открытых задач (РОЗ) состоит из
двух частей: интерфейсной и вычислительной (Рис.1. 3). Интерфейсная
часть написана на Borland Delphi 7.0, вычислительная – на Borland C++
3.0. Обе части представляют собой отдельные исполняемые модули,
обмен данными между которыми осуществляется с помощью файлов
специальных форматов (см. ПРИЛОЖЕНИЕ 2).
Рис.1. 3. Структура модулей решателя открытых задач.
Интерфейсная часть решателя (файл solver.exe) позволяет эксперту
произвести начальную настройку системы: задать список параметров
фактов и их значений, а также собрать из параметров удачные и неудачные
сочетания, которые потом сохранить как начальную базу фактов (Рис.1.4).
После того как эксперт сформирует начальную базу фактов, вступает в
действие математический модуль решателя открытых задач.
8
Рис.1.4. Основная форма интерфейсного модуля решателя открытых задач.
Математический модуль РОЗ представляет собой целую группу
файлов, каждый из которых отвечает за свою часть математической
обработки базы знаний. Основной математический модуль (файл
math_mod.exe) строит функцию выбора, модуль построения локальных
экстремумов
(файл lok_extr.exe) строит локальные максимумы и
минимумы, а затем с помощью модуля генерации гипотез (файл
gener_gp.exe) строятся гипотезы.
Начальная база знаний передается из интерфейсной части РОЗ в
математический модуль с помощью набора текстовых файлов, имеющих
имя math.*(где * – расширение, в зависимости от типа данных, которые
содержит файл).
При разработке новой версии пользовательского интерфейса [9]
решателя открытых задач были использованы три принципа объектноориентированного программирования [10, 11]:
 Инкапсуляция (Encapsulation) – механизм, объединяющий данные и
программный код, и позволяющий манипулировать с этими
данными, защищая и то и другое от внешнего вмешательства или
неправильного использования;
 Полиморфизм (Polymorphism) – свойство объекта, позволяющее
использовать одно и тоже имя для решения двух и более задач, но
технически разных.
 Наследование (Inheritance) – процесс, посредством которого один
объект (наследник) может приобретать свойства другого объекта
(предок).
Использование
средств
объектно-ориентированного
программирования позволяет разложить проблему на связанные между
9
собой задачи. Каждая проблема становится самостоятельным объектом,
содержащим свои собственные коды и данные, которые относятся к этому
объекту.
Воспользуемся
основными
свойствами
объектноориентированного программирования для расширения возможностей
базовых классов решателя открытых задач, разработанных в [9].
1.3.Особенности реализации пользовательского
интерфейса
Структура форм ввода и модификации информации представлена на
(Рис.1. 5).
Рис.1. 5 — Структура форм ввода информации РОЗ.
Основная форма модуля решателя открытых задач TfmSolverMain
(см. Рис.1.6) разделена на несколько экранов:
 коэффициенты функции выбора[5] – получение информации о
пространства внутренних параметров базы знаний (БЗ) РОЗ
(Параметры и их именные переменные, а также их веса)
 Нелинейные компоненты функции выбора[5-7] – информация о
нелинейных компонентах функции выбора, весах и именных
переменных, входящих в эти нелинейные компоненты.
 Удачные и неудачные факты, локальные максимумы и минимумы –
отображение гистограммы базы фактов (БФ) или отображения
списка сгенерированных гипотез. По щелчку на отдельном столбце
гистограммы (Рис.1.6) можем получить расшифровку
факта
(гипотезы, локального экстремума и т.д.)
10
Рис.1.6. Основная форма решателя открытых задач.
Также форма содержит главное меню программы, а также панель
инструментов, дублирующую функции главного меню.
Окно
расшифровки
факта
представляет
собой
класс
TfmSolverObjectView (см. [9]), объекты которого создаются во всех случаях
работы с отдельно взятым объектом xi, принадлежащим базе фактов РОЗ.
Эта форма «умеет» не только представлять факт в наглядном виде, но и
редактировать именные значения введенного факта (Рис.1.7).
Рис.1.7. Окно расшифровки факта.
Формирование пространства внутренних параметров БЗ Dn
производится на форме «Редактор параметров» TfmSolverParam[9]. В
верхней части окна редактирования ( Рис.1.8) пространства внутренних
параметров представлен список параметров базы фактов РОЗ. В нижней
части окна список именных переменных принадлежащих параметру в
верхней части.
11
Рис.1.8. Редактор формирования пространства внутренних параметров.
Редактор базы фактов РОЗ реализован при помощи объекта класса
TfmSolverObjectList – редактора базы фактов. Этот объект реализует
редактор списка ( Рис.1.9) объектов РОЗ по введенному типу объекта.
Выборка осуществляется в процессе создания формы в конструкторе
(constructor)[10]:
constructor Create(AOwner: TComponent; ASolverBase:
TSolverBase;
AObjectClass
:TSolverObjectClass
=
ocFact; AObjectType :TSolverObjectType = sotSuccess);
reintroduce; overload;
Таблица 1 — Параметры конструктора класса TfmSolverObjectList
«Редактор базы фактов»
Параметр
AOwner: TComponent
Описание.
Объект-владелец – в общем случае
основная форма РОЗ.
ASolverBase: TSolverBase;;
База Знаний РОЗ (см. 0).
AObjectClass
Класс объектов для редактирования (см. 0,
:TSolverObjectClass = ocFact
Таблица 6).
AObjectType
Тип объектов для редактирования (см. 0,
:TSolverObjectType
= Таблица 7).
sotSuccess
12
Рис.1.9. Редактор неудачных фактов.
С помощью этой формы осуществляется ввод и редактирование базы
фактов РОЗ[9]. В верхней части формы представлен список фактов, окно
снизу отображает список параметров с именными значениями,
составляющими факт – объект базы знаний (БЗ) РОЗ. По кнопке
«добавить» производится создание нового объекта БЗ, в процессе
создания которого, факт заполняется именными значениями параметров
БЗ.
Унификация взаимодействия решателя открытых
задач с блоком качественной оценки гипотез
Обучение и настройка решателя открытых задач является
итерационным процессом (Рис. 1.10). В начале работы эксперт формирует
пространство внутренних параметров, заполняя список параметров и
значений именных переменных, которые в последствии собирает в
различные факты. На следующем этапе строится функция выбора, в
процессе построения которой взвешиваются все факты, находящиеся в
базе знаний. Также на этом этапе происходит формирование локальных
максимумов и минимумов. Далее проверяется критерий останова обучения
решателя. Если решение не получено, то далее, с помощью
математического модуля решателя открытых задач, происходит
формирование базы гипотез. Эксперт, пользуясь своими знаниями,
производит оценку полученных гипотез, после чего все оцененные
гипотезы пополняют начальную базу фактов, а все неоцененные гипотезы
1.4.
13
отбрасываются, чтобы потом возможно, быть оцененными во время другой
итерации обучения решателя открытых задач. Далее происходит
построение функции выбора, получение локальных экстремумов и так
далее до полной остановки алгоритма.
Рис. 1.10. Алгоритм процесса обучения решателя открытых задач.
Взаимодействие эксперта с интерфейсом решателя открытых задач
(см. Рис.1. 11) а именно постановка и решение открытой задачи[6] с
помощью РОЗ состоит из следующих этапов [11]:
 формирование поискового пространства Dn в виде набора параметров xi
со значениями xi  ai1,ai2 ,, aik  , i  1, n , где каждому именному
значению aij ставится в соответствие вспомогательная булева
переменная xij{0,1}, j= 1, ki ;
i
14
 определение экспертом внешних показателей качества и правил в виде
условий перехода через известные барьеры или граничные значения
f1гр,, fSгр по каждому из внешних показателей качества f1x ,, f S x :
frгр  fr x   max, либо frгр  fr x   min , r  1, S . задающих P(x) так, что
 1, тогда xT – множеству "удачных примеров";
P(x)

(2.1)
=
 0, тогда xF – множеству "неудачных примеров".
 задание исходной обучающей выборки <T, F>, где |Т|>1 и |F|>1,
примеры для множеств T, F (удачных и неудачных фактов) задаются в
виде векторов x = (x1, x2, .., xn) – это начальные знания эксперта;
 обобщение существующей обучающей выборки <T, F> в виде правила
выбора:
  0, если x  T, P(x) = 1
g(x) 
(2.2)
  0, если x  F, P(x) = 0
представляющего собой квазилинейную функцию выбора (ФВ) с
нелинейными составляющими следующего вида:
n
ki
V
g ( x)  y(C, X , H , Z )  ci , j * xi , j   hv * zv  C0
i 1 j 1
v1
(2.3)
Где:
C0 – пороговое значение для функции выбора;
n – общее число внутренних параметров;
xi – внутренний параметр рассматриваемой предметной области,
i  1, n , xi= ai1 ,, aik ;
ki – число значений внутреннего параметра xi;
xij –переменная соответствующая aij – конкретному j-му значению
параметра xi ;
cij – весовой коэффициент при соответствующем xij;
V – количество нелинейных компонент (НК) данной ФВ;
hv – весовой коэффициент при v-й НК, v  1,V ;
zv – v-я нелинейная компонента, представляет собой логическое
произведение значений переменных из пространства Dn, v  1,V , позволяет
частично или полностью исключить зону ошибок F+.
– выдвижение xo—эмпирических гипотез с помощью механизма R{x0}
по функции выбора вида (2.3) с нелинейными составляющими;
– проверка вариантов xo через оценочное правило (2.2);
– увеличение обучающей выборки за счет проверенных эмпирических
гипотез;
i
15
– возврат к построению ФВ (переход на новый уровень знаний об
объекте).
Применительно к задачам, решаемым в данной работе функцию
выбора g(x) следует рассматривать как обобщенный показатель качества,
во-первых, потому, что ее знак отражает значение правила качественной
оценки P(x) и во-вторых, потому, что по величине g(x) можно судить о
степени соответствия объекта х достижению поставленной цели.
Самым долгим процессом в схеме работы РОЗ является процесс
принятия решений по сгенерированным математическим аппаратом
гипотезам.
Первым шагом на пути ускорения процесса вынесения решения по
гипотезам было ввод в систему РОЗ положительных и запрещенных
комбинаций параметров. Это позволило задавать такие пары параметрзначение, появление которых в гипотезе, позволяло однозначно пометить
ее как удачную или неудачную. Но этот механизм окончательно не
освобождал эксперта от рутинной работы по оценке списка гипотез.
Рис.1. 11. Взаимодействие эксперта с решателем открытых задач.
Следующим шагом можно назвать внесение в решатель открытых
задач изменений, позволяющих вклинится в процесс оценки гипотез, и
часть гипотез, еще до подачи их эксперту, оценить автоматически,
пользуясь какими либо правилами (Рис.1.12). В такой схеме работы
решателя, эксперт задает параметры базы знаний, формирует начальную
базу фактов, а потом настраивает блок качественной оценки (БКО).
16
Преимущество такой схемы работы в том, что можно создавать различные
варианты модуля автоматической оценки. Чем полнее эксперт настроит
модуль оценки, чем больше возможных ситуаций будет рассмотрено в
модуле, тем меньше времени будет потрачено на оценку.
Рис.1.12. Взаимодействие эксперта и решателя открытых задач с блоком
качественной оценки.
17
2. БЛОК КАЧЕСТВЕННОЙ ОЦЕНКИ (БКО) ГИПОТЕЗ И
ВОЗМОЖНЫЕ СПОСОБЫ ЕГО РЕАЛИЗАЦИИ
2.1. Простейший способ реализации правил выбора.
Основанная задача, решаемая блоком качественной оценки (БКО) –
это оценка предлагаемых Решателем открытых задач гипотез. При
совместном использовании Решателя и блока качественной оценки гипотез
необходимо учитывать, что качество оценки гипотез, а следовательно и
достоверность полученного решения, будет зависеть от
точности
реализации оценивающего алгоритма БКО.
При реализации оценивающего алгоритма, будем исходить из того,
что идеальный алгоритм – это тот, который использует человек,
рассматривая гипотезу, предложенную решателем. В основе предлагаемой
логики оценки лежит конструкция «если это, значит то», т.е. экспертчеловек оценивает гипотезу, составляя различные значения параметров
этой гипотезы:
 Анализируются значения важных параметров предметной
среды, и если эти параметры не соответствуют заданным, то
можно со значительной долей уверенности утверждать, что
гипотеза является неудачной;
 Производится
последовательный
анализ
оставшихся
параметров, выявляются противоречия в значениях,
осуществляется проверка соответствия отдельных значений
друг другу;
 Выносится
окончательное
решение
об
истинности
предложенной гипотезы с точки зрения набора параметров
предметной среды и соответствия друг другу всех параметров
на основе анализа, проведенного в предыдущем пункте.
В большинстве языков программирования существует стандартная
конструкция «если … то …» (см. Формула 1).
Формула 1. Стандартная конструкция «Если .. то…»
Если < условие > то < действие1 > иначе < действие1 >
С помощью такой конструкции легко реализовать простейший
алгоритм автоматической оценки гипотез. Главное достоинство алгоритма,
реализованного таким образом – его простота, главный недостаток большой объем работ при описании алгоритма в формулах. Объем работ
18
можно сократить, если выделить внутри задачи логические связи между
параметрами, определить запрещенные комбинации, определить
допустимый разброс параметров и т.д.
Качество оценки гипотезы должно максимально соответствовать
качеству оценки, предлагаемой экспертом-человеком. В случае
достижения подобного соответствия мы получим комплекс программ,
практически
самостоятельно
решающих
задачу
поискового
проектирования, поставленную человеком. Следовательно, можно создать
блок оценки, применимый для большинства задач, решаемых при помощи
РОЗ, и, что самое ценное, логика решения задачи, реализованная в блоке,
будет наиболее точно соответствовать логике человека-эксперта.
Подобный подход продемонстрирован в работе студентов Воронкова
Е.С. и Селиверстова С.С. группы А-7-00 Московского Энергетического
Института (ТУ) на примере создания блока качественной оценки гипотез,
настроенного на заданную предметную область – коммутаторы третьего
уровня (Рис.2.1).
19
Рис.2.1. Алгоритм работы блока качественной оценки гипотез
(коммутаторы третьего уровня)
В разработанном блоке оценки реализована функция настройки на
предметную область. При первой передаче сгенерированных гипотез в
блок качественной оценки появляется диалоговое окно, где пользователь
настраивает параметры проблемной среды, тем самым подстраивая и
корректируя алгоритм оценки. Далее все происходит автоматически –
необходимо лишь инициировать построение функции выбора и генерацию
Решателем гипотез.
Обобщая все вышеизложенное можно сказать, что при грамотном
анализе задачи и тщательной разработке алгоритма оценки
автоматический блок может полностью заменить собой человекаэксперта, тем самым ускорив процесс поискового проектирования.
20
2.2. Реализация правил выбора на основе маскирования
параметров
Рассмотрим более сложный способ формирования списка правил
БКО генерируемых гипотез. Алгоритм оценки гипотезы основывается на
комплексном анализе предметной области поставленной открытой задачи.
Причем анализ осуществляется с учетом приоритетов внешних
показателей качества, расставленных постановщиком задачи. Остановимся
более подробно на методике анализа.
Именные значения каждого i-го параметра открытой задачи можно
представить в виде набора целых чисел 0,1,…, ni , соответствующего
номеру именного значения в списке параметров. Таким образом,
изначально значение каждый параметра принадлежит некоторому
интервалу (0, ni ), где ni - число именных значений i-го параметра;
Далее, в порядке расставленных приоритетов, берется один из
внешних показателей качества. Для него делается выборка параметров, к
которым он наиболее чувствителен. Каждый
из параметров
рассматривается в виде интервала, на котором вычеркиваются
(«маскируются») неудовлетворяющие данному внешнему показателю
качества характеристики. Таким образом, интервал сужается. Причем,
интервал сужается тем больше, чем чувствительнее внешний показатель
качества
к рассматриваемому параметру. Потом рассматривается
следующий по чувствительности параметр. Опять накладывается «маска»,
теперь уже нового параметра. Сумма незамаскированных частей
интервалов дает нам область положительных решений. Потом берется
следующий по приоритету внешний параметр, опять делается выборка и
накладываются «маски» и т.д. Таким образом, «маски» накладываются
друг на друга, и выделяется общая область положительных решений.
Для наилучшего понимания метода «маскирования» приведем
пример оценки гипотезы. Число параметров открытой задачи возьмем
равным трем. Число внешних показателей качества – двум.
На рисунке 2.2 показана начальная положительная область, то есть
до оценки гипотезы. На рис.2.3 – положительная область при
рассмотрении более приоритетного первого показателя качества.
Положительная область наиболее чувствительна к параметру 2, поэтому
размер «маски» больше, а интервал уже. На рис. 2.4 показана
положительная область при рассмотрении второй по приоритету
характеристики. Она тоже более чувствительна ко второму параметру, но
так как ее приоритет ниже, то и размер маски меньше. На рис.2.5 показана
объединенная положительная область.
Оценка гипотезы сводится к рассмотрению вопроса попадания
параметров гипотезы в положительную область, сформированную
маскированием параметров.
21
1
2
3
4
5
Параметр1
10
50
60
Параметр2
α
β
γ
δ
θ
Параметр3
a
b
c
d
Рис.2.2. Начальная положительная область
1
2
3
4
5
Параметр1
10
50
60
Параметр2
α
β
γ
δ
θ
Параметр3
a
b
c
d
Рис.2.3. Положительная область для первого внешнего показателя качества
1
2
3
4
5
Параметр1
10
50
60
Параметр2
α
β
γ
δ
θ
Параметр3
a
b
c
d
Рис.2.4. Положительная область для второго внешнего показателя качества
1
2
3
4
5
Параметр1
10
50
60
Параметр2
α
β
γ
δ
θ
Параметр3
a
b
c
d
Рис.2.5. Сумма областей для обоих внешних показателей качества
Приведем пример постановки и решения открытой задачи. Такой
способ формирования правил оценок был использован при написании
курсового проекта «Поисковое проектирование Blade-сервера» студентов
группы А-7-01 Московского Энергетического Института Грешиловой М. и
22
Логинова А. Выступая в роли специалистов по выбору решений на основе
технологии blade, следовало настроить РОЗ на проблемную область. Для
этого, в первую очередь был выделен ряд параметров (факторов), которые
определяет конфигурацию вариантов реализаций серверов. Так, в
соответствии с техническим заданием на проект были выделены
следующие предметные переменные:
 Число CPU в «лезвии»;
 Размер жёстких дисков (HDD);
 Размер оперативной памяти (ОП);
 Частота применяемых CPU;
 Число сетевых интерфейсов на лезвие;
 Число используемых лезвий;
 Цена;
 Класс решаемой задачи;
 Тип предприятия, на котором будет применяться серверное
решение;
Из приведенного выше списка видно, что ряд параметров относится
непосредственно к аппаратной части, а вот остальные параметры как раз и
являются внешними показателями качества (цена, класс задачи, тип
предприятия), зависящими от набора аппаратных параметров.
Остановимся более подробно на классе решаемых задач и типе
предприятия. В данной работе рассматривался подбор конфигурации
blade-сервера для одного из типов задач, для каждого из которых можно
составить последовательность наиболее важных параметров blade-сервера,
к изменению которых данный класс наиболее чувствителен, а именно:
 Почтовые службы (число и тип CPU, размер HDD, размер ОП,
число сетевых интерфейсов);
 Хранилище баз данных (размер HDD, число сетевых
интерфейсов, размер ОП, число и тип CPU);
 Антивирусные приложения (размер ОП, число и тип CPU,
число сетевых интерфейсов, размер HDD);
Типы предприятий, для которых проектируется blade-сервер, можно
разделить, воспользовавшись классической классификацией:
 Малые предприятия;
 Средние предприятия;
 Крупные предприятия;
При построении конфигурации сервера было приняты правила:
 Для малого предприятия необходимо оборудование недорогое,
с низкими характеристиками;
 Для среднего – среднее по цене и характеристикам
оборудование;
23
 Для крупного – наиболее мощное, но, соответственно, дорогое
оборудование;
Блок качественной оценки в рабочем режиме настраивается таким
образом, что выбирается задача определенного класса для нахождения
типа предприятия. Во избежание различных ситуации “запутывания”
решателя был выбран режим полного оценивания. Были установлены
следующие критерии (Рис.2.6):
Рис.2.6. Настройка блока качественной оценки
За время решения задачи было произведено 32 итерации. В ходе
обучения количество нелинейностей росло и к 32 итерации достигло
значения 155. Число гипотез колебалось от 32 до 482. Начиная с 28
итерации количество гипотез установилось равным 152 и в течении
оставшихся
итераций оставалось без изменений. Предложенные
локальные максимумы удовлетворяют требованиям. На основании этих
фактов был сделан вывод о том, что решатель обучился. На (Рис.2.7)
показан случайный локальный максимум, полученный на финальной
итерации.
24
Рис.2.7. Локальный максимум
2.3. Способ расчета показателей качества сформированных
гипотез на основе сравнения с эталонной гипотезой
Еще более сложным примером блока качественной оценки является
блок качественной оценки, ведущий анализ факта на основе эталонных
гипотез. Для построения такого блока следует выполнить начальный
анализ предметной области и выделить перечень критериев оценки, а
также перечень показателей (параметров), по которым следует вести
анализ. На основе перечня параметров мы должны оценивать гипотезу как
удачную или неудачную. Для проведения оценки предлагается следующий
механизм:
 Для каждого из критериев, определяется набор параметров (из
общего перечня), влияющих на данный критерий.
 Определяется вес каждого из параметров во всех наборах (сумма
весов всех параметров должна равняться единице). Так как для
каждого критерия определен свой набор параметров, то,
соответственно, для каждого параметра в разных наборах будут
определены разные веса.
 Определяется степень влияния (вес) каждого из критериев, при
оценке гипотезы. Сумма весов всех критериев должна равняться
единице.
 Для каждого параметра составляется шкала значений, в которую
заносятся все значения, которые может принимать каждый из
параметров. Значения записываются в шкалу в порядке
возрастания, и каждому значению присваивается его номер в
шкале, номера так же присваиваются в порядке возрастания.
25
 Определяется эталонная модель, которая воспринимается как
наихудшая из удачных.
 Гипотеза проверяется на наличие запрещенных комбинаций, если
запрещенные комбинации есть, то гипотеза признается
неудачной, в противном случае – выполняются действия,
описанные ниже в п. 7).
 Рассчитывается показатель качества гипотезы, и эталонной
модели, и если показатель качества гипотезы меньше показателя
качества эталонной модели, то гипотеза оценивается, как
неудачна, как удачная – в противном случае.
Все величины, описанные в п.п.1–5, должны задаваться в качестве
исходных данных. Для расчета показателя качества предлагается
использовать следующий алгоритм.
1) Введем следующие обозначения:
 количество параметров: M;
 количество критериев: N;
 набор значений параметров, заданных в гипотезе: V(i), i=1..M;
 веса параметров: Pv(i, j), i=1..N, j=1..M, если j-ый параметр не
влияет на i-ый критерий, то Pv(i, j)=0;
 вес критерия при оценке гипотезы: Pk(i), i=1..N;
 количество всех возможных значений параметра: S(i), i=1..M;
 шкала всех возможных значений параметров: Zv(i,j), i=1..M,
j=1..S(i);
 показатель качества параметра: Xv;
 показатель качества критерия: Xk;
 показатель качества гипотезы: Xg;
 счетчики циклов: i, j, k.
2) Алгоритм расчета показателя качества гипотезы (Xg):
Xg:=0;
для i от 1 до N цикл
Xk:=0;
для j от 1 до M цикл
Xv:=0;
k:=1;
пока Xv=0 и k<=S(j) цикл
если V(j)=Zv(j,k) то
Xv:=k;
кесли;
k:=k+1;
26
кц;
Xk:=Xk+Xv*Pv(i,j);
кц;
Xg:=Xg+Xk*Pk(i);
кц;
3) В представленном алгоритме исходными данными являются
следующие параметры:
 количество параметров (M);
 количество критериев (N);
 набор значений параметров, заданных в гипотезе;
 веса параметров (Pv);
 вес критериев (Pk);
 количество всех возможных значений параметра (S);
 шкала всех возможных значений параметров (Zv).
Подобный подход был продемонстрирован в работе «удаленные
системы информационного взаимодействия и определения своего
местоположения на основе карманных персональных компьютеров и
навигационной аппаратуры потребителя». После проведения тщательного
анализа предметной области были сформулированы следующие критерии
оценки:
 стоимость;
 эргономика;
 коммуникабельность;
 точность определения координат;
 производительность.
При анализе учитываются следующие показатели:
для карманного персонального компьютера:
 тактовая частота процессора;
 объем оперативной памяти;
 наличие разъема CF и SD;
 наличие средств BlueTooth и Wi-Fi;
 операционная система;
 диагональ экрана;
 разрешение экрана;
 время работы без подзарядки;
для навигационной аппаратуры потребителя:
 количество каналов обработки информации от спутников;
 заявленная производителем точность определения координат;
 тип навигационной аппаратуры потребителя.
27
В работе были определены критерии оценки гипотез и перечень
показателей (параметров), по которым ведется анализ. Таким образом, на
основе данных параметров проводилась оценка гипотезы как удачная или
неудачная.
2.4. Блок качественной оценки гипотез на основе имитационного
моделирования
Рис.2.9. Блок качественной оценки на основе имитационной модели
1. Постановка задачи
Дано:
1. База знаний Решателя открытых задач по рабочим станциям
настроенная на определенную предметную область (Эффективная
работа с СУБД, с графикой, с математическими вычислениями и
т.д.);
2. Справочник, содержащий список сетевых адаптеров;
3. Справочник, содержащий список сред передачи данных;
4. Граф сетевой распределенной задачи, предназначенный для
решения на моделируемой сети;
5. Тип сети (Параллельная сеть, Параллельно-конвейерная сеть,
Конвейерная сеть);
В качестве внешних показателей качества возьмем два параметра:
6. Производительность параллельной мультикомпьютерной сети (P).
7. Стоимость реализации (Sр).
28
Требуется решить задачу определения оптимальной конфигурации
параллельной мультикомпьютерной сети
с целью максимизировать
производительности сети и минимизировать ее стоимость.
29
РЕАЛИЗАЦИЯ АВТОМАТИЧЕСКОГО ВЗАИМОДЕЙСТВИЯ
РЕШАТЕЛЯ С БЛОКОМ КАЧЕСТВЕННОЙ ОЦЕНКИ ГИПОТЕЗ
Перейдем к рассмотрению возможности разработки блок
качественной оценки (БКО) гипотез реализующего следующие функции.
 Отображение списка оцениваемых гипотез;
 Возможность выбора гипотез для автоматической оценки;
 Автоматическая оценка списка гипотез;
 Отображение результатов оценки;
Программное обеспечение (ПО) должно представлять собой
приложение с графическим интерфейсом пользователя. Платформа –
персональный компьютер семейства IBM PC, операционная система –
32 разрядная Windows. Среда разработки – Delphi 7.0.
3.
3.1. Программная реализация блока качественной оценки
Реализация блока качественных оценок сделана с помощью
динамически подключаемых библиотек (Dynamic Link Library) – файлов с
расширением .dll [10]. Для подключения библиотек внешнего оценочного
модуля на форме «Настройки программы» (Рис.2.9) была введена
возможность выбора файла с расширением .dll, после подключения файла
в системе становится доступен пункт основного меню «Модуль авт.
оценки» (. Рис.2.10)
Рис.2.9. Подключение блока качественной оценки.
Рис.2.10. Пункт меню "Блок качественной оценки".
30
В дальнейшем при работе эксперта с решателем открытых задач
после построения функции выбора и генерации гипотез будет вызвана
функция SolverRateModuleFunc, и часть гипотез будет оценены (Рис.2.12.)
с помощью модуля автоматической оценки. Гипотезы, которые не были
оценены модулем, будут отображены на гистограмме гипотез, и могут
быть оценены обычным образом.
Рис.2.12. Информация о результатах автоматической оценки гипотез.
Блок качественной оценки реализуется в среде Borland Delphi 7.0.
Первоначально создаем проект динамически подключаемой библиотеки,
для чего в среде Borland Delphi 7.0 выбираем пункт меню <File\New\Other>
и в окне на экране выбираем DLL Wizard (см. Рис.2.13). После чего
сохраняем только что созданный проект под именем example.dpr.
Внимание! При создании библиотеки не забудьте включить в него файлы
модулей из каталога .\SolverLocal\Units.
Рис.2.13 - Создание проекта DLL
31
3.2. Список экспортируемых функций
Интерфейс решателя открытых задач в процессе работы должен
вызвать из DLL одну из двух экспортируемых функций. Заголовки
экспортируемых функций прописываются в проекте в разделе exports, а
тело функции прописывается в любом из модулей проекта. В нашем
примере заголовки будут прописаны в example.dpr, а тело функции будет
прописано в модуле ExampleExportUnit.pas.
exports
GetRateModuleFunc
name
'GetRateModuleFunc',
//Экспортируемая функция оценки гипотез.
GetRateModuleForm
name
'GetRateModuleForm';
//Экспортируемая функция настройки системы
TSolverRateModuleFunc – Функция автоматической оценки списка
гипотез (см. Таблица 2). Вызов этой функции осуществляется после того,
как корректно завершил работу модуль генерации гипотез (т.е. гипотезы
сгенерированны, файлы гипотез записаны).
Таблица 2 - Параметры функции GetRateModuleFunc
Параметр
AOwner:
TComponent;
ASolverBase:
TSolverBase;
Описание
Объект,
являющийся
владельцем для
всех
создаваемых в процессе работы объектов.
База данных решателя открытых задач. Через этот
объект можно получить список всех параметров базы
знаний, а также списки фатов и гипотез.
Параметр – запись, содержащая два поля: количество
гипотез оцененных положительно, а также
количество гипотез, оцененных отрицательно.
Возвращаемое значение логического типа. Если
возвращаемое значение «истина», то модуль
корректно оценил часть гипотез.
ARateFuncInfo:
rRateFuncInfo
Result: boolean;
Для начальной настройки системы опишем еще одну функцию
TSolverRateModuleForm (см. Таблица 3). Вызов этой функции
осуществляется когда угодно в процессе работы Решателя открытых задач,
и позволяет эксперту настроить блок оценки.
Таблица 3 — Список параметров функции настройки БКО
TSolverRateModuleForm.
Параметр
AOwner: TComponent;
Описание
Объект, являющийся владельцем для всех
32
ASolverBase: TSolverBase;
ARateModuleOptions:
pRateModuleOptions
Result: TForm;
создаваемых в процессе работы объектов.
База данных решателя открытых задач. Через
этот объект можно получить список всех
параметров базы знаний, а также списки
фатов и гипотез.
Описание параметров, которые следует
вернуть из настройки оценочного модуля
Объект класса TForm – форма настройки
модуля автоматической оценки гипотез.
Функция GetRateModuleForm предназначена для вывода формы
настройки блока качественной оценки для будущего использования. В
примере будет просто заглушка, которая будет создавать, а затем
показывать пустую форму.
Тела функций поместим в отдельный файл. Создаем в проекте новый
модуль (File\New\Unit). Создается пустой модуль. В разделе interface
прописываем полные заголовки экспортируемых функций РОЗ. Не
забывайте включать в раздел uses, те модули, которые вы собираетесь
использовать. В разделе implementation прописываются тела функций.
Функция GetRateModuleFunc в соответсвтии с заданием должна
вызвать интерфейс БКО, и передать данные об оцененнх гипотезах
гипотезах в интерфейс РОЗ. В самом общем виде вызов формы БКО
выглядит таким образом: Заглушки в исходном коде <<>> заменяем на
программный код, когда появится в проекте форма (Объект класса TForm).
function GetRateModuleFunc(AOwner: TComponent; var
ASolverBase:
TSolverBase;
var
ARateFuncInfo:
rRateFuncInfo):boolean; //заголовок функции оценки
begin
Result := False;
<<Создаем форму оценки гипотез.>>>
try
ASolverBase.StartTransaction;
//Начинаем
работу по изменению данных в БЗ
if ShowModal = mrOk then begin
//Если все
нормально, то
ASolverBase.CommitTransaction;
//Сохраняем
изменения
ARateFuncInfo
:=
<<Возвращаем
значение
о
оцененных гипотезах>>
Result := True; //ВСЕ ОК!
end else
33
ASolverBase.RollbackTransaction;
откатываем операции
finally
<!!!Почистить за собой форму!!!!>
end;
end;
//Иначе
3.3. Форма выбора гипотез для последующей оценки
Для создания формы в проекте следует выбрать пункт меню
(File\New\Form). Зададим название формы (name fmExampleMain) и
заголовок (caption) "Список гипотез для оценки". Форму будет отображать
список полученных из блока генерации гипотез для последующего выбора
и оценки. Для отображения списка гипотез воспользуемся объектом
TItemList.
Перепишем конструктор формы(constructor), добавив в него еще
один параметр – базу знаний. Для быстрого доступа к базе знаний РОЗ
создадим для формы приватное (private) свойство (property) FSolverBase:
TSolverBase. Для быстрого доступа к параметрам функции создадим еще
одно поле FRateFuncInfo: rRateFuncInfo и создадим общедоступную
(public) функцию для доступу к этому полю:
TfmExampleMain = class(TForm)
lvSolverHipothesis: TListView;
< …………..>
private
FSolverBase: TSolverBase;
FRateFuncInfo: rRateFuncInfo;
< …………..>
public
property
HipSolverBase:
TSolverBase
read
FSolverBase write FSolverBase;
function GetRateFuncInfo: rRateFuncInfo;
constructor
Create(AOwner:
TComponent;
var
ASolverBase: TSolverBase); reintroduce; overload;
end;
constructor TfmExampleMain.Create(AOwner: TComponent;
var ASolverBase: TSolverBase);
var
i, j: integer;
begin
34
<Вызов
предыдущего
конструктора,
полей формы>
<Заполнение списка гипотез>
end;
инициализация
3.4. Структура базовых классов решателя открытых задач
Для хранения и обработки базы знаний в интерфейсном модуле
решателя открытых задач была разработана новая структура классов
(Рис.2.14). При этом к ней предъявлялись следующие требования:
 Простота модификации;
 Простота добавления новых вариантов комбинаций параметров
(фактов);
 Объектно-ориентированный подход к разработке.
Основной класс TSolverBase – база знаний решателя открытых задач,
содержит в себе объект класса TSolverParamList – список параметров, а
также объект класса TSolverObjectList – список сочетаний параметров.
Список
параметров
представляет
собой
наследника
класса
TList(список)[4], что позволяет оперировать с ним как со списком
указателей. В поле Items(элементы списка) записываются указатели на
объекты типа TSolverParam – параметры базы знаний РОЗ. Параметры
базы знаний содержат в себе наименование параметра, его уникальный
номер (УН), а также список именных переменных. Обьект сочетаний
параметров содержит в себе список различных сочетаний параметров РОЗ.
Поскольку все факты с котрыми оперирует эксперт в процессе настройки
РОЗ представляют собой различные сочетания параметров РОЗ, то было
созданно описание одного класса, который «умеет» хранить в себе
сочетания параметров. Обьекты класса TSolverObject (сочетание
параметров РОЗ) содержат наименование, свой уникальный номер, а также
список значений. Каждое значение параметра РОЗ описывается
комбинаций уникальных номеров— (УН Параметра, УН Значения). Таким
образом мы избегаем большого расхода памяти при хранении базы знаний,
а также удобства операций с ними.
35
Рис.2.14. Структура классов базы знаний решателя открытых задач.
Класс TSolverParam
С помощью объектов этого класса (class) описываются все
параметры базы знаний. Также содержит в себе список именных значений.
Рассмотрим некоторые свойства (property) этого класса.
TSolverParam = class(TList)
private
<……>
<Приватные поля>
<……>
public
<……>
<общедоступные поля и функции>
<……>
function
GetValueIndex(ValueID:
Integer):
integer;
function
GetValueIndexByValue(Value:
String):
integer;
function GetValueID(Index: integer): Integer;
function FindParamValue(ParamValue: String; var
Index: integer): Boolean;
function
ValueByName(Value:
ShortString):
Integer;
property ParamID: Integer;
36
property Value[index: integer]: ShortString read
GetValue write SetValue;
property ValueByID[ValueID: integer]: ShortString
read GetValueByID write SetValueByID;
property Weight[index: integer]: Integer;
property ParamIndex: Integer read FParamIndex;
property ParamName: string;
end;
Именные значения в этом списке представлены указателями на
структуру (см. Таблица 4):
RSolverParamValue = record
pValueID: integer;
pValue: ShortString;
pWeight: Integer;
end;
Таблица 4 - Описание структуры RsolverParamValue
Поле
pValueID: integer;
pValue:
ShortString;
pWeight: Integer;
Описание
ID именного значения, может отличатся от индекса в
списке.
Именное значение.
Вес именного значения.
Таблица 5 - Описание некоторых полей класса TSolverParam
Поле
property ParamName
property ParamID
property Weight
FindParamValue
Описание
Наименование параметра
ID(уникальный номер) параметра .
Вес именного значения параметра(доступ по номеру именног
параметра)
Возвращает истину, если именное значение <ParamValu
String> был успешно найдено, номер параметра возвращается
<Index: integer>
Различные варианты доступа к именным значениям
ValueByName
property ValueByID
property Value
GetValueIndex
Варианты перевода ID именного значения в его номер в списк
GetValueIndexByValue TList. Или наоборот.
37
GetValueID
Класс TSolverObject.
Класс описывает все объект базы фактов, такие как: гипотезы,
факты, Локальные максимумы и минимумы, запрещенные фигуры,
условные экстремумы. По сути является списком, содержащим указатели
на структуру.
PSolverFactValue = ^RSolverFactValue;
RSolverFactValue = record
fParamID: integer;
fValueID: integer;
fErrorValue: Boolean;
end;
TSolverObject = class(TList)
private
<……>
<Приватные поля>
<……>
protected
public
<……>
<общедоступные поля и функции>
<……>
property ObjectName: string read FObjectName
write SetObjectName;
property
ObjectClass:
TSolverObjectClass
read
FObjectClass write FObjectClass;
property
ObjectType:
TSolverObjectType
read
FObjectType write FObjectType;
property
ObjectList:
TSolverObjectList
read
FObjectList;
property ObjectWeight: integer read FObjectWeight
write FObjectWeight;
function
ParamByName(AParamName:
String):
PSolverFactValue;
function
ParamById(AParamId:
Integer):
PSolverFactValue;
38
function
integer;
end;
ValuesCount(MeaningValue:
Boolean):
Для разделения различных типов сочетаний параметров в объект
TSolverObject были введены два поля типа TSolverObjectClass – класс
объекта решателя (см. Таблица 6), а также типа TSolverObjectType – тип
объекта решателя (Таблица 7).
Таблица 6 — Классы объектов базы фактов РОЗ.
Класс обьекта
TSolverObjectClass
ocFact
Описание
ocLocalMax
ocLocalMin
ocConditionalMax
ocConditionalMin
ocNonLinear
ocHipothesis
ocPositiveComp
ocNegativeComp
ocConditionalExtremumValues
Объект описывает факт решателя открытых
задач.
Локальные экстремумы функции выбора.
Условные экстремумы функции выбора
Нелинейная составляющая функции выбора
Гипотеза
Положительные
или
отрицательные
(запрещенные) комбинации фигур.
Параметры условного экстремума
Таблица 7 — Типы объектов базы фактов РОЗ.
Тип объекта
TsolverObjectType
sotSuccess
sotUnsuccess
sotIndefinite
sotNone
Описание
Удачное или неудачное сочетание параметров
(используется в фактах, гипотезах, максимумах
или минимумах)
Неопределенно состояние факта.
Таким образом, удается разделить сочетания параметров решателя
открытых задач на факты, гипотезы, комбинации параметров, экстремумы
функции выбора и т.д, а также будет достигнута легкость
модифицирования кода. Например, для появления в системе РОЗ нового
варианта сочетания параметров, будет достаточно просто добавить новый
тип и класс. Соответственно таким же образом в интерфейсной части
39
удается избежать дублирования кода, отделив обработчикков событий
форм в соответствии с классом обрабатываемого объекта.
ЗАКЛЮЧЕНИЕ
Приведенные методические указания вносят дополнительный вклад
в повышение эффективности решения открытых задач, а в целом, в
дальнейшее развитие разработанной в МЭИ теории индуктивного
продолжения функции выбора [ ]. Да, действительно, решатель, как
открытая интеллектуальная система, предъявляет минимум требований к
эксперту (в нашем случае, студенту), работающего над постановкой
собственной открытой задачи. Да, действительно, повышается
достоверность искомого
причинно-следственного знания за счет
целенаправленного порождения эмпирических гипотез и их качественной
оценки. И это уже неплохо. Но вот что важно. Окончательный эффект от
решения открытой задачи зависит от степени «интеллектуальности» блока
качественной оценки гипотез. А уж если блок построен, то остается лишь
один шаг к осуществлению автоматического взаимодействия решателя
теперь уже не с экспертом, а с БКО. Так что круг замкнулся. Вот почему
данное пособие, как надеются его авторы, облегчит муки творчества
любого студента, приступающего к выполнению курсовой работы в такой
важной и увлекательной области как поисковое проектирование
вычислительных систем.
40
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Аляева Ю.В. Разработка методов и инструментальных средств
прогнозирования
качественных
характеристик
мультикомпьютерных систем // дис. на соискание уч. ст. к.т.н. – М.;
МЭИ, 1999г.—190с.
Нариньяни А.С. Недоопределенность в системах представления и
обработки знаний//Изв. АН СССР. Техн. кибернетика. 1986. №5.
Нечеткие множества в моделях управления и искусственного
интеллекта//Под ред. Поспелова Д.А. М.: Наука, 1986.
Проблемы представления и обработки не полностью определенных
знаний//Под ред. Нариньяни А.С. М.: РосНИИ ИИ, 1996.
Дзегеленок И.И. Поисковое проектирование мультикомпьютерных
систем с использованием индуктивных обобщений. Автореферат
дис. На соискание уч. ст. д.т.н. – М.; МЭИ, 1996г.—40с.
Дзегеленок И.И. Открытые задачи поискового проектирования //
Учебное пособие по курсу "Основы инженерного творчества." –
М.: МЭИ, 1991. – 66 с.
Дзегеленок И.И. Логика поиска проектных решений // Учебное
пособие по курсу "Теоретические основы машинного
проектирования." – М.: МЭИ, 1984. – 64 с.
Корлякова М.О. Разработка методов и средств приобретения
эмпирических
знаний
в
поисковом
проектировании
вычислительных систем. Автореферат на соискание уч. ст. к.т.н.—
М.:МЭИ, 1998г.—20с.
Кондратьев М.А. Разработка средств сетевого взаимодействия
решателя открытых задач и разработка микропроцессорной
системы. //Бакалаврская работа – М,;МЭИ, 2003г – 234с.
Архангельский А.Я. Delphi 7. Справочное пособие. – СПб.:
«Бином», 2003. – 1024 с.
Шилдт Г.. Самоучитель C++: пер. с англ. – СПБ.; BHV – СанктПетербург, 1997. – 512 с., ил.
Дзегеленок И.И., Аляева Ю.В., Кузнецов А.. Лабораторные работы
по курсу «Поисковое проектирование вычислительных систем».—
М.: Изд-во МЭИ, 2001.—40 с.
Олифер В.Г. Олифер Н.А. Компьютерные сети, принципы,
технологии, протоколы. – СПб.: Питер, 2001.-672 с.: ил.
Брежнев А.Ф., Смелянский Р.Л., «Семейство протоколов TCP/IP»,
1994.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.:
BHV – Санкт-Петербург, 2002 г. – 608с.
41
16 Башлыков А.А., Еремеев А.П. Экспертные системы поддержки
принятия решений в энергетике /Под ред. А.Ф. Дьякова. – Изд-во
МЭИ, 1994. – 216с., ил.
17. Абижанова И.К.
Ильин И.В.
Хорошун И.В. «Разработка
архитектуры вычислительного кластера». Курсовой проект
по дисциплине «Поисковое проектирование вычислительных
систем». М.:МЭИ, 2005г.—29с.
18. Дзегеленок И.И. Методология поискового проектирования
вычислительных систем // Информационная математика.–
Изд-во РАЕН АСТ-Физматлит, № 1(4), 2004, с. 110–119,
19. Дзегеленок И.И. Активное добывание знаний как инновационная
технология открытого образования Материалы VIII
международной научно-практической конференции
«Качество дистанционного образования. Концепции,
проблемы, решения (EDO–2006)».– М.:МГИУ, 2006, с.101–
105
20. Дзегеленок И.И. Открытые интеллектуальные системы // В книге
«Техническое творчество: теория, методология, практика»
Энциклопедический словарь-справочник / Под ред. А.И.
Половинкина, В.В. Попова. - М.: НПО «Информ-система»,
1995. - 408с.
21. Дзегеленок И.И., Сетевые образовательные технологии актуализации
знаний // Информационные технологии в проектировании и
производстве: Научно-технический журнал.– М.: Изд-во
ФГУП «Всероссийский институт межотраслевой
информации». 2003. №3. С.10–15.
22. Вагин В.Н., Еремеев А.П., Дзегеленок И.И.,, Колосов О.С., Фролов
А.Б. –Становление и развитие научной школы
искусственного интеллекта в Московском энергетическом
институте.– Журнал: «Программные продукты и системы»,
2010, №3, с.3–16
1.
42
ПРИЛОЖЕНИЕ 1. Перечень тем курсовых работ, выполненных с
использованием технологии поискового проектирования (2008-2009
г.г.)
1. «Проблема выбора провайдера, предоставляющего сеансовый
доступ в Интернет по коммутируемым линиям связи».
2. «Поисковое проектирование коммутатора 3-го уровня для
корпоративной сети с использованием автоматического блока
оценки.
3. «Проблема выбора звуковой карты».
4. «Проблема выбора межсетевого экрана»,
5. «Поисковое проектирование сетевых маршрутизаторов»,
6. «Проблема
выбора
провайдера,
предоставляющего
широкополосный доступ в сеть Интернет»,
7. «Проблема
выбора
оптимальной
среды
разработки
приложений»,
8. «Поисковое проектирование архитектуры вычислительного
кластера»,
9. «Поисковое проектирование топологии радиосети передачи
данных»,
10. «Поисковое проектирование топологии сети передачи
данных»,
11. «Проблема выбора сетевых программных средств для
проведения видеоконференций»,
12. «Проблема выбора видеокарты для задач динамической
визуализации»,
13. «Обеспечение устойчивой работы 1С-предприятиеГрешилова,
14.«Поисковое проектирование Блайд- сервера»,
15. «Поисковое проектирование двуядерного процессора»,
16. «Поисковое проектирование ЛВС CAN» ,
17. «Поисковое проектирование отражающей памяти
18. «Проблема выбора средств аутентефикации пользователей»,
19. «Проблема выбора сканера»
20. «Поисковое проектирование средств позиционирования(GPS)
на местности с помощью КПК»,
21. «Проблема выбора видеокарты
22.«Прогнозирование поведения рынка ценных бумаг»,
23.«Поисковое проектирование сети счетчиков электроэнергии»,
24.«Сжатие файлов на ПМК- Сети
25. «Коммутаторы в масштабах предприятия»,
26. «Рабочая станция для ресурсоемкой графики»,
43
27. «СУБД для интернет- проектов»,
28. «Проблема выбора методов распознавания образов»,
29. «Проблема
выбора
оптимальной
видеокарты
для
компьютерной графики»,
30. «Проблема выбора интернет-провайдера
31. «Компьютерные обучающие программы
32. «Оптимальное печатающее устройство»,
33. «Выбор оптимального адаптера беспроводной связи»,
34.«Поисковое проектирование программных и аппаратных
средств настройки сервера БД»,
35. «Терминальная сеть на базе OC Linux»,
36. «Проблема выбора GPS навигатора»,
37.«Конфигурирование системы взаимной проверки знаний»,
38. «Кластер для очень больших задач», Москва, МЭИ, группа А8-03, 2007 г.;
39.«Многофункциональное
устройство
для
строительной
организации»,
40. «Проблема выбора адаптера беспроводной связи»,
41. «Конфигурация рабочей станции»,
42. «Архитектура вычислительного кластера»,
43.«Проблема выбора смартфона»,
44. «Выбор КПК»,
45. «Поисковое проектирование файловых веб-сервисов»,
46. «Поисковое проектирование портативного ПК»,
47. «Оптимальный цифровой фотоаппарат»,
48.«Автоматизация удаленного промышленного объекта»,
49. «Проблема выбора оптимальной модели танка» (МГГУ,
кафедра САПР).
50.«Проблема выбора места работы», (МГГУ, кафедра САПР).
51.«Проблема выбора интернет провайдера», (МГГУ, кафедра
САПР).
44
ПРИЛОЖЕНИЕ 2. Форматы файлов решателя открытых задач
Таблица 8 — Структура файла базы знаний (NBZ).
<Npar>—число параметров базы знаний.
<Npar[1]>—число именных значений 1-го параметра.
…
<Npar[Npar]>—число именных значений Npar-го параметра.
< NTFact >—число удачных фактов.
<NTFact>—число неудачных фактов.
<Наименование 1-го параметра>
<1-е именное значение 1-го параметра>
<2-е именное значение 1-го параметра>
< Npar[1]-е имеенное значение 1-го параметра>
…
<Наименование Npar -го параметра>
<1-е именное значение Npar -го параметра>
<2-е именное значение Npar -го параметра>
< Npar[Npar]-е имеенное значение Npar -го параметра>
<Имя 1-го удачного факта>
<именное значение 1-го параметра 1-го удачного факта >
<именное значение 2-го параметра 1-го удачного факта >
…
<именное значение Npar -го параметра 1-го удачного факта >
….
<Имя NTFact -го удачного факта>
<именное значение 1-го параметра NTFact -го удачного факта >
<именное значение 2-го параметра NTFact -го удачного факта >
…
<именное значение Npar -го параметра NTFact -го удачного факта >
%
<Имя 1-го неудачного факта>
<именное значение 1-го параметра 1-го неудачного факта >
<именное значение 2-го параметра 1-го неудачного факта >
…
<именное значение Npar -го параметра 1-го неудачного факта >
….
<Имя NFFact -го неудачного факта>
<именное значение 1-го параметра NFFact -го неудачного факта >
<именное значение 2-го параметра NFFact -го неудачного факта >
…
<именное значение Npar -го параметра NFFact -го неудачного факта >
%
45
<Вес 1-го именного значения 1-го параметра>
…
<Вес Npar[1]-го именного значения 1-го параметра>
<Вес 1-го именного значения Npar -го параметра>
…
<Вес Npar[Npar]-го именного значения Npar -го параметра>
%
<1-е именное значение 1-й запрещенной комбинации>
<2-е именное значение 1-й запрещенной комбинации>
<3-е именное значение 1-й запрещенной комбинации>
<4-е именное значение 1-й запрещенной комбинации>
….
<1-е именное значение N-й запрещенной комбинации>
<2-е именное значение N-й запрещенной комбинации>
<3-е именное значение N-й запрещенной комбинации>
<4-е именное значение N-й запрещенной комбинации>
Таблица 9 — Формат файла параметров условного экстремума (math.usl)
….
Именное значение 1-го выбранного параметра
…
Именное значение n-го выбранного параметра
….
Таблица 10 — Формат файла пространства внутренних параметров
(math.par)
<Наименование 1-го параметра>
<1-е именное значение 1-го параметра>
<2-е именное значение 1-го параметра>
< Npar[1]-е имеенное значение 1-го параметра>
…
<Наименование Npar -го параметра>
<1-е именное значение Npar -го параметра>
<2-е именное значение Npar -го параметра>
< Npar[Npar]-е имеенное значение Npar -го параметра>
Таблица 11 — Формат файлов базы фактов (math.sot(удачные факты),
math.sof(неудачные факты))
<Имя 1-го удачного факта>
46
<именное значение 1-го параметра 1-го удачного факта >
<именное значение 2-го параметра 1-го удачного факта >
…
<именное значение Npar -го параметра 1-го удачного факта >
….
<Имя NTFact -го удачного факта>
<именное значение 1-го параметра NTFact -го удачного факта >
<именное значение 2-го параметра NTFact -го удачного факта >
…
<именное значение Npar -го параметра NTFact -го удачного факта >
%
<Имя 1-го неудачного факта>
<именное значение 1-го параметра 1-го неудачного факта >
<именное значение 2-го параметра 1-го неудачного факта >
…
<именное значение Npar -го параметра 1-го неудачного факта >
….
<Имя NFFact -го неудачного факта>
<именное значение 1-го параметра NFFact -го неудачного факта >
<именное значение 2-го параметра NFFact -го неудачного факта >
…
<именное значение Npar -го параметра NFFact -го неудачного факта >
Таблица 12 — Формат файлов экстремумов функции выбора(lok_max.txt,
lock_min.txt, usl_max.txt, usl_min.txt)
<именное значение 1-го параметра 1-го экстреума >
<именное значение 2-го параметра 1-го экстреума >
…
<именное значение Npar -го параметра 1-го экстреума >
….
<именное значение 1-го параметра NTFact -го экстреума >
<именное значение 2-го параметра NTFact -го экстреума >
…
<именное значение Npar -го параметра NTFact -го экстреума>
%
47
СОДЕРЖАНИЕ
ВВЕДЕНИЕ……………………………………………………………………
1. ТЕХНОЛОГИЯ ПОИСКОВОГО ПРОЕКТИРОВАНИЯ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ……………………………………….
1.1 Укрупнённая технологическая схема……………………………
1.2 Решатель открытых задач как основной инструмент формирования
эмпирического знания на основе выдвижения ГИПОТЕЗ6
1.3 Особенности реализации пользовательского интерфейса
1.4 Унификация взаимодействия решателя с блоком качественной
оценки гипотез
.2. БЛОК КАЧЕСТВЕННОЙ ОЦЕНКИ (БКО) И ВОЗМОЖНЫЕ
СПОСОБЫ ЕГО РЕАЛИЗАЦИИ
2. 1
Простейший способ реализации правил выбора
2. 2
Реализация правил выбора на основе маскирования параметров
2..3
Способ расчета показателей качества сформированных гипотез
на основе сравнения с эталонной гипотезой
2.4. БКО на основе имитационного моделирования
3.
РЕАЛИЗАЦИЯ АВТОМАТИЧЕСКОГО ВЗАИМОДЕЙСТВИЯ
РЕШАТЕЛЯ С БЛОКОМ КАЧЕСТВЕННОЙ ОЦЕНКИ ГИПОТЕЗ
3.1.Программная реализация блока качественной оценки
3.2.Список экспортируемых функций
3.3.Форма выбора гипотез для последующей оценки
3..4.
Структура базовых классов решателя открытых задач
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ 1. Форматы файлов решателя открытых задач
ПРИЛОЖЕНИЕ 2. Перечень тем курсовых работ, выполненных с
применением решателя в режиме автоматического взаимодействия с БКО
48
Учебное издание
Дзегеленок Игорь Игоревич,
Кондратьев Михаил Алексеевич,
Аляева Юлия Владимировна
ПРИМЕНЕНИЕ РЕШАТЕЛЯ ОТКРЫТЫХ ЗАДАЧ
Методические указания по курсу
«Поисковое проектирование вычислительных систем»
Редактор издательства
_________________________________________________________________
Темплан издания МЭИ
Подписано в печать
Печать офсетная. Формат
.Физ. печ. л. Тираж
Изд. № Заказ
_______________________________________________________________
Издательство МЭИ, 111250, Москва, Красноказарменная ул., д.14
Отпечатано в типографии
Московский энергетический институт
(технический университет)
49
Документ
Категория
Компьютеры, Программирование
Просмотров
195
Размер файла
1 454 Кб
Теги
выполнения, учебно, пособие
1/--страниц
Пожаловаться на содержимое документа