Introduction

There is a wide class of optimizing problems with restrictions on discrete values of solution elements (arguments of the objective function) [Ros00,VTE16]. These include many problems from combinatorics, graph theory, operations research. Mathematical apparatus of derivatives and gradients is not applicable for them, but it is successfully used in solving problems of continuous optimization [Kar14]. To solve some of them, exact methods with polynomial time asymptotic (for example, methods of Prim and Kruskal [Pri57,Kru56] for getting minimal spanning tree, Kuhn-Munkres method for assignment problem solving [Kuh56,Mun57], etc.) are well known, while other problems belonging to the NP class don't have similar methods. To solve them, in practice, heuristic methods are used successfully. They provide decisions of good quality for reasonable computing time.

Known methods for solving discrete optimization problems can be divided into the following classes:

• limited-search methods (Brute Force, branch and bound method [LD60], modifications of the Brute Force with limited number of branches or limited depth of the analyzed subtree within the combinatorial search tree, SAT-based methods [CD06,ZKS16]);

• methods with sequential formation of the decision (greedy methods, random and weighted random methods, ant colony optimization method [VDMT14, Dor92, VT14]);

• methods based on the modification of the current decision or set of decisions with using some rules that are specific to the problem being solved (random walks method, simulated annealing method, evolutionary (genetic) methods, bee colony method [GK14, KGV83, Kar83, PGKORZ05]);

Copyright c by the paper's authors. Copying permitted for private and academic purposes.

In: E. Ivashko, A. Rumyantsev (eds.): Proceedings of the Third International Conference BOINC:FAST 2017, Petrozavodsk, Russia, August 28 -September 01, 2017, published at http://ceur-ws.org

• methods based on the movement in arguments space with subsequent mapping of the current agent position to one of the decisions of discrete optimization problem (particle swarm optimization method, firefly method, fish school search method, gravitational search method, etc. [Kar14, GK14, KE95]).

Limited Brute Force methods cluster has exponential or factorial asymptotic time complexity in the common case, while other methods have polynomial asymptotic time complexity. By combining the elementary methods that are shown above, it is possible to construct hybrid multistep methods [Kar14].

Statement of the Problem

Different heuristic methods are characterized in practice both by the different costs of computer time, and by the different quality of the decisions obtained, in this view it is interesting to compare quality of decisions aimed to select the best of methods. For this purpose a test problem of getting shortest path

P (G) = a i1 = a beg , a i2 , ..., a iQ = a end in graph G = A, V was selected, where A = {a 1 , a 2 , ..., a N } is a set of vertices, |A| = N is a number of vertices (size of a problem), V = {v 1 , v 2 , ..., v M } ⊆ A × A is a set of arcs, |V | = M is a number of arcs, v i = a (i) beg , a (i) end , a (i) beg ∈ A, a (i)

end ∈ A, and the arcs are weighted by the length value

L(v i ) > 0, i = 1, M . Target function in the specified problem is a length of path L(P ) = R−1 j=1 L(a ij , a ij+1 ) → min, density of graph d(G) = M N (N −1) ∈ [0,0; 1,0]

has a role of restriction as in graphs with low density a large number of decisions are prohibited. Selected problem has exact optimal decision (abbr. O) that can be obtained polynomially using Dijkstra algorithm [Dij59] for a quadratic time, that allows to use it as test problem for estimating deviations of decisions quality from optimum for heuristic methods. In a number of combinatorial optimization problems it was shown [VVT15,VT15] that heuristic methods are characterized by significantly different behavior during solving problems with different size of a problem and different power of restrictions. For the purpose of careful analysis of this feature a computer experiment was organized. During this experiment it was formed a sample Λ = {G 1 , G 2 , ..., G K } of K = 1000 graphs with pseudorandom structure, given number of vertices N , density d and pseudo-random values of arcs lengths 0 < L(v i ) ≤ 1. For the obtained decisions (paths P with length L(P )) the following average parameters was calculated: average length of paths (abbr. AVG)

Q = K i=1 Q(G i )φ(G i ) K ,(1)

where Q(G i ) = L(P ∈ G i ) is the quality of the best decision (path with minimal length) for selected method, φ(G i ) ∈ {0, 1} is function that has 1 value if the decision was found with selected method and 0 otherwise; average deviation of quality of the best decision from optimum (abbr. DIFF)

∆Q = K i=1 (Q(G i ) − Q * (G i )) φ(G i ) K ,(2)

where Q * (G i ) is a quality of optimal decision (length of the shortest path) given by Dijkstra algorithm; probability of finding decision (abbr. PFD)

p = K i=1 φ(G i ) K (3)

and probability of finding optimal decision (abbr. PFOD)

p opt = K i=1 θ(G i ) K (4)

where

θ(G i ) = 0, Q(G i ) > Q * (G i ), 1, Q(G i ) = Q * (G i ).(5)

