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

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

12 3

Ю.О. Чернышев , Н.Н. Венцов , П.А. Панасенко

1 Филиал военной академии связи, Краснодар 2Донской государственный технический университет, Ростов-на-Дону 3 Филиал военной академии связи, Краснодар

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

Введение

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

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

На основании выше изложенного, актуальной задачей исследования является разработка адаптивных алгоритмов оценки соответствия текущих решений оптимизационных задач нечетким ограничениям. Одним из направлений решения данной проблемы является разработка эволюционных алгоритмов, например, искусственных иммунных систем [5,6,8,9]. Способы адаптивного задания нечетких команд на основе лингвистических переменных приведены в работах [10-12].

Постановка задачи адаптивной формализации нечетких требований

Известно, что формализовать требования одного эксперта можно при помощи функции принадлежности ¿(х), описывающей степень соответствия аргумента функции х некоторому условию [4]. Если в качестве оценки размера схемы взять длину ее полупериметра Ь, то функция ¿г^Ь) описывает допустимость создания схемы с длиной полупериметра Ь по мнению 1-го эксперта, а да(Ь) - недопустимость. Каждому эксперту достаточно задать одну из функций ¿г^Ь) или да(Ь).

Тогда обобщенную функцию ¿г, описывающую целесообразность создания схемы с длиной полупериметра Ь, по мнению всех экспертов можно получить при помощи операторов конъюнкции или дизъюнкции: т.е. ¿г(Ь)=&мг^Ь) или juг(Ь)=v¿гi(Ь). Аналогично рассуждая можно получить различные варианты функции ¿г.

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

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

щЪ)

0,35 0,4 0,45 0.5 '."'.5? 0.6 0,65 '."'.7 '."'.7? 0,3 0,35 0,9 0,95 1 1,05 Д пЖ

Рис. 1. - Исходные графики принадлежности длины полупериметра Х к разрешающему и запрещающему правилу Из данных представленных на рис.1 следует, что графики функций гХ(Х) и гХ(Х) пересекаются на отрезках [0,45;0,5] и [0,8;0,85]. Точки Х=0,5 и Х=0,8 принадлежат отрезку, на котором разрешающее правило доминирует над запрещающим, а точки Х=0,45 и Х=0,85 принадлежат отрезкам, на которых запрещающие правило доминирует над разрешающим. Поэтому

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

Импликации по Райхенбаху определяются на основе формулы [13]:

цЯ

где хуе [0,1].

На рис. 2 приведен график, полученный в результате вычисления /1Щрг(Ь),рг(Ь)), т.е. график зависимости обобщенной степени принадлежности, полученной в результате импликации запрещающего правила в разрешающее, на основе логики Райхенбаха, от длины полупериметра Ь.

¿¿й 1 0,3 0.6 0.4 0,2

0 Н-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1

[Л ГГ [Л 1/, I/. 1 [Л г- I/. со '-т' [Л т

«• о т о о !" о о Л Д, пт

о о с. с. с. о о

Рис. 2. - График изменения степени принадлежности, от длины

полупериметра Ь, полученный в результате применения операции

цШу2Ь

Из рис. 1,2 и формулы (1) следует, что равенство ^Я(^2(Ь),^г(Ь))=1 истинно в точках Ь=0,6 и Ь=0,65, так как ^г(0,6)=0 и ^г(0,65)=0, а в точке Ь=0,7, так как ^г(0,7)=1.

В точке Ь=0,5 значения функций равны ^г(0,5)=0,3, ^г(0,5)=0,25, ^Я(^(0,5),^г(0,5))=0,825, а в точке Ь=0,8 - ^г(0,8)=0,78, М0,8)=0,71, ^Я(М0,8)М0,8))=0,842.

В точке Ь=0,45 значения функций равны ¡г(0,45)=0,2 ¡г(0,45)=0,5

а в точке ¿=0,85 ¡г(0,85)=0,5, ¡¿(0,85)=0,75,

¡Я(М0,85),^г(0,85))=0,62.

Наименьшие значения функции ¡К(^(Ь),^г(Ь)) совпадают с границами анализируемой области определения. Значения функции в граничных точках ¿=0,35 и ¿=1,05 соответственно равны ¡Я(^1(0,35),^г(0,35))=0,24 и ^Д(М1,05)М1,05))=0,17.

