Логический подход к оптимизации при интервальной неопределенности параметров

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

Логический подход к оптимизации при интервальной неопределенности параметров

Левин В.И., д.т.н., профессор



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

, (1)

где - вектор аргументов, причем , - числовое множество, - вектор интервальных параметров, т.е. параметры - замкнутые интервалы , в которых находятся все возможные значения этих параметров. Каждому значению аргумента , согласно (1) соответствует одно значение функции в виде некоторого интервала . Необходимо найти значение аргумента , для которого соответствующее значение функции экстремально (максимально или минимально). Мы ограничимся задачами дискретной оптимизации, где множество дискретно. Для решения сформулированной задачи необходимо уметь сравнивать величины интервалов и выделять экстремальные интервалы. Введем детерминированные операции непрерывной логики: (дизъюнкция), (конъюнкция) и далее - соответствующие недетерминированные (в частности, интервальные) операции этой логики:

(2)

где и - любые числовые множества (в частности, интервалы). Как видно из (2), дизъюнкция (конъюнкция) двух числовых множеств определяется как множество возможных значений дизъюнкции (конъюнкции) двух чисел в условиях, когда эти числа пробегают независимо друг от друга все возможные значения внутри соответствующих интервалов.

Следуя [1], введем отношение неравенства интервалов как

. (3)

Как известно [1], два интервала и , такие, что или , называются сравнимыми по отношению , другие и называются несравнимыми по этому отношению. В некоторой системе интервалов интервал называется максимальным (минимальным), ec-ли он сравним c интервалами по отношению и . В [1] были получены следующие результаты.

Теорема 1. Для того чтобы интервалы и были сравнимы в отношении (несравнимы), необходимо и достаточно выполнения условия (выполнения условий или ).

Теорема 2. Для того чтобы в системе интервалов интервал был максимальным, необходимо и достаточно выполнения следующих условий: , а для того, чтобы был минимальным, выполнения условий Результаты теоремы 1 позволяют сравнивать интервалы, распространять на них понятие оптимума и выяснять условие существования этого оптимума. Результаты теоремы 2 позволяют строить алгоритмы выделения экстремальных интервалов, сводя их к алгоритмам выделения экстремальных точечных величин. Это позволяет сводить интервальные оптимизационные задачи к детерминированным, что и составляет основу для решения интервальных задач.

В качестве примера изложенного подхода рассмотрим задачу о назначениях. Интервальная задача о назначениях на должности состоит в распределении должностей между претендентами так, чтобы минимизировать суммарные издержки по работе. При этом издержки от работы каждого претендента на каждой должности задаются с точностью до интервала. Математически эта задача состоит в отыскании булевой матрицы назначений , обращающей в минимум сумму издержек , где - заданная матрица издержек, - издержки от работы в j-й должности i-го претендента. При этом элементы - интервальные величины, вида отрезков , в которых рассеяны значения . Соответственно оказывается интервальной матрицей вида , где . Искомая матрица X должна удовлетворять обычным условиям нормировки в виде . Задача о назначениях является простейшей моделью оптимального выбора назначений на должности. При этом xij=1 означает выбор для j-й должности i-го претендента (чему соответствуют издержки ). Для решения задачи необходимо сравнение интервальных величин. Последнее выполняется согласно изложенному выше. При этом получаем следующие результаты [2].

Теорема 3. Для того чтобы интервальная задача о назначениях на должности с матрицей издержек имела решение , необходимо и достаточно, чтобы это же решение имели две детерминированные задачи о назначениях с матрицами издержек и .

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

Теоремы 3, 4 сводят решение интервальной задачи о назначениях на должности к решению двух детерминированных задач о назначениях, которые естественно назвать нижней и верхней граничными задачами; их матрицы издержек равны соответственно и .Из изложенного вытекает такой алгоритм решения интервальной задачи назначения на должности, с интервальными матрицами и .

Шаг 1. Отыскание множества решений нижней граничной задачи, т.е. детерминированной задачи о назначениях с матрицей издержек . Для этого можно использовать метод ветвей и границ (позволяет при небольшом числе должностей быстро и просто получить решение), метод, основанный на вычислении логических определителей [2] (позволяет при небольших не только получать решение, но и анализировать его при варьировании элементов матрицы ), венгерский метод [3] (дает возможность находить решение при больших ), метод случайного поиска (позволяет быстро найти приближенное решение) [4].

