Разработка алгоритма управления процессом адаптации нечетких проектных метаданных
Выбор алгоритма, решающий задачу Штейнера большой размерности с низкой погрешностью за приемлемое время. Сущность треугольной и трапецеидальной функция принадлежности. Корректировка параметров функции принадлежности. Разработка автомата адаптации.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 29.05.2017 |
Размер файла | 157,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Разработка алгоритма управления процессом адаптации нечетких проектных метаданных
Н.Н. Венцов
г. Ростов-на-Дону
Описание проблемной области. В качестве примера рассмотрим запрос, сформулированный на естественном языке: «Выбрать алгоритмы, решающие задачу Штейнера большой размерности с низкой погрешностью за приемлемое время». В данном запросе фигурируют одно четкое высказывание «алгоритмы, решающие задачу Штейнера» и три нечетких высказывания: «большой размерности», «с низкой погрешностью», «за приемлемое время». Четкое высказывание «алгоритмы, решающие задачу Штейнера» однозначно описывает интересующее множество алгоритмов. В свою очередь нечеткие высказывания: «большой размерности», «с низкой погрешностью», «за приемлемое время» подразумевают наличие некоторой функции принадлежности, численно характеризующей степень принадлежности, элемента к соответствующему не четкому множеству.
В случае конечного множества аргументов функция принадлежности может быть задана перечислением т.е. непосредственным указанием для каждого элемента его степени принадлежности нечеткому множеству. В качестве примера зададим нечеткую переменную «приемлемое время», определим область рассуждений переменной «приемлемое время» тремя характеристиками сложности алгоритма: линейная, полиномиальная, экспоненциальная. Принадлежность каждого элемента области рассуждений нечеткому множеству «приемлемое время» определим перечислением С={0.98/линейная,0.5/полиномиальная, 0.03/экспоненциальная}.
В случае непрерывной (бесконечной) области определения, функция принадлежности чаще всего принимает треугольный или трапецеидальный вид. Треугольная функция принадлежности задается тройкой чисел (a, b, c), и ее значение в точке x вычисляется согласно выражению:
(1)
Аналогично задание трапецеидальной функции принадлежности осуществляется четверкой чисел (a, b, c, d):
(2)
Так как треугольная функция является частным случаем трапецеидальной, рассмотрим последнею в качестве примера (рис.1)
Рис. 1 Пример трапецеидальной функции принадлежности
На рис. 1 приведена функция принадлежности заданная кортежем (0, 2, 4, 6). В качестве аргументов функций (1)-(2) выступают некоторые численные характеристики объекта, для которого необходимо определить степень принадлежности к нечеткому множеству.
Высказывания «с низкой погрешностью» и «за приемлемое время»динамически стабильны в том плане что в ближайшей перспективе погрешность алгоритма равная 0,05 скорее всего будет считаться низкой, а полиномиальная временная сложность - приемлемой. Подобные рассуждения неприменимы к выражению «большой размерности» так как число элементов в проектируемых СБИС постоянно увеличивается (Гордон Мур высказал предположение, согласно которому число транзисторов на кристалле будет удваиваться каждые 24 месяца). Пусть логическая переменная «размерность задачи» принимает два значения «не большая» и «большая». Параметры функции принадлежности для каждого значения логической переменной определим кортежами: «не большая» (0,0,102,105) и «большая» (103,108,1010,1010). Графики функций принадлежности приведены на рис. 2.
Рис. 2 Графики трапецеидальных функций принадлежности
На рис. 2 численные характеристики размерностей задач откладываются по оси абсцисс как показатели степени с основанием 10, а по оси ординат степени принадлежности задач указанной размерности к значениям «не большая» и «большая» логической переменной «размерность задачи».
Логично предположить что с течением времени параметры функции принадлежности логической переменной «размерность задачи» будут увеличиваться и данные изменения необходимо адекватно отражать. В подобных ситуациях целесообразно корректировать вершины трапеции на основе решений принимаемых экспертом-проектировщиком (ЭП) в схожих ситуациях. Для этих целей необходимо разработать систему поддержки принятия решений (СППР), например аналогичную по структуре представленной в [1].
Постановка задачи. Необходимо разработать алгоритм, позволяющий адаптивно корректировать параметры функции принадлежности. Корректировку параметров функции принадлежности предлагается осуществлять на основе анализа реакции ЭП на результаты запросов.
Предполагается, что взаимодействие ЭП и СППР состоит в следующем:
ЭП генерирует нечеткий запрос.
В качестве результата выполнения запроса система возвращает ЭП множество потенциальных решений.
Если ЭП находит необходимое решение во множестве потенциальных решений - СППР приступает к анализу действий эксперта. Если же эксперт не находит требуемый ответ он может задать параметры запроса «вручную».
Логично предположить что СППР должна функционировать таким образом чтобы минимизировать необходимость «ручной» генерации запросов. По этой причине для повышения эффективности функционирования СППР необходимо разработать методы корректировки нечетких проектных метаданных (параметров функций принадлежности) хранимых в базе данных (БД) на основе анализа действий ЭП.
Предлагаемый подход основывается на корректировке параметров функции принадлежности. Решение x, хранящееся в БД, попадает во множество потенциальных решений только в том случае если , где индекс соответствия решения x нечеткому высказыванию а, - минимальный индекс соответствия. Таким образом, для любого решения x из множества потенциальных решений X справедливо:
Из множества потенциальных решений X для дальнейшего анализа эксперт выбирает подмножество . Если выполняется условие:
,
принадлежность алгоритм штейнер
где логично предположить что необходимо скорректировать параметры функции принадлежности таким образом, чтобы несколько увеличить.
Для управления процессом корректировки нечетких данных разработан автомат адаптации (АА) схема которого приведена на рис. 4 [2,3]. Предлагаемый АА поддерживает две альтернативы A1 и A2. Состояние S11 - соответствует альтернативе A1, а состояния S21 - S23 альтернативе A2.
Размещено на http://www.allbest.ru/
Рис. 4 Схема предлагаемого АА
Альтернатива A1 заключается в необходимости корректировать параметры функции принадлежности, а альтернатива A2 подразумевает неизменность параметров функции принадлежности. Схема выработки управляющих сигналов поощрения (+) и наказания (-) АА представлена в таблице.
Таблица Управляющие сигналы
Отклик Альтернатива |
|||
A1 |
+ |
- |
|
A2 |
- |
+ |
Данный подход позволяет увеличивать степень принадлежности потенциальных решений на основе субъективных, последовательных мнений экспертов. При этом наличие механизма адаптации позволяет снижать влияние разовых, выпадающих из общей концепции, мнений.
Литература
1. Бова В.В., Гладков Л.А., Кравченко Ю.А., Курейчик В.В., Курейчик В.М., Марков В.В., Нужное Е.В., Родзин С.И., Рогозов Ю.И., Свиридов А.С., Щеглов С.Н. Адаптивные и бионические методы и интеллектуальном анализе данных. - Таганрог: Изд-во ТТИ ЮФУ, 2010. - 109 с.
2. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. -Таганрог: Изд-во ТРТУ, 2000.
3. Лебедев Б.К. Адаптация в САПР. Монография. Таганрог: Изд-во ТРТУ, 1999.
Размещено на Allbest.ru
Подобные документы
Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Целевая функция с определенным направлением экстремума и система ограничений для нее. Разработка алгоритма программы, ее листинг.
курсовая работа [385,6 K], добавлен 15.05.2014Общее понятие графа, его виды и сущность вершинного покрытия. Написание точного алгоритма решения задачи о надежности сети, нахождение минимального покрытия. Реализация данного алгоритма на языке TurboC++. Код программы, решающий поставленную задачу.
курсовая работа [1,3 M], добавлен 27.06.2014Анализ функции и разработка алгоритма по ее вычислению. Программирование отдельных блоков и структур алгоритма. Структура Паскаль-программы. Раздел описаний, подпрограммы, тело программы. Полная Паскаль-программа в соответствии с разработанным алгоритмом.
курсовая работа [241,8 K], добавлен 30.01.2016Состав и принцип работы аппаратуры. Выбор параметров корреляционного анализа и Фурье-анализа. Разработка и применение алгоритма корреляционного анализа. Реализация алгоритма Фурье-анализа на языке С++ и алгоритма корреляционного анализа на языке С#.
дипломная работа [4,6 M], добавлен 30.11.2016Анализ заданной сложной функции и разработка структурной схемы алгоритма по её вычислению. Программирование отдельных блоков и структур алгоритма решаемой задачи на языке Паскаль. Полная программа в соответствии с алгоритмом. Результаты расчётов на ПК.
курсовая работа [59,2 K], добавлен 09.04.2012Описание алгоритма работы и разработка структурной схемы МКС. Схема вывода аналогового управляющего сигнала, подключения ЖК-дисплея, клавиатуры и аварийного датчика. Разработка блок-схемы алгоритма главной программы работы МКС. Функция инициализации.
курсовая работа [5,7 M], добавлен 26.06.2016Разработка структурной схемы вычислительного устройства, выбор системы команд и определение форматов. Разработка алгоритма командного цикла, выполнения арифметических и логических операций. Проектирование операционного автомата, устройств управления.
курсовая работа [2,8 M], добавлен 15.05.2014Обучение нейросимулятора определению видовой принадлежности грибов по их заданным внешним признакам с применением алгоритма обратного распространения ошибки. Зависимость погрешностей обучения и обобщения от числа нейронов внутреннего слоя персептрона.
презентация [728,2 K], добавлен 14.08.2013Разработка линейной программы на языке С++. Разработка программ с разветвленной структурой. Составление по заданному варианту схемы алгоритма и программы вычисления тригонометрической функции с абсолютной погрешностью с использованием разложения в ряд.
лабораторная работа [1,2 M], добавлен 12.01.2011