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

Файл статьи: SE-BMSTU...o214.pdf (1103.27Кб)

Рассматриваем задачу оценки качества численной аппроксимации множество (фронта) Парето в задаче многокритериальной оптимизации (МКО-задаче). Имеем в виду, что Парето-аппроксимация получена с помощью того или иного популяционного, например, генетического алгоритма. В конечном счете, целью работы является сравнительная оценка эффективности популяционных алгоритмов Парето-аппроксимации. Разработано большое число характеристик (индикаторов) качества Парето-аппроксимации. Поэтому задачу оценки качества Парето-аппроксимации рассматриваем также как многокритериальную (многоиндикаторную). Известен ряд программных систем, которые в разной степени решают задачу оценки качества Парето-аппроксимации. Общим недостатком этих систем является отсутствие WEB-интерфейса, а также отсутствие поддержки многоиндикаторной оценки качества Парето-аппроксимации (хотя поддержка вычисления значений большого числа этих индикаторов имеется). Программная система PARETO RATING призвана устранить указанные недостатки известных систем. Поскольку популяционные алгоритмы Парето-аппроксимации являются, как правило, стохастическими, рассматриваем статистические методы оценки качества двух и более Парето-аппроксимаций (а тем самым и оценки алгоритмов, с помощью которых эти аппроксимации получены): методы на основе ранжирования указанных аппроксимаций; методы на основе индикаторов качества; методы на основе так называемых эмпирических функций достижимости. Приводим формальную постановку МКО-задачи и общую схему популяционных алгоритмов её решения, даем обзоры известных индикаторов качества Парето-аппроксимации и статистических методов оценки качества Парето-аппроксимаций, представляем описание архитектуры системы и основные особенности её программной реализации, иллюстрирует эффективность принятых алгоритмических и программных решений.

1. Карпенко А.П., Семенихин А.С., Митина Е.В. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 4. Режим доступа: http://www.technomag.edu.ru/doc/363023.html (дата обращения 01.06.2014).
2. Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results // Evolutionary Computation. 2000. Vol . 8, no . 2. P . 173-195. DOI: 10.1162/106365600568202
3. Белоус В.В., Грабик А.В., Грошев С.В., Шибитов И.А. Качество Парето-аппроксимации в задаче многокритериальной оптимизации // XVIII Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении»: материалы. Ч. 1. Иркутск: ИСЭМ СО РАН, 2013. С. 6-12.
4. Белоус В.В., Грошев С.В., Карпенко А.П., Шибитов И.А. Программные системы для оценки качества Парето-аппроксимации в задаче многокритериальной оптимизации. Обзор // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 4. DOI:10.7463/0414.0709198
5. Fonseca C.M., Grunert da Fonseca V., Hall A.O. Inferential performance assessment of stochastic optimizers and the attainment functions // In: Evolutionary Multi-Criterion Optimization. Proc. First International Conference, EMO 2001 / Zitzler E., Deb K., Thiele L., Coello C.A.C., Corne D., eds. Springer Berlin Heidelberg, 2001. P. 213-225. DOI: 10.1007/3-540-44719-9_15
6. Лотов А. В., Поспелова И. И. Многокритериальные задачи принятия решений: учеб. пособие. М .: МАКС Пресс , 2008. 197 c.
7. Density and approximations of -distribution for different testproblems // System Optimization: сайт. Режим доступа:http://www.tik.ee.ethz.ch/sop/download/supplementary/testproblems/ (дата обращения 01.06.2014).
8. Fonseca C. M., Fleming P. J. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization // Proc. of the 5th International Conference on Genetic Algorithms, San Mateo, California, 1993. P. 416-423.
9. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., 1989. 201 p.
10. Conover W.J. Practical Nonparametric Statistic. 3^rd ed. New York: John Wiley and Sons, 1999. 583 p.
11. Efron B., Tibshirani R. An introduction to the bootstrap. London: Chapman and Hall, 1993. 436 p.
12. Shaw K. J., Nortcliff A. L., Thompson M., Love J., Fleming P.J., Fonseca C.M. Assessing the Performance of Multiobjective Genetic Algorithms for Optimization of a Batch Process Scheduling Problem // Proc. of the 1999 Congress on Evolutionary Computation. CEC 99. Vol. 1. IEEE Service Center, 1999. P. 37-45. DOI: 10.1109/CEC.1999.781905
13. Knowles J. A summary-attainment-surface plotting method for visualizing the performance of stochastic multiobjective optimizers // Proc. of the 5th International Conference on Intelligent Systems Design and Applications, 2005. ISDA '05. IEEE, 2005. P.552-557. DOI: 10.1109/ISDA.2005.15