Наука и Образование: научно-техническое издание: Анализ эффективности различных сверток критериев оптимальности в задаче многокритериальной оптимизации

УДК.519.6

МГТУ им. Н.Э. Баумана

dmitry_moor@mail.ru

Введение

К настоящему времени разработано множество методов решения задачи многокритериальной оптимизации. Большая часть этих методов основана на сведении многокритериальной задачи оптимизации к однокритериальной, посредством свертки частных критериев оптимальности в скалярную функцию. Свертки, позволяющие находить все эффективные решения в задачах одного класса, оказываются непригодными для решения задач другого класса. Таким образом, выбор типа свертки в задачах многокритериальной оптимизации является важным этапом, от которого зависит сама возможность нахождения оптимального решения. Данная работа имеет целью провести сравнительный анализ эффективности некоторых наиболее часто используемых сверток критериев оптимальности.

1 Постановка МКО-задачи

Пусть – вектор варьируемых параметров задачи. Множеством допустимых значений вектора является ограниченное и замкнутое множество , где

- «технологический» параллелепипед допустимых значений вектора параметров; множество формируют ограничивающие функции , так что

;

где - n-мерное арифметическое пространство.

Векторный критерий оптимальности со значениями в критериальном пространстве определен в параллелепипеде П. Лицо, принимающее решения (ЛПР), стремится минимизировать на множестве каждый из частных критериев оптимальности , что условно можно записать в виде

, (1)

где - искомое решение задачи многокритериальной оптимизации (МКО-задачи). Полагаем, что частные критерии оптимальности тем или иным образом нормализованы, так что

Прямой адаптивный метод решения МКО-задачи, который исследуется в данной работе, основан на предположении существования «функции предпочтений ЛПР» , которая определена на множестве допустимых значений вектора варьируемых параметров и выполняет отображение этого множества на множество действительных чисел R. При этом задача многокритериальной оптимизации сводится к задаче выбора вектора такого, что

Предполагается, что при предъявлении ЛПР вектора параметров X, а также значений всех частных критериев оптимальности , это лицо может оценить соответствующее значение своей функции предпочтений .

Обозначим операцию свертки частных критериев оптимальности, где - вектор весовых множителей; – множество допустимых значений этого вектора. При каждом фиксированном векторе метод скалярной свертки сводит решение задачи (1) к решению однокритериальной задачи глобальной условной оптимизации (ОКО-задачи)

. (2)

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

В результате МКО-задача сводится к задаче выбора вектора такого, что

. (3)

Поскольку обычно , переход от задачи (1) к задаче (3) важен с точки зрения уменьшения вычислительных затрат.

Величину будем считать лингвистической переменной со значениями от «Очень-очень плохо» до «Отлично». Ядро нечеткой переменной обозначим , так что значению переменной «Очень-очень плохо» соответствует , а значению «Отлично» - . В результате МКО-задача сводится к задаче отыскания вектора , обеспечивающего максимальное значение дискретной функции :

. (4)

2 Используемые свертки

Под свертыванием частных критериев оптимальности понимается построение функции , которая может быть использована при принятии решения в качестве скалярного критерия вместо указанных частных критериев оптимальности [1].

Множество, в которое векторный критерий оптимальности отображает множество , обозначим и назовем критериальным множеством (множеством достижимости).

Будем говорить, что критериальная точка доминирует критериальную точку по Парето, если для всех критериев имеем и хотя бы для одного частного критерия .

Критериальная точка называется оптимальной по Парето, если множество критериальных точек, доминирующих точку по Парето, пусто. Такая точка называется также недоминируемой по Парето. Множество критериальных точек, оптимальных по Парето на , называют множеством Парето в пространстве критериев, а также парето-оптимальным, парето-эффективным или недоминируемым множеством в пространстве критериев и обозначают P.

