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

Э.В. Лазарсон,

проф., к.т.н., svarka@pstu.ru

ПГТУ, г. Пермь

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

Tables of conformity are used for the problems simulation in computer- aided design. Possible variants of solutions searching were analyzed by such tables

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

Сущность формы таблицы соответствий (ТС), предложенной Г.К. Горанским [1], можно пояснить на примере табличной модели, взятой из работы [2] (табл.1).

Таблица 1

Типичный вид и структура таблицы соответствий

Y	X1			X2					X3				X4
	1	2	3	1	2	3	4	5	1	2	3	4	1	2	3	4
Решение 1 – Y1	1	1	1		1	1			1	1	1		1	1	1	1
Решение 2 – Y2	1			1	1	1	1		1	1	1	1	1	1	1	1
Решение 3 – Y3	1	1	1			1	1	1				1	1
Решение 4 – Y4	1	1						1			1	1		1
Y={ Y1, Y2, Y3, Y4} – вектор выходных параметров X={X1,X2, X3, X4} – вектор входных параметров Значения входных параметров условно обозначены цифрами 1,2,…,n

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

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

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

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

Проблема оказалась настолько серьезной, что потребовало проведения специальных исследований. В результате были разработаны методы и приемы преодоления неоднозначности решений, генерируемых табличными моделями [2]. В частности, автором предложен новый тип моделей – таблицы соответствий со степенями принадлежности (μ_А), введенными в теории нечетких множеств [3]. Это означает отказ от указания соответствий бинарными значениями нулевой функции (1-соответствие имеется, 0-соответствия нет) и переход к использованию любых значений μ_А в интервале от нуля до единицы.

В табл.2 показано, какой вид приняла предыдущая табличная модель после указания в ней соответствий степенями принадлежности. Значения μ_А были определены по построенным графикам функций принадлежности для факторов X₂ и X₃ и по результатам бинарных сравнений по столбцам таблицы (подробности можно найти в работе [2]).

В случае использования ТС предложенного вида необходимо определиться с методикой поиска по ним оптимального решения. Непосредственный визуальный анализ таблиц исключается из-за множественности вариантов и отсутствия правила предпочтения. Также неприемлем анализ вариантов решений путем построения минимизированных граф-схем алгоритмов [1], поскольку такие схемы удается построить только для небольших по размерам моделей.

Таблица 2

Таблица соответствий со степенями принадлежности

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

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

Сначала в исходной таблице оставим только столбцы, соответствующие элементам заданного условия, остальные исключим как ненужные. Затем исключим все строки, содержащие нулевые решения. Результаты этих преобразований показаны на рис.1. Таким образом, оптимальное решение задачи предстоит находить по данным нормализованной частичной таблицы (рис.1б), размеры которой многократно меньше, чем исходной ТС (матрица 4x3 против 16x4).

а) б)

рис.1 Частичные таблицы: а – после исключения ненужных столбцов;

б – после исключения строки с нулевым решением

Обзор литературы показал существование двух подходов к поиску оптимальных решений по ТС со степенями принадлежности. Согласно принципу обобщения Л.Заде множество выходных параметров Y можно рассматривать как некоторое нечеткое множество В, функция принадлежности которого μ_В(Y) связана с функцией принадлежности μ_А(X) множества A(X) входных параметров через максимальный критерий [3]

(1)

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

Другой подход к поиску оптимального решения предложил автор теории таблиц соответствий Г.К. Горанский, который ввел понятие о баллах эффективности, близких к понятию степени принадлежности [4]. Средний балл эффективности q_уj^ср подсчитывается по сторонам для каждого j-го решения в ТС по формуле:

(2)

Здесь в числителе сумма всех степеней принадлежности μ_А(X)>0 в j-ой строке, n – количество указанных степеней.

Оптимальному решению будет соответствовать максимальное значение q_у^ср.

Результаты расчета вышеуказанных критериев оптимальности по формулам 1 и 2 применительно к данным таблицы рис.1б показаны в столбцах 6 и 7 табл.3. Дополнительно в столбце 8 приведены подсчитанные нами значения произведений степеней принадлежности, также по строкам:

(3)

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

Как видно из таблицы, расчеты по методикам Л. Заде и Г.К. Горанского привели к разным результатам – оптимальными признаны соответственно решения Y₃ и Y₁. По нашему мнению методика Л.Заде, ориентированная только на минимальные значения μ_А(X) по строкам, не учитывает остальные значения и с этой точки зрения методика Г.К. Горанского представляется более предпочтительной.

Таблица 3

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

Y	X12	X25	X33	X43	μВ(Y)	qуj^ср	П(μj(Xi))
1	2	3	4	5	6	7	8
Y1	1	0,1	0,8	1	0,1	0,97	0,080
Y2	0,2	0,3	1	1	0,2	0,83	0,060
Y3	1	0,8	0,4	0,1	0,4	0,77	0,032

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

Литература

1. Автоматизированные системы технологической подготовки производства в машиностроении / под. ред. Г.К. Горанского. – М.: Машиностроение, 1976. – 240с.

2. Лазарсон Э.В. Теория и методы решения многовариантных неформализованных задач выбора (с примерами из области сварки). – Пермь: Изд-во Перм. гос. техн. ун-та, 2008. – 270с.

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

4. Горанский Г.К. Методика разработки и оптимизации таблиц решений для автоматизированного проектирования в АС ТПП // Применение вычислительной техники и других средств автоматизации проектирования. Вып.4. – Минск: БелНИИНТИ, 1989. – 59с.