О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада
Рассмотрены вопросы модификации нечеткого метода вектора спада для решения многокритериальной оптимизационной задачи комбинаторного типа для случая разнородных исходных данных. Основное внимание уделено изучению метода, его частичных реализаций с учетом вида используемых функций принадлежности. Для...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84558 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 2. — С. 150-158. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84558 |
|---|---|
| record_format |
dspace |
| spelling |
Парасюк, И.Н. Каспшицкая, М.Ф. 2015-07-10T11:36:05Z 2015-07-10T11:36:05Z 2009 О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 2. — С. 150-158. — Бібліогр.: 4 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84558 519.21 Рассмотрены вопросы модификации нечеткого метода вектора спада для решения многокритериальной оптимизационной задачи комбинаторного типа для случая разнородных исходных данных. Основное внимание уделено изучению метода, его частичных реализаций с учетом вида используемых функций принадлежности. Для иллюстрации используется оптимизационная задача на выборках с заданным числом элементов. Розглянуті питання модифікації нечіткого методу вектора спаду для розв’язування багатокритеріальної оптимізаційноої задачі комбінаторного типу для випадку різнорідних вихідних даних. Основна увага приділена вивченню методу, його часткових реалізацій з урахуванням вигляду використовуваних функцій приналежності. Для ілюстрації використовується оптимізаційна задача на вибірках із заданим числом елементів. Modification issues of slump-vector fuzzy method for combinatorial-type multicriterion optimization problem in the case of heterogeneous basic data are considered. Main attention is devoted to the study of the method and its partial implementations taking into account a type of membership functions used. For illustration purposes, the optimization problem on samples with predefined number of elements is used. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада Про розв’язування комбінаторної багатокритеріальної оптимізаційної задачі нечітким методом вектора спаду On a solution to combinatorial multicriterion optimization problem by slump-vector fuzzy method Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| spellingShingle |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада Парасюк, И.Н. Каспшицкая, М.Ф. Теория и методы оптимизации |
| title_short |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| title_full |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| title_fullStr |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| title_full_unstemmed |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| title_sort |
о решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада |
| author |
Парасюк, И.Н. Каспшицкая, М.Ф. |
| author_facet |
Парасюк, И.Н. Каспшицкая, М.Ф. |
| topic |
Теория и методы оптимизации |
| topic_facet |
Теория и методы оптимизации |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про розв’язування комбінаторної багатокритеріальної оптимізаційної задачі нечітким методом вектора спаду On a solution to combinatorial multicriterion optimization problem by slump-vector fuzzy method |
| description |
Рассмотрены вопросы модификации нечеткого метода вектора спада для решения многокритериальной оптимизационной задачи комбинаторного типа для случая разнородных исходных данных. Основное внимание уделено изучению метода, его частичных реализаций с учетом вида используемых функций принадлежности. Для иллюстрации используется оптимизационная задача на выборках с заданным числом элементов.
Розглянуті питання модифікації нечіткого методу вектора спаду для розв’язування багатокритеріальної оптимізаційноої задачі комбінаторного типу для випадку різнорідних вихідних даних. Основна увага приділена вивченню методу, його часткових реалізацій з урахуванням вигляду використовуваних функцій приналежності. Для ілюстрації використовується оптимізаційна задача на вибірках із заданим числом елементів.
Modification issues of slump-vector fuzzy method for combinatorial-type multicriterion optimization problem in the case of heterogeneous basic data are considered. Main attention is devoted to the study of the method and its partial implementations taking into account a type of membership functions used. For illustration purposes, the optimization problem on samples with predefined number of elements is used.
|
| issn |
ХХХХ-0003 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84558 |
| citation_txt |
О решении комбинаторной многокритериальной оптимизационной задачи нечетким методом вектора спада / И.Н. Парасюк, М.Ф. Каспшицкая // Компьютерная математика. — 2009. — № 2. — С. 150-158. — Бібліогр.: 4 назв. — рос. |
| work_keys_str_mv |
AT parasûkin orešeniikombinatornoimnogokriterialʹnoioptimizacionnoizadačinečetkimmetodomvektoraspada AT kaspšickaâmf orešeniikombinatornoimnogokriterialʹnoioptimizacionnoizadačinečetkimmetodomvektoraspada AT parasûkin prorozvâzuvannâkombínatornoíbagatokriteríalʹnoíoptimízacíinoízadačínečítkimmetodomvektoraspadu AT kaspšickaâmf prorozvâzuvannâkombínatornoíbagatokriteríalʹnoíoptimízacíinoízadačínečítkimmetodomvektoraspadu AT parasûkin onasolutiontocombinatorialmulticriterionoptimizationproblembyslumpvectorfuzzymethod AT kaspšickaâmf onasolutiontocombinatorialmulticriterionoptimizationproblembyslumpvectorfuzzymethod |
| first_indexed |
2025-11-25T23:32:44Z |
| last_indexed |
2025-11-25T23:32:44Z |
| _version_ |
1850587189526659072 |
| fulltext |
Рассмотрены вопросы модифика-
ции нечеткого метода вектора
спада для решения многокритери-
альной оптимизационной задачи
комбинаторного типа для случая
разнородных исходных данных. Ос-
новное внимание уделено изучению
метода, его частичных реализаций
с учетом вида используемых функ-
ций принадлежности. Для иллюст-
рации используется оптимизацион-
ная задача на выборках с заданным
числом элементов.
© И.Н. Парасюк,
М.Ф. Каспшицкая, 2009
ÓÄÊ 519.21
È.Í. ÏÀÐÀÑÞÊ, Ì.Ô. ÊÀÑÏØÈÖÊÀß
Î ÐÅØÅÍÈÈ ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÎÍÍÎÉ ÇÀÄÀ×È
ÍÅ×ÅÒÊÈÌ ÌÅÒÎÄÎÌ
ÂÅÊÒÎÐÀ ÑÏÀÄÀ
Введение. Вопросы формализации и реше-
ния комбинаторных оптимизационных задач
в размытых информационных пространствах
в настоящее время остаются весьма актуаль-
ными. Несмотря на богатый арсенал методов,
накопленный в данной области, дальнейшие
исследования в этом направлении представ-
ляются чрезвычайно важными. Среди таких
методов, в частности, следует отметить ме-
тод вектора спада (МВС) [1], позволяющий
определить локальные решения задачи даже
в весьма сложных практических случаях. На-
копление опыта применения этого метода
для различных информационных сред явля-
ется не только полезным делом, но и весьма
желательным. Собственно поэтому, проводя
исследования в данном направлении, авто-
рами настоящей статьи предложены различ-
ные нечеткие варианты метода вектора спа-
да, основанные на понятии размытой окрест-
ности, для решения однокритериальных оп-
тимизационных задач [2, 3].
В настоящей работе рассматривается во
многом более сложная задача – многокрите-
риальная комбинаторная оптимизационная
задача для случая разнородных информаци-
онных данных, представленных для ее реше-
ния. Предлагаются различные модификации
нечеткого варианта метода вектора спада,
описаны его соответствующие версии для
определения множества Парето.
150 Компьютерная математика. 2009, № 2
О РЕШЕНИИ КОМБИНАТОРНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ …
Постановка задачи. Пусть даны множество А элементов, |А| = n, и множе-
ство признаков B, |B|=k. Причем, относительно множества В заметим, что оно
состоит из объектов разной природы: четких чисел, нечетких чисел, булевых
переменных либо лингвистических переменных.
И пусть каждому из элементов аі, і=1, . . ., n множества А поставлен в соот-
ветствие кортеж из k объектов, что принадлежат множеству В. Таким образом,
множеству А соответствует матрица
ijαA ⎡ ⎤= ⎣ ⎦ ,
где αij – признак j Bβ ∈ элемента аі; представленный объектом одного из четы-
рех видов; например, в работе [3] это было четкое или нечеткое число постоян-
ного наименования для всей таблицы A~ .
Суть задачи. состоит в том, чтобы выбрать из множества А подмножество
А0⊇А из m элементов таким образом, чтобы достичь минимума функционалов
Fr(x), r = 1,2 . . ., r0 при выполнении условия U(x)≤C, C=const.
Формально имеем обобщение задач 1, 2 из [3]. Отличие заключается в мно-
гокритериальности задачи и разнородности признаков.
Естественно считать, что каждый из критериев отдельно определен на дан-
ных одного типа: либо на четких числах; либо на размытых числах; либо на бу-
левых переменных, либо на лингвистических переменных.
Для простоты представим множество В как объединение множеств B Bs,
s=1, 2, 3, 4, причем Bu B ∩ B Bt = ∅, u, t = 1, 2, 3, 4, u≠t. Считаем, что В1 включает в
себя те признаки, которые выражаются четкими числами; В2 – признаки, кото-
рые выражаются нечеткими числами; В3 – признаки, выраженные булевыми пе-
ременными; В4 – лингвистическими переменными; x∈X, по-прежнему, является
выборкой m элементов из множества А, Х – множество всех таких выборок.
Далее, F1(x)=F1(x, B B1), F2(x) = F2(x, B2B ), F3(x) = F3(x, B B3), F4(х) = F4(x, B4B ).
Аналогично представляется U(х).
Метод вектора спада в этом случае сводится к построению последователь-
ности приближенных множеств Парето. Следовательно, выбираем, как и в [2],
начальное приближение x0∈X. Задаем функцию принадлежности для точек из
множества Ω(x0), например,
μ(x, x0) = 01, если ( ) ( ), 1, 2, 3, 4, ( ) ,i iF x F x i U x C< = ≤
μ(x, x0) = 0, если хотя бы одно из вышеприведенных неравенств не выполняется.
Рассмотрим этот процесс более детально. Как видно, согласно матрице ,A
некоторому х, равному, например, (а1, а4, а6), будет соответствовать матрица
A~ (х)=
11 12 1
41 42 4
61 62 6
α α , ...,α
α α , ...,α
α α , ...,α
n
n
n
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
.
Компьютерная математика. 2009, № 2 151
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Если признаки упорядочены согласно множеств В1, В2, В3, В4, т. е. столбцы
матрицы A~ описывают сначала группу признаков, что принадлежит множеству
В1, потом группу признаков, что принадлежат множеству В2 и т.д., то матрица
A~ (х) схематически будет представлена блоками Вi(х):
)(~ xA =[В1(x), В2(x), В3(x), В4(x)].
В этих предположениях представляем далее задачу как поиск такого множе-
ства х*∈Х мощности m, на котором достигаются минимумы на множестве Х для
функций F1(x) = F1(x, B B1(x)), . . ., F4(x) = F4(x, B4B (x)) при условии U(x) ≤ C.
Допустим, что для числового определения Fi(x) можно взять расстояние
между соответствующими αij ∈BBr, r = 1, 2, 3, 4. Тогда
D(x1,x2)= ( )
1 2
,
i j
i j
a x a x
d a a
∈ ∈
∑ ∑ , где ( ) ( ), ,k ljd al a d kj= α α∑
в зависимости от того, какому из подмножеств принадлежат 1 2 3, ( , ,lj kj B B Bα α
или 4 )B определяем соответствующие расстояния:
для четких чисел как суммарную абсолютную величину разницы четких чисел;
для нечетких чисел как суммарную абсолютную величину разницы не-
четких чисел;
для булевых переменных – как расстояние Хемминга;
для лингвистических переменных – устанавливаются на основе экспертных
оценок.
Таким образом,
F1(x) выражается в четких числах,
F2(x) выражается в нечетких числах,
F3(x) выражается в целых числах,
F4(x) выражается в нечетких приближенных числах.
Алгоритм 1. Задав определенный вид функций принадлежности (пока не
вникая в ее суть), формируем окрестность Ω~ (х,x0). Из точек этой окрестности
образуем множество Ω~ 0(х,x0), для которого
Fi(x, BBі (x)) ≤ Fi (x0, Bi B (x0)), i = 1, 2, 3, 4, х∈Ω
~ (х,x0).
Ясно, что Ω~ (х, x0) ⊇ Ω~ 0(х, x0). Множество Ω~ 0(х, x0) является пересечением
четырех подмножеств окрестности Ω
~ (х, x0), соответственно для которых
Fi (x ,Bі (x)) ≤ Fi (x0, Bi (x0)), i = 1, 2, 3, 4. В каждом из этих подмножеств найдем
точки , , , , что дают минимум соответствующих функций
F
1
0x 2
0x 3
0x 4
0x
i (x, BBі (x)).
Компьютерная математика. 2009, № 2 152
О РЕШЕНИИ КОМБИНАТОРНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ …
Далее, строим окрестности этих точек (опять посредством соответствующих
функций принадлежности), находим их пересечение и на этом пересечении точ-
ки, что предоставляют минимум соответствующим целевым функциям. Эти дей-
ствия можно продолжить и дальше в виде итераций, пока пересечение множеств
не будет постоянным на двух соседних шагах итераций, или приближенное ре-
шение, найденное на определенном шаге итерации, удовлетворит требованиям
для принятия решений. Таким образом, наши действия можно интерпретировать
как нахождение приближенного множества Парето: в этом случае на некотором
шаге s итерационного процесса Ω~ s(х, xs) = ∅. Приближенным множеством Па-
рето считаем Ω~ s-1(х, xs-1).
Для последующих обобщений введем два определения.
Определение 1. Размытая окрестность четкого множества D ⊂ X задается
с помощью функции принадлежности Ф(х)= ),(max yx
Dy
ϕ
∈
, x∈X, где ϕ(x,y) – функ-
ция принадлежности х при фиксированном y∈D.
Определение 2. Размытая окрестность размытого множества D, что опреде-
лена с помощью функции принадлежности μ(y) на универсуме X, задается
с помощью функции принадлежности ℘(x)= max ( , ( ))
y D
x y
∈
ω μ , где ω(x,μ(y)) –
функция принадлежности х при фиксированном y.
Отметим, что нечеткую окрестность можно трактовать как частичный слу-
чай бинарного нечеткого отношения на универсумах X1=X\D, X2=D [4].
Пользуясь этими определениями, сформируем вариант МВД для решения
многокритериальной оптимизационной задачи. Напомним, что решением мно-
гокритериальной минимизационной задачи служит такое множество Π⊂X на
котором невозможно уменьшение одного из критериев без увеличения хотя бы
одного из других критериев.
Общая схема МВС в рассматриваемом случае выглядит следующим образом:
Алгоритм 2.
1. Выбираем произвольно (или руководствуясь определенными рассужде-
ниями) множество D0 – начальное множество. На множестве D0 находим множе-
ство Парето Π0.
2. С помощью заданной функции принадлежности ϕ(x, y) x∈X, y∈Π0 на-
ходим окрестность D и в ней решаем рассматриваемую многокритериальную
задачу; находим таким образом множество Парето Π1.
3. Полученное множество Парето П1 выбираем центром „окрестности" D2,
и, как выше, рассматриваем в этой окрестности многокритериальную задачу;
решение ее обозначим Π2.
Итерационный процесс продолжаем, пока на некоторой итерации s не ока-
жется, что Πs=Πs-1, или полученное приближенное решение не удовлетворит
требованию ОПР.
Компьютерная математика. 2009, № 2 153
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
Отметим что основными моментами метода есть: задание функции принад-
лежности (в данном случае функции ϕs(x, y) x∈X, y∈Ds, s=1, . . . ,) и способа на-
хождения локального решения (в данном случае Πs).
Относительно выбора функции принадлежности следует заметить, что от
удачного выбора ее зависит успешность решения задачи. Этот вопрос является
слишком важным и нуждается в детальном изучении, которому будет посвящен
отдельный раздел данной работы.
Не менее важным является способ нахождения локальных решений задачи
в подмножестве Πs окрестности Ds. В частности, в случае дискретной много-
критериальной задачи и при условии незначительной мощности Ds, можно вос-
пользоваться методом полного перебора.
Например, пусть D = {x1, x2, . . ., x6}. Согласно этому получаем числовые по-
следовательности Fi (xj) = Fi (xj, BBi (xj)), i = 1, 2, 3, 4; j = 1, 2, …, 6, которые упо-
рядочены по убыванию. Удобно воспользоваться табличной записью, где первой
позицией в строке является наименование критерия, а все другие – аргументы
соответствующих значений критерия, упорядоченных по убыванию (табл. 1).
ТАБЛИЦА 1. Критерии и их аргументы
F1 x1 x3 x4 x5 x2 x6
F2 x2 x4 x3 x5 x1 x6
F3 x4 x1 x5 x6 x3 x2
F4 x1 x2 x4 x3 x5 x6
Далее, в табл. 2 запишем „динамику" спада значений критериев. К примеру,
запись 1→4 в первой строке второго столбца означает, что F1(x3) ≥ ≥ F1 (x4) и т. д.
Такое упорядочение в дальнейшем будет использовано для построения прибли-
женного множества Парето, а также может быть применимо для определения
множества «перспективных точек», т.е. множества точек, в которых возможно
совокупное уменьшение всех частных критериев.
ТАБЛИЦА 2. Динамика спада значений критериев
F1 1→3 1→4 1→5 1→2 1→6 3→4 3→5 3→2
3→6 4→5 4→2 4→6 5→2 5→6 2→6
F2 2→4 2→3 2→5 2→1 2→6 4→3 4→5 4→1
4→6 3→5 3→1 3→6 5→1 5→6 1→6
F3 4→1 4→5 4→6 4→3 4→2 1→5 1→6 1→3
1→2 5→6 5→3 5→2 6→3 6→2 3→2
F4 1→2 1→4 1→3 1→5 1→6 2→4 2→3 2→5
2→6 4→3 4→5 4→6 3→5 3→6 5→6
Компьютерная математика. 2009, № 2 154
О РЕШЕНИИ КОМБИНАТОРНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ …
Исходя из схематических записей табл. 2, приходим к следующим выводам:
в точке х1 уменьшаются функции F2 и F3;
в точке х2 уменьшаются функции F1 и F3;
в точке х3 уменьшаются функции F1, F2, F3 и F4;
в точке х4 уменьшаются функции F1, F2 и F4;
в точке х5 уменьшаются функции F1, F2, F3 и F4;
в точке х6 уменьшаются функции F1, F2, F3 и F4.
Таким образом, точками, в которых уменьшаются все критерии, есть
х3, х5, х6. Приближенным множеством Парето является множество {x1, x2, x4}.
О функциях принадлежности. Пусть задано k критериев (в данном случае
k = 4) Fj (x), j = 1, 2 . . ., k, x∈X. Для решения задачи, согласно вышеизложен-
ного алгоритма 1, задано k функций принадлежности μ1(x), μ2(x),…,μk(x),
с помощью которых строим нечеткие окрестности для нахождения локальных
минимумов соответствующих критериев. Для простоты будем считать, что
способ вычисления функции μj(x), j=1,2,…,k, не изменяется в течение вычисли-
тельного процесса и значения μj(x) на шаге итерации i зависят от xi, т. е. μj (x) =
= μj (x, xi). Возникает практический вопрос: как построить функции принадлеж-
ности μj (x), j = 1, 2,..., k, такие, чтобы они „улавливали" те точки x∈X с окрест-
ности Ω(x, xi), і = 0,1 ..., которые являются более перспективными относитель-
но минимизации критерия. Например, если F(х)>0 на всем пространстве Х, то
μ(x,xi)=
( ) , если ( ) ( ),
( )
0, если ( ) ( )
i
i
i
F x F x F x
F x
F x F x
⎧ ≤⎪
⎨
⎪ >⎩
имеет вышеуказанные свойства.
Дальше, пусть Φ(х) – мажоранта функции F(x), а функция ϕ(х) – ее мино-
ранта, т. е. ϕ(х)≤ F(x)≤ Φ(х) для x∈X. Тогда функциями принадлежности могут
служить, например, функции
μ1(x,xi)=
( ) , если ( ) ( ),
( )
0, если ( ) ( );
ii
i
F x x F x
x
x F x
⎧ Φ ≥⎪ Φ⎨
⎪ Φ <⎩
μ2(x, xi)=
( ) , если ( ) ( ),
( )
0, если ( ) ( );
ii
i
F x x F x
x
x F x
⎧ ϕ ≥⎪ ϕ⎨
⎪ ϕ <⎩
Компьютерная математика. 2009, № 2 155
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
μ3(x,xi)=
( ) , если ( ) ( ),
( )
0, если ( ) ( );
i
i
i
F x F x x
x
F x x
⎧ ≤ Φ⎪Φ⎨
⎪ > Φ⎩
μ4(x,xi)=
( ) , если ( ) ( ),
( )
0, если ( ) ( ).
i
i
i
x x F x
F x
x F x
⎧ϕ
ϕ ≤⎪
⎨
⎪ ϕ >⎩
Относительно функций μ3(x, xi) и μ4(x, xi), то они особенно могут быть по-
лезными в алгоритмах МВС, которые для определения локального решения на
определенном шаге итеративного процесса используют мажоранту и миноранту
целевой функции.
Как и в работах [3, 4], для функций принадлежности, что определяют нечет-
кий вариант МВC, имеют место понятия адекватности, индифферентности и
противоречивости функции принадлежности условиям задачи и схеме приме-
няемого варианта МВС. Функцию принадлежности, что действует в окрестности
– универсуме , обозначим μ(x, x)Ω( ix i).
Для задачи минимизации будем придерживаться следующих определений.
Если μ(xi+1, xi) > μ(xi, xi–1), то алгоритм МВС, построенный с помощью
функции μ, будет адекватным; если μ(xi+1, xi) = μ(xi, xi–1) – индифферентным, а
при условии μ(xi+1, xi) < μ(xi, xi–1) – противоречивым. Естественно, что приме-
нять противоречивые алгоритмы не стоит, кроме некоторых частных случаев.
Что касается функций принадлежности, что действуют в окрестности – уни-
версуме ) , то в общем случае относительно рассматриваемой задачи, она
записывается так:
Ω( ix
μ(x, xi) = μ(x, xi, F1(x),…, Fs(x), F1(xi),…, Fs(xi), U(x) – C, U(xi) – C).
В случае алгоритма 1, когда минимизацию проводим на каждом шаге итера-
ции для частичных критериев Fr, r=1, . . . , s, и приближенным множеством Па-
рето считаем пересечение соответствующих окрестностей, то функцией принад-
лежности в этой окрестности будет величина
μ(x, xi) = min(μ1(x, xi), μ2(x, xi), . . . , μs(x, xi)).
Компьютерная математика. 2009, № 2 156
О РЕШЕНИИ КОМБИНАТОРНОЙ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИОННОЙ …
Из последней записи можно сделать вывод, что при адекватности каждой из
функций принадлежности μr (x, xi), r = 1,…, s, функция принадлежности μ(x, xi)
тоже будет адекватной.
Утверждение. В случае адекватности функции принадлежности μ(x) зада-
чу минимизации функции F(x) можно заменить задачей максимизации функции
μ(x), причем их локальные решения на каждом шаге алгоритма совпадают.
Доказательство легко осуществить за принципом “от противного”.
Заключение. В настоящей работе рассмотрены нечеткие алгоритмы реше-
ния задач одного класса многокритериальной оптимизации в четкой постановке
на примере оптимизационной задачи на выборках с заданным числом элементов.
Вполне очевидно, что предложенный подход может успешно применяться для
решения других типов задач, а также в случае представления их в нечетком ви-
де, т.е. применение нечеткого алгоритма для решения задачи с нечеткими ис-
ходными данными. При этом темой отдельных исследований могут служить во-
просы построения устойчивых алгоритмов нечеткого метода вектора спада для
решения задач комбинаторной оптимизации в четкой и нечеткой постановках, а
также оценивание получаемых приближенных решений.
І.М. Парасюк, М.Ф. Каспшицька
ПРО РОЗВ’ЯЗУВАННЯ КОМБІНАТОРНОЇ БАГАТОКРИТЕРІАЛЬНОЇ
ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ НЕЧІТКИМ МЕТОДОМ ВЕКТОРА СПАДУ
Розглянуті питання модифікації нечіткого методу вектора спаду для розв’язування багато-
критеріальної оптимізаційноої задачі комбінаторного типу для випадку різнорідних вихідних
даних. Основна увага приділена вивченню методу, його часткових реалізацій з урахуванням
вигляду використовуваних функцій приналежності. Для ілюстрації використовується
оптимізаційна задача на вибірках із заданим числом елементів.
I.N. Parasyuk, M.F. Kаspschicka
ON A SOLUTION TO COMBINATORIAL MULTICRITERION
OPTIMIZATION PROBLEM BY SLUMP-VECTOR FUZZY METHOD
Modification issues of slump-vector fuzzy method for combinatorial-type multicriterion optimiza-
tion problem in the case of heterogeneous basic data are considered. Main attention is devoted to the
study of the method and its partial implementations taking into account a type of membership func-
tions used. For illustration purposes, the optimization problem on samples with predefined number
of elements is used.
Компьютерная математика. 2009, № 2 157
И.Н. ПАРАСЮК, М.Ф. КАСПШИЦКАЯ
The questions of modification of unclear method of vector of slump are considered
for the decision of multicriterion optimization task of combinatorics type for the case
of heterogeneous basic data. Basic attention is spared the study of method, his partial
realization taking into account the type of in-use functions of belonging. For illustra-
tion an optimization task is used on selections with the set number of elements.
1. Сергієнко І.В. Один метод роз`язування задач на відшукання екстремальних значень.
//Автоматика. – 1964. – № 5. – С. 15–21.
2. Парасюк И.Н.,Каспшицкая М.Ф. О развитии метода вектора спада на случай размытых
окрестностей // Компьютерная математика. – 2008. – № 2. – С. 145–155.
3. Парасюк И.Н., Каспшицкая М.Ф. Размытый алгоритм метода вектора спада для решения
оптимизационных задач на выборках // Компьютерная математика. – 2009. – № 1.
– С. 152–163.
4. Леоненков А.В. Нечеткое моделирование в среде MATLAB u fuzzy TECH. – СПб.:
БХВ-Петербург, 2005.–736 с.
Получено 22.04.2009
Îá àâòîðàõ:
Парасюк Иван Николаевич,
член-корреспондент НАН Украины, заведующий отделом
Института кибернетики имени В.М. Глушкова НАН Украины,
E-Mail: ivpar1@i.com.ua
Каспшицкая Мария Фадеевна,
кандидат физико-математических наук, старший научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины.
Компьютерная математика. 2009, № 2 158
mailto:ivpar1@i.com.ua
|