Юртаев Александр Григорьевич — аспирант
Саратов, 410054
Alexander G. Yurtaev — PhD Student
Saratov, 410054
Введение. В современной инженерной и научно-технической практике многокритериальная оптимизация часто обеспечивает поиск компромиссных решений без задания весовых коэффициентов и границ, формируя Парето-фронт посредством эвристической аппроксимации на основе генетических алгоритмов. Однако даже аппроксимированный Парето-фронт представляет собой множество точек, что затрудняет анализ и отбор решений. Для упорядочения и структурирования полученных решений возможным решением становится кластеризация, позволяющая выделить репрезентативные группы компромиссов. Научная новизна предлагаемого метода кластеризации заключается в комбинации алгоритмов Ordering Points to Identify the Clustering Structure и k-means с выделением медоидов, обеспечивающей автоматическое удаление шума и компактное представление репрезентативных стратегий. Метод. Предложен метод двухэтапной кластеризации. На первом этапе применен алгоритм Ordering Points to Identify the Clustering Structure, с помощью которого строится упорядоченный профиль плотности и автоматически фильтруются шумовые точки по порогу досягаемости. На втором этапе использован алгоритм k-means, выполнено разбиение отфильтрованного ядра Парето-фронта на кластеры и вычислены центроиды, а затем медоиды — реальные представители данных. Основные результаты. Проведены два эксперимента на трехмерных множествах точек Парето-фронта (1226 и 2514 ядровых точек после фильтрации). В результате применения предложенной методики получено разбиение на 10 кластеров. Установлено, что после фильтрации доля шумовых точек составила менее 1 % от общего числа решений. Фильтрация позволяет существенно снизить значения метрики, оценивающей качество центров кластеров, при умеренном увеличении суммарного времени выполнения кластеризации. Показано, что малая рассогласованность центроидов и соответствующих медоидов свидетельствует о высокой репрезентативности полученных кластеров. Обсуждение. Предложенный комбинированный метод, сочетающий применение алгоритмов Ordering Points to Identify the Clustering Structure и k-means, требует настройки двух параметров, автоматически адаптируется к нелинейным плотностям и размерам входных данных. Область применения метода может быть расширена для любых задач многокритериальной оптимизации, решаемых посредством построения и анализа Парето-фронта, включая инженерную оптимизацию, логистику, энергетику и финансовое моделирование. В перспективе возможно внедрение адаптивных методов для автоматического определения оптимальных параметров используемых алгоритмов, а также обеспечения адаптации к динамическим изменениям многокритериальных задач.
In contemporary engineering and scientific practice, multi-objective optimization often facilitates the search for compromise solutions without prescribing weight coefficients or bounds, forming a Pareto front via heuristic approximation based on genetic algorithms. However, even an approximated Pareto front consists of a large set of points, which complicates analysis and selection of solutions. To organize and structure the obtained results, clustering can be employed to identify representative groups of trade-offs. The scientific novelty of the proposed clustering method lies in the combination of Ordering Points to Identify the Clustering Structure and k-means algorithms with the introduction of medoids identification, which ensures automatic noise removal and a compact representation of representative strategies. A two-stage clustering approach is proposed. At the first stage, Ordering Points to Identify the Clustering Structure algorithm is used to construct an ordered density profile and to automatically filter out noise points based on the reachability threshold. At the second stage, the k-means algorithm is applied to the filtered Pareto front core to partition it into clusters, compute the centroids, and then determine the medoids — real representative data points. Two experiments were conducted on three-dimensional Pareto front datasets (1226 and 2514 core points after filtering). As a result of applying the proposed approach, a partition into 10 clusters was achieved. It was found that after filtering, the proportion of noise points was less than 1 % of the total number of solutions. The filtering step significantly reduced the metric assessing the quality of cluster centers, with only a moderate increase in the total clustering time. A small discrepancy between centroids and their corresponding medoids indicates the high representativeness of the resulting clusters. The proposed hybrid method, combining Ordering Points to Identify the Clustering Structure and k-means algorithms, requires the adjustment of only two parameters and automatically adapts to nonlinear densities and input data scales. The scope of this method can be extended to any multi-objective optimization problems solved through the construction and analysis of the Pareto front, including engineering optimization, logistics, energy systems, and financial modeling. In the future, the approach may be enhanced by integrating adaptive mechanisms for automatic determination of optimal algorithm parameters, as well as dynamically changing multi-objective problem settings
The authors declare that there are no conflicts of interest present.