Будем говорить, что критериальная точка доминирует критериальную точку по Слейтеру, если для всех критериев. Критериальная точка называется оптимальной по Слейтеру, если множество критериальных точек, доминирующих точку по Слейтеру, пусто. Такая точка называется также недоминируемой по Слейтеру. Множество критериальных точек, оптимальных по Слейтеру на , называют множеством Слейтера в пространстве критериев и обозначают S.

Можно доказать справедливость следующих утверждений [2].

Если свертка критериев является убывающей по бинарному отношению доминирования по Парето на множестве , и существует точка такая, что

то

Если свертка критериев является убывающей по бинарному отношению доминирования по Слейтеру на множестве , и существует точка такая, что

то

III. Если свертка критериев является невозрастающей по бинарному отношению доминирования по Парето на множестве , и существует единственный вектор такой, что

то

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

В данной работе исследуются следующие свертки:

1) линейная свертка , где – параметры свертки, ;

2) свертка Гермейера , , где – параметры свертки;

3) свертка на основе отклонения от идеальной точки , где - идеальная точка, - некоторая метрика в пространстве .

3 Исследование эффективности различных сверток частных критериев оптимальности

Ниже приведен сравнительный анализ указанных выше сверток частных критериев оптимальности применительно к трем задачам многокритериальной оптимизации.

3.1 Двухкритериальная МКО-задача (невыпуклый связный фронт Парето):

(5)

3.1.1 Линейная свертка. Свертка критериев оптимальности в этом случае имеет вид

где

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

Некоторые результаты решения задачи (5) представлены в таблице 1, которую иллюстрирует рисунок 1:

1) для любого вектора , такого, что , решением задачи (2) является точка с координатами (1,0);

2) для любого вектора , такого, что , решением задачи (2) является точка с координатами (0,1);

3) единственным случаем, когда решением задачи (2) может оказаться точка (0.5, 0.5) является случай равенства .

Таким образом, использование линейной свертки в задаче с невыпуклым фронтом Парето не позволяет получить все эффективные по Парето решения.

Таблица 1. Результаты решения МКО-задачи (5)


1	0.1	1.0	0.0	1	1.7
2	0.1	1.0	0.0	1	2.0
3	0.8	0.0	1.0	1	1.8
4	0.0	1.0	0.0	1	2.3	8.7	1.1	12.3	0.1
5	0.1	1.0	0.0	1	2.1	8.9	1.1	12.3	0.1
6	0.1	1.0	0.0	1	1.9	9.4	1.1	12.6	0.1
7	0.6	0.0	1.0	1	1.6	9.6	1.2	12.5	0.1
8	0.0	1.0	0.0	1	2.8	9.8	1.2	14.0	0.1
9	0.7	0.0	1.0	1	1.7	10.6	1.2	13.7	0.1
10	0.9	0.0	1.0	1	2.7	10.8	1.2	14.9	0.1
11	0.3	1.0	0.0	2	1.5	10.7	1.2	13.6	0.1
12	0.8	0.0	1.0	1	2.1	11.6	1.2	15.2	0.1
13	0.3	1.0	0.0	2	1.6	22.4	2.3	26.5	0.1
14	0.3	1.0	0.0	2	1.6	24.2	2.4	28.6	0.1

Рис. 1. Множество достижимости : задача (5); линейная свертка критериев

3.1.2 Свертка Гермейера. Свертка критериев оптимальности в этом случае имеет вид

где

Линии уровня этой свертки представляют собой границу конуса . Здесь точка – вершина конуса - точка в пространстве критериев с координатами (, ); величина определяется из условия ; – неотрицательный ортант.

Некоторые результаты решения задачи (5) представлены в таблице 2, которую иллюстрирует рисунок 2.

Таблица 2. Результаты решения МКО-задачи (5)