To compare methods for selected values of vertices number N and density of graph d it is required from several minutes to several hours of computational time. To analyze the behavior of methods under different conditions of use there was organized a computing experiment based on distributed computing project Gerasim@Home1 on BOINC platform [And04]. Within this experiment we studied the behavior of methods for 2 ≤ N ≤ 500 and 0 < d ≤ 0,2 with steps ∆N = 1 and ∆d = 0,001, obtained results are presented in this article. For each set of source data for iteration methods there was organized formation of C max = 1000 decisions with selection the best of them.

Brief Classification of Heuristic Methods with Sequential Formation of the Decision

We give a brief description of the heuristic methods (a detailed description is given in the works [VTE16, VDMT14, VT14]). As it has already been shown above, for optimal decisions with quality Q * (G i ) Dijkstra algorithm was used. With using a greedy method (abbr. G) from the current vertex a curr as a direction of movement such a vertex a i is chosen that L(a curr , a i ) = ∞ and i = arg min j L(a curr , a j ). With using random search method (abbr. RS) as a direction of movement random vertex a i is chosen that L(a curr , a i ) = ∞, and lengths of arcs L(a curr , a i ) do not effect the choice of direction. With using weighted random search method (abbr. WRS) direction of movement is chosen as i = arg min

j [L(a curr , a i )(1 + 2D(r k − 0,5))]

, where r k is a pseudo-random value with a uniform distribution in the range of r k ∈ [0,0; 1,0], L(a curr , a i ) = ∞. The meaning of the used heuristic is in combination of greedy and random methods of decisions forming by using variable parameter D of scatter about the greedy heuristic L(a curr , a i ) (with D = 0 method is equal to greedy, and with D 1 -to random search). In the ant colony method (abbr. AC) direction of movement is chosen as i = arg min j η α j τ β j r k , where η j = 1 L(acurr,aj ) , τ j is amount of pheromone at arc (a curr , a j ). During initializing of method all arcs have τ 0 of pheromone, after moving of Z ants of colony each of them increase pheromone value to ∆τ = Q L(P l ) value in the arcs of path P l , that was found by l-th ant of colony, after that pheromone is evaporated from all arcs: τ

(t+1) ij = τ (t) ij (1 − p)

, where t is a discrete time (iteration number). Schematically choosing of direction in combinatorial tree is shown in fig. 1. During solving problems with restrictions using heuristic methods with sequential formation of the decision the appearance of "dead ends" is possible where from the current vertex of the combinatorial tree it is impossible to go to any of the vertices of the underlying tier (in the problem of getting the shortest path in graph it is impossible to move to one of the vertexes which has not been visited yet). During increasing power of restrictions (in the problem of getting the shortest path in graph -during decreasing density of graph d) the probability of this situation in practice increases. For a greedy method this leads to the fact that if you get into the "dead end" the decision can't be found. For random and weighted random methods this leads to the appearance of iterations of work, where there is no correct decisions and, as a result, improvement of the record. With restriction on maximal number of iterations C max for these methods it is possible that a decision exists, but the algorithm does not find it because all attempts have been completed in "dead ends". For ant colony method presence of "dead ends" leads to situation when hitting the "dead ends" the ant does not mark the path by the pheromone and the algorithm actually stops functioning, because there is no finding new decisions and updating the record.

In the article [VMT14] as one of the ways out of this situation, it was suggested to make a combinatorial return to one tier of a combinatorial search tree upwards and then to visit the next (in lexicographical order) vertex behind the "dead end" (fig. 2).

Figure 2: Illustration of the principle of combinatorial returns: a -source graph (the shortest path between vertexes a 3 and a 1 is bolded, dashed line corresponds to the greedy decision ended in the "dead end"); bcorresponding combinatorial tree; c -the greedy decision with return from disallowed "dead end" vertex a 5 ; dorder of movement in combinatorial tree with return from -"dead end" vertex.

Number R of combinatorial returns must be limited by a reasonable value (in organized experiments value R = 1000 was used), otherwise when R → ∞ methods with sequential formation of the decision turns into the Brute Force when it is used in conditions of strong restrictions, that has negative influence on the time complexity. For selected value of R computing time costs was increased by no more than 1,5x times [VT116]. For all heuristic methods discussed above (G, RS, WRS and AC) the program implementations were developed both in basic version and with support of combinatorial returns principal (abbr. GR, RSR, WRSR and ACR correspondently).

Before using weighted random search and ant colony methods in practice it is required to select values of its tuning parameters (solve the problem of meta-optimization). For this purpose a number of computing experiments was organized where in correspondence with articles [VDMT14,VT14] the following values are selected: spread value D = 1,0, greed by path length α = 0,28, greed by pheromone β = 0,82, amount of pheromone at one act of colony Q = 1, initial pheromone amount τ (0) = 100, pheromone evaporation speed p = 0,1, colony size Z = 100. In all experiments selected tuning parameters are constant.

Computing Experiments and Analysis of the Experimental Data