Максимумы функции ^(¡1(Ь),^г(Ь)) являются признаками доминирования разрешающих факторов гЬ(Ь) над запрещающими факторами гЬ(Ь) Минимумы функции ¡иК(^(Ь), ¡.1г(Ь)) соответствуют доминированию запрещающих факторов ^Ь(Ь), над разрешающими гЬ(Ь).

На рис. 3 приведен график, полученный в результате вычисления ¡¡Я(^г(Ь) ¡(Ь)) т.е. график зависимости обобщенной степени принадлежности, полученной в результате импликации разрешающего правила в запрещающее на основе логики Райхенбаха, от длины полупериметра Ь.

¿¿й 1

0,6 0,4 0,2

О Н-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1

[/ т [/ [/ [Л т !- т сэ ь". т г „мл

Ч =.' =.' -'. =.' г"": с. о пт

.-. .-. .-,

Рис. 3. - График изменения степени принадлежности, от длины полупериметра Ь, полученный в результате применения операции

¡К

Из рис. 1,3 и формулы (1) следует, что значения функций ^Я(^г(Ь),^г(Ь)) минимальны в точках Ь=0,65 и Ь=0,7 и равны соответственно

^Я>г(0,65),М0,65))=0,11 и ^Я(М0,7),М0,7))=0,12 .

В точке Ь=0,5 значения функций равны ^г(0,5)=0,3, ^г(0,5)=0,25, ^Я(^г(0,5),^г(0,5))=0,775, а в точке Ь=0,8 - ^г(0,8)=0,78, ^(0,8)=0,71, ^Я>(0,8),М0,8))=0,779.

В точке Ь=0,45 значения функций равны ^г(0,45)=0,2, ^г(0,45)=0,5, ^Я>г(0,45), ^(0,45))=0,9, а в точке Ь=0,85 - ^г(0,85)=0,5, ^(0,85)=0,75,

^Я>(0,85), М0,85))=0,875.

Наибольшие значения функции ^Я(^г(Ь),^г(Ь)) соответствуют границам анализируемой области определения. Значения функции в граничных точках Ь=0,35 и Ь=1,05 соответственно равны

^Я>(0,35),М0,35))=0,99 и ^Я(М1,05),М1,05))=0,993.

Максимумы функции ^Я(^г(Ь),^г(Ь)) являются признаками доминирования запрещающих факторов гЬ(Ь) над разрешающими гЬ(Ь). Минимумы функции ^Я(^г(Ь),^г(Ь)) соответствуют доминированию разрешающих факторов гЬ(Ь) над запрещающими гЬ(Ь).

Импликация по Лукасевичу ^Ь определяется на основе формулы [13]:

^Ь

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

Рис. 4. - График изменения степени принадлежности, от длины

полупериметра Ь, полученный в результате применения операции

/лЬ

Из рис.1,4 и формулы 2 следует, что в случае, если ¡л(Ь)<^г(Ь), то ¡лЬ(^2(Ь),^г(Ь))=1, т.е. если принадлежность решения к запрещающему множеству меньше, чем к разрешающему, то ^Ь(^г(Ь),^г(Ь))=1. В точках Ь=0,5 цЬ(0,5)=1, а также в точке Ь=0,85 - ^Ь(0,85)=1.

Наименьшие значения функции ¡иЬ(^2(Ь),^г(Ь)) совпадают с границами анализируемой области определения. Значения функции в граничных точках Ь=0,35 и Ь=1,05 соответственно равны ^(^(0,35), ^г(0,35))=0,25 и

цЦМ1,05),М1,05))=0,18.

Максимумы функции ¡иЬ(^2(Ь),^г(Ь)) являются признаками доминирования разрешающих факторов гЬ(Ь) над запрещающими факторами гЬ(Ь). Минимумы функции ¡иЬ(^2(Ь),^г(Ь)) соответствуют доминированию запрещающих факторов гЬ(Ь), над разрешающими гЬ(Ь).

На рис. 5 приведен график, полученный в результате вычисления ¡иЬ(гЬ(Ь)^Ь(Ь)). т.е. график зависимости обобщенной степени принадлежности, полученной в результате импликации разрешающего правила в запрещающее на основе логики Лукасевича, от длины полупериметра Ь.

Рис. 5. - График изменения степени принадлежности, от длины полупериметра Ь, полученный в результате применения операции

1лЬ