1	0.62	0.45	0.76	6	4.84
2	0.56	0.49	0.63	7	4.38
3	0.75	0.30	0.93	3	4.63
4	0.00	1.00	0.00	1	3.04	44.04	1.96	49.12	0.04
5	0.37	0.75	0.45	6	4.81	55.58	2.83	63.32	0.07
6	0.38	0.74	0.45	6	4.93	39.59	2.72	47.35	0.07
7	0.56	0.49	0.62	7	4.34	38.52	3.44	46.43	0.09
8	0.50	0.50	0.51	8	4.08	32.41	5.41	42.04	0.45
9	0.49	0.50	0.50	8	3.79	23.87	4.49	32.32	0.54
10	0.49	0.50	0.50	9	3.73	25.22	4.21	33.32	0.66
11	0.48	0.51	0.49	9	4.06	25.55	4.24	34.05	1.13
12	0.48	0.52	0.49	9	3.79	27.87	4.17	36.04	1.49
13	0.48	0.53	0.50	9	3.67	27.83	4.16	35.88	1.75
14	0.48	0.53	0.49	9	3.71	29.80	4.03	37.77	1.96

Рис. 2. Множество достижимости : задача (5); свертка Гермейера

Из рисунка 2 следует, что с помощью свертки Гермейера можно найти все эффективные и слабо эффективные решения.

3.1.3 Свертка на основе отклонения от идеальной точки. Под идеальной точкой понимают такой вектор , компоненты которого являются минимумами соответствующих частных критериев оптимальности по отдельности, т.е. , , .

Свертка критериев оптимальности в этом случае имеет вид , где - идеальная точка, - метрика в пространстве . При построении данной свертки могут быть использованы различные метрики. В работе используется евклидова метрика. Таким образом, получим

где

, - идеальная точка.

В задаче (5) идеальной точкой является точка Линии уровня свертки на основе отклонения от идеальной точки представляют собой эллипсы, для которых коэффициенты , и значение функции свертки определяют малую и большую полуоси (рис. 3). Полуоси указанных эллипсов определяются следующим образом: , .

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

Таблица 3. Результаты решения МКО-задачи (5)


1	0.79	0.01	0.99	1	1.66
2	0.02	1.00	0.00	1	3.11
3	0.20	0.99	0.01	1	1.71
4	0.21	0.99	0.02	1	1.69	8.74	1.19	11.72	0.09
5	0.47	0.50	0.50	9	1.60	8.92	1.16	11.78	0.11
6	0.50	0.50	0.50	9	1.60	22.95	2.14	26.81	0.12
7	0.50	0.50	0.50	9	1.54	21.95	2.43	26.04	0.14
8	0.50	0.50	0.50	9	1.56	18.81	2.20	22.73	0.15

Рис. 3. Множество достижимости : задача (5); свертка на основе отклонения от идеальной точки

Если выполняется условие , где , то решение задачи (5) достигается в точке с координатами (0.5, 0.5). Иначе, в случае существует следующая альтернатива.

1. Если , то решение находится в области, для которой , (рис. 3);

2. Если , то решение находится в области, для которой , .

Таким образом, свертка на основе идеальной точки позволяет получить большее количество эффективных решений, чем линейная свертка. Тем не менее, эта свертка не позволяет получить все эффективный решения, именно в этом заключается ее недостаток по сравнению со сверткой Гермейера. Этот недостаток можно устранить, если использовать другую метрику (например, чебышевскую [6]).

3.2 Двухкритериальная МКО-задача (невыпуклый несвязный фронт Парето):

;

(6)

3.2.1 Линейная свертка. Некоторые результаты исследования представлены в таблице 4 и на рисунке 4, который иллюстрирует таблицу.

Таблица 4. Результаты решения МКО-задачи (6)