Шаг 2. Отыскание множества решений Me верхней граничной задачи, т.е. детерминированной задачи о назначениях с матрицей издержек A2, с использованием тех же методов, что и на шаге 1.

Шаг 3. Нахождение пересечения M множеств Mн и Me. Для этого перебираются элементы одного множества и помечаются те из них, которые входят во второе множество. Если M (непустое множество), то любая булева матрица назначений Xk из M есть решение данной интервальной задачи о назначениях. Если M = (пустое множество), то данная задача не имеет решения.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

блокирующий неопределенный оптимизация опровержимость

Пусть L - язык нечеткой логики Заде. Синтаксис языка L совпадает с синтаксисом обычной пропозициональной логики, т.е. L состоит из формул, построенных из атомов с применением логических связок ~, , и . Семантика L определяется с помощью нечетких интерпретаций v: L [0,1], удовлетворяющим следующим условия для произвольных формул б, в L:

v(~б) = 1-v(б), v(бв) = min{v(б),v(в)}, v(бв) = max{ v(б),v(в)},

v(бв) = max{1-v(б),v(в)}.

С каждой формулой бL и числами e, f, 0еf1, ассоциируется предложение eбf, называемое фактом. Это предложение истинно или ложно при интерпретации v так, что

v(eбf) = df ev(б)f.

(В дальнейшем мы пишем бe вместо eб1 и бe вместо 0бe.)

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

S |= ф df не существует интерпретации v такой, что все факты

уЕ истинны, v(у) = 1, а факт ф ложен, v(ф) = 1.

Нечеткая пропозициональная база знаний, или, проще, нечеткая база знаний - это конечное множество S формул из L. Состояние базы знаний S - это конечное подмножество У L* такое, что:

* (eбf)У бS;

* бS e, f [0,1]. (eбf)У;

* (eбf), (e' бf ')У e = e', f = f ' .

Состояние У базы знаний S также называется базой фактов для этой базы знаний.

Каждую формулу кL можно рассматривать как запрос к состоянию У нечеткой базы знаний S. Ответ на запрос к - это всякий факт екf такой, что У |= екf.

