10.14489/vkit.2019.10.pp.013-020

DOI: 10.14489/vkit.2019.10.pp.013-020

Казаков П. В.
ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ КЛАСТЕРИЗАЦИИ ПОПУЛЯЦИИ В ПРОСТРАНСТВЕ ПЕРЕМЕННЫХ
(с. 13-20)

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

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

Kazakov P. V.
EFFICIENCY INCREASE OF MULTI-OBJECTIVE GENETIC ALGORITHMS USING THE CLUSTERIZATION OF A POPULATION IN THE VARIABLE SPACE
(pp. 13-20)

Abstract. The paper introduces a new manner for improving of obtained by MOGA (Multi-Objective Genetic Algorithm) solutions. It is based on the concept of dividing the population into set of clusters according to solutions similarity. In different of most MOGA the clusterization of population is implemented in the variable space, enables to enhance diversity of population and to increase the number of non-dominated solutions. The special procedures for the clustering of current population and copying the clusters in the next population were developed. The dominance principal by fitness-value is used for clustering. The number of clusters depends on additional parameter the radius of cluster’s hypersphere that is determined experimentally. By the special rule the individuals corresponded to centroids of clusters are copied in the new population. The clusters are recalculated for every population. The influence of the radius cluster to the number of non-dominated solutions variation was studied. The cluster modification should be integrated into any multi-objective genetic algorithm. By the analytical evaluation has been studied, this MOGA modification has additional computationally complexity from linear to quadratic. In experiments it was tested with the evolutionary algorithms SPEA2, NSGA-II on the special benchmark problems (DTLZ) with a various number of criteria using the set of performance indices. The used clustering in the variable space algorithms were achieved a better distribution and convergence to the true Paretofront in some cases.

Keywords: Multi-objective optimization; Pareto set and front; Multi-objective genetic algorithms; Clusterization of population.

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

Рус

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

Eng

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

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

Рус

1. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд., перераб. и доп. М.: Дрофа, 2006. 175 с.
2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. 320 с.
3. Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. Hoboken: Wiley, 2009. 536 p.
4. Казаков П. В. Кластерное расширение генетического алгоритма для решения многоэкстремальных задач оптимизации // Информационные технологии. 2009. № 8. С. 33 – 38.
5. 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. Р. 95 – 100.
6. Janson S., Merkle D. A New Multi-Objective Particle Swarm Optimization Algorithm Using Clustering Applied to Automated Docking // Hybrid Metaheuristics Second International Workshop, HM 2005. Lecture Notes in Computer Science. V. 3636. Р. 128 – 142.
7. Luna F., Nebro A., Alba E. New Ideas in Applying Scatter Search to Multiobjective Optimization // Evolutionary Multi-Criterion Optimization: Third Intern. Conf., EMO 2005. Lecture Notes in Computer Science. V. 3410. P. 443 – 458.
8. Казаков П. В. Оценка эффективности генетических алгоритмов многокритериальной оптимизации. Часть 2 // Информационные технологии. 2012. № 9. С. 42 – 46.
9. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA–II / K. Deb et al. // IEEE Transactions on Evolutionary Computation. 2002. V. 6, No. 2. P. 182 – 197.
10. Казаков П. В. Оценка эффективности генетических алгоритмов многокритериальной оптимизации. Часть 1 // Информационные технологии. 2012. № 8. С. 2 – 6.

Eng

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. Gladkov L. A., Kureychik V. V., Kureychik V. M. (2006). Genetic Algorithms. Moscow: FIZMATLIT. [in Russian language]
3. Deb K. (2009). Multi-Objective Optimization Using Evolutionary Algorithms. Hoboken: Wiley.
4. Kazakov P. V. (2009). Cluster extension of the genetic algorithm for solving multi-extreme optimization problems. Informatsionnye tekhnologii, (8), pp. 33 – 38. [in Russian language]
5. Zitzler E., Laumanns M., Thiele L. (2002). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Proceedings of the EUROGEN’2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pp. 95 – 100.
6. Janson S., Merkle D. (2005). A New Multi-Objective Particle Swarm Optimization Algorithm Using Clustering Applied to Automated Docking. Hybrid Metaheuristics Second International Workshop, HM 2005. Lecture Notes in Computer Science, Vol. 3636, pp. 128 – 142.
7. Luna F., Nebro A., Alba E. (2005). New Ideas in Applying Scatter Search to Multiobjective Optimization. Evolutionary Multi-Criterion Optimization: Third International Conference, EMO 2005. Lecture Notes in Computer Science, Vol. 3410, pp. 443 – 458.
8. Kazakov P. V. (2012). Evaluation of the effectiveness of genetic algorithms for multicriteria optimization. Part 2. Informatsionnye tekhnologii, (9), pp. 42 – 46. [in Russian language]
9. Deb K. et al. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation, Vol. 6, (2), pp. 182 – 197.
10. Kazakov P. V. (2012). Evaluation of the effectiveness of genetic algorithms for multicriteria optimization. Part 1. Informatsionnye tekhnologii, (8), pp. 2 – 6. [in Russian language]

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

Рус

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

DOI: 10.14489/vkit.2019.10.pp.013-020

Скопируйте 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.2019.10.pp.013-020

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.