1	0.86	0.00	0.29	1	1.7
2	0.74	0.01	0.26	7	2.0
3	0.37	0.04	0.19	7	1.3
4	0.20	0.04	0.19	7	1.4	11.4	1.1	14.3	0.05
5	0.05	1.00	0.00	1	1.4	13.5	1.0	16.3	0.05
6	0.45	0.04	0.20	8	1.4	14.5	1.0	17.2	0.08
7	0.54	0.03	0.20	8	1.6	17.7	1.2	20.9	0.08
8	0.54	0.03	0.20	8	1.5	19.5	1.3	22.8	0.08
9	0.57	0.03	0.20	8	1.6	21.0	1.3	24.4	0.08
10	0.56	0.03	0.20	8	1.6	23.1	1.3	26.4	0.08
11	0.64	0.02	0.21	9	1.7	26.0	2.5	30.7	0.65
12	0.66	0.02	0.22	9	1.7	32.2	1.8	36.3	0.10
13	0.66	0.02	0.21	9	1.7	36.3	1.8	40.4	0.11
14	0.66	0.02	0.22	9	1.8	33.8	1.9	38.2	0.13

Рис. 4. Множество достижимости : задача (6); линейная свертка

Использование линейной свертки в данной задаче не позволяет получить все точки множества Парето в данной задаче. Эффективные точки, которые не могут быть получены с использованием данной свертки, обозначены на рисунке 4 черным.

Таким образом, можно сформулировать следующие выводы:

1) для любого вектора , такого, что , решением задачи (6) будет точка с координатами (1,0);

2) для любого вектора , такого, что , решение задачи (6) будет принадлежать множеству {} (на рисунке 4 выделено красным).

Здесь C – константа ().

3.2.2 Свертка Гермейера. Результаты исследования задачи (6) для данной свертки представлены в таблице 5 и на соответствующем рисунке 5.

Таблица 5. Результаты решения МКО-задачи (6)


1	0.55	0.05	0.19	6	2.82
2	0.06	0.96	0.07	1	3.11
3	0.86	0.03	0.21	8	5.06
4	1.00	0.00	0.50	1	1.71	14.29	2.05	18.18	0.05
5	0.71	0.05	0.19	6	2.58	24.02	2.37	29.08	0.30
6	0.85	0.03	0.21	7	4.40	22.18	2.83	29.54	0.32
7	0.85	0.03	0.21	7	4.65	37.70	2.95	45.43	0.28
8	0.89	0.02	0.22	9	4.66	40.94	2.56	48.30	0.29
9	0.86	0.03	0.21	7	4.91	25.61	2.68	33.38	1.50
10	0.86	0.03	0.21	7	5.07	29.14	3.05	37.44	1.51
11	0.16	0.65	0.14	3	3.27	31.34	2.66	37.47	1.53
12	0.87	0.03	0.22	9	4.31	30.60	3.75	38.87	1.98
13	0.87	0.03	0.21	8	4.81	35.69	3.84	44.57	2.31
14	0.93	0.01	0.25	8	4.14	34.27	3.71	42.36	2.48
15	0.87	0.03	0.22	9	4.90	47.43	3.30	55.88	3.81
16	0.86	0.03	0.21	8	4.74	47.91	3.55	56.47	4.00
17	0.85	0.03	0.21	7	4.91	51.77	3.90	60.86	4.13
18	0.81	0.04	0.20	6	3.64	59.29	4.57	67.80	4.28
19	0.89	0.02	0.22	9	4.71	43.29	4.06	52.40	4.48
20	0.89	0.02	0.22	9	4.73	44.35	3.97	53.39	4.71
21	0.89	0.02	0.22	9	4.49	67.28	4.02	76.14	4.94

Рис. 5. Множество достижимости : задача (6); свертка Гермейра

Отметим, что в задаче (6) использование свертки Гермейера позволяет найти все эффективные точки (на рисунке 5 фронт Парето есть объединение множеств 1, 2, 3, 4, 5).

3.2.3 Свертка на основе отклонения от идеальной точки. Результаты исследования данной свертки представлены в таблице 6 и на рисунке 6, который иллюстрирует эту таблицу.

Таблица 6. Результаты решения МКО-задачи (6)