The computing experiment took 4 months in the grid with real performance about 2 TFLOP/s. Figure 3 shows the experimental results for optimal decisions provided by Dijkstra algorithm. First of all it should be noted that the level lines in fig. 3a are very similar to hyperbolas in coordinates (d; N ). Minimal length of paths corresponds to the graphs with high density and big number of vertexes (top right corner in fig. 3). The greatest length of the paths is observed for graphs with low density with big number of vertexes (top left corner in fig. 3). Dijkstra's algorithm guarantees a decision in case of its existence (if the graph in which the path is found is connected), therefore the dependence in fig. 3b can be treated as probability of getting connected graph for selected values of N and d. During decreasing of graph d density for each N such value d can be chosen that probability of finding decision is p ≈ 1, but p < 1, and also value d , that p ≈ 0, but p > 0. For example, for N = 100 these values are d ≈ 0,063 and d ≈ 0,002. If in the selected range of densities d ≤ d ≤ d one of methods X provides the probability of obtaining a decision lower than the Dijkstra algorithm (p X < p O ), then this indicates that for some test cases decisions exist but have not been found.

Figures 4 and 5 show dependencies for greedy method (G) and for its modification with combinatorial returns (GR). Their analysis allows us to draw a number of conclusions. First of all, the analysis of deviations of decisions quality from the optimum (fig. 4a and 5a) shows that greedy decisions are several times worse than optimal ones, that is a known fact for most problems. Analysis of dependencies of decision finding probabilities for the considered pair of methods shows that greedy method is a subject to falling into the "dead ends" and its border d is located more to the right than the border of Dijkstras algorithm. Adding to it the possibility of making combinatorial returns shifts this boundary to the left (fig. 5b, the boundary shift is indicated by an arrow), providing a significantly higher probability of finding decisions, although the quality of the decisions themselves still leaves much to be desired. Probability of finding the optimal decision for both the methods is very small: it is equal to p = 0,2 for graphs with small amount of vertexes and high density, and significantly decreased with the growth of the problem size. Analysis of given areas shows that for graphs of high density d > d combinatorial returns are not required, but during density decreasing (or increasing power of restriction) they start to have a positive impact. Border between the areas of preferred usage of the considered pair of methods can be empirically approximated by a hyperbola N = A d , where A is some constant, from where it is possible to obtain the following expression:

N = A N (N − 1) M ⇒ 1 = A N − 1 M ⇒ M = A(N − 1).(6)

For the given pair of methods A ≈ 8. Using this expression, it can be concluded that in case of M > A(N − 1) a classical greedy method is efficient, but in case of M < A(N − 1) its efficiency can be statistically significantly increased by implementing support for combinatorial returns.

Similar dependencies were obtained for methods RS, RSR, WRS, WRSR, AC and ACR (fig. 7 -9). These methods demonstrate a substantially smaller deterioration in the quality of the decisions found with respect to the optimum, which particularly applies to weighted random search and ant colony methods as they have higher convergence rate [VT216]. Dependencies of the probability of finding decisions for basic implementations and implementations with support of combinatorial returns are qualitatively similar to the dependencies considered above for the pair of greedy methods: support of the combinatorial returns increases probability of finding decisions in the area d ≤ d ≤ d . The area of finding optimal decisions p opt → 1 is located mainly in the lower right corner of the diagrams, that corresponds to graphs with small number of vertexes. Adding support of the combinatorial returns expands the indicated area both in the direction of graphs with a large number of vertices (to the top) and toward graphs with a lower density (to the left).

Results of pair wise comparison of methods with and without combinatorial returns by criterion of the maximum probability to find optimal decision are shown in fig. 10. from them by the location of the boundary between the areas of preferential use of methods (by values of constants A X , X ∈ {RS, W RS, AC}). It should be noted that among the three algorithms without the support of combinatorial returns the ant colony method feels relatively comfortable in a larger range of graph densities (for them A AC A RS and A AC A W RS ). However, there is also an area of low-density graphs where support of combinatorial returns provides an advantage. Fig. 11 shows comparison results of all above-mentioned heuristic methods by the criterion of the maximum probability of finding optimal decision p opt .

Their analysis allows us to conclude that for dense graphs the ant colony method is the best among considered ones. During density decreasing from value d < d ≈ 4,5

N the modified method of an ant colony with support of combinatorial returns turns out to be more effective. In a narrow area of very small graph density the algorithms AC, ACR and RSR demonstrate approximately equal efficiency.

Prospects for the Future Investigations

The current series of experiments performed within Gerasim@Home project has several objectives and aimed to subset of heuristic methods with sequential formation of the decision only. In addition, it would be interesting to study the quality of solutions obtained using different iterative methods such as modifications of limited depth first search, group intelligence approaches [Kar83,PGKORZ05], modifications of simulated annealing [KGV83], random walks, particle swarm optimization [KE95] and so on. Also all of heuristic methods requires testing in different combinatorial optimization problems (logic multicontrollers design [Ros00], different graph theory problems, etc.). Fine tuning of variable parameters of methods during meta-optimization or adaptation is another one important problem that needs to be investigated.