Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках
Предложен класс нечетких алгоритмов метода вектора спада. Принципиальное отличие их состоит в представлении окрестностей, в которых действует метод, системой размытых множеств (окрестностей), что значительно расширило область применения алгоритмов. Приведены результаты исследований относительно конк...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6227 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 1. — С. 152-163. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859760675476209664 |
|---|---|
| author | Парасюк, И.Н. Каспшицкая, М.Ф. |
| author_facet | Парасюк, И.Н. Каспшицкая, М.Ф. |
| citation_txt | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 1. — С. 152-163. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | Предложен класс нечетких алгоритмов метода вектора спада. Принципиальное отличие их состоит в представлении окрестностей, в которых действует метод, системой размытых множеств (окрестностей), что значительно расширило область применения алгоритмов. Приведены результаты исследований относительно конкретного класса задач комбинаторной оптимизации – оптимизационных задач на выборках.
Запропоновано клас нечітких алгоритмів методу вектора спаду, принципова відмінність якого полягає у представленні околів, в яких діє метод, системою розмитих множин (околів), що значно розширило область застосування алгоритмів. Отримані результати досліджень щодо конкретного класу задач комбінаторної оптимізації – оптимізаційних задач на виборках.
A class of fuzzy algorithms for slump-vector method is proposed. The main feature of these algorithms is the representation of the neighborhoods of method's operation by the system of fuzzy sets (neighborhoods), that considerably extends the range of application of the algorithms. The results of investigation of a particular class of combinatorial optimization problems, i.e., sample optimization problems, are presented.
|
| first_indexed | 2025-12-02T02:47:05Z |
| format | Article |
| fulltext |
152 Компьютерная математика. 2009, № 1
Предложен класс нечетких алго-
ритмов метода вектора спада.
Принципиальное отличие их со-
стоит в представлении окрест-
ностей, в которых действует
метод, системой размытых мно-
жеств (окрестностей), что зна-
чительно расширило область при-
менения алгоритмов. Приведены
результаты исследований отно-
сительно конкретного класса за-
дач комбинаторной оптимизации
– оптимизационных задач на вы-
борках.
© И.Н. Парасюк,
М.Ф. Каспшицкая, 2009
ÓÄÊ 519.21
È.Í. ÏÀÐÀÑÞÊ, Ì.Ô. ÊÀÑÏØÈÖÊÀß
ÐÀÇÌÛÒÛÉ ÀËÃÎÐÈÒÌ
ÌÅÒÎÄÀ ÂÅÊÒÎÐÀ ÑÏÀÄÀ
ÄËß ÐÅØÅÍÈß
ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÇÀÄÀ×
ÍÀ ÂÛÁÎÐÊÀÕ
Введение. Применение понятий и методов
размытой математики позволяет значительно
расширить круг решаемых практических за-
дач, которые либо не поддаются решению
средствами четкой математики, либо такое
решение является слишком сложным и про-
блематичным. Эффективнее в этом плане
могут быть так называемые размытые алго-
ритмы, которые можно применять для рабо-
ты как в четком, так и в размытом информа-
ционном пространствах. Под нечетким алго-
ритмом вообще понимаем такой алгоритм,
результатом которого является нечеткий ма-
тематический объект – нечеткое число, не-
четкое множество и т. п.
В работе [1] предложен класс нечетких ал-
горитмов метода вектора спада (МВС). Суть
заключается в представлении системы окре-
стностей, в которых действует метод, систе-
мой размытых множеств (окрестностей). Это
дало возможность значительно расширить
область применения алгоритмов. В данной
работе продолжаются исследования, начатые
в [1], относительно конкретного класса задач
комбинаторной оптимизации – оптимизаци-
онных задач на выборках.
Постановка задачи. Исследуем класс оп-
тимизационных задач на выборках, общая
формулировка которого звучит так.
Пусть задано конечное целочисленное
множество { }n
iiaA 1== . Обозначим Х={x} –
множество всех подмножеств множества А.
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 153
Общая задача (основная) заключается в следующем. Нужно найти такой елемент
x*∈X, который предоставляет экстремум функции F(x) при выполнении условия
U(x*)≤C.
Кроме этого, пусть задана матрица
1 1α( , ) n n
i j i jA a a = == , которая характе-
ризует связи (влияния) между элементами аi, aj; будем считать, что 0 ≤ α(ai, aj) ≤ 1
Понятно, что если некоторые 00 , ji aa не связаны или эти связи не учитываются
при формулировке задачи, то соответствующие α( 00 , ji aa ) = 0.
Если такое предостережение касается всех элементов множества А, то соот-
ветствующая матрица связей вырождается в нуль-матрицу. В допущении этой
работы матрица A~ имеет ненулевые элементы.
Заметим, что матрица A~ может быть употреблена для построения целевой
функции F(х) и ограничивающих условий U(х), что будет проиллюстрировано
дальше на примере двух типов задач.
Рассмотрим общую формулировку задачи. Отметим, что эта задача уже из-
учалась, относительно нее разработан алгоритм МВС, основывающийся на
системе окрестностей, которые строятся на основе использования метричности
пространства выборок Х [1]. Расстоянием между двумя точками x1, x2 ∈ X выби-
ралась величина d(x1, x2) = |(x1 ∪ x2)\(x1 ∩ x2)|. Символ |a| означает мощность мно-
жества а. Как отмечено в работе [2], этот алгоритм является индифферентным
относительно условий задачи.
Будем считать, как и в работе [2], что система окрестностей в алгоритме
МВC, адаптированном к рассмотренной задаче, является системой размытых
множеств (окрестностей). Понятно, что эта система определяется совокупно-
стью функций принадлежности (пример такой функции приведен в [2]). Отме-
тим, что при построении указанных функций принадлежности использовалось
множество (x1 ∪ x2)\(x1 ∩ x2), которое играло основную роль при построении
классического алгоритма метода МВС. В этой работе рассмотрены функции
принадлежности, основанные на других соображениях.
Элементы матрицы A~ могут входить в определение функций F(x) и U(x)
или играть вспомогательную роль, как это было при определении функций при-
надлежности в работах [2, 3]. Здесь не выделены носители функций принадлеж-
ности, они определялись как элементы универсума Х, предоставляющие функ-
ции принадлежности ненулевые значения. Впрочем, если универсум Х имеет
большую мощность, то целесообразно вводить ограниченный определенным
образом носитель. Например, носитель можно определить как подмножество,
что предоставляет позитивное значение функции принадлежности μ(х), если х
принадлежит одному из подмножеств, полученных следующим образом:
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Компьютерная математика. 2009, № 1 154
1. Из точки х0 удаляем поочередно по одному элементу, заменяя его на эле-
менты из множества А\х0. Мощность носителя в этом случае не превышает
|x0|⋅|А\х0|.
2. Из точки х0 удаляем поочередно по одному элементу, заменяя двумя из
множества А\х0. Максимальное количество таких образований будет
|x0| 0 0| \ | (| \ | 1)
2
A x A x .⋅ − Понятно, что мощность соответствующего носителя не
будет превышать вышеуказанное число.
3. Из точки х0 удаляем по два элемента, заменяя их одним элементом из
множества А\х0. Таких элементов будет 0 0| | (| | 1)
2
x x⋅ −
⋅|А\х0|; мощность носителя
ограничена сверху этим числом. Здесь, как и выше, х0 – некоторый фиксирован-
ный элемент пространства Х.
Возможны и другие варианты. Следует отметить, что в большинстве ука-
занных в работах [1–3] случаях построение носителя и соответствующей функ-
ции принадлежности ведется ориентировочно к физическому содержанию ре-
шения задачи. Если такую ориентацию не проводить, то лучше воспользоваться
одним из индифферентных алгоритмов.
Прежде чем рассмотрим основной аспект данной работы – решение одного
класса комбинаторных задач вариантом размытого алгоритма МВС, приведем
еще два примера функций принадлежности. Считаем F(x) ≥ 0, x ∈ X.
При выполнении условия U(x0) ≤ C
μ(x,x0) =
0
0
0
( )1 , если ( ) ( ) и ( )
( )
0, если ( ) ( ),
0, если ( )
F x F x F x U x C,
F x
F x F x
U x C.
⎧ − ≤ ≤⎪
⎪⎪ >⎨
⎪ >⎪
⎪⎩
(1)
Если U(x0)>C, то целесообразно воспользоваться функцией принадлежности
μ(x,x0) =
0
0
0
0
0
0 0
( )1 , если ( ) ( ) и ( )
( )
0, если ( ) ( ),
0, если ( )) ( ),
( ) ( )max (1 , ) , если ( ) ( ).
( ) ( ) C
F x F x F x U x C,
F x
F x F x
U x U x
F x U x C C U x U x
F x U x
⎧ − ≤ ≤⎪
⎪
>⎪⎪
⎨ ≥
−
− < <
−⎩
⎪
⎪
⎪
⎪
.
(2)
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 155
Алгоритм МВС, использующий функцию принадлежности (2), „затягивает"
текущие локальные экстремумы в область допустимых решений. Таким обра-
зом, исчезает необходимость поиска начального допустимого решения. В этом
случае достаточно задать любую точку х0∈Х.
Отметим, что признаком окончания вычислительного процесса на некото-
ром шаге n0 при вышесделанных допущениях относительно определенности
функции принадлежности на всем универсуме Х, является выполнение тождест-
ва 0),μ( 0 ≡nxx при всех х∈Х, х≠
0nx . В частности, относительно функций при-
надлежности (1) и (2) имеем: если
)(
)(
1
0xF
xF
− ≤0, то, чтобы выражение
0 0
( ) ( )max 1 ,
( ) ( )
F x U x C
F x U x C
⎛ ⎞−
−⎜ ⎟−⎝ ⎠
было отрицательным или равным нулю, необходи-
мо, чтобы
CxU
CxU
−
−
)(
)(
0
тоже было тождественно равно (или меньше) нуля.
Учитывая вышесделанное допущение U(
0nx )>C, необходимо, чтобы U(x)–C ≤ 0,
т. е. U(x)≤C. Таким образом, тождество 0),μ( 0 ≡nxx является признаком ло-
кального решения.
Вообще говоря, можно доказать, что получить (гарантировано) глобальное
решение можно только в случае, когда носителем является весь универсум Х.
Рассмотрим три задачи.
Задача 1. Найти подмножество m≤n элементов множества А, имеющее наи-
меньшую суммарную связь с другими элементами этого множества; m – фикси-
рованное число.
Задача 2. Найти подмножество m≤n элементов множества А, имеющее наи-
большую суммарную связь всех элементов, принадлежащих этому подмножеству.
Отметим, что задачи 1 и 2 широко применяются при построении прибли-
женных алгоритмов решения основной задачи классификации.
Задача 3. Найти кратчайший путь из точки
0ia в точку 0ja . Исходя из со-
держания задач 1, 2 и 3, их уместно формализировать на множестве Х, которое
является множеством всех подмножеств множества А.
Следовательно, задача 1: найти подмножество х*⊂А, которое предоставляет
минимум функции
F(x)= ∑ ∑
∈ ∈xa x\Aa
ji
i j
a,ad )( , (3)
при условии |x|=m.
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Компьютерная математика. 2009, № 1 156
Примем, что расстояние d(ai, aj) равно элементу αij матрицы A~ или длине
любой цепи, что cоединяет элементы ai и aj . Понятно, что вообще таких „рас-
стояний" будет одно, несколько или связь между элементами ai, aj отсутствует.
В последнем случае точки ai, aj будем считать изолированными и положим
d(ai,aj) = ∞. Отметим также, что матрица A~ не является симметричной, т. е.
αij ≠ αji. Этот факт следует учитывать в последующих вычислениях.
Для наглядности в задачах 1 и 2 допустим, что d(ai,aj) = αij. Суть МВС при
данных допущениях заключается в следующем.
1. Выбираем некоторое подмножество х0 |x0|=m. Определяем все возможные
суммарные связи между элементами этого множества и элементами множества
A\x0 и выбираем наилучший. (Можно определить не все, только некоторые из
них и выбрать „лучший", но это нужно исследовать отдельно, поскольку здесь
МВС будет применяться на двух этапах: выбор окрестности для нахождения х
и выбор „лучшей стратегии" в окрестности). Соответствующее значение целе-
вой функции будет F(x0).
2. Определим функцию принадлежности, от удачного выбора которой бу-
дет зависеть как точность полученного решения, так и время, ограниченное на
его определение. Очевидно, что когда можно предложить функцию принадлеж-
ности „созвучную" задаче (адекватную), то решение задачи будет проходить бо-
лее успешно. Следовательно, руководствуясь этими рассуждениями, предложим
такие функции принадлежности.
Для небольших m, т. е. таких, для которых может быть выполнен полный
перебор
μ(x, x0)=
1 min α
2( 1)
i j
ij
a x a A\xm
∀ ∈ ∀ ∈
− ∑ ∑ , x ∈ Ω(x0). (4)
Для больших m выбираем m0 < m, таких ai ∈ Х, для которых соответствую-
щие αij не меньше заданной величины α(х), и обозначим это множество x(m0).
Тогда
0μm (x, x0)=
0 00 ( ) ( )
1 min α .
2( 1)
i
ij
a x m a A\x mj
m ∀ ∈ ∀ ∈− ∑ ∑ (5)
Областью определения Ω(x0) функции принадлежности μ(x,x0) будем счи-
тать все множество Х подмножеств множества А, или ее часть, например, под-
множество, элементы которого образуются путем замены каждого элемента
ai∈x0 на элемент из множества A\x0. Количество таких точек будет |x0| ⋅ |A\x0|.
Конечно, второй случай при значительных мощностях множества А (следова-
тельно, и множества Х) является более целесообразным с практической точки
зрения. Область определения Ω(x0) вычисляет носитель функции принадлежно-
сти μ(x,x0), если из нее исключить точки, придающие этой функции нулевое зна-
чение. Обозначим его )(Ω~ 0x и будем считать окрестностью точки x0.
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 157
3. Следующий шаг в решении задачи А – нахождение минимума функции
F(x), определенной по формуле (3) в окрестности )(Ω~ 0x . Как следует из опреде-
ления функции F(x), между каждой парой точек ai∈x и aj∈A\x находим кратчай-
шее из возможных расстояний, а затем – сумму всех таких расстояний d(ai, aj).
Напомним, что х принадлежит )(Ω~ 0x . Нахождение кратчайшего расстояния меж-
ду парой точек ai, aj∈A – задача достаточно сложная и этот вопрос дальше будет
рассматриваться отдельно. Пока ограничимся случаем d(ai, aj) = αij. Отдельно рас-
смотрим случай, когда αij (элементы матрицы А) – величины размытые.
4. Полученный в п. 3 элемент, предоставляющий F(x) минимум в окрестно-
сти )(Ω~ 0x обозначим х1 и возвращаемся к п.3, заменив х0 на х1.
5. Вычисление прекращаем, когда полученный на некотором шаге k итера-
ционного процесса, который описывается пп. 3 и 4, элемент xk совпадает с эле-
ментом xk-1, полученным на предыдущем витке итерации, или решение xk удов-
летворяет требованиям пользователя.
Заметим, что в случае, когда вычислительный процесс прекратился, однако
полученное решение не удовлетворяет, можно вычисление продолжить, изменив
соответствующим образом функцию принадлежности.
Как вытекает с вышеупомянутого, элемент х∈ )(Ω~ 0x принадлежит размы-
тому множеству )(Ω~ 0x и характеризуется функцией принадлежности μ(x, x0).
Следовательно, F(x, x0) как функция от размытой величины будет также размы-
той величиной с определенной функцией принадлежности ν(F(х, х0), μ(x, х0)),
которая определяется соответственно принципу обобщения [4].
Задачу 1 рассмотрим в двух аспектах: матрица
A~ =
7
6
5
4
3
2
1
0 0,3 0,8 0,6 0,5 0,8 0,1
0,5 0 0,4 0,2 0,7 0,3 0,1
0,7 0,9 0 0,1 0 0.3 0,5
0,1 0,4 0,6 0 0,9 0,1 0,2
0,7 0 0,3 0 0 0,4 0,1
0,2 0,1 0 0,1 0,8 0 0,5
0,1 0,2 0,3 0,6 0,4 0,3 0
будет представлена четкими числами и размытыми треугольными числами. Для
четкой матрицы A~ используем классический вариант МВС и вариант МВС,
который определяется функцией принадлежности
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Компьютерная математика. 2009, № 1 158
μ(х,х0) = 0 0
0
1 minα , , \ ( , ), если Ω( ),
0, если Ω( )
ij i ja x a A x x x x
x x
⎧ − ∈ ∈ ∈⎪
⎨
∈⎪⎩
при μ(х, х0) > 0,9.
Данные расчетов относительно первых двух случаев представлены в табл. 1, 2.
Третий случай рассмотрен детально.
ТАБЛИЦА 1. Решение задачи 1 классическим вариантом МВС
Окрестность Но-
мер
ите-
рации
k
x0
)(Ω~ 0x
F(x*)
*
0x
1
2
(a1,a5,a6)
(a1,a5,a4)
(a7,a5,a6)
{(a1,a5,a6), (a2,a5,a6), (a1,a2,a6), (a1,a5,a2),
(a3,a5,a6), (a1,a3,a6), (a1,a5,a3), (a4,a5,a6),
(a1,a4,a6), (a1,a5,a4), (a7,a5,a6), (a1,a7,a6),
(a1,a5,a7)}
{(a2,a5,a4), (a1,a2,a4), (a3,a5,a4),(a1,a3,a4),
(a1,a5,a6), (a7,a5,a4), (a1,a7,a4), (a7,a2,a4),
(a7,a3,a6), (a7,a5,a6), (a7,a4,a6)}*)
3,2
3,2
(a1,a5,a4)
(a7,a5,a6)
(a1,a5,a4)
(a7,a5,a6)
ТАБЛИЦА 2. Данные вычислений по МВС при μ(х,х0) =
⎪⎩
⎪
⎨
⎧
∈
∈−
)(Ω~ 0,
)(Ω~ ,min1
0
0
xx
xxαij
при μ(х,х0) ≥ 0,9
Окрестность Номер
итера-
ции k
x0
)(Ω~ 0x
F(x*)
*
0x
1
2
(a1,a 5,a6)
(a1,a5,a4)
(a7,a5,a6)
{(a1,a5,a6), (a2,a5,a6), (a1,a2,a6), (a3,a5,a6),
(a1,a3,a6), (a1,a5,a3), (a4,a5,a6), (a1,a4,a6),
(a1,a5,a4), (a7,a5,a6), (a1,a7,a6), (a1,a5,a7),
(a1,a5,a4)}
{(a2,a5,a4), (a1,a2,a4), (a3,a5,a4),(a1,a3,a4),
(a1,a5,a6), (a7,a5,a4), (a1,a7,a4),(a7,a2,a4),
(a7,a4,a6)}*)
3,2
3,2
(a1,a5,a4)
(a7,a5,a6)
(a7,a5,a6)
В прикладных задачах часто возникает ситуация, когда элементы матрицы
A~ являются размытыми числами. Например, задача классификации, рассмот-
ренная в [2], – подтверждение вышеизложенного, а задача 3 может быть рас-
смотрена как „стилизованная” задача классификации.
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 159
Следовательно, пусть элементы матрицы A~ – нечеткие числа. Таким обра-
зом, значение целевого функционала и ограничивающих функционалов тоже
являются нечеткими, т. е. относительно задачи 1 функционал
F(x)= ∑ ∑
∈∀ ∈∀xa xAa
lk
kl \
α (6)
является нечетким числом, а ограничивающее условие |x|=m будет звучать так:
„|x| приблизительно равен m", или, уточнено „|x| не более m±k", где k – целое
число, заданное ОПР.
Будем считать что αlk является нечетким треугольным числом, т. е. таким,
у которого график функции принадлежности приобретает вид треугольника
с ядром core(αlk)= αlk, где αlk соответствующий четкий элемент таблицы A~ ,
а носитель состоит из двух равных отрезков длиной βlk, т.е. boun(αlk,)= βlk
(см. рис. 1, 2, а также [4]).
Примем βlk = 0,1αlk. При таких условиях для (6) ядро core(F(x)) =
= ∑ ∑
∈∀ ∈∀
⋅
xa xAak
lk
l \
α , а носитель supF(x)=[ ∑ ∑
∈∀ ∈∀
⋅
xa xAa
lk
kl \
0,9α , ∑ ∑
∈∀ ∈∀
⋅
xa xAa
lk
kl \
1,1α ],
l = 1, 2, . . . , |x|, k=1, 2, … , A\|x|.
Поскольку треугольное нечеткое число является частным случаем нечеткого
числа (L–R)-типа, то арифметические операции над треугольными числами
iaΔ =(ai, αi, βi), I = 1, 2 осуществляются как над нечеткими числами (L–R)-типа:
1
Δa + 2
Δa =< c, δ, γ), где c = a1 + a2, δ = α1 + α2, γ = β1 + β2, 1
Δa – 2
Δa = < c, δ, γ),
где c = a1 – a2, δ = α1 + β2, γ = β1 + α2.
Операции умножения и деления нечетких чисел (L–R)-типа определяются
при выполнении некоторых дополнительных условий.
Расширенный максимум треугольных чисел 1
Δa і 2
Δa характеризуется таки-
ми параметрами: а=max{a1,a2}, α = a-max{a1–α1, a2–α2}, β=max{a1+β1, a2+β2}–a.
Расширенный минимум треугольных чисел 1
Δa , 2
Δa : а=min{a1,a2},
α = a–min{a1–α1, a2–α2}, β=min{a1+β1, a2+β2}–a.
В случае k чисел, iaΔ , i=1, . . . , k, имеем: для расширенного максимума
а=max{a1,a2, . . .,k}, α = a-max{a1–α1, a2–α2, . . ., ak–αk}, β=max{a1+β1, a2+β2, . . ,
. . . , ak+αk}–a; для расширенного минимума а=min{a1,a2, . . . ,k}, α =
= a–min{a1 – α1, a2 –. . .α2, . . . , ak–αk}, β = min{a1+β1, a2+β2, . . . , ak+αk} – a.
В частности, значение целевой функции F(x) при x = x0=(a1, a5, a6)., согласно
допущениям, сделанным в этом примере, о размытости чисел αij матрицы A~ ,
является треугольным размытым числом.
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Компьютерная математика. 2009, № 1 160
μ(s) μ(s)
1 1
0
⋅
α lk – βlk lkα
⋅
lkα
⋅
+βlk s 0 1 2 3 4 5 s
3,24 3,6 3,96
РИС. 1. Пример нечеткого РИС. 2. Треугольное размытое число
треугольного числа Δ
1F (x0) к примеру 3
Δ
1F (x0)= (α12+α13+α14+α17) + (α52+α53+α54+α57) + (α62+α63+α64+α67), которое
определяется параметрами а(х0) = (
⋅
α 12+
⋅
α 13+
⋅
α 14+
⋅
α 17) + (
⋅
α 52+
⋅
α 53+
⋅
α 54+
⋅
α 57) +
+(
⋅
α 62+
⋅
α 63+
⋅
α 64+
⋅
α 67) = (0,5+0,1+0,2+0,1) + (0+0,3+0,6+0,8) + (0,3+0+0,4+0,3)=
= 0,9+1,7+1,0=3,6;
γ(x0)= δ(x0)= (0,1
⋅
α 12+0,1
⋅
α 13+0,1
⋅
α 14+0,1
⋅
α 17) + (0,1
⋅
α 52+0,1
⋅
α 53+0,1
⋅
α 54+0,1
⋅
α 57) +
+ (0,1
⋅
α 62+0,1
⋅
α 63+0,1
⋅
α 64+0,1
⋅
α 67)=0,1 а(х0) =0,1⋅3,6=0,36.
При этих допущениях проследим расчеты примера 1. Заметим, что значение
F(x) будет нечетким числом. Чтобы не осложнять расчетов, оставим число m
четким. Допущение о нечеткости m не изменит существенно алгоритма решения
задачи, однако несколько осложнит его.
Следовательно, как и в примерах 1, 2 положим x0 = (a1, a5, a6); A\x0 = (a2, a3,
a4, a7); n = 7; m = 3.
)(Ω~ 0x ={(a1, a5, a6); (a2, a5, a6); (a1, a2, a6); (a1, a5, a2); (a3, a5, a6); (a1, a3, a6);
(a1, a5, a3); (a4, a5, a6); (a1, a4, a6); (a1, a5, a4); (a 7, a 5, a 6); (a 1, a 7, a 6); (a 1, a 5, a 7)}.
Аналогично для всех других точек окрестности )(Ω~ 0x , воспользовавшись
вышепроведенными вычислениями, имеем
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 161
FΔ( 1
0x )= FΔ(a2 ,a5, a6) = <4,5; 0,45; 0,45>; FΔ( 2
0x ) =FΔ(a1, a2, a6) = <4,1; 0,41;0,41>;
FΔ( 3
0x )=FΔ(a1, a5, a2 = <4,2; 0,42; 0,42>; FΔ( 4
0x )=FΔ(a3 , a5, a6) = <5,5; 0,55; 0,55>;
FΔ( 5
0x )=FΔ(a1, a3, a6) = <5,4; 0,54; 0,54>; FΔ( 6
0x )=FΔ(a1, a5, a3) = <5,6; 0,56; 0,56>;
FΔ( 7
0x )=FΔ(a4, a5, a6) = <3,5; 0,35; 0,35>; FΔ 8
0( )x =FΔ(a1, a4, a6) = <3,5; 0,35; 0,35>;
FΔ( 9
0x )=FΔ(a1, a5, a4) = <3,2; 0,32; 0,32>; FΔ( 10
0x )=FΔ(a7, a5, a6) = <3,2; 0,32; 0,32>;
FΔ( 11
0x ) = FΔ(a1, a7, a6) = <4,6; 0,46; 0,46>; FΔ( 12
0x ) = FΔ(a1, a5, a7); μ( 12
0x ) =
= <3,7; 0,37; 0,37>.
В случае нечетких данных матрицы A~ получим
0Ω
min
x x( )∈
FΔ(x) = <3,2; 3,2–3,2+032; 3,2+0,32–3,2> = <3,2;0,32;0,32>.
Таким образом, решением задачи 1 при нечетких значениях элементов мат-
рицы A~ и других допущениях, сделанных выше, точками локального экстрему-
ма в окрестности )(Ω~ 0x остаются множества 9
0x ={a1, a5, a4}, 10
0x ={a7, a5, a6}
со значениями целевой функции FΔ( 9
0x ) = FΔ( 10
0x ) = < 3,2; 0,32; 0,32>.
Аналогичные действия проводятся на следующих итерациях МВС.
Если для определения окрестности воспользоваться функцией принадлежности,
например,
μ(x,x0)=
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎨
⎧
∈≤
∈
∈
∈
∈
∈
∈
, )(Ω~ ,5,0,αmax если ,0
, )(Ω~ если ,0
),(Ω~ ,αmax
0
\
0
0
\
xx
xx
xx
ij
xAa
xa
ij
xAa
xa
j
i
j
i
то в этом случае сокращается перебор в окрестности )(Ω~ 0x . Решение остается
таким, как и в предыдущих случаях.
В случае треугольных нечетких чисел вычисления значительно упрощаются
по сравнению, например, с нечеткими числами, представленными колоколооб-
разными функциями принадлежности. В связи с этим следует заметить также,
что треугольные нечеткие числа часто используются при решении практических
нечетких задач.
Отметим также основные положительные моменты введения расширенного
понятия окрестности:
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Компьютерная математика. 2009, № 1 162
1) в случае четкой функции принадлежности, как функции характеристиче-
ской, получим возможность разработки схем новых алгоритмов;
2) в случае четкой функции принадлежности со значениями в интервале
[0,1], кроме позитива, отмеченного в п. 1), получаем возможность сокращения
перебора значений критерия в окрестности;
3) если функция принадлежности является нечеткой, то, кроме 1) и 2), зна-
чительно расширяется спектр практических задач, которые можно решить МВС.
Представленный в этой работе вариант МВС при надлежащем определе-
нии функции принадлежности может обобщать другие известные методы.
Например, пусть задан ряд функций, удовлетворяющих определению функций
принадлежности
μ(x,x0), μ(x,x1),…,μ(x,xk),… ,
где x∈X; xi∈X, i=0,1,..,k являются параметрами. Пусть основной вариант МВС
действует в окрестностях Ω(x0), Ω(x1), . . . , Ω(xk), где xi – локальные решения
определенной задачи в окрестности Ω(xi-1). Обозначим Si=Ω(x0)∪Ω(x1) ∪ . . . ∪
∪ Ω(xi-1) ∪ Ω(xi). Тогда функция принадлежности ν(x,xi), что определяет окрест-
ности )(Ω~ ix , примет вид
ν(x,xi)=
⎩
⎨
⎧
∈
∈
. если 0,
, если ),,μ(
i
ii
Sx
Sxxx
Таким образом определен один из вариантов метода запретов [5].
Заключение. Так как большинство практических задач формулируются в
нечеткой математической среде, то разработка нечетких алгоритмов для их
решения весьма целесообразна в связи с тем, что переход к четким моделям при-
водит к частичной потере информации, а это отрицательно сказывается на точ-
ности полученных решений. С другой стороны, многие нечеткие задачи вообще
не могут быть представлены в четком виде. Наглядным примером может слу-
жить одна из задач, возникающих в растениеводстве [6].
І.М. Парасюк, М.Ф. Каспшицька
РОЗМИТИЙ АЛГОРИТМ МЕТОДУ ВЕКТОРА СПАДУ ДЛЯ РІШЕННЯ
ОПТИМІЗАЦІЙНИХ ЗАДАЧ НА ВИБОРКАХ
Запропоновано клас нечітких алгоритмів методу вектора спаду, принципова відмінність яко-
го полягає у представленні околів, в яких діє метод, системою розмитих множин (околів), що
значно розширило область застосування алгоритмів. Отримані результати досліджень щодо
конкретного класу задач комбінаторної оптимізації – оптимізаційних задач на виборках.
РАЗМЫТЫЙ АЛГОРИТМ МЕТОДА ВЕКТОРА СПАДА ДЛЯ РЕШЕНИЯ …
Компьютерная математика. 2009, № 1 163
I.N. Parasyuk, M.F. Kаspschicka
FUZZY ALGORITHM FOR SLUMP-VECTOR METHOD FOR SOLVING OPTIMIZATION
PROBLEMS ON SAMPLES
A class of fuzzy algorithms for slump-vector method is proposed. The main feature of these algo-
rithms is the representation of the neighborhoods of method's operation by the system of fuzzy sets
(neighborhoods), that considerably extends the range of application of the algorithms. The results of
investigation of a particular class of combinatorial optimization problems, i.e., sample optimization
problems, are presented.
1. Парасюк И.Н., Каспшицкая М.Ф. О развитии метода вектора спада на случай раз-
мытых окрестностей // Компьютерная математика. – 2008. – № 2. – С . 145–155.
2. Каспшицкая М.Ф., Парасюк И.Н. О некоторых классах размытых задач класси-
фикации: формализация, методы решения // Компьютерная математика. – 2004. –
№ 1. – С. 73–90.
3 Каспшицкая М.Ф., Глушкова В.В. О формализации некоторых задач выбора и
принятия решений в математической среде // Компьютерная математика. – 2006.
– № 2. – С. 19–31.
4. Леоненков А.В. Нечеткое моделирование в среде MATLAB u fuzzy TECH. –
Санкт-Петербург: БХВ-Петербург, 2005. – 736 с.
5. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации.–Киев: Наук. думка,
2003. – 259 с.
6. Сыч З., Бобось И., Гопчак В. Как правильно выбрать сорт // Овощеводство. –
2008. – № 4. – С. 18–23; № 5. – С. 12–17.
Получено 26.11.2008
Îá àâòîðàõ:
Парасюк Иван Николаевич,
член-корреспондент НАН Украины, заведующий отделом
Института кибернетики имени В.М. Глушкова НАН Украины,
E-Mail: ivpar1@i.com.ua
Каспшицкая Мария Фадеевна,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
|
| id | nasplib_isofts_kiev_ua-123456789-6227 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-02T02:47:05Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Парасюк, И.Н. Каспшицкая, М.Ф. 2010-02-19T14:56:01Z 2010-02-19T14:56:01Z 2009 Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 1. — С. 152-163. — Бібліогр.: 6 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/6227 519.21 Предложен класс нечетких алгоритмов метода вектора спада. Принципиальное отличие их состоит в представлении окрестностей, в которых действует метод, системой размытых множеств (окрестностей), что значительно расширило область применения алгоритмов. Приведены результаты исследований относительно конкретного класса задач комбинаторной оптимизации – оптимизационных задач на выборках. Запропоновано клас нечітких алгоритмів методу вектора спаду, принципова відмінність якого полягає у представленні околів, в яких діє метод, системою розмитих множин (околів), що значно розширило область застосування алгоритмів. Отримані результати досліджень щодо конкретного класу задач комбінаторної оптимізації – оптимізаційних задач на виборках. A class of fuzzy algorithms for slump-vector method is proposed. The main feature of these algorithms is the representation of the neighborhoods of method's operation by the system of fuzzy sets (neighborhoods), that considerably extends the range of application of the algorithms. The results of investigation of a particular class of combinatorial optimization problems, i.e., sample optimization problems, are presented. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теория и методы оптимизации Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках Розмитий алгоритм методу вектора спаду для рішення оптимізаційних задач на виборках Fuzzy algorithm for slump-vector method for solving optimization problems on samples Article published earlier |
| spellingShingle | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках Парасюк, И.Н. Каспшицкая, М.Ф. Теория и методы оптимизации |
| title | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| title_alt | Розмитий алгоритм методу вектора спаду для рішення оптимізаційних задач на виборках Fuzzy algorithm for slump-vector method for solving optimization problems on samples |
| title_full | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| title_fullStr | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| title_full_unstemmed | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| title_short | Размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| title_sort | размытый алгоритм метода вектора спада для решения оптимизационных задач на выборках |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6227 |
| work_keys_str_mv | AT parasûkin razmytyialgoritmmetodavektoraspadadlârešeniâoptimizacionnyhzadačnavyborkah AT kaspšickaâmf razmytyialgoritmmetodavektoraspadadlârešeniâoptimizacionnyhzadačnavyborkah AT parasûkin rozmitiialgoritmmetoduvektoraspadudlâríšennâoptimízacíinihzadačnaviborkah AT kaspšickaâmf rozmitiialgoritmmetoduvektoraspadudlâríšennâoptimízacíinihzadačnaviborkah AT parasûkin fuzzyalgorithmforslumpvectormethodforsolvingoptimizationproblemsonsamples AT kaspšickaâmf fuzzyalgorithmforslumpvectormethodforsolvingoptimizationproblemsonsamples |