1	0.26	0.04	0.19	6
2	0.32	0.04	0.19	6
3	0.02	1.00	0.00	1
4	0.96	0.01	0.23	9	2.23	15.39	1.58	19.30	0.05
5	0.85	0.03	0.20	7	3.17	16.54	1.93	21.74	0.08
6	1.00	0.00	0.29	5	1.79	15.79	2.66	20.35	0.31
7	0.87	0.03	0.20	7	2.98	16.33	2.85	22.29	5.03
8	0.87	0.03	0.20	7	2.91	21.73	3.83	28.62	4.96
9	0.50	0.04	0.19	6	3.07	23.00	3.85	30.09	4.98
10	0.90	0.03	0.21	7	3.04	20.28	3.71	27.21	2.62
11	0.90	0.03	0.21	7	2.70	23.13	2.97	29.00	2.61
12	0.99	0.00	0.28	6	1.98	25.99	3.43	31.62	2.69
13	0.89	0.03	0.20	7	3.11	24.69	4.19	32.22	2.87
14	0.88	0.03	0.20	7	3.21	29.11	3.82	36.40	2.91
15	0.94	0.02	0.22	9	2.64	26.30	3.18	32.36	2.93
16	0.90	0.03	0.21	7	3.03	30.92	3.45	37.71	3.45
17	0.89	0.03	0.21	7	3.10	29.64	3.50	36.54	3.48
18	0.17	0.05	0.19	6	2.94	32.46	3.34	39.06	3.52
19	0.90	0.03	0.21	8	2.98	33.55	2.87	39.73	3.47
20	0.87	0.03	0.20	8	3.30	35.63	3.17	42.40	3.65
21	0.83	0.03	0.20	7	3.41	34.16	4.45	42.34	3.70

Рис. 6. Множество достижимости : задача (6); свертка на основе отклонения от идеальной точки

В задаче (6) использование свертки на основе идеальной точки позволяет получить большее количество эффективных решений, чем при использовании линейной свертки. Например, может быть получена точка A= (рис. 6). Тем не менее, все эффективные точки с помощью этой свертки получить нельзя.

3.3 Трехкритериальная МКО-задача (невыпуклый связный фронт Парето):

(7)

3.3.1 Линейная свертка. Свертка критериев имеет вид

где . Результаты исследования эффективности линейной свертки при решении задачи (7) приведены в таблице 7 и на рисунке 7.

Таблица 7. Результаты решения МКО-задачи (7)

