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 формат).

Стоимость статьи 250 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

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

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2014.09.pp.023-029}

Eng

This article is available in electronic format (PDF).

The cost of a single article is 250 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 fill out the form below:

{jform=2,doi=10.14489/vkit.2014.09.pp.023-029}