Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією
The accuracy of decision making based on the models of optimal choice with disjunctive constraint max f(x̃)= ∑i=1…nω(xi) with the condition D(x̃) = ∨j=1…mKj(x̃) = 1 for the case when the restriction is given exactly, but the information for the goal function is presented only by the weight order ω(x...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/171541 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1867334369631272960 |
|---|---|
| author | Donskoj, V. I. |
| author_facet | Donskoj, V. I. |
| author_institution_txt_mv | [
{
"author": "V. I. Donskoj",
"institution": null
}
] |
| author_sort | Donskoj, V. I. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-06-25T17:03:13Z |
| description | The accuracy of decision making based on the models of optimal choice with disjunctive constraint max f(x̃)= ∑i=1…nω(xi) with the condition D(x̃) = ∨j=1…mKj(x̃) = 1 for the case when the restriction is given exactly, but the information for the goal function is presented only by the weight order ω(x1) ≥ ... ≥ ω(xn) ≥ 0, is estimated. |
| first_indexed | 2025-07-17T10:25:20Z |
| format | Article |
| fulltext |
© В.И. Донской, 2004
Системні дослідження та інформаційні технології, 2004, № 4 77
TIДC
ТЕОРЕТИЧНІ ТА ПРИКЛАДНІ ПРОБЛЕМИ
ІНТЕЛЕКТУАЛЬНИХ СИСТЕМ ПІДТРИМКИ
ПРИЙНЯТТЯ РІШЕНЬ
УДК 519.8
ОЦЕНКА ТОЧНОСТИ ПСЕВДОБУЛЕВЫХ
КАНОНИЧЕСКИХ МОДЕЛЕЙ ПРИНЯТИЯ РЕШЕНИЙ
ПРИ НЕПОЛНОЙ ИНФОРМАЦИИ
В.И. ДОНСКОЙ
Оценивается точность принятия решений на основе моделей оптимального
выбора с дизъюнктивным ограничением ∑ =
= n
i ixxf 1 )()~(max ω при усло-
вии 1)~()~(
1
==
=
∨ xKxD j
m
j
для случая, когда ограничение задано точно, но
информация о целевой функции представлена только порядком весов
0)(...)( 1 ≥≥≥ nxx ωω .
ВВЕДЕНИЕ
Изучение и разработка моделей выбора оптимальных решений на основе
накопленных знаний — важное направление в области интеллектуального
анализа и обработки информации. В настоящее время вопросы извлечения и
представления знаний изучены гораздо глубже, чем подходы к построению
процедур выбора оптимальных (с точностью, определяемой имеющейся не-
полной начальной информацией) решений на базе полученных знаний. Вы-
бор решений в интеллектуализированных компьютерных системах осущест-
вляется путем синтеза моделей, адекватных имеющейся (но, как правило,
неполной) начальной информации, представленной знаниями и прецедента-
ми-фактами.
Классический подход к синтезу моделей принятия решений основан на
построении области допустимых решений и оценочной (скалярной или век-
торной) целевой функции.
Для выбора моделей в рамках классического подхода используется ин-
формация двух видов: качественная информация о классе, в котором оты-
скивается модель, и информация о параметрах модели. Основным недостат-
ком классических моделей выбора решений является их «условная»
согласованность с моделируемыми объектами и явлениями. При выборе
классических моделей предполагается выполнение некоторых, обычно же-
стких, условий, определяющих вид модели. Независимо от имеющихся эм-
В.И. Донской
ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 78
пирических данных, модель фиксируется, и далее требуется получить зна-
чения всех ее числовых параметров.
Неклассическое индуктивное моделирование основывается на преце-
дентах (фактах) и знаниях, представляющих собой, главным образом, отно-
шения определенного вида, которым удовлетворяют или априорно должны
удовлетворять прецеденты.
В настоящей работе предполагается возможным предикатное описание
объектов, т.е. использование свойств-предикатов в качестве семантической
базы представления проблемной области. Предикатам ставятся в соответст-
вие булевы переменные, на основе которых могут строиться модели ограни-
чений и целевых функций. Задание свойств-предикатов обычно является
основой определения баз знаний продукционного типа, накопления наборов
эмпирических значений в базах экспериментальных данных, извлечения ло-
гических закономерностей (аналогий), представительных наборов, деревьев
решений. На базе предикатного описания объектов строятся дизъюнктивные
нормальные формы (ДНФ) — логические описания областей индуктивной и
дедуктивной выводимости, выводимости по аналогии [1–4]. В работе оце-
нивается точность решений, выбираемых на основе модели, которая синте-
зируется по прецедентной информации и/или знаниям продукционного типа
в форме с дизъюнктивным ограничением. Замечательным свойством такой
модели является то, что информации только о порядке слагаемых аддитив-
ной целевой функции с неотрицательными весами оказывается достаточ-
но, чтобы, имея ДНФ-ограничение, оценить точность выбранного GREEDY
алгоритмом решения. Последнее — основной результат статьи.
СИНТЕЗ КАНОНИЧЕСКИХ ПСЕВДОБУЛЕВЫХ МОДЕЛЕЙ И ИХ
СВОЙСТВА
В работе [1] показано, что любая задача псевдобулевой оптимизации вида
nnBWxxfextr }1,0{~),~( =⊆∈ ,
где RBf n →: , может быть представлена в канонической форме с дизъюнк-
тивным ограничением
⎪⎩
⎪
⎨
⎧
= ,1)~(
),~(
xD
xfextr (1)
где =)~(xD jrj
jr
j
jj
m
j
xx
σ
σ &&1
11
…∨
=
— произвольная ДНФ характеристической
функции Wϕ множества W , определяемая выражением
⎪⎩
⎪
⎨
⎧
∉
∈
=
.~,0
,~,1
)~(
Wx
Wx
xWϕ
Рассмотрим важный для приложений случай, когда целевая функция
является аддитивной с неотрицательными весами
Оценка точности псевдобулевых канонических моделей принятия решений …
Системні дослідження та інформаційні технології, 2004, № 4 79
∑
=
=
n
i
ixxf
1
)()~( ω , 0)( ≥ixω .
Класс псевдобулевых функций обозначим { }RBfnPS n →= :)(2 .
Значение канонической формы (1) станет ясным с учетом следующих
результатов [1].
• Как уже отмечено выше, любая задача псевдобулевой оптимизации
представима в форме (1) с ДНФ-ограничением.
• Если задача оптимизации линейной псевдобулевой функции с ограни-
чениями-неравенствами приводится к эквивалентной форме с ДНФ-
ограничением за число шагов, ограниченное полиномом от размерности за-
дачи, то она разрешима за полиномиальное время.
• Для любой нелинейной задачи безусловной оптимизации функции
)(2 nPSf ∈ найдется эквивалентная ей задача оптимизации линейной функ-
ции )(2 mPSg∈ в форме с дизъюнктивным условием, где m — число сла-
гаемых приведенного полинома для функции f без учета свободного члена.
Задачи псевдобулевой оптимизации, представленные в форме с ограни-
чениями типа неравенств или в ином виде, как следует из изложенного вы-
ше, совсем не обязательно специально приводить к форме с ДНФ-
ограничением, поскольку такое приведение равносильно решению задачи и
в некоторых случаях может оказаться сложнее, чем решение другим мето-
дом. Важность использования канонической формы объясняется прежде
всего тем, что уже изучены методы построения ДНФ-ограничений, исполь-
зующие в качестве начальной информации прецеденты, накопленные в ба-
зах эмпирических данных и/или продукции, составляющие базы знаний [2,4].
Оказалось, что, используя указанную начальную информацию, построить
ограничения в форме ДНФ гораздо проще (и точнее), чем в другой форме
(например, в виде неравенств).
МАТРОИДЫ И КАНОНИЧЕСКИЕ МОДЕЛИ
Пусть }{ neeE ,...,1= — конечное множество; )(EB — булеан над E ;
)(EBJ ⊆ — зафиксированное семейство подмножеств. Семейство J назы-
вают системой независимости, если
J∈∅ ; JACAJC ∈⇒⊂∧∈ )()( . (2)
Множества, входящие в J , называют независимыми.
Пару >< JE, называют матроидом, если непустое семейство J яв-
ляется системой независимости, и все максимальные по включению незави-
симые подмножества (базы) любого множества ES∈ равномощны. Мощ-
ность баз множества S называется его рангом )(Sr , а ранг )(Er множества
E называется рангом матроида. Любые две базы матроида (максимальные
независимые множества в E ) равномощны и имеют ранг )(Er [5].
Если в задаче
В.И. Донской
ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 80
⎪
⎪
⎩
⎪
⎪
⎨
⎧
→
⊆∈
+
∈
∑
RE
EBJJS
e
Se
:
),(;
),(max
ω
ω
(3)
пара >< JE, является матроидом, то, согласно теореме Радо-Эдмондса [5],
«жадный» (GREEDY) алгоритм обеспечивает точное решение задачи (3),
притом с полиномиально ограниченной трудоемкостью, если только свойст-
во « JA∈ » для любого EA⊆ вычислимо с полиномиальной сложностью.
В задаче (1) булевы переменные nxx ,...,1 связываются с элементами
множества }{ neeE ,...,1= так, что вектор nααα ,...,~
1= значений перемен-
ных nxx ,...,1 определяет множество EeS ii ⊆== }1:{~ αα . Если =)~(xD
)~(
1
xK j
m
j
∨
=
= — ДНФ, определяющая ограничение канонической моде-
ли (1), то уравнение 1)~( =xD равносильно условию JS x ∈~ . Обозначив
{ },...,1~ nx xxE = , исследуем, при каких условиях >< )~(,~ xDEx — матроид.
Теорема 1. В канонической модели (1) пара >< )~(,~ xDEx является мат-
роидом тогда и только тогда, когда одновременно выполняются условия:
1) 1)0
~
( =D ;
2) любая простая импликанта булевой функции Df , определяемой
ДНФ )~(xD , не содержит положительных литералов и имеет ранг
)(min Mrnr −= , где )(Mr — ранг матроида >< )~(,~ xDEx .
Доказательство. Необходимость. Справедливость 1) немедленно сле-
дует из выражения (2) в определении системы независимости.
Пусть Df — булева функция, определяемая ДНФ )~(xD , и K — про-
стая импликанта для Df . Если бы K содержала положительный литерал, то
она имела бы вид HxK s= . Но тогда, согласно определению матроида, им-
пликантой для Df была бы и конъюнкция HxK s=1 . Поскольку
HHxHx ss =∨ , то это противоречило бы тому, что K — простая импли-
канта. Следовательно, в K содержится некоторое количество kr отрица-
тельных литералов, из которых ни один нельзя удалить, поскольку K —
простая импликанта. Если
krjj xxK ∧⋅⋅⋅∧=
1
,
то
⎪⎩
⎪
⎨
⎧
∉
∈
=
},...,{,1
},,...,{,0
:~
1
1
k
k
r
r
i jji
jji
σσ — база матроида M .
Все базы матроида равномощны, откуда )(Mrnrk −= .
Достаточность очевидна.
Оценка точности псевдобулевых канонических моделей принятия решений …
Системні дослідження та інформаційні технології, 2004, № 4 81
Следствие 1. Если ДНФ )~(xD в задаче (1) в канонической форме с ог-
раничением 1)~( =xD можно преобразовать в
ДНФ )~(xD− , не имеющую положительных
литералов и реализующую ту же функцию,
что и )~(xD , то ограничение 1)~( =xD опреде-
ляет некоторую систему независимости
nBJ ⊂ . А если в ДНФ )~(xD− все конъюнк-
ции являются простыми импликантами и
имеют одинаковый ранг, то >< )~(,~ xDEx —
матроид.
На рис. 1 показан матроид M , все базы
которого лежат в )(Mr -слое куба nB и соот-
ветствуют некоторому набору его вершин,
каждая из которых содержит ровно )(Mr
единиц.
НЕПОЛНОТА НАЧАЛЬНОЙ ИНФОРМАЦИИ И ОБОСНОВАНИЕ
РЕШЕНИЙ
В настоящей работе неполная начальная информация в задаче выбора реше-
ния описывается следующим образом.
Целевая функция достоверно является аддитивной, но не задана точно,
имеется лишь информация о «порядке» весов переменных
0)(...)(
1
≥≥≥
nii xx ωω .
Полагается, что начальная информация для выбора решения порож-
дена (не известной полностью) моделью ∑
=
=
n
i
ixxf
1
)()~(max ω при условии
1)~( =xD , где )~(xD — ДНФ, реализующая характеристическую функцию
множества допустимых решений задачи. Далее будем полагать, что )~(xD
получена некоторым способом [2, 4] и точно описывает ограничения.
Пусть J — семейство независимости, но пара >< JE, , вообще говоря,
может не быть матроидом. Обозначим для любого множества EF ⊆
}вбаза:min{),( FCCJFlr −= ,
}вбаза:max{),( FCCJFur −= .
Число
),(
),(min)(
}0),(:{ JFur
JFlrJk
JFurEF ≠⊆
= называется кривизной системы
независимости J и удовлетворяет двойному неравенству 1)(0 ≤< Jk . При-
чем 1)( =Jk только тогда, когда >< JE, — матроид. Пусть GS — множе-
1,1,…,1
0,0,…,0
r(M)-слой
Рис. 1
В.И. Донской
ISSN 1681–6048 System Research & Information Technologies, 2004, № 4 82
ство, отобранное GREEDY алгоритмом решения задачи (3), а 0S — множе-
ство, на котором в действительности достигается искомый экстремум.
Доказано [6], что для любой неотрицательной функции ω имеет место
неравенство
).(
)(
)(
0
Jk
S
SG ≥
ω
ω
Далее используется аналогичный подход на основе кривизны ДНФ,
описывающей систему независимости.
Определение 1. Кривизной ДНФ j
m
j
KD ∨
=
=
1
называется число
}{max
}{min
)(
1
1
−
≤≤
−
≤≤
−
−
=
j
mj
jmj
rn
rn
Dk ,
где −
jr — число отрицательных литералов в конъюнкции jK .
Определение 2. Пусть Df — булева функция, определяемая ДНФ D ;
)( DfS — множество всех простых импликант функции Df ; −
Lr — число
отрицательных литералов в простой импликанте )( DfSL∈ . Кривизной бу-
левой функции Df называется число
}{max
}{min
)(
)(
)(
−
∈
−
∈
−
−
=
L
fSL
LfSL
D
rn
rn
fk
D
D .
Теорема 2. ).(
)~(
)~(
опт
D
G fk
xf
xf
≥
Доказательство. Не теряя общности, будем считать, что переменные
перенумерованы и упорядочены по весу, так что 0)(...)( 1 ≥≥≥ nxx ωω . Обо-
значим µ=− −
∈
}{min
)(
L
fSL
rn
D
; Mrn L
fSL D
=− −
∈
}{max
)(
. Заметим, что nM <≤< µ1 .
Тогда
M
fkk D
µ
== )( , и число элементов в любом независимом множестве
лежит в отрезке ],[ Mµ .
Убедимся в том, что ).~()()~( оптxffkxf DG ≥ Пусть Ω — независимое
множество переменных с максимальным весом, ∑
Ω∈
=Ω=
e
efxf )()()~( опт ω , и
∑
∈
==
Ge
G ewGfxf )()()~( , где G — множество переменных, отобранных
GREEDY алгоритмом.
Очевидно, µ≥||G . Тогда
=
Ω
≤=Ω=Ω= ∑∑
Ω∈Ω∈ ee
D ee
M
f
M
kfxffk )(
||
1)(1)()()~()( опт ωµωµµ
Оценка точности псевдобулевых канонических моделей принятия решений …
Системні дослідження та інформаційні технології, 2004, № 4 83
}.~()()()(1
G
Gee
xfGfewea ==≤≤= ∑∑
∈Ω∈
Ω
µ
ω
µ
µµ
Здесь Ωa — средний вес элементов множества Ω , а µΩ — множество,
состоящее из первых µ по порядку (больших) элементов множества Ω .
Приведенная цепочка неравенств доказывает теорему.
На рис. 2 булевы наборы )(Dur -слоя имеют норму M , а наборы
)(Dlr -слоя — норму µ .
Процесс выбора и оценивания решений состоит в следующем.
1. Получить каноническую форму задачи.
2. Упорядочить переменные по весу.
3. Упростить ДНФD , стараясь получить
минимальную или тупиковую ДНФ *D .
4. Выбрать в *D конъюнкцию *j
K , следуя
правилу GREEDY алгоритма.
5. Взять в качестве решения булев вектор,
обращающий в единицу конъюнкцию *j
K и
имеющий единичные значения всех перемен-
ных, не входящих в *j
K . Если ДНФ D точно
определяет область допустимых решений, а
ДНФ *D не содержит положительных литералов,
то ).~()()~( оптxfDkxf G ≥
6. Вычислить кривизну ДНФ )( *Dk . Если для заданной точности ε
выполнено ε−≥1)( *Dk , то имеется гарантия, что решение, найденное
GREEDY алгоритмом, будет отличаться от оптимального решения опт
~x не
более, чем на )~( оптxfε или ε100 %.
ЛИТЕРАТУРА
1. Донской В.И. Задачи псевдобулевой оптимизации с дизъюнктивным огра-
ничением // Журн. вычисл. матем. и матем. физики. — 1994. — 34, № 3. —
C. 389–398.
2. Донской В.И. Логические продукционные системы: анализ и синтез // Киберне-
тика и системный анализ. — 1994. — № 4. — C. 11–22.
3. Донской В.И. Слабоопределенные задачи линейного булева программиро-
вания // Журн. вычисл. матем. и матем. физики. — 1988. — 28, № 9. —
C. 1379–1385.
4. Donskoy V. Pseudo-Boolean scalar optimization models with incomplete information
// OROGM Newsletter. — 1996. — № 1/2. — P. 20–26.
5. Edmonds J. Matroids and Greedy Algorithms // Math. Programming. —
1971. — P. 127–136.
6. Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle
algorithms // Discrete Math. — 1978. — 24, № 3. — P. 85–120.
Поступила 18.06.2003
1,1,…,1
0,0,…,0
lr(D)-слой
ur(D)-слой
Рис. 2
|
| id | journaliasakpiua-article-171541 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:25:20Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/cc/5d647a3857a67299eb1e098d7e4092cc.pdf |
| spelling | journaliasakpiua-article-1715412019-06-25T17:03:13Z Accuracy estimation of pseudo-boolean decision making models with incomplete information Оценка точности псевдобулевых канонических моделей принятия решений при неполной информации Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією Donskoj, V. I. The accuracy of decision making based on the models of optimal choice with disjunctive constraint max f(x̃)= ∑i=1…nω(xi) with the condition D(x̃) = ∨j=1…mKj(x̃) = 1 for the case when the restriction is given exactly, but the information for the goal function is presented only by the weight order ω(x1) ≥ ... ≥ ω(xn) ≥ 0, is estimated. Оценивается точность принятия решений на основе моделей оптимального выбора с дизъюнктивным ограничением max f(x̃)= ∑i=1…nω(xi) при условии D(x̃) = ∨j=1…mKj(x̃) = 1 для случая, когда ограничение задано точно, но информация о целевой функции представлена только порядком весов ω(x1) ≥ ... ≥ ω(xn) ≥ 0. Оцінюється точність прийняття рішень на основі моделей оптимального вибору з диз’юнктивним обмеженням max f(x̃)= ∑i=1…nω(xi) за умовою D(x̃) = ∨j=1…mKj(x̃) = 1 для випадку, коли обмеження задано точно, але інформація про цільову функцію представлена тільки порядком вагів ω(x1) ≥ ... ≥ ω(xn) ≥ 0. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-25 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171541 System research and information technologies; No. 4 (2004); 77-83 Системные исследования и информационные технологии; № 4 (2004); 77-83 Системні дослідження та інформаційні технології; № 4 (2004); 77-83 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/171541/171203 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Donskoj, V. I. Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title | Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title_alt | Accuracy estimation of pseudo-boolean decision making models with incomplete information Оценка точности псевдобулевых канонических моделей принятия решений при неполной информации |
| title_full | Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title_fullStr | Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title_full_unstemmed | Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title_short | Оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| title_sort | оцінка точності псевдобулевих канонічних моделей прийняття рішень за неповною інформацією |
| url | https://journal.iasa.kpi.ua/article/view/171541 |
| work_keys_str_mv | AT donskojvi accuracyestimationofpseudobooleandecisionmakingmodelswithincompleteinformation AT donskojvi ocenkatočnostipsevdobulevyhkanoničeskihmodelejprinâtiârešenijprinepolnojinformacii AT donskojvi ocínkatočnostípsevdobulevihkanoníčnihmodelejprijnâttâríšenʹzanepovnoûínformacíêû |