╧
1	0.43	0.58	0.00	0.66	0.00	0.66	1
2	0.63	0.14	0.21	0.00	0.66	0.66	1
3	0.42	0.36	0.21	0.33	0.33	1.00	1
4	0.01	0.76	0.21	0.66	0.00	0.66	1	4.09	8.63	2.22	22.98	0.09
5	0.60	0.39	0.00	0.00	0.66	0.66	1	4.01	8.62	2.61	23.45	0.11
6	0.40	0.59	0.00	0.66	0.00	0.66	1	3.92	8.84	2.37	23.53	0.12
7	0.26	0.73	0.00	0.66	0.00	0.66	1	4.06	9.39	2.63	24.56	0.14
8	0.71	0.28	0.00	0.00	0.66	0.66	1	3.98	9.37	2.50	24.55	0.15
9	0.51	0.48	0.00	0.33	0.33	1.00	1	4.02	9.34	2.46	24.79	0.16
10	0.74	0.18	0.07	0.00	0.66	0.66	1	3.63	10.64	2.55	25.97	0.17
11	0.60	0.39	0.00	0.00	0.66	0.66	1	4.06	10.74	2.58	26.67	0.18
12	0.61	0.38	0.00	0.00	0.66	0.66	1	4.06	12.05	2.56	28.12	0.18
13	0.62	0.37	0.00	0.00	0.66	0.66	1	3.75	12.69	2.62	28.89	0.19
14	0.63	0.14	0.22	0.00	0.66	0.66	1	3.19	13.42	2.56	29.08	0.20
15	0.13	0.13	0.72	0.66	0.66	0.00	1	3.49	13.32	2.76	29.50	0.21
16	0.50	0.39	0.09	0.00	0.66	0.66	1	3.47	14.88	2.73	31.21	0.22
17	0.67	0.32	0.00	0.00	0.66	0.66	1	3.87	15.02	2.86	32.23	0.22
18	0.23	0.48	0.27	0.66	0.00	0.66	1	2.83	17.11	2.82	33.30	0.23
19	0.38	0.61	0.00	0.66	0.00	0.66	1	4.1	16.40	2.97	34.23	0.24
20	0.52	0.47	0.00	0.00	0.66	0.66	1	4.12	16.92	2.72	34.47	0.24
21	0.53	0.46	0.00	0.00	0.66	0.66	1	3.94	18.76	2.79	35.89	0.25
22	0.54	0.45	0.00	0.00	0.66	0.66	1	4.17	18.77	2.85	36.67	0.26
23	0.51	0.25	0.23	0.33	0.33	1.00	1	2.75	20.77	3.02	37.82	0.26
24	0.45	0.54	0.00	0.66	0.00	0.66	1	3.66	20.69	2.78	38.35	0.27
25	0.75	0.24	0.00	0.00	0.66	0.66	1	4.04	21.72	2.86	40.16	0.28
26	0.71	0.28	0.00	0.00	0.66	0.66	1	4.1	21.93	2.91	41.17	0.28
27	0.32	0.67	0.00	0.66	0.00	0.66	1	3.76	23.31	3.02	41.90	0.29
28	0.27	0.72	0.00	0.66	0.00	0.66	1	3.79	23.78	2.99	42.65	0.29
29	0.61	0.38	0.00	0.00	0.66	0.66	1	4.06	26.93	2.86	46.43	0.30

Рис. 7. Множество достижимости : задача (7); линейная свертка

Поверхностями уровня в этой задаче являются плоскости (на рисунке 7 показана фиолетовым), для которых весовые коэффициенты , , определяют нормальный вектор плоскости , а величины есть длины отрезков, отсекаемых плоскостью на осях координат (C – значение функции свертки).

Рисунок показывает, что в задаче (7) использование линейной свертки не позволяет получить все эффективные решения (кружками показаны эффективные точки, получающиеся в процессе решения МКО-задачи).

3.3.2 Свертка Гермейера. Свертка критериев оптимальности в этом случае имеет вид:

где , .

Результаты решения задачи представлены в таблице 8 и на рисунке 8.

Таблица 8. Результаты решения МКО-задачи (7)

╧
1	0.34	0.00	0.64	0.66	0.66	0.0000	1
2	0.01	0.89	0.08	0.66	0.00	0.6668	1
3	0.80	0.07	0.12	0.00	0.66	0.6667	1
4	0.49	0.50	0.00	0.66	0.00	0.6667	2	14.12	7.85	2.35	32.29	0.09
5	0.46	0.53	0.00	0.66	0.00	0.6677	2	16.80	9.43	18.83	52.30	0.09
6	0.46	0.53	0.00	0.66	0.00	0.6667	1	12.21	9.68	17.52	46.83	0.09
7	0.37	0.26	0.36	0.33	0.33	0.3339	9	10.92	15.96	66.17	100.46	0.81
8	0.02	0.45	0.52	0.66	0.66	0.0006	1	11.68	21.33	60.85	101.46	0.81
9	0.37	0.25	0.37	0.33	0.33	0.3334	9	12.60	23.57	55.17	99.04	0.81
10	0.37	0.25	0.37	0.33	0.33	0.3333	9	11.18	27.05	69.36	115.42	0.81
11	0.37	0.25	0.37	0.33	0.33	0.3334	9	11.61	31.25	61.31	112.11	0.81
12	0.37	0.25	0.37	0.33	0.33	0.3334	9	11.70	29.42	72.54	121.71	0.82
13	0.37	0.25	0.37	0.33	0.33	0.3335	9	10.79	31.72	56.99	107.66	0.82
14	0.37	0.25	0.37	0.33	0.33	0.3334	9	13.14	32.75	58.40	112.60	0.82

