|
DOI: 10.14489/vkit.2019.03.pp.003-010
Казаков П. В.
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С ДИФФЕРЕНЦИАЛЬНОЙ ЭВОЛЮЦИЕЙ ДЛЯ СРЕДЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ CUDA
(c. 3-10)
Аннотация. Рассмотрен параллельный генетический алгоритм многокритериальной оптимизации с дифференциальной эволюцией. Данный алгоритм реализован с применением технологии параллельных вычислений CUDA (Compute Unified Device Architecture) для графических процессорных устройств. Приведены результаты анализа сокращения времени вычислений при использовании такого алгоритма для задач с различным числом критериев и популяций разного размера.
Ключевые слова: многокритериальная оптимизация; множество и граница Парето; многокритериальные генетические алгоритмы; дифференциальная эволюция; параллельные вычисления; технология CUDA.
Kazakov P. V.
MULTI-OBJECTIVE GENETIC ALGORITHM WITH A DIFFERENTIAL EVOLUTION FOR THE CUDA-BASED PARALLEL COMPUTING ENVIRONMENT
(pp. 3-10)
Abstract. One of the effective methods for multi-objective optimization problems solving is genetic algorithms for multi-objective optimization. Multi-Objective Genetic Algorithms (MOGA) have been gaining increasing attention among researchers and practitioners because of MOGA capability to obtain a set of Pareto-optimal solutions. The developing and study of MOGA is related with improving of precision of obtained solutions and decreasing of time computing for that. In this study the time efficiency of genetic algorithm with DE (Differential Evolution) implemented on the NVIDIA CUDA (Compute Unified Device Architecture) platform is compared. Differential evolution is a population-based direct-search algorithm for global optimization. Differential evolution is suitable for parallel implementation on the GPUs (Graphics Processing Unit). The original DE scheme is used in MOGA implementation. All operations of MOGA with DE were distributed among CPU (Central Processing Unit) and GPU for the most performance. Achievable speedups of the proposed MOGA were examined using a set of benchmark multi-objective problems DTLZ. Its performance was studied for the different number of criterions and population sizes. The obtained results indicate that proposed parallel MOGA with DE leads to speedups up to 4.7…10.2 times higher compared to one CPU thread. The results also show that the proposed GPU implementation of MOGA can provide better results in the shorter time or produce better results in equal time.
Keywords: Multi-objective optimization; Pareto set and front; Multi-objective genetic algorithms; Differential evolution; Parallel computing; CUDA technology.
П. В. Казаков (Брянский государственный технический университет, Брянск, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
P. V. Kazakov (Bryansk State Technical University, Bryansk, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд., перераб. и доп. М.: Дрофа, 2006. 175 с.
2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В. М. Курейчика. 2-е изд., испр. и доп. М.: ФИЗМАТЛИТ, 2006. 320 с.
3. Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. New York: John Wiley, 2009. 517 p.
4. Luna F., Nebro A. J., Alba E. Parallel Evolutionary Multiobjective Optimization // Parallel Evolutionary Computations / N. Nedjah, E. Alba, L. de Macedo (Eds.). Berlin: Springer, 2006. Р. 33 – 56.
5. Боресков А. В., Харламов А. В. Основы работы с технологией CUDA. М.: ДМК Пресс, 2010. 232 с.
6. Wong M. L. Parallel Multi-Objective Evolutionary Algorithms on Graphics Processing Units // Proc. of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (GECCO’09). 2009. Р. 2515 – 2522.
7. Mezura-Montes E., Velázquez-Reyes J., Coello Coello C. A. A Comparative Study of Differential Evolution Variants for Global Optimization // Proc. of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’2006). NY, 2006. P. 485 – 492.
8. Tušar T., Filipič B. Differential Evolution Versus Genetic Algorithms in Multiobjective Optimization // Proc. of the 4th Intern. Conf. on Evolutionary Multi-Criterion Optimization (EMO’2007). Berlin, 2007. V. 4403. P. 257 – 271. doi: 10.1007/978-3-540-70928-2_22
9. A Comparison of Many-Threaded Differential Evolution and Genetic Algorithms on CUDA / P. Kromer et al. // Proc. of the Third World Congress on Nature and Biologically Inspired Computing. 2011. P. 516 – 521.
10. De Veronese L., Krohling R. Differential Evolution Algorithm on the GPU with C-CUDA // Congress on Evolutionary Computation (CEC). 2010. P. 1 – 7. doi: 10.1109/CEC.2010.5586219
11. Zhu W., Li Y. GPU-Accelerated Differential Evolutionary Markov Chain Monte Carlo Method for Multi-Objective Optimization over Continuous Space // Proc. of the 2nd Workshop on Bio-Inspired Algorithms for Distributed Systems. 2010. P. 1 – 8. doi:10.1145/ 1809018.1809021
12. Казаков П. В. Использование дифференциальной эволюции при определении множества Парето генетическими алгоритмами многокритериальной оптимизации // Информационные технологии. 2015. Т. 21, № 2. С. 109 – 116.
13. Казаков П. В. Оценка эффективности генетических алгоритмов многокритериальной оптимизации. Часть 2 // Информационные технологии. 2012. № 9. С. 42 – 46.
14. Pospichal P., Jaros J., Schwarz J. Parallel Genetic Algorithm on the CUDA Architecture // Proc. of the European Conference on the Applications of Evolutionary Computation. Part I. V. 6024. 2010. P. 442 – 451.
1. Sobol' I. M., Statnikov R. B. (2006). The choice of optimal parameters in problems with many criteria. 2nd ed. Moscow: Drofa. [in Russian language]
2. Kureychik V. M. (Ed.), Gladkov L. A., Kureychik V. V. (2006). Genetic algorithms. 2nd ed. Moscow: FIZMATLIT. [in Russian language]
3. Deb K. (2009). Multi-Objective Optimization Using Evolutionary Algorithms. New York: John Wiley.
4. Macedo de L., Nedjah N., Luna F., Nebro A. J., Alba E. (2006). Parallel Evolutionary Multiobjective Optimization. Parallel Evolutionary Computations, pp. 33-56. Berlin: Springer.
5. Boreskov A. V., Harlamov A. V. (2010). CUDA Technology Basics. Moscow: DMK Press. [in Russian language]
6. Wong M. L. (2009). Parallel Multi-Objective Evolutionary Algorithms on Graphics Processing Units. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference (GECCO’09), pp. 2515-2522.
7. Mezura-Montes E., Velázquez-Reyes J., Coello Coello C. A. (2006). A Comparative Study of Differential Evolution Variants for Global Optimization. Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO’2006), pp. 485- 492. New York.
8. Tušar T., Filipič B. (2007). Differential Evolution Versus Genetic Algorithms in Multiobjective Optimization. Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization – EMO 2007, Vol. 4403, pp. 257-271. doi: 10.1007/978-3-540-70928-2_22
9. Kromer P. et al. (2011). A Comparison of Many-Threaded Differential Evolution and Genetic Algorithms on CUDA. Proceedings of the Third World Congress on Nature and Biologically Inspired Computing, pp. 516- 521.
10. De Veronese L., Krohling R. (2010). Differential Evolution Algorithm on the GPU with C-CUDA. Congress on Evolutionary Computation (CEC), pp. 1-7. doi: 10.1109/CEC.2010.5586219
11. Zhu W., Li Y. (2010). GPU-Accelerated Differential Evolutionary Markov Chain Monte Carlo Method for Multi-Objective Optimization over Continuous Space. Proceedings of the 2nd Workshop on Bio-Inspired Algorithms for Distributed Systems, pp. 1-8. doi:10.1145/ 1809018.1809021
12. Kazakov P. V. (2015). The use of differential evolution in determining the Pareto set by genetic algorithms for multicriteria optimization. Informatsionnye tekhnologii, 21(2), pp. 109-116. [in Russian language]
13. Kazakov P. V. (2012). Evaluating the effectiveness of genetic algorithms for multicriteria optimization. Part 2. Informatsionnye tekhnologii, (9), pp. 42-46. [in Russian language]
14. Pospichal P., Jaros J., Schwarz J. (2010). Parallel Genetic Algorithm on the CUDA Architecture. Proceedings of the European Conference on the Applications of Evolutionary Computation. Part I, Vol. 6024, pp. 442- 451.
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2019.03.pp.003-010
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2019.03.pp.003-010
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»