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

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

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

Ю.О. Чернышев

Н.Н. Венцов

П.А. Панасенко

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

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

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

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

Тогда обобщенную функцию µr, описывающую целесообразность создания схемы с длиной полупериметра L, по мнению всех экспертов можно получить при помощи операторов конъюнкции или дизъюнкции: т.е. µr(L)=µr_i(L) или µr(L)=µr_i(L). Аналогично рассуждая можно получить различные варианты функции µz.

Ситуация усложняется когда одновременно присутствуют функции µr_i(L) и µz_j(L), т.е. одни эксперты дают рекомендации в разрешающей, а другие в запрещающей форме. На рис.1 графики описывают в нечеткой форме степени принадлежности размещения элементов, характеризуемых длиной полупериметра L к разрешающему rL(L) и запрещающему zL(L) правилу, т.е. график rL(L) соответствует функции µr(L), а график zL(L) - µz(L).

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

Рис. 1. Исходные графики принадлежности длины полупериметра L к разрешающему и запрещающему правилу

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

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

µR(x,y)=1-x+x*y, (1)

где x,y[0,1].

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

Рис. 2. График изменения степени принадлежности, от длины полупериметра L, полученный в результате применения операции µR(zL(L),rL(L))

Из рис. 2 и формулы (1) следует, что равенство µR(µz(L),µr(L))=1 истинно в точках L=0,6 и L=0,65, так как µz(0,6)=0 и µz(0,65)=0, а в точке L=0,7, так как µr(0,7)=1.

В точке L=0,5 значения функций равны µr(0,5)=0,3, µz(0,5)=0,25, µR(µz(0,5),µr(0,5))=0,825, а в точке L=0,8 - µr(0,8)=0,78, µz(0,8)=0,71, µR(µz(0,8),µr(0,8))=0,842.

В точке L=0,45 значения функций равны µr(0,45)=0,2 µz(0,45)=0,5 µR(µz(0,45),µr(0,45))=0,6, а в точке L=0,85 µr(0,85)=0,5, µz(0,85)=0,75, µR(µz(0,85),µr(0,85))=0,62.

Наименьшие значения функции µR(µz(L),µr(L)) совпадают с границами анализируемой области определения. Значения функции в граничных точках L=0,35 и L=1,05 соответственно равны µR(µz(0,35),µr(0,35))=0,24 и µR(µz(1,05),µr(1,05))=0,17.

Максимумы функции µR(µz(L),µr(L)) являются признаками доминирования разрешающих факторов rL(L) над запрещающими факторами zL(L). Минимумы функции µR(µz(L), µr(L)) соответствуют доминированию запрещающих факторов zL(L), над разрешающими rL(L).

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

Рис. 3. График изменения степени принадлежности, от длины полупериметра L, полученный в результате применения операции µR(rL(L),zL(L))

Из рис. 3 и формулы (1) следует, что значения функций µR(µr(L),µz(L)) минимальны в точках L=0,65 и L=0,7 и равны соответственно µR(µr(0,65),µz(0,65))=0,11 и µR(µr(0,7),µz(0,7))=0,12.

В точке L=0,5 значения функций равны µr(0,5)=0,3, µz(0,5)=0,25, µR(µr(0,5),µz(0,5))=0,775, а в точке L=0,8 - µr(0,8)=0,78, µz(0,8)=0,71, µR(µr(0,8),µz(0,8))=0,779.

В точке L=0,45 значения функций равны µr(0,45)=0,2, µz(0,45)=0,5, µR(µr(0,45), µz(0,45))=0,9, а в точке L=0,85 - µr(0,85)=0,5, µz(0,85)=0,75, µR(µr(0,85), µz(0,85))=0,875.

Наибольшие значения функции µR(µr(L),µz(L)) соответствуют границам анализируемой области определения. Значения функции в граничных точках L=0,35 и L=1,05 соответственно равны µR(µr(0,35),µz(0,35))=0,99 и µR(µr(1,05),µz(1,05))=0,993.

Максимумы функции µR(µr(L),µz(L)) являются признаками доминирования запрещающих факторов zL(L) над разрешающими rL(L). Минимумы функции µR(µr(L),µz(L)) соответствуют доминированию разрешающих факторов rL(L) над запрещающими zL(L).

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

µL(x,y)=min(1-x+y;1). (2)

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

Рис. 4. График изменения степени принадлежности, от длины полупериметра L, полученный в результате применения операции µL(zL(L),rL(L))

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

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

Максимумы функции µL(µz(L),µr(L)) являются признаками доминирования разрешающих факторов rL(L) над запрещающими факторами zL(L). Минимумы функции µL(µz(L),µr(L)) соответствуют доминированию запрещающих факторов zL(L), над разрешающими rL(L).

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

Рис. 5. График изменения степени принадлежности, от длины полупериметра L, полученный в результате применения операции µL(rL(L),zL(L))

Из рис. 5 и формулы (1) следует, что значения функций µL(µr(L),µz(L)) минимальны в точках L=0,65 и L= 0,7 и равны соответственно µR(µr(0,65),µz(0,65))=0,11 и µR(µr(0,7),µz(0,7))=0,12.

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

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

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

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

Сопоставив графики импликаций µR(µz(L),µr(L)) и µL(µz(L),µr(L)), можно утверждать, что график µR(µz(L),µr(L)) формирует меньшую область полностью допустимых решений, для которых µL(µz(L),µr(L))=1, по сравнению с µL(µz(L),µr(L)). Из тестового примера следует что µR(µz(L),µr(L))=1 в точках, для которых µz(L)=0 или µr(L)=1. Функция µL(µz(L),µr(L))=1 в случае, если µz(L)µr(L). Поэтому в соответствии с изложенным можно утверждать, что при проектировании систем повышенной надежности (точности) целесообразнее использовать функцию µR(µz(L),µr(L)) по сравнению с функцией µL(µz(L),µr(L)). Импликацию µL(µz(L),µr(L)) целесообразнее использовать при проектировании подсистем, выполняющих второстепенные функции, не являющихся системно образующими и т.д.

Литература

логика райхенбах лукасевич

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). С. 71-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 с.

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