Рис. 8. Множество достижимости : задача (7); свертка Гермейра

Поверхностями уровня в данной задаче являются конусы (рис. 8).

3.3.3 Свертка на основе отклонения от идеальной точки. Под идеальной точкой понимают такой вектор , компоненты которого являются минимумами соответствующих частных критериев оптимальности по отдельности, т.е. , , .

Функция свертки имеет вид

где

В данной задаче идеальной точкой является точка Результаты решения задачи представлены в таблице 9 и на рисунке 9.

Таблица 9. Результаты решения МКО-задачи (7)

╧
1	0.38	0.55	0.05	0.33	0.33	1.00	1
2	0.31	0.17	0.50	0.33	1.00	0.33	1
3	0.05	0.22	0.72	0.66	0.66	0.00	1
4	0.45	0.04	0.49	0.33	1.00	0.33	1	4.02	9.55	4.46	28.08	0.09
5	0.43	0.13	0.42	0.33	1.00	0.33	1	3.24	9.49	2.68	24.07	0.11
6	0.37	0.62	0.00	0.33	0.33	1.00	1	4.16	9.28	2.67	25.08	0.12
7	0.25	0.52	0.21	0.33	0.33	1.00	1	3.08	11.14	2.83	26.44	0.14
8	0.04	0.65	0.30	1.00	0.33	0.33	1	4.08	10.45	3.24	27.28	0.15
9	0.39	0.60	0.00	0.33	0.33	1.00	1	4.24	12.07	2.88	29.03	0.16
10	0.66	0.33	0.00	0.33	0.33	1.00	1	4.71	12.18	2.86	29.65	0.17
11	0.55	0.44	0.00	0.33	0.33	1.00	1	4.57	12.37	2.79	29.97	0.18
12	0.02	0.13	0.83	0.66	0.66	0.00	1	4.82	13.21	3.22	31.54	0.18
13	0.74	0.25	0.00	0.33	0.33	1.00	1	4.39	12.84	3.19	30.79	0.19
14	0.46	0.53	0.00	0.33	0.33	1.00	1	4.07	13.02	2.65	29.66	0.20
15	0.86	0.13	0.00	0.00	0.66	0.67	1	4.09	13.81	2.55	30.52	0.21
16	0.53	0.25	0.21	0.04	0.66	0.66	1	2.69	14.84	2.68	30.39	0.22
17	0.39	0.18	0.41	0.33	1.00	0.33	1	2.62	15.95	2.86	31.88	0.22
18	0.45	0.54	0.00	0.33	0.33	1.00	1	4.04	16.04	2.78	33.46	0.23
19	0.38	0.61	0.00	0.33	0.33	1.00	1	3.98	17.11	2.89	34.73	0.24
20	0.15	0.84	0.00	0.66	0.00	0.66	1	4.26	17.95	2.81	36.15	0.24
21	0.57	0.42	0.00	0.33	0.33	1.00	1	3.92	18.33	2.63	35.87	0.25
22	0.58	0.41	0.00	0.33	0.33	1.00	1	3.99	19.19	2.81	37.27	0.26
23	0.32	0.20	0.46	0.33	1.00	0.33	1	2.69	20.31	2.82	37.12	0.26
24	0.57	0.42	0.00	0.33	0.33	1.00	1	3.97	20.81	2.92	39.44	0.27
25	0.45	0.54	0.00	0.33	0.33	1.00	1	4.01	23.21	2.78	42.12	0.28
26	0.37	0.05	0.56	0.33	1.00	0.33	1	3.54	23.40	2.88	41.38	0.28
27	0.45	0.04	0.49	0.33	1.00	0.33	1	3.51	24.10	2.84	42.08	0.29
28	0.58	0.41	0.00	0.33	0.33	1.00	1	4.16	25.15	3.01	44.58	0.29
29	0.49	0.50	0.00	0.33	0.33	1.00	1	4.02	26.49	2.89	45.94	0.30
30	0.81	0.18	0.00	0.00	0.66	0.67	1	4.21	29.30	3.21	49.25	0.30
31	0.22	0.21	0.56	0.33	0.33	0.33	9	2.8	28.39	3.11	47.16	0.31
32	0.18	0.22	0.59	0.33	0.33	0.33	9	2.93	52.50	39.13	105.18	2.31
33	0.18	0.22	0.59	0.66	0.66	0.00	1	2.94	47.59	33.91	95.01	2.35
34	0.25	0.25	0.49	0.33	0.33	0.33	9	2.70	61.84	82.24	157.51	6.76

