10.14489/vkit.2014.09.pp.023-029

DOI: 10.14489/vkit.2014.09.pp.023-029

Аверченков В. И., Казаков П. В.
О НОВОМ СПОСОБЕ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ЭВОЛЮЦИОННЫХ МЕТОДОВ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
(с. 23-29)

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

Ключевые слова: многокритериальная оптимизация; принципы Парето; граница Парето; многокритериальные генетические алгоритмы; динамический размер популяции.

Averchenkov V. I., Kazakov P. V.
THE NEW MANNER FOR IMPROVING OF THE EVOLUTIONARY METHODS FOR A MULTI-OBJECTIVE OPTIMIZATION
(pp. 23-29)

Abstract. The new manner for a dynamic control of the population size in multi-objective genetic algorithms is suggested. A varying population size allows an algorithm to adapt to search space, to enhance diversity of population and to increase the number of nondominated solutions. This manner is based on using of the chromosomes with two additional parameters – an age and a lifetime. The «age» of a chromosome is equal to the number of generations the one stays in the population. The age increases after each generation and if it has exceeded the lifetime parameter value, a chromosome is removed from a population. The special expressions for the lifetime parameter calculation are obtained. It is recalculated every time after evaluated fitness of chromosome. A lifetime depends on Pareto rank and fitness of chromosome. A lifetime increases if one has improved in comparison with a previous generation. This model of SAPS (Self-Adaptive Population Size) can use with any multi-objective evolutionary algorithms and has relatively low additional computationally complexity. SAPS model was tested with the evolutio-nary algorithms NSGA-II, SPEA2 on the special benchmark problems (DTLZ) using the set of performance indices. The algorithms that used SAPS in many cases achieved a better distribution and convergence to the true Pareto-front than their respective predecessors.

Keywords: Multi-objective optimization; Pareto’s principles; Pareto front; Multi-objective genetic algorithms; Dynamic varying population size.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

В. И. Аверченков, П. В. Казаков (Брянский государственный технический университет) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

V. I. Averchenkov, P. V. Kazakov (Bryansk State Technical University) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Соболь И. М. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд., перераб. и доп. М.: Дрофа, 2006. 175 с.
2. Ногин В. Д. Принятие решений в многокритери-альной среде: количественный подход. 2-е изд., испр. и доп. М.: ФИЗМАТЛИТ, 2004. 176 с.
3. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы М.: ФИЗМАТЛИТ, 2006. 320 с.
4. Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Hoboken: Wiley, 2009. 536 p.
5. Казаков П. В. Генетические алгоритмы много-критериальной оптимизации. Обзор // Информационные технологии. 2011. № 9. С. 2 – 8.
6. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA–II / K. Deb еt al. // IEEE Transactions on Evolutionary Computation. 2002. V. 6, N 2. P. 182 – 197.
7. Scalable Test Problems for Evolutionary Multi-Objective Optimization / K. Deb еt al. // Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. N. Y.: Springer, 2005. P. 105 – 145.
8. Zitzler E, Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm // Proc. of the EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. 2002. P. 95 – 100.
9. Performance Assessment of Multiobjective Optimizers: An Analysis and Review / E. Zitzler еt al. // IEEE Transactions on Evolutionary Computation. 2003. V. 7, N 2. P. 117 – 132.

Eng

1. Sobol' I. M. (2006). Selection of optimal parameters in problems with multiple criteria. (2nd (Revised and Supplemented) ed.). Moscow: Drofa.
2. Nogin V. D. (2004). Decision making in multicriteria environment: a quantitative approach. (2nd (Revised and Supplemented) ed.). Moscow: FIZMATLIT.
3. Gladkov L. A., Kureichik V. V., Kureichik V. M. (2006). Genetic algorithms. Moscow: FIZMATLIT.
4. Deb K. (2009). Multi-objective optimization using evolutionary algorithms. Hoboken: Wiley.
5. Kazakov P. V. (2011). Genetic algorithms for multiobjective optimization. Overview. Informatsionnye tekhnologii, (9), pp. 2-8.
6. Deb K. еt al. (2002). A fast and elitist multiobjective genetic algorithm: NSGA–II. IEEE Transactions on Evolu-tionary Computation, 6(2), pp. 182-197.
7. Deb K. еt al. (2005). Scalable Test Problems for Evolutionary Multi-Objective Optimization. Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. N. Y.: Springer, pp. 105-145.
8. Zitzler E, Laumanns M., Thiele L. (2002). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Pro-ceedings of the EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pp. 95-100.
9. Zitzler E. еt al. (2003). Performance assessment of multiobjective optimizers: An analysis and review. IEEE Transactions on Evolutionary Computation, 7(2), pp. 117-132.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2014.09.pp.023-029

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2014.09.pp.023-029

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.