Об одном классе генетических алгоритмов в задачах оптимизации на комбинаторных конфигурациях

Abstract

В статье введено понятие евклидовой комбинаторной конфигурации как отображения абстрактного множества в арифметическое евклидовое пространство. Сформулирована задача оптимизации на множестве евклидовых комбинаторных конфигураций. Рассмотрены особенности применения генетических алгоритмов для решения указанного класса задач. Описаны принципы формирования начальной популяции, механизмы отбора, выбор операторов кроссовера и мутации. Подход иллюстрируется на задаче комбинаторной оптимизации на множестве перестановок. Приведены примеры построения различных операторов кроссовера для евклидовых конфигураций перестановок. Про один клас генетичних алгоритмів в задачах оптимізації на комбінаторних конфігураціях. У статті введено поняття евклідової комбінаторної конфігурації як відображення абстрактної множини в арифметичний евклідовий простір. Сформульовано задачу оптимізації на множині евклідових комбінаторних конфігурацій. Розглянуто особливості застосуван ня генетичних алгоритмів для розв’язання зазначеного класу задач. Описано принципи формування початкової популяції, механізму відбору, вибір операторів кросовера і мутації. Підхід ілюструється на задачах комбінаторної оптимізації на множині перестановок. Наведені приклади побудови різних операторів кросовера для евклідових конфігурацій перестановок. On the class of genetic algorithms in optimization problems on combinatorial configurations. The concept of the euclidean combinatorial configuration as the mapping of an abstract set into an arithmetic euclidean space is introduced. The problem of optimization on the set of euclidean combinatorial configurations is formulated. The peculiarities of the application of genetic algorithms for solving this class of problems are considered. Principles of formation of the initial population, selection mechanisms, choice of crossover operators and mutation are described. The proposed approach is illustrated on the problem of combinatorial optimization on the set of permutations. examples of the construction of various crossover operators for euclidean permutation configurations are given