Из рис. 1,5 и формулы (1) следует, что значения функций ¡иЬ(^г(Ь),^2(Ь)) минимальны в точках Ь=0,65 и Ь= 0,7 и равны соответственно ^Я(^г(0,65),М0,65))=0,11 и ^Я(^г(0,7),М0,7))=0,12 .

В точке Ь=0,5 значения функций равны ^г(0,5)=0,3, ^г(0,5)=0,25, ^Ь(^г(0,5),М0,5))=0,95, а в точке Ь=0,8 - ^г(0,8)=0,78, ^г(0,8)=0,71, ^Ь(^г(0,8),^г(0,8))=0,94.

В точке Ь=0,45 значения функций равны ^г(0,45)=0,2, ^г(0,45)=0,5, ^Ь(^г(0,45),^г(0,45))=1, а в точке Ь=0,85 - ^г(0,85)=0,5, ^(0,85)=0,75, ^Ь(^г(0,85),^г(0,85))=1.

Наибольшие значения функции ¡иЬ(^г(Ь),^2(Ь)) соответствуют границам анализируемой области определения. Значения функций в граничных точках Ь=0,35 - ^Ь(^г(0,35),^г(0,35))=1 и Ь=1,05 ^Ь>(1,05),М1,05))=1.

Заключение

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

Сопоставив графики импликаций wR(wz(L),^r(L)) и juL(wz(L),Wr(L)), можно утверждать, что график juR(wz(L),wr(L)) формирует меньшую область полностью допустимых решений, для которых jwL(wz(L),wr(L))=1, по сравнению с wL(wz(L),wr(L)). Из тестового примера следует что juR(wz(L),wr(L))=1 в точках, для которых wz(L)=0 или wr(L)=1. Функция wL(wz(L),wr(L))=1 в случае, если wz(L)<wr(L). Поэтому в соответствии с изложенным можно утверждать, что при проектировании систем повышенной надежности (точности) целесообразнее использовать функцию juR(wz(L),wr(L)) по сравнению с функцией jwL(wz(L),wr(L)). Импликацию juL(wz(L),wr(L)) целесообразнее использовать при проектировании подсистем, выполняющих второстепенные функции, не являющихся системно образующими и т. д.

Благодарность

Работа выполнена при финансовой поддержке РФФИ - проекты № 1301-00343 и 15-01-05129.

Литература

1. Литвиненко В. А. Адаптивные алгоритмы проектных операций САПР ЭВА // IS-IT'14: тр. Междунар. конгр. по интеллект. системам и информ. технологиям, п. Дивноморское, 2 -9 сент./ ЮФУ. М.: Физматлит, 2014. Т.1, С. 113-119.

2. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. Таганрог: Издательство ТРТУ, 2003. 108 с.

3. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009. 1024 p.

4. Малышев Н.Г., Берштейн Л.С., Боженюк А.В. Нечеткие модели для экспертных систем в САПР. М.: Энергоатомиздат, 1991. 136 с.

5. Dasgupta, D. "Information Processing in the Immune System", New Ideas in Optimization, (Eds.) D. Corne, M. Dorigo & F. Glover, McGraw Hill, London, 1999. pp. 161-165.

6. Calenbuhr V., Bersini Я., Varela F.J., Stewart J. The impact of the structure of the connectivity matrix on the dynamics of a simple model for the immune network // Proc. 1st Copenhagen Symp. on Computer Simulation in Biology, Ecology and Medicine (Ed. E.Mosekilde). 1993. pp. 41-45.

7. Остроух Е.Н. , Золотарева Л.И., Бычков А.А., Долгов В.В. Векторная оптимизация перерабатывающих процессов с учетом сырьевого дефицита // Фундаментальные исследования. 2011. №12-1. С. 224-227.

8. Чернышев Ю.О., Венцов Н.Н., Мухтаров С.А. Применение логик Лукасевича и Заде при реализации метода отрицательного отбора // Известия ЮФУ. Технические науки. 2013. №7 (144). С. 91 -77.

9. Венцов Н.Н. Эволюционный подход к моделированию распределительных процессов// Инженерный вестник Дона, 2013, №4 URL: ivdon.ru/magazine/archive/n4y2013/1886.

10. Венцов Н.Н. Разработка алгоритма управления процессом адаптации нечетких проектных метаданных// Инженерный вестник Дона, 2012, №1 URL: ivdon.ru/ru/magazine/archive/n1y2012/630.

