Машиностроение и компьютерные технологии. 2017; : 64-74
Поддержка принятия многокритериальных решений на основе много-индикаторной оценки качества Парето-аппроксимации
https://doi.org/10.24108/1117.0001339Аннотация
В работе рассмотрена проблема многоиндикаторного выбора «наилучшего» алгоритма для решения МКО-задачи. Из большого числа известных алгоритмов решения задачи многокритериальной оптимизации (МКО-задача) выделяем алгоритмы, основанные на предварительном построении аппроксимации ее фронта (множества) Парето и называемые П-алгоритмами.
Ввиду наличия большого числа П-алгоритмов возникает проблема выбора «наилучшего» алгоритма для данной МКО-задачи (и/или данного класса этих задач) ‑ проблема метаоптимизации. Ввиду наличия большого числа П-алгоритмов возникает проблема выбора «наилучшего» алгоритма для данной МКО-задачи (и/или данного класса этих задач) ‑ проблема метаоптимизации. Ставим задачу структурной мета-оптимизации П-алгоритмов, которая предполагает одновременное построение П-аппроксимации и оптимизацию этой аппроксимации по одному или нескольким П-индикаторам.
В работе приведена постановка базовой МКО-задачи и описаны используемые индикаторы качества П-аппроксимации. Рассматриваются несколько методов выбора «наилучшего» П-алгоритма - метод, основанный на использовании того или иного способа визуализации многоиндикаторных оценок качества П-аппроксимации, метод на основе скалярной свертки выбранных лицом, принимающим решения (ЛПР) индикаторов качества П-аппроксимации, а также авторский автоматизированный метод, предполагающий предварительную аппроксимацию функции предпочтений ЛПР. Для каждого метода представлено математическое описание, рассмотрены достоинства и недостатки, а также показаны пути преодоления этих недостатков.
Основной научный результат работы заключается в разработке оригинального метода PREF-I решения МКО-задачи задачи на основе выявления так называемой функции предпочтений (ЛПР). Этот метод можно считать развитием метода PREF, ориентированного на решение исходной МКО-задачи.
Список литературы
1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. 2-е изд. М.: Физматлит, 2007. 256 с.
2. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.
3. Knowles J., Corne D. On metrics for comparing nondominated sets // Evolutionary computation 2002: Congress on evolutionary computing: CEC '02 (Honolulu, Hawaii, USA, May 12-17, 2002): Proc. Vol. 1. N.Y.: IEEE, 2002. Pp. 711-716. DOI: 10.1109/CEC.2002.1007013
4. Zitzler E., Thiele L., Laumanns M., Fonseca C.M., da Fonseca V.G. Performance assessment of multiobjective optimizers: An analysis and review // IEEE Trans. on Evolutionary Computation. 2003. Vol. 7. No. 2. Pp. 117-132. DOI: 10.1109/TEVC.2003.810758
5. Белоус В.В., Грошев С.В., Карпенко А.П. ВЕБ-ориентированная среда визуализации многомерного фронта Парето // Информационные и математические технологии в науке и управлении. 2017. № 1(5). C. 94-101.
6. Ларичев О.И. Теория и методы принятия решений: учебник. 3-е изд. М.: Физматкнига; Логос, 2006. 392 с.
7. Karpenko A.P., Mukhlisullina D.T., Ovchinnikov V.A. Multicriteria optimization based on neural network approximation of decision maker’s utility function // Optical Memory and Neural Networks (Information Optics). 2010. Vol. 19. No. 3. Pp. 227–236. DOI: 10.3103/S1060992X10030045
8. Conover W.J. Practical nonparametric statistics. 3rd ed. N.Y.: Wiley, 1999. 584 p.
9. Deb K. Multi-objective optimization using evolutionary algorithms. Chichester; N.Y.: Wiley, 2001. 497 p.
10. Грошев С.В., Карпенко А.П. Мета-оптимизация популяционных алгоритмов многоцелевой оптимизации // Интернет-журнал «Науковедение». 2016. Т. 8. № 6(37). С. 52. DOI: 10.15862/52TVN616
11. Грошев С.В., Карпенко А.П., Остроушко В.А. Комбинированный метод визуализации фронта Парето в задаче многокритериальной оптимизации, основанный на диагональном пересчете гиперпространства // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2016. № 8. С. 150-164. DOI: 10.7463/0816.0844030
12. Mersmann O., Bischl B., Trautmann H., Preuss M., Weihs C., Rudolph G. Exploratory landscape analysis // 13th annual conf. on evolutionary computation: GECCO’11 (Dublin, Ireland, July 12–16, 2011): Proc. N.Y.: ACM, 2011. Pp. 829-836. DOI: 10.1145/2001576.2001690
13. Грошев С.В., Карпенко А.П., Сабитов Д.Р., Шибитов И.А. Программная система PARETO RATING для оценки качества Парето-аппроксимации в задаче многокритериальной оптимизации // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 7. С. 193-214. DOI: 10.7463/0714.0720253
Mechanical Engineering and Computer Science. 2017; : 64-74
Multiple-criteria Decision-making Support Based on the Multi-Indicator Evaluation of the Pareto-Approximation Quality
https://doi.org/10.24108/1117.0001339Abstract
The paper considers a problem, which is defined as multi-indicator finding the "best" algorithm to solve a multiple-criteria optimization (MCO) problem. Of a large number of known algorithms for solving the MCO, we deal with the algorithms based on the preliminary construction of its Pareto front (set) approximation and called P-algorithms.
Because of a large number of P-algorithms, a problem of choosing the "best" algorithm for the given MCO problem (and / or this class of these problems) arises, i.e. a meta-optimization problem. We pose the problem of structural meta-optimization of P-algorithms, which suggests a simultaneous P-approximation construction and optimization of this approximation according to one or several P-indicators.
The paper presents basic MCO-problem formulation and describes used P-approximation quality indicators. Considers several methods to choose the "best" P-algorithm such as a method based on using one or another method to visualize multi-indicator estimates of P-approximation quality, a method based on the scalar convolution of P-approximation quality indicators, chosen by a decision-maker (DM), and an author's automated method that supposes a preliminary approximation of the function of preference. Provides mathematical description, considers advantages and disadvantages, as well as shows the ways to overcome these shortcomings.
The main research result involves a development of the original PREF-I method to solve the MCO problem based on identification of so-called DM’s function of preference. This method may be thought as evolution of the PREF method aimed at solving the initial MCO problem.
References
1. Podinovskii V.V., Nogin V.D. Pareto-optimal'nye resheniya mnogokriterial'nykh zadach. 2-e izd. M.: Fizmatlit, 2007. 256 s.
2. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi: ucheb. posobie. M.: Izd-vo MGTU im. N.E. Baumana, 2014. 446 s.
3. Knowles J., Corne D. On metrics for comparing nondominated sets // Evolutionary computation 2002: Congress on evolutionary computing: CEC '02 (Honolulu, Hawaii, USA, May 12-17, 2002): Proc. Vol. 1. N.Y.: IEEE, 2002. Pp. 711-716. DOI: 10.1109/CEC.2002.1007013
4. Zitzler E., Thiele L., Laumanns M., Fonseca C.M., da Fonseca V.G. Performance assessment of multiobjective optimizers: An analysis and review // IEEE Trans. on Evolutionary Computation. 2003. Vol. 7. No. 2. Pp. 117-132. DOI: 10.1109/TEVC.2003.810758
5. Belous V.V., Groshev S.V., Karpenko A.P. VEB-orientirovannaya sreda vizualizatsii mnogomernogo fronta Pareto // Informatsionnye i matematicheskie tekhnologii v nauke i upravlenii. 2017. № 1(5). C. 94-101.
6. Larichev O.I. Teoriya i metody prinyatiya reshenii: uchebnik. 3-e izd. M.: Fizmatkniga; Logos, 2006. 392 s.
7. Karpenko A.P., Mukhlisullina D.T., Ovchinnikov V.A. Multicriteria optimization based on neural network approximation of decision maker’s utility function // Optical Memory and Neural Networks (Information Optics). 2010. Vol. 19. No. 3. Pp. 227–236. DOI: 10.3103/S1060992X10030045
8. Conover W.J. Practical nonparametric statistics. 3rd ed. N.Y.: Wiley, 1999. 584 p.
9. Deb K. Multi-objective optimization using evolutionary algorithms. Chichester; N.Y.: Wiley, 2001. 497 p.
10. Groshev S.V., Karpenko A.P. Meta-optimizatsiya populyatsionnykh algoritmov mnogotselevoi optimizatsii // Internet-zhurnal «Naukovedenie». 2016. T. 8. № 6(37). S. 52. DOI: 10.15862/52TVN616
11. Groshev S.V., Karpenko A.P., Ostroushko V.A. Kombinirovannyi metod vizualizatsii fronta Pareto v zadache mnogokriterial'noi optimizatsii, osnovannyi na diagonal'nom pereschete giperprostranstva // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2016. № 8. S. 150-164. DOI: 10.7463/0816.0844030
12. Mersmann O., Bischl B., Trautmann H., Preuss M., Weihs C., Rudolph G. Exploratory landscape analysis // 13th annual conf. on evolutionary computation: GECCO’11 (Dublin, Ireland, July 12–16, 2011): Proc. N.Y.: ACM, 2011. Pp. 829-836. DOI: 10.1145/2001576.2001690
13. Groshev S.V., Karpenko A.P., Sabitov D.R., Shibitov I.A. Programmnaya sistema PARETO RATING dlya otsenki kachestva Pareto-approksimatsii v zadache mnogokriterial'noi optimizatsii // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2014. № 7. S. 193-214. DOI: 10.7463/0714.0720253
