In the analysis of methods of multicriteria optimization. The detailed implementation of the parallel algorithm of the simulated annealing method is reproduced by the example of the extension of a large-scale travelling salesman problems. For this purpose are used such properties as multithreading and multicore of modern computer systems. An application software system was developed. We conducted a number of experimental studies. Adhering to the results that indicate that more computational process optimization is available that is at the optimal gap of the multicriteria optimization problem, the large rate for probable variations are parallel threads and computer cores.
In the process of designing intelligent control systems, there is often the task of
determining the best values for the parameters or structure of objects [
For example, the task of the travelling salesman problem is widely used in
computer-aided design, transportation systems, PCB (printed circuit boards) manufacturing,
protein structure studies, X-ray crystallography, and other fields. An important feature
of these problems is their large dimension and the inability to obtain real-time
solutions [
Purpose and task. The purpose of this work is to parallel the simulated annealing method and to develop software for large-scale multicriteria optimization. To achieve this goal, you must solve the following problems: ─ To analyze the existing methods of multicriteria optimization and to outline the advantages of using the simulated annealing method; ─ Develop an application software system to parallelize large-scale problem solving, based on the simulated annealing method; ─ Without reducing the generality, as an example of solving a travelling salesman problem, to evaluate the effectiveness of the proposed algorithm of parallel calculations in terms of quality and timing of the task based on the experimental studies and comparative analysis of the results obtained.
The object of study – Is the process of paralleling the annealing method when solving large-scale multicriteria optimization problems.
The subject of the study – Is methods, algorithms and software for solving largescale multicriteria optimization problems.
Research methods. The simulated annealing method to solve large-scale multicriteria optimization problems was analyzed in this work. For the parallelization, it is suggested to use the many thread properties and Java programming tools. Algorithm theory, object-oriented programming methods were used in the development of the software. 2
The optimization problem as a whole is reduced to finding the extremum (minimum
or maximum) of the objective function with given constraints [
The values of the vector variables must be defined: x (x1, x2 ,..., xm ) , which satisfy the limitation of appearance gi (x1, x2 ,..., xm ) bi , for every i 1, ..., k and at which the maximum or minimum of the objective function is reached f (x) (x1, x2 ,..., xm ) : f (x) (x1, x2 ,..., xm ) (max, min) . The final solution to the problem is a pair that consists of the optimal solution and the optimal value of the objective function.
The methods of mathematical programming give a great variety of algorithms for
solving this problem [
Local extremum search algorithms are designed to determine one of the local extrema on the set of endless solutions in which the objective function takes the maximum or minimum value. In their construction, both deterministic descent in the extremum and random search can be used. The deterministic methods distinguish between zero-order and gradient (1st and 2nd order) methods. The first ones are based on calculations only of the values of the optimized function. The second use partial derivatives of the second order. Methods of stochastic programming or neural networks are used to find extremum in cases where the type of optimized function is not fully known or its structure is too complex. The effectiveness of the optimal search procedure - the ability to find the solution and the convergence to the solution on the speed depend on the type of function and the method applied to it.
Of the direct methods of multicriteria optimization in the search for local
extremum the most famous are [
The task of finding the global extremum of a function on a valid set X is to find the point x X , for which is executed: f (x ) f (x), f (x ) f (x) for each x X . Limitations related to computational error and other factors often do not allow finding the exact solution to the problem. In this case, there is a search for an approximate solution, that is, the point of many optimal solutions X x X : f (x) f (x ) . Finding the exact solution can be considered as a case of searching for a close solution with 0 .
The global extremum search algorithms are divided into deterministic, statistical
and combined [
Determined methods for finding a global solution include the Gomori algorithm or
the cutting-plane method. The latter is an alternative basis for the construction of both
accurate and approximate algorithms for solving integer programming problems.
Currently, their high efficiency in combination with the branch and bound
method [
In severe cases, optimality may not be obtained or proved by an acceptable number of steps, however, even in this case, the clipping methods allow us to find an approximate integer solution with a given error (in the previously known neighborhood of the optimal solution).
Cutting-plane method algorithms can be effectively used to solve both partial integer programming problems, including the traveling salesman problem, the maximum cut problem, the knapsack problem, and the overall integer linear programming problem.
Compared to branch and bound methods, cutting-plane methods are more technological in programming because they do not require extra amount of RAM to store the decision tree, but at the same time less versatile because they are not able to work with relaxed subtasks that are convex programming tasks. The first cutting-plane algorithm was proposed by R.E. Gomori in 1958. Currently, these methods are effectively used to solve various tasks, including the travelling salesman problem.
Recent studies [
Genetic algorithms are a class of optimization methods based on imitations of
processes occurring in nature, in particular natural selection – a concept voiced from the
evolutionary theory of Charles Darwin [
Reformulate the optimization problem as the problem of finding the maximum of a function f (x1, x2 ,..., xn ) , called the fitness function. It is necessary that f (x1, x2 ,..., xn ) 0 in a limited area of definition, continuity and differentiation are absolutely not required. Each parameter of the fitness function is encoded by a row of bits. The individual will be called a row, which is a concatenation of rows of an ordered set of parameters.
The versatility of genetic algorithms is that only parameters such as adaptability and decision coding depend on a particular task. The rest of the steps for all tasks are the same. With the function of fitness among all individuals, the population distinguishes: ─ the most adapted, which get the opportunity to cross and give offspring; ─ the worst (bad decisions) that are removed from the population.
In addition to the global extremum search methods described above, there is also the method of simulated annealing that was selected in the article for further research.
The algorithm of simulated annealing is based on the simulation of a physical process that occurs during crystallization of a substance from a liquid state into a solid, including when annealing of metal. The final state after crystallization corresponds to the minimum energy of the lattice configuration.
Before applying any optimization algorithm, the data on which the model will be formed are selected according to certain requirements, namely: 1. Volume and representativeness, that is, the data should be as fresh as possible, and the sample should be large depending on the number of parameters being optimized. 2. The minimum of rules and parameters, because with the increase of parameters that are optimized, the probability of fitting the model to historical data increases, rather than reflecting the real patterns of market behavior. 3. The sample should be divided into two parts. One part of the data to create a model, the other – to test the created model. 3
Without reducing the generality, let us look at the main aspects of parallelizing the
annealing simulation method, as an example of solving a traveling salesman problem.
It is known that the traveling salesman problem has a wide application [
The traveling salesman problem can be represented as a model on a graph, that is, using vertices and edges between them. Thus, the vertices of the graph correspond to the cities and the edges (i, j) between vertices i i j - ways of communication between these cities. To each rib (i, j) it is possible to set the criterion of profitability of the route Ci, j 0 , which can be understood as, for example, distance between cities, time or cost of travel. Thus, the solution to the traveling salesman problem is to find the Hamilton cycle of the minimum weight cycle in a fully weighted graph. 4
The following describes the algorithm of the annealing method. This algorithm is proposed in the paper to be used in solving large-scale multicriteria optimization problems.
The main elements of the annealing method are: 1. A limited set S .
A valid target function J , that is defined at the set S . Let us mark S S,, the set of global minimum of the function J .
For each i S,, call the set S (i) S {i} as the set of adjacent nodes of i . 4. For each i set of positive coefficients qij , j S (i) , such that qij 1. jS (i)
Suppose that j S(i) if and only if i S (i). 5.
Non-growing function T : N (0, ), called the freezing schedule and T (t) temperature of the moment t.
6. Initial conditions x(0) S.
The algorithm is based on a discrete-time inhomogeneous Markov chain x(t),, whose development is as follows: 1. If the current state x(t) , equivalent to i , select the next node j for i randomly, the probability of choosing an individual j S(i) is qij . 2. Then the next state x(t 1) is defined as follows: 2.1. 2.2.
If J ( j) J (i), then x(t 1) j.
If
J ( j) J (i), then x(t 1) j
with the probability exp(J ( j) J (i) / T (t), else x(t 1) i.
Formally, j i, j S(i).
1 P x(t 1) j x(t) i qij exp T (t)
max J ( j) J (i) , of if
If j i, j S(i), then P x(t 1) j x(t) i 0.
You can justify the described method by considering the inhomogeneous Markov chain xT (t), for which temperature T (t) is kept constant level of T . Suppose that the Markov chain is irreducible and aperiodic and qij q ji for every i, j. Then xT (t) is a Markov reversible chain with its invariant probability of distribution 1 J (i) T (i) exp T , i S, where ZT - is the normalizing constant. At T 0,
ZT
probability distribution T concentrates on the plural S the global minimum. The
conditions of convergence of the algorithm are formulated by Hayek [
Java implements integrated multithreaded programming support. A multithreaded program contains two or more parts that can be executed simultaneously.
Each part of such a program is called a thread, and each thread specifies a separate execution path. In other words, multithreading is a specialized form of multitasking.
In a multitasking environment, the smallest element of managed code is thread. This means that one program can perform two or more tasks simultaneously. For example, a text editor can format text at the same time as it is printed, as long as the two actions are performed by two separate threads.
Multithreading allows you to write effective programs that make the most of the available power of the processor of the system. Another advantage of multithreading is that it minimizes downtime. This is especially important for interactive Java-based networking environments, as they have idle time and downtime.
For example, the speed of data transmission over a network is much lower than the speed at which a computer can process it. Even reading and writing local file system resources is much slower than the processing speed of the processor. And, of course, the user enters the keyboard much slower than the computer can process.
In single-threaded environments, your application is forced to wait for such tasks to complete before moving on to the next one, even if the program is idle most of the time, waiting for input. Multithreading helps reduce downtime because other threads can run while one waits.
Java assigns to each thread a priority that determines the behavior of that thread relative to others. Thread priorities are given by integers that determine the relative priority of one thread over the other.
The priority value itself is irrelevant – the higher priority of thread is not executed faster than the lower priority when it is the only executable thread at this time.
Instead, the thread priority is used to make the decision when switching from one running thread to another. This is called context switching. The rules that determine when context switching should take place are quite simple.
The thread may voluntarily give way to management. To do this, you can either explicitly concede the execution queue, suspend the thread, or block the I/O wait time. In this scenario, all other threads are checked, and the CPU resources are transferred to the thread with the highest priority ready to execute.
The thread may be interrupted by another, more priority thread.
In this case, the low priority thread, which is not occupied by the processor, is simply terminated by the high priority thread, no matter what it does. 5
─ Set the initial temperature and random initial solution; ─ We get into a cycle that is active until the condition is reached. ─ Now we choose a neighbor making small changes in the decision. ─ We then decide whether a new decision is worth considering. ─ We reduce the temperature and make a new iteration of the cycle.
For better optimization when initiating a temperature variable, you should choose a temperature that will initially allow practically any movement against the current solution. This gives the algorithm a better idea of exploring the entire search space before cooling and settling in a more focused area.
For a better understanding of the algorithm, we decided to visualize the results. In Fig. 1 is shown the initial map of the cities to be crawled.
In Fig. 2 is shown the operation of the algorithm for the number of cities: 20 and cooling rate 0.1. And in Fig. 3 at the same number of cities and cooling rate – 0.0001.
In Fig. 4 is shown the operation of the algorithm at a coolingrate of 0.1 and the number of cities: 100. And in Fig. 5 – at a coolingrate of 0.0001 and the number of cities: 100.
From the results of testing the algorithm at different cooling rates, we can conclude that the lower the cooling temperature, the better the algorithm works to find a solution to the travelling salesman problem.
For the sake of clarity and objective assessment of parallelization performance, tests were conducted on different cities and PCs with different amount of cores.
In the Tabl. 1 is shows the results of calculations performed on two-core PC without parallelization.
Tabl. 1. Solution time of theTSP without parallel on the 2-core, s
In the Tabl. 2 is shown the results of the calculations performed on two parallel nuclear PCs.
Tabl. 2. Solution time of theTSP with 2-core parallel, s
In the Tabl. 3 is shown the results of the calculations performed on four-core nonparallel PCs.
Tabl. 3. Solution time of theTSP without parallel on the 4-core, s
In Fig. 6 the dependence of the program execution time on the number of flows on two and four nuclear architectures with/without the use of parallel simulated annealing method for the number of cities – 20 is presented.
Here 1 – is dependency without parallelization on a dual-core processor; 2 – without parallelization on quad-core; 3 – with parallelization on a dual-core processor; 4 – with a quad-core parallel. These designations are preserved when the following dependencies are displayed (see Fig. 7-8).
In Fig. 7 the dependence of the program execution time on the number of threads on two- and four-core architectures with/without the use of parallel simulated annealing method for the number of cities – 100 is presented.
In Fig. 8 shows the dependence of the program execution time on the number of threads on two- and four-core architectures with/without the use of parallel simulated annealing method for the number of cities – 600.
In the process carrying out numerical experiments, it was found that for a small number of cities, the execution time of the program at parallel is almost indistinguishable from the execution time of the program in a single thread. But the larger the number of cities, the better results at parallelization. Also, the program works more efficiently with more cores of PC.
In order to organize efficient calculations suitable for large-dimensional problems, in this work was proposed a parallel algorithm for finding the global extremum – a method of simulated annealing. An application software system has been developed to give the opportunity to solve a large-scale traveling salesman problem. The program is written in Java using a property such as multithreading. On the basis of a number of numerical experiments, the advantages of the proposed approach were analyzed: graphs of dependencies of the implementation time of the sequential and parallel algorithm depending on the dimension of the processed data and the multicore architecture of the corresponding computing system were constructed. On the basis of coefficients of efficiency and acceleration the prospects of further optimization of the computational process due to the modern development of multi-core systems are investigated.