Решение многокритериальных задач синтеза с использованием логико-комбинаторного подхода

Размещено на http://www.allbest.ru/

Санкт-Петербургский горный университет

Решение многокритериальных задач синтеза с использованием логико-комбинаторного подхода

Белозеров А.Л. аспирант

Аннотация

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

Ключевые слова: логико-комбинаторный подход, иерархический морфологический подход, взвешенное степенное среднее.

Abstract

The paper deals with the synthesis of multiobjective structural problems, in which the formation of a set of possible solutions is based on the logic-combinatorial approach. Plenty of options given in the framework of the paradigm of the ontological engineering and hierarchical morphological approach - a system of logical equations at two levels: at the level of the basic functions on the level instances of the basic functions. The objective function is formed as a convolution of particular indicators based on the weighted average power. We present the basic algorithm to minimize additive solutions with performance on special bracket form.

Keywords: logical-combinatorial approach, hierarchical morphological approach, the average weighted degree.

В статье рассматривается решение многокритериальных задач структурного синтеза (дискретного программирования), в которых формирование множества возможных решений осуществляется на основе логико-комбинаторного подхода (ЛКП) [1, 3, 5]. Под многокритериальным синтезом понимают формирование множества альтернативных вариантов структуры синтезируемого объекта, так и выбор оптимального варианта структуры. В задачах управления и проектирования синтезируемый объект рассматривается как система, взаимодействующая с внешней средой (надсистемой), причем под структурой системы обычно понимают состав элементов и подсистем рассматриваемой системы, закрепление определенных функций за элементами и подсистемами, а также организацию связей и отношений между подсистемами, элементами и внешней средой. Множество вариантов задается в рамках парадигмы онтологического инжиниринга и иерархического морфологического подхода (ИМП) - системой логических уравнений на двух уровнях: на уровне базовых функций и на уровне экземпляров базовых функций. Целевая функция формируется как свертка частных показателей на основе взвешенного степенного среднего (ВСС) [4,6].

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

Предполагаем, что синтезируемый объект характеризуется составом базовых функций (БФ). Если имеется один вариант состава БФ, то множество возможных решений задается классической МТ. Например, в задаче синтеза системного блока ПЭВМ, состоящего из системного блока (SysBloc), корпуса (Korp), блока питания (BlocPit) и материнской платы (MatPlata), включающей процессор (Proc) и оперативную память (OpMem), множество V возможных решений задается различными вариантами реализации четырех базовых функций Korp, BlocPit, Proc и OpMem. В общем случае m базовых функций, это множество задается декартовым произведением:

(1)

где - множество вариантов реализации (экземпляров) j-й базовой функции, - элемент, реализующий k-й вариант базовой функции j. Каждый вариант - . В еще более общем случае, когда множество V задается в виде ОСФ, а структурные варианты могут различаться составом базовых функций, мы вводим функцию , отображающую множество элементов Z в множество базовых функций F.

Целевая функция основана на n показателях , причем показатели являются аддитивными, а показатель - максиминным. Аддитивные показатели - это минимизируемые показатели (стоимость, масса, интенсивность отказов и т.д.). Значение i -го аддитивного показателя для варианта вычисляется по формуле

(2)

где - значение i -го аддитивного показателя элемента .

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

В качестве целевой функции, характеризующей технико-экономическое совершенство синтезируемого объекта, мы используем максимизируемую на V свертку в форме ВСС [4,7]:

(3)

где y_i - нормированное значение и - вес i-го показателя, r - степень ВСС. Смысл использования (3) в качестве максимизируемой целевой функции основан в том, что при . Благодаря этому, при значениях >1, мы отдаем предпочтение, и в тем большей степени, чем больше , вариантам , которые имеют наилучшее значение наихудшего показателя (максимин). Тем самым обеспечивается гармонизация [2] показателей синтезируемого объекта.

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

(4)

где вычисляется по формуле (2).

Нормированный максиминный показатель для каждого варианта получается взятием минимума

(5)

где - нормированное значение максиминного показателя элемента . Если -максимизируемый показатель, то вычисляется по формуле

(6)

где - целевое значение для j-й БФ. Если среди показателей , имеются минимизируемые, то вместо (6) следует использовать формулу

В базовом алгоритме минимизации на ОСФ, а именно, реализуется поиск варианта , доставляющего

(7)

для n нормированных аддитивных показателей , где - выбираемые пользователем весовые коэффициенты, причем . Пользователь использует эти весовые коэффициенты для того, чтобы найти наилучшую точку на выпуклой оболочке множества Парето. Дополнительное обоснование можно найти в [5, 8].

Базовый алгоритм программы основан на том, что вычисление нормированных значений для минимизируемых аддитивных показателей , используемых в формуле (7), выполняется по формуле:

(8)

Очевидно, что для

(9)

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

(10)

Минимизацию правой части выражения можно заменить минимизацией

(11)

(12)

- это аддитивный вклад элемента в целевую функцию (7) по всем показателям с учетом весовых коэффициентов . Остается получить формулу для , т.е. для максиминных показателей.

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

(13)

Где , или на минимизацию суммы

(14)

где - это нормированный аддитивный вклад минимаксного показателя в целевую функцию (7):

(15)

Таким образом, представление множества возможных решений V в виде ОСФ1 или ОСФ2 [3, 5] позволяет найти глобальный минимум и некоторое подмножество V_s субоптимальных решений для (7) за счет отбора в каждой дизъюнкции элементов , обеспечивающих локальный минимум и близкие к нему значения. Оптимальное решение относительно целевой функции (3) получается путем подбора пользователем весовых коэффициентов и перебора на подмножестве V_s. Практический пример применения решения будет рассмотрен в следующей статье.

комбинаторный многокритериальный уравнение логический

Список литературы / References

1. Анкудинов Г.И. Об одном общем подходе к свертыванию частных критериев эффективности // Автоматизированные системы управления.- Л.: ЛГУ, 1974.- Вып.1.- С.39-41.

2. Богданов А.А. Тектология: Всеобщая организационная наука.- М.: Финансы, 2003.- 496 с.

3. Анкудинов Г.И. Синтез структуры сложных объектов.- Л.: ЛГУ, 1986.- 260 с.

4. Анкудинов Г.И., Анкудинов И.Г. Нелинейная свертка частных критериев на основе интервальных оценок // Материалы научной конференции. Часть 1.- СПб.: СЗТУ, 2003.- С. 136-139.

5. Анкудинов И.Г. Автоматизация структурного синтеза и принятия решений в управлении и проектировании.- СПб.: Изд-во Политехн. ун-та, 2008.- 202 с.

6. Анкудинов Г.И, Анкудинов И.Г. Гармонизация иерархий на основе взвешенного степенного среднего // «Управление развитием крупномасштабных систем (MLSD'2012)». VI международная конференция, 1-3 октября 2012 г., Москва. - Материалы: в 2-х т.- 1 т.- С. 139.

7. Анкудинов Г.И, Анкудинов И.Г. Мультикритериальный выбор решений на основе предельных уступок и коэффициентов замещения показателей // Записки Горного института, СПб, 2014, Т. 208. С. 208-215.

8. Ногин В.Д. Принятие решений при многих критериях. Учебно-методическое пособие.- СПб. Издательство «ЮТАС», 2007. - 104 с.

9. Рябов О. Н. Модели и методы автоматизированного синтеза сборочных комплексов модульной структуры для приборостроения: автореф дис. канд. технических наук ГОУ ВПО «Саратовский государственный технический университет», Саратов, 2006.

Размещено на Allbest.ru