An optimization problem on a set of Euclidean combinatorial configurations is formulated. Peculiarities of applying genetic algorithms to solving this class of problems are explored. Principles of formation of an initial population and selection mechanisms are described. A choice of crossover and mutation operators is justified. Examples of the construction of crossover operators for sets of Euclidean configurations are given. A genetic algorithm of optimization on permutation configurations sets is presented. Based on the algorithm, a random search approach is offered for optimization on spherically-located and well-described sets. The algorithm was tested on a problems of balancing masses of rotating objects.
Traditionally, combinatorial optimization problems are considered as difficult [1]-[3], which leads to the necessity of developing effective approximate methods for their solution. Nowadays, development of theory and methods of computational intelligence regarding problems of combinatorial optimization is of interest of researchers. Of particular importance is a class of evolutionary methods [4]-[6], to which genetic algorithms belong [7]-[9]. Modern publications in this direction [10]-[14] prove the effectiveness of applying genetic and other evolutionary algorithms in solving combinatorial optimization problems.
In the development of combinatorial optimization theory, an important place is occupied by an area of formalization of concepts such as “combinatorial set”, “combinatorial object”, “combinatorial configuration”. Not of less importance is investigating properties of functions given on these sets. Combinatorial configuration is one of the fundamental concepts. Depending on classes of combinatorial configuration sets, various optimization problems arise. Respectively, methods of their solving are highly determined by the properties of these configurations’ sets.
In this paper, we consider a class of so-called Euclidean combinatorial configurations as the basis of developing new approaches to solving combinatorial optimization problems by genetic algorithms. 2
The Euclidean Combinatorial Configurations
: U V
(
We represent the combinatorial configuration of a tuple ,U ,V , , where
U { u1 ,...,un } – is initial set, V { v1 ,...,vk } v is resulting set, is a mapping of
type (
The papers [16-18] are devoted to the study of combinatorial configurations. Further development of the concept of a combinatorial configuration was made by weakening the conditions on the finiteness of V [11, 18]. Thus, it is assumed that the resulting set V can be countable, and a combinatorial configuration, in this case, is called a combinatorial object. In [11, 18] another direction for a generalization of the concept is proposed. Namely, combinatorial objects of order k are defined that allows to expand significantly the range of real-world problems that can be formalized.
We focus on considering a class of combinatorial configurations where elements of the resulting set V are numerical vectors. The selection of such a class is justified by a wide range of real problems, in which the elements of the initial set U are characterized by a certain set of numerical parameters (for example, physical and metric characteristics). First of all, it concerns the placement problems for geometric objects and other problems of Geometric Design. The synthesis of spatial configurations is based on the concept of configuration spaces of geometric objects proposed in [19-22].
Let us B be the set of vectors of a space Rm of the same dimension m , i.e., bl b1l ,...,bml T Rm , l Jk . Let B be the resulting set V . Then the configuration will be an ordered sequence of vectors of b j1 ,b j2 ,...,b jn B . Each configuration bj1 ,bj2 ,...,bjn is put in a one-to-one correspondence to a vector x x1 ,..., xN RN , N nm , i.e., there exists a bijection such that: x , =1 x .
x x1 ,..., xN ( b1 j1 ,...,b1 jn ,b2 j1 ,...,b2 jn ,...,bmj1 ,...,bmjn ) .
Definition. A Euclidean combinatorial configuration (an e-configuration) is a mapping : ,U ,B, R N , where B is the resulting set; is a mapping of the form : U B ; are constraints on the mappings ,.
We represent the Euclidean configuration by a tuple ,U ,B, . Let be a set
whose elements are all possible combinatorial configurations for the given U ,B ,
which satisfy a system of constraints . Then will be a Euclidean combinatorial
set [23], and its image E of the set in RN will be a set of all Euclidean
combinatorial configurations that satisfy (
Genetic Algorithms for Optimization on C -Sets
Let us consider an optimization problem on a C -set E as follows:
f ( x ) min, x E .
(
Methods of solving optimization problems on C -sets, as a rule, are based on applying the theory of convex extensions and extremal properties of functions defined on vertex-located sets, e.g., sets coinciding with its convex hull vertex sets [23-26]. Among vertex-located sets, there are many those inscribed into a hypersphere. Such sets are called polyhedral-spherical, properties of which allow developing specific optimization methods [27] - [32].
Let us consider features of an implementation of genetic algorithms for optimization on C -sets. Genetic algorithms operate with a variety of solutions (populations) formed by a sample of individuals. Chromosomes form individuals with parameters of the problem coded in them. Chromosomes are ordered sequences of genes. A gene is an atomic element of a genotype, in particular, of a chromosome. A set of chromosomes of each individual determines its genotype (a structure). Thus, the individuals of the population can be either genotypes or single chromosomes. The totality of external and internal signs corresponding to a given genotype determines a phenotype of the individual, i.e., decoded structure or a set of the considered problem parameters.
For the class of combinatorial optimization problems under consideration, we assume that the genotype and phenotype of the population individuals coincide, the chromosome is a feasible e-configuration x x1 ,..., xN , and the genes are the values of its components in the sequence. Solutions are positioned in the population by their position on the surface of the function being examined. In this case, new solutions are generated successively as different combinations of parts of the existing individuals of the populations.
Typically, the generation of the initial population involves a random selection of individuals. For our class of problems, we are talking about a random choice of feasible e-configurations. This generation problem is of independent interest and is solved depending on the class of configurations under consideration.
The next step is to select the parent pairs. As a rule, the elite selection is applied in this case, i.e., it is selected k individuals with the best found so far values of the objective function f ( x ) and parent pairs are composed of them. If one selects all possible combinations of parental pairs, there will be k( k -1 ) / 2 pairs in total. A specifics of the class of problems under consideration make it possible to offer the following approach to the choice of parental pairs. Evaluating the Euclidean distances between the best k individuals, one can cluster the searching domain. Let there are choose k0 k clusters, in each of which nearby individuals are grouped. Parent pairs are selected from only one cluster. Naturally, in this case, the number of descendants will be less than with a full search of pairwise combinations. However, different rules of crossing, as well as mutations allow getting the required amount of offspring.
In connection with this, we describe the methods for the formation of the crossover operator based on the properties of various classes of sets of e-configurations. Suppose two individuals – e-configurations x x1 ,..., xN and y y1 ,..., yN - are chosen for crossing. The most common methods of crossbreeding are single-point, two-point and, in general, k -point crossovers. In this case, the parents are divided into the points j1 , j2 ,..., jk , where j1 j2 ... jk , and their parts alternate in the offspring. Also, a uniform crossover is well-known for which the value of the component is taken from the first parent with probability p and the second parent with probability (1- p ) .
A generalized crossover is of interest in which a special bit mask vector determines which a child gene inherits from the parent.
The complex combinatorial structure of the set E leads to the fact that the resulting descendants x and y , as a rule, do not satisfy the constraint system . Therefore, the crossover operators demonstrated above will be called quasi-crossover ones. The result z of the quasi-crossover under Euclidean combinatorial configurations x x1 ,..., xN and y y1 ,..., yN is represented in the form z = H( x, y ) .
To form feasible e-configurations by the quasi-crossover of parental individuals, special transformations of z can be required. In this regard, we propose the following approach to choose a Euclidean combinatorial configuration z z1 ,...,zN that satisfies the constraint system and is closest to the individual z z1 ,..., zN obtained as a result of quasi-crossover. Thus, we have the auxiliary problem of projecting a point z onto the C -set E , which solution is z PrE z .
Consequently, the crossover operator for the pair x x1 ,..., xN and y y1 ,..., yN of e-configurations is representable as z PrE H( x, y ).
A search of z implies solving the optimization problem
z z min, z E .
A specifics of different C -sets allows including many of them in a class of
welldescribed ones [33], i.e., sets on which linear problems are polynomially solvable. If,
in addition, E is inscribed into a hypersphere, the problem (
A set E Rn is said to be spherically-located if there exist such τ R n and a number r 0 such that for any z E z τ r.
(
Let E be a spherically located C -set, then, by (
1 N where z z0 2 z τ 2 z0 τ 2
N 2( z τ,z0 τ ) ci zi b,
i 1
N N ci 2( zi0 τi ), b r 2 ( zi0 τi )2 2 τi ( zi0 τi ).
i 1 i 1
Thus, the solution of problem (
N function f( z ) ci zi on the set E , equivalently, on the polyhedron conv E .
i 1
Developing this approach, we propose the following ways of obtaining descendants for individuals x x1 ,..., xN and y y1 ,..., yN . Considering that individuals Euclidean combinatorial configurations - are elements of Euclidean space, we use the property of linearity of this space. To search for offspring, we will choose a linear combination of individuals x and y , and then perform projecting onto E .
a simple linear combination of parental pairs:z PrE (x + y) ;
Let us consider a general approach for the formation of a crossover operator that takes into account different schemes for constructing linear combinations x and y :
a weighted linear combination of parental pairs in accordance with the values
of the function f ( x ) at these points
z PrE xf (x) + yf (y) .
(
Moreover, in the maximization problem, a larger coefficient corresponds to a larger value of the function; a randomized weighted linear combination:
z PrE pxf (x) + ( 1 - p )yf (y) , where p is a random variable uniformly distributed on a segment 0,1 .
In general, it makes sense to assume that the descendant retains the genes of its parents as well as of other ancestors. Then the crossover operator with a weighted linear combination of k individuals will take the form:
k z PrE xi f (xi )
i1 or a randomized weighted linear combination:
k z PrE pi xi f (xi ) ,
i1 k where pi 1 .
i 1 4
A Genetic Algorithm of Optimization on the Permutation Set Let us consider the application of the described approach in solving the optimization problem on the combinatorial set of permutations (without repetitions). In this case, the Euclidean combinatorial configuration ,,U , B, is given by a bijective mapping and a set of constraints . Let the set B be such that m 1, k N n , i.e., B b1 ,b2 ,...,bn is the set real numbers ordered as follow b1 b2 ... bn . Then the Euclidean combinatorial configuration z z1 ,..., zn Rn is an ordered set of numbers from B . In particular, we can choose B Jn .
The set of all Euclidean combinatorial configurations satisfying the above property is called the basic permutation (without repetitions) C -set, which we denote by E( B ). It is known [34, 35] that the set E( B ) is polyhedral-spherical and coincides with the set of solutions of the system of linear and quadratic constraints: n n zi bi , i 1 i 1 i W zi
W bi , W Jn , i 1 n zi 2 i 1 n 2 bi , i 1 1n i n 1bi where W card W .
E( B ) at the point z z1 ,...,zn , where z i 1 ,...,n , i Jn , i j i, j Jn , i j is such that E( B ) is well-described set. n ci zi attains its minimum on the set i 1 bi , i Jn , and the sequence c1 ... cn . Thus, i Jn and the sequence 1 ,...,n , i J n , that z01 ... z0n .
Since the set E( B ) is polyhedral-spherical and well-described, then for any point z0 z10 ,..., zn0 Rn it is possible to find the nearest point of E( B ) in the closed form. Namely, it is representable in the form z z1 ,...,zn , where z i bni1 , i j i, j Jn , i j is such
The results are directly generalized to the case if k n , but E is still consists of permutation configurations induced by the same multiset. In this case, E is the basic permutation with repetitions C -set. This two classes of permutation C -sets are united in a class of basic generalized permutation C -sets to which the above results are applicable. Also, the Boolean C -set Bn along with its special subclasses such as the Boolean permutation C -set, the Boolean half-cube C -set, permutation matrices set are spherically-located and well-described. Respectively, the above results are extendable to the classes. 5
A Hybrid Approach to Optimization on C -Sets
Consider the optimization problem (
E is spherically-located, namely,
E Sr ( a ) .
(
Note that together with the finiteness of E , the condition (
E vert P ,
(
E is well-described (
Thus, (
So, a search for new approaches to the solution of the problem (
An interesting feature of optimization over sets of type (
We offer the following hybrid method of a random search for solving (
Step 0. Put parameter m Z ;
Step 1. Initial iteration: i 0 . Generate M -element sampling (an initial population) from E : X i xij jJM , where M C m2 .
The initial record is f min min f xij , xmin arg min f xij .
jJM jJM
Step 2. Perform a descent from the individuals along the adjacent vertices to local minimizers of f x : Y i yij jJM , where yij - is a local minimizer of f x obtained from xij .
Step 3. Form a basis S Y i of the multiset Y i , i.e., a set of its various elements. From Y i yij jJM , choose m the best ones by values of f x and form a set Z i zij jJm from them.
if f min min f zij , then f min min f zij , xmin min f x .
jJm jJm xZi Step 5. Make the crossing within Z i , namely: j j' find a center of the segment zij , zij' - zijj' zij zij'
2 ' i and project z jj' onto E creating in such a way a new M -element sampling (a new population) from E :
Z' i z'jij'
, Z' i M , j, j' z'jij' PrE zijj' .
1 j j'm
Step 6. Set i i 1 . Check the termination condition. If it does not hold, set X i Z' i1 and go to Step 2.
As a termination criterion, an achievement of the maximum number of iterations, non-improvement of the current record for a prescribed number of iterations, and so on can be applied.
The advantage of the offered method is that it uses the structural specifics of each particular combinatorial set. On the one hand, it allows, when crossing distant elements, obtaining feasible elements, differ significantly from the elements, then performing a search in a vicinity of the new elements, thus decreasing the probability of omitting an exact solution. On the other hand, if the points are subjected to the crossing, which are already sufficiently close to each other, then the new points will "inherit" general properties of both "parents". For instance, if two points belong to the same hyperface of a polytope, then as a result of their crossing is also a point on the hyperface. 6
Consider the use of the proposed genetic algorithm in solving the problem of balancing solids. There are a set of points Aj ( x j , y j , z j ), j J N 1,2,..., N in the space R3 and a set of geometric objects Si , i J N with masses mi , i J N , whose centers of mass are at points Ti ( xi , yi , zi ), i J N respectively. It is necessary to place the center of gravity of each of the objects Si , i J N in one of the points Ai , i J N so, that the deviation of the center of gravity of the system relative to the point A0 ( x0 , y0 , z0 ) was minimal. If the deviation of the center of gravity of the placed objects from a point A0 is considered in the Euclidean metric, then the objective function of the problem can be written as follows: where
F( m )
2 2 2 , N mi xi x0 i1
N mi yi , y0 i1
N mi zi , z0 i1
,
N m mi , m ( m1 ,...,mN ) .
i1 m m m
Since each point Ti , i J N , must be placed in one and only one of the points Aj , j J N , the given task belongs to the class of assignment problems. Therefore, it can be formulated as an optimization problem on the set of N -permutations induced by a masses’ set m1,..., mN .
This class includes a problem of balancing masses of rotating parts, occurred in a turbine construction, power plant engineering, etc.
Problem statement: on a perfectly balanced disk, it is necessary to place the blades with the specified angular pitch so that the total unbalance of the system is minimal. The objective function of the problem is determined by the static moments of the blades with respect to a pair of mutually perpendicular axes. Let mi , i J N be the static moments of the blades about axes of their coordinate systems. If the blade is at an angle k to the axis Ox , then, about this axis, its moment is equal mi cos k and about the axis Ox
mi sin k in a coordinate system associated with the disk. Then
the total imbalance of the system of the blades Si , i J N is as follows:
f ( m ) i1 mi cos i i1 mi sin i 2 1/ 2 ,
N 2 N
(
We tested the proposed genetic algorithms for solving the balancing problem (
Also, it was solved a test problem of balancing rotating masses offered in [36]. The
unbalance was calculated using the formula (
The report offers a new approach to implementing genetic algorithms in Combinatorial Optimization. A notion of a Euclidean combinatorial configuration is introduced as a mapping of a finite abstract set of an arbitrary nature into Euclidean space. As a result of this mapping, an optimization problem over a combinatorial configuration set is equivalently formulated as a discrete optimization problem on a finite point configuration which elements are Euclidean combinatorial configurations. Consideration is given to the specifics of implementing genetic algorithms to solving this class of problems: methods for the formation of the initial population and selection mechanisms are proposed, and the choice of crossover and mutation operators is formalized and justified. As an example, it is considered optimization on Euclidean permutational configurations. Based on the genetic algorithm, a random search method is offered for optimization over spherically-located and well-described sets that cover a wide class of problems in theoretical and practical domains. 24. Yakovlev, S.V.: The theory of convex continuations of functions on vertices of convex polygons. Comp. Math. and Math. Physics 34, 959-965 (1994) https://dl.acm.org/citation.cfm?id=196926. 25. Yakovlev, S.V.: Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics, vol. 25, no. 3, pp. 385-391 (1989) doi:10.1007/BF01069996. 26. Yakovlev, S.V., Valuiskaya, O.A.: Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukrainian Mathematical Journal, vol. 53, no.9, pp. 1535-1545 (2001) doi:10.1023/A:1014374926840. 27. Stoyan, Y.G., et al.: Quadratic optimization on combinatorial sets in Rn. Cybernetics and
Systems Analysis, vol. 27, no. 4, pp. 561–567 (1991) doi:10.1007/BF01130367. 28. Stoyan, Y.G., et al.: Construction of convex continuations for functions defined on a hypersphere. Cybernetics and Systems Analysis, vol. 34, no. 2, pp. 27–36 (1998). doi:10.1007/BF02742066. 29. Yakovlev, S.V., Grebennik, I.V.: Localization of solutions of some problems of nonlinear integer optimization. Cybernetics and Systems Analysis, vol. 29, no. 5, pp. 727-734 (1993) doi:10.1007/BF01125802. 30. Yakovlev, S.V., Pichugina, O.S.: Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybernetics and Systems Analysis, vol. 54. no. 1, pp. 99-109 (2018) doi:10.1007/s10559-018-0011-6. 31. Pichugina, O., Yakovlev, S.: Optimization on polyhedral-spherical sets: theory and applications. Proceedings of the IEEE First Ukraine Conference on Electrical and Computer Engeneering, pp. 1167-1175 (2017) doi:10.1109/UKRCON.2017.8100436 32. Yakovlev, S.V., Pichugina, O.S., Yarovaya, O.V.: Polyhedral spherical configuration in discrete optimization. Journal of Automation and Information Sciences, vol. 51, no. 1, pp. 38-50 (2019). 33. Berstein, Y., et al.: Parametric nonlinear discrete optimization over well-described sets and matroid intersections. Math. Program., vol. 124, no. 1–2, pp. 233–253 (2010). 34. Yemelichev, V.A., et al.: Polytopes, graphs and optimisation. Cambridge University Press,
Cambridge (1984). 35. Pichugina, O.S., Yakovlev, S.V.: Functional and analytic representations of the general permutations. Eastern-European Journal of Enterprise Technologies, vol. 1, no. 4, pp. 2738 (2016) doi:10.15587/1729-4061.2016.58550. 36. Stoyan, Y.G., et al.: Method of balancing rotating discretely distributed masses.
Energomashinostroenie, no. 2, pp. 4–5 (1982).