Рис. 9. Множество достижимости : задача (7); свертка на основе отклонения от идеальной точки

Линии уровня функции свертки представляют собой эллипсоиды, для которых величины , , определяют полуоси эллипсоида (C – значение функции свертки).

Рисунок 9 показывает, что здесь, так же, как и в предыдущих задачах, данная свертка позволяет находить большее число эффективных точек, чем линейная свертка. Тем не менее, не все эффективные точки могут быть найдены.

На рисунке 10 представлена зависимость времени выполнения одной итерации от номера итерации. Видно, что как в двухкритериальной задаче (6), так и в трехкритериальной задаче (7) использование свертки Гермейера является наиболее затратным с точки зрения времени выполнения итераций. Время, затрачиваемое на вычисления в случае использования линейной свертки, мало отличается от времени выполнения итераций в случае использования свертки на основе идеальной точки. Следовательно, использование свертки на основе идеальной точки в данных задачах является более выгодным решением, чем использование линейной свертки, т.к. позволяет получить больше эффективных точек. Заметим также, что в случае использования линейной свертки в трехкритериальной задаче оптимальное решение вообще не было достигнуто.

Рис. 10. Время выполнения одной итерации как функция номера итерации

4 Выводы

Любое решение задачи (2) с использованием линейной свертки есть эффективный по Парето вектор. Однако не всякий эффективный по Парето вектор может быть получен с помощью этой свертки.

Свертка Гермейера позволяет получить как эффективные, так и слабо эффективные решения. На практике, когда ЛПР интересуют только эффективные решения, получение слабо эффективного решения является недостатком. Этот недостаток можно устранить, если применить метод выделения эффективных точек из множества Слейтера, предложенный Джоффрионом [4].

Основным недостатком свертки на основе идеальной точки является зависимость результата решения МКО-задачи от выбора метрики.

Авторы благодарят своего научного руководителя д.ф.-м.н., профессора МГТУ им.Н.Э. Баумана Карпенко А.П. за плодотворное обсуждение работы, а также за всестороннюю помощь по ее совершенствованию.

Литература

1. Лотов А.В. Введение в экономико-математическое моделирование.- М.: Наука, 1984.- 392 с.

2. Лотов А.В., Поспелова И.И. Многокритериальные задачи принятия решений: Учебное пособие. – М.:МАКС Пресс, 2008.- 197 с.

3. Карпенко, А.П. Один класс прямых адаптивных методов многокритериальной оптимизации / А.П.Карпенко, В.Г.Федорук // Информационные технологии.- 2009.- ╧5.- С.24-30.

4. Черноруцкий И.Г. Методы принятия решений. – СПб.: БЧВ-Петербург, 2005.-416 с.

5. Гермейер Ю. Б. Введение в теорию исследования операций. М.: Наука, 1971.

6. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения: Пер. с англ. – М.: Радио и связь, 1992. – 504 с.: ил.

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408