11. Чернышев Ю.О., Венцов НН., Мухтаров С.А. К вопросу об интеллектуальной поддержке процесса доводки СБИС// Известия ЮФУ. Технические науки. 2012. № 7 (132). С. 63-69.

12. Чернышев Ю.О., Венцов НН., Мухтаров С.А. Разработка алгоритма интеллектуальной поддержки улучшения промежуточных решений оптимизационных задач// Вестник ДГТУ. 2012. № 5 (56). С. 68-76.

13. Берштейн Л.С., Боженюк А.В. Анализ использования оператора импликации в нечетком правиле вывода по аналогии// Известия ТРТУ. Технические науки. 2004. № 3 (38). С. 5 -10.

14. Нечеткие множества в моделях управления и искусственного интеллекта/Под редакцией Д.А. Поспелова. М.: Наука. Гл. ред. Физ.-мат. лит., 1986. 321 с.

15. Борисов А.Н., Алексеев А.В., Крумберг О.А. и др. Модели принятия решений на основе лингвистической переменной. Рига: Зинатне, 1982. 256 с.

References

1. Litvinenko V.A. Adaptivnye algoritmy proektnykh operatsiy SAPR EVA. IS-IT14: tr. Mezhdunar. kongr. po intellekt. sistemam i inform. tekhnologiyam, p. Divnomorskoe, 2 -9 sent. YuFU. M.: Fizmatlit, 2014. Vol.1, pp. 113-119.

2. Lebedev B.K. Intellektual'nye protsedury sinteza topologii SBIS [Intellectual procedure for the synthesis of topology for VLSI]. Taganrog: Izdatel'stvo TRTU, 2003. 108 p.

3. Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar. Handbook of algorithms for physical design automation. CRC Press, New York, USA, 2009.1024 p.

4. Malyshev N.G., Bershteyn L.S., Bozhenyuk A.V. Nechetkie modeli dlya ekspertnykh sistem v SAPR [Fuzzy models for expert systems in CAD]. M.: Energoatomizdat, 1991. 136 p.

5. Dasgupta, D. "Information Processing in the Immune System", New Ideas in Optimization, (Eds.) D. Corne, M. Dorigo & F. Glover, McGraw Hill, London, 1999. pp. 161-165.

6. Calenbuhr V., Bersini H., Varela F.J., Stewart J. The impact of the structure of the connectivity matrix on the dynamics of a simple model for the immune network. Proc. 1st Copenhagen Symp. on Computer Simulation in Biology, Ecology and Medicine (Ed. E.Mosekilde). 1993. pp. 41-45.

7. Ostroukh E.N., Zolotareva L.I., Bychkov A.A., Dolgov V.V. Fundamental'nye issledovaniya. 2011. №12-1. рр. 224-227.

8. Chernyshev Yu.O., Ventsov N.N., Mukhtarov S.A. Izvestiya SFedU. Engineering Sciences. 2013. №7 (144). pp. 91 -77.

9. Ventsov N.N. Inzenernyj vestnik Dona (Rus), 2013, №4 URL: ivdon.ru/magazine/archive/n4y2013/1886.

10. Ventsov N.N. Inzenernyj vestnik Dona (Rus), 2012, №1 URL: ivdon.ru/ru/magazine/archive/n1y2012/630.

11. Chernyshev Yu.O., Ventsov N.N., Mukhtarov S.A. Izvestiya SFedU. Engineering Sciences. 2012. №7 (132). pp. 63 -69.

12. Chernyshev Yu.O., Ventsov NN., Mukhtarov S.A. Vestnik DGTU. 2012. № 5 (56). pp. 68-76.

13. Bershteyn L.S., Bozhenyuk A.V. Izvestiya TSURE.Engineering Sciences. 2004. № 3 (38). pp. 5 -10.

14. Nechetkie mnozhestva v modelyakh upravleniya i iskusstvennogo intellekta [Fuzzy sets in management models and artificial intelligence]. Pod redaktsiey D.A. Pospelova. M.: Nauka. Gl. red. Fiz.-mat. lit., 1986. 321 p.

15. Borisov A.N., Alekseev A.V., Krumberg O.A. i dr. Modeli prinyatiya resheniy na osnove lingvisticheskoy peremennoy [The decision-making model based on linguistic variable]. Riga: Zinatne, 1982. 256 p.