Очевидно, что 0к1 является тривиальным ответом на запрос к. Ясно также, что если екf - ответ на запрос и 0е'е, f f `1, то e'кf `также является ответом. Значит, существует оптимальный ответ е0кf0 на запрос к, где e0 - супремум значений e , а f0 - инфимум значений f таких, что S |= eбf.

Пример 1. Возьмем базу знаний S = {pq, qr} и ее состояние У = {0.7pq, 0.4qr0.6}. Пусть к = p~r - запрос к У. Тогда 0.4p~r 0.6 - оптимальный ответ (как это будет показано в п.3).

Для нахождения оптимального ответа на запрос к базе фактов может быть применен метод аналитических таблиц, который мы рассмотрим в п.2.

Общим состоянием нечеткой базы знаний S назовем состояние У0, у которого в каждом факте вместо конкретных чисел из [0,1] стоят различные параметры (переменные). В качестве параметров будем использовать символы a, b, c, d, a1, b1, c1, d1, a2, b2, c2, d2,… Каждое конкретное состояние У для S получается из У0 путем некоторого назначения л параметрам конкретных чисел. Это назначение должно быть таким, что (aбb) У0 (албbл) У. (Мы рассматриваем л как подстановку чисел вместо параметров; ал - результат этой подстановки для параметра а.) Таким образом, У0л = У.

Общий ответ на запрос к к общему состоянию У0 базы знаний S - это предложение вида gкh, где g и h - некоторые выражения, составленные из параметров состояния У0. Выражения g и h должны быть такими, чтобы при любом назначении w было (gлкhл) У. Оптимальный общий ответ на запрос к - это такой общий ответ g0кh0, что при любой подстановке факт g0лкh0л является оптимальным ответом на запрос к базе фактов.

Пример 2. Пусть S = {pq, qr} - нечеткая база знаний и запрос к = p~r из примера 1. Общим состоянием для S является У0 = {apqb, cqrd}. В п.3 мы покажем, что оптимальным общим ответом на запрос к У0 служит

0.4p~rcase[min{b,1- c} if a+c >1b+d >1;

b if a+c1b+d >1;

1- c if a+c >1 and b+d1;

1 if a+c1 and b+d1].

(Здесь case - функция выбора: case[v1 if л1, v2 if л2, …, vN if лN] = vi, где i - первое число такое, что выполняется условие лi .) Взяв подстановку л ={a:=0.7, b:=1, c:=0.4, d:= 0.6} и применив ее к этому оптимальному общему ответу, мы получим конкретный оптимальный ответ 0.4p~r0.6.

Метод аналитических таблиц приводит к алгоритму AL со следующими свойствами:

AL применим к произвольной паре (У, к), где У - база фактов, (т.е. конкретное состояние нечеткой базы знаний);

результатом AL(У, к) применения алгоритма AL к паре (У, к) является оптимальный ответ на запрос к к базе фактов У;

AL имеет экспоненциальную оценку (в худшем случае) для времени вычисления (относительно размера (У, к) ).

Метод аналитических таблиц также лежит в основе алгоритма AL0 со следующими свойствами:

AL0 применим к произвольной паре (S, к), где S - нечеткая база знаний;

результатом AL0(S, к) применения алгоритма AL0 к паре (S, к) является оптимальный общий ответ на запрос к к общему состоянию У0 нечеткой базы знаний (которое получается путем назначения параметров в качестве нижней и верхней оценки для каждого бS);

AL0 имеет экспоненциальную оценку для времени вычисления (относительно размера (S, к) ).

Рассмотрим ситуацию, когда фиксированы нечеткая база знаний S и запрос к. Задача состоит в построении алгоритма ALS,к, обладающего следующими свойствами:

ALS, к применим к произвольному состоянию У базы S;

результат ALS, к(У) применения алгоритма ALS, к к состоянию У есть оптимальный ответ на запрос к, т.е. ALS, к(У) = AL(У, к).

Эта задача легко решается с использованием алгоритма AL0. Нужно применить этот алгоритм к паре (S, к). В результате его применения получится оптимальный общий ответ g0кh0 к общему состоянию У0. В этом ответе выражения g0 и h0 содержат параметры, скажем, а1, а2,…, аn. Тогда алгоритм ALS, к включает g0 и h0 и его применение следует этапам:

0. Дано состояние У нечеткой базы знаний S.

1. Найти подстановку л = {аi := еi | 1in} такую, что У0л = У.

2. Применить л к g0 и h0.

3. Выдать оптимальный ответ g0лкh0л.

ВЫЧИСЛЕНИЕ КОНКРЕТНЫХ ОПТИМАЛЬНЫХ ОТВЕТОВ

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

max{x,y}z xz и yz, max{x,y} < z x < z и y < z,

max{x,y}z xz или yz, max{x,y} >z x > z или y > z,

min{x,y}z xz или yz, min{x,y} < z x < z или y < z,

min{x,y}z xz и yz, min{x,y} > z x > z и y > z.

Пусть М - множество фактов вида бe, б < e, бe and б > e, где бL и e[0,1]. В табл.1 приведены правила вывода (по методу аналитических таблиц) для логики М.



Таблица 1: Правила вывода для логики M

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

Пример 3. Пусть нечеткая база знаний S, ее состояние У и запрос к те же, что и в примере 1. Состояние У можно заменить на эквивалентное состояние У*={pq0.7, qr0.4, qr0.6}. Тогда У* |= gp~ry в том и только том случае, если невыполнимы следующие два множества фактов:

У1={pq0.7, qr0.4, qr0.6, p~r < x},

У2 ={pq0.7, qr0.4, qr0.6, p~r > y}.

На рис.1 показаны деревья вывода А и Б для множеств У1 и У2. В дереве А ветвь (1) замкнута, так как содержит противоречивую пару неравенств q0.7 и q0.6. Ветвь (2) будет замкнутой, если значение y выбрать так, чтобы пара неравенств r < 1-y и r0.4 стала противоречивой. Также ветвь (2) будет замкнута, если взять у = 1 (так как тогда p > 1, что невозможно). Таким образом, ветвь (2) в дереве А замкнута тогда и только тогда, когда у = 1 или 0.41-у (т.е.. у0.6).



Рис. 1. Деревья вывода для множеств У1 и У2

В дереве Б ветвь (3) замкнута, так как содержат противоречивую пару неравенств q0.7 и q0.6. Ветвь (4) будет замкнута, если х0.7. Ветвь (5) будет замкнута, если 1- х0.6, т.е. х0.4. Таким образом, дерево Б замкнуто для данного х, если х0.7 х0.4, т.е если х0.4. Следовательно, наибольшим х, при котором дерево Б замкнуто является max{x | х0.4} = 0.4.

Итак, оптимальным ответом на запрос к указанной базе фактов У служит факт 0.4 p~r0.6.

Замечание. В работе [2] был предложен метод нахождения оптимальных ответов на запросы для нечеткой базы знаний, который близок к изложенному (на примере) методу.

НАХОЖДЕНИЕ ОПТИМАЛЬНЫХ ОБЩИХ ОТВЕТОВ

Рассмотрим нахождение оптимальных общих ответов сначала на примере.

Пример 4. Пусть нечеткая база знаний и запрос те же, что и в примерах 1, 2 и 3, т.е. S = {pq, qr} и к = p~r. Общим состоянием базы знаний S является У0 = {apqb, cqrd}. Рассмотрим два множества общих фактов У1 = У0{ p~ r >y} и У2 = У0{p~r < x}, для которых построим полные деревья вывода (рис.2 и рис.3).

Рис.2. Дерево вывода для множества У1

В первом дереве на ветви (1) имеется пара неравенств qa и q1-c, которая будет противоречивой тогда и только тогда, когда a > 1- c т.e. a+c >1. Мы скажем, что факты qa и q1-c составляют блокирующую пару и что a+c >1 есть условие опровержимости этой пары. Заметим, что факты pa и pb мы не считаем блокирующей парой, так как условие ab тривиально истинно (и, значит, не может быть опровергнуто). Факт p> y является блокирующим; его условием опровержимости является у = 1 (благодаря тому, что неравенство р >1 тривиально ложно). Точно также, блокирующим является факт r <1- y с условием опровержимости у = 1 (благодаря тому, что неравенство r < 0 тривиально ложно).



Рис.3. Дерево вывода для множества У2

В табл. 2 содержатся все блокирующие факты для дерева рис.2 с указанием условий их опревержимости и номеров ветвей, на которых лежат эти пары. Из этой таблицы мы видим, что пары с номерами 1 и 4 замыкают все ветви дерева рис.2, если выполнены условия их опровержимости. Аналогично, все ветви дерева замыкаются парами с номерами 2 и 3. Наконец, каждый из фактов p >y и r <1- y замыкает дерево, если у = 1. Таким образом, дерево рис.2 будет замкнутым тогда и только тогда, когда выполнено условие

Д: (a+c >1y1- c)(b+d >1 yb)y = 1

Это условие эквивалентно следующему:

Д' : case[y1- cyby = 1 if a+c >1b+d >1;

yby = 1 if a+c1b+d >1;

y1- cy = 1 if a+c >1b+d1;

y = 1 if a+c1b+d1].

Отсюда получаем:

В табл.3 представлены блокирующие факты для дерева рис.3, откуда видно, что это дерево замкнуто тогда и только тогда, когда выполнено условие (xa)(x1- d)x = 0. Следовательно,

g = max{x | (xa)(x1- d)x = 0} = min{a,1- d}.

Таблица 2. Блокирующие факты для дерева рис.2

1	(q1- c, qa)	a+c >1	(1), (3)
2	(qb, q1-d )	b+d >1	(3), (4)
3	(pb, p >y)	yb	(1), (2)
4	(q1- c, qa)	y1- c	(2), (4)
5	p > y	y = 1	(1), (2), (3), (4)
6	r < 1- y	y = 1	(1), (2), (3), (4)

Таблица 3. Блокирующие факты для дерева рис.3

1	(pa, p < x)	xa	(1), (3), (5), (7)
2	(rd, r > 1- x)	x1- d	(2), (4), (6), (8)
3	(qa, q1-c)	a+c >1	(1), (2), (5), (6)
4	р < x	x = 0	(1), (3), (5), (7)
5	r > 1- x	x = 0	(2), (4), (6), (8)

В табл.3 представлены блокирующие факты для дерева рис.3, откуда видно, что это дерево замкнуто тогда и только тогда, когда выполнено условие (xa)(x1- d)x = 0. Следовательно,

g = max{x | (xa)(x1- d)x = 0} = min{a,1- d}.

Возьмем теперь произвольные базу знаний S и запрос к . Для множеств фактов У0{к < x} and У0{к > y} построим деревья вывода Т1 и Т2. Легко видеть, что в дереве T1 могут встречаться пары блокирующих фактов и соответствующие опровергающие условия следующих видов:

(paj, p ak), aj > ak,

(p1- aj, p ak), aj + ak < 1,

(paj, p1- ak), aj + ak > 1,

(p aj, p < x) x aj,

(p1- aj, p < x) x1- aj,

(p >1- x, paj), x1- aj,

(p >1- x, p1- aj), x aj,

(p > 1- x, p > x), x Ѕ.

Кроме того, факты вида р< x и p >1 - x рассматриваются как блокирующие с условием опровержения х = 1.

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

Для множества Е блокирующих пар фактов и/или отдельных блокирующих фактов положим:

b(E) ={b(р) | рE}, c(E) = Л{c(р) | рE} (конъюнкция условий).

Множество E назовем покрытием, если b(E) совпадает с множеством всех ветвей дерева. Таким образом, если Е - покрытие и условие c(E) выполнено, то дерево будет замкнутым. Покрытие Е называется тупиковым (или локально минимальным), если Е перестает быть покрытием при выбрасывании любого его элемента (т.е. Е \ {р} для любого рЕ не является покрытием).

Пусть E1, E2,…, Em - все тупиковык покрытия дерева Т1. Возьмем условие C = c(E1)c(E2)…c(Em). Пусть K - множество всех входящих в С условий видов: aj > ak, aj + ak < 1 или aj + ak > 1, а H - множество всех входящих в С условий видов: x aj, x1- aj, x1- aj, x aj или x Ѕ ). Для подмножеств X H обозначим r[X] множество правых частей неравенств из Х.

Пусть и - какое-либо назначение булевых значений условиям из K, т.е. и: K{0,1}. Положим

и* = (Л{у | уK, и(у) = 1})(Л {у | уK, и(у) = 0}).

Рассматривая и как подстановку, мы обозначаем через Cи результат применения и к C. Тогда

Cи = c(E1)иc(E2)и…c( Em)и ,

и ясно, что

max{x | Cи} = max{max{x|c(Ej)и} | 1jm}

= max{min r[c(Ej)и}] | 1jm}.

Поскольку g0 = max{x | C}, получаем:

g0 = case[max{min r[c(Ej)и}] | 1jm} if и*, и: K{0,1}].

Для анализа дерева Т2 мы используем аналогичные обозначения:

F1, F2,…, Fn - все тупиковые покрытия для дерева Т2;

D = c(F1)c(F2)…c(Fm);

L аналогично K и M аналогично H;

щ: L{0,1};

щ* = (Л{у | уL, щ(у) = 1})(Л {у | уL, щ(у) = 0}).

Поскольку g0 = min{x | D}, получаем:

h0 = case[min{max{r[c(Fj)щ}] | 1jn} if щ*, щ: K{0,1}].



ЛИТЕРАТУРА

1. Плесневич Г.С. Метод аналитических таблиц для нахождения оценок в логике Заде// Труды 11-й Национальной конференции по искусственному интеллекту с международным участием (Дубна, 28 сентября - 3 октября 2008 г.). - М.: УРСС, 2008. - Т.3. - С.249-259.

2. Straccia U. Reasoning and Experimenting within Zadeh's Fuzzy Propositional Logic// Technical Report 2000-b4-011, Instituto di Elaborazione delle Ricerche, Pisa, Italy, 2000.

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

...