This work considers a parallel algorithm for the multi-objective optimization. The algorithm is based on the application of the informationstatistical approach for solving reduced scalar problem in which the set of the global optima coincides to the set of the weakly e cient solutions of the initial multi-objective problem. In the work the parallelization scheme, which is common for all information-statistical global search algorithms, was applied to the sequential algorithm of the multi-objective optimization. Also, in this work one of the convergence speedup techniques based on local properties of objective functions has been applied to the multi-objective problems.
The multi-objective optimization problems attract an increasing interest in recent years since these ones most completely re ect the controversy of the requirements arising to the modeled objects of real world. In such problems, the solutions are a compromised decision of a set of these ones. As a rule, these compromised solutions are chosen either from a set, in which all elements cannot be improved with respect to any criterion without the worsening of the other criteria (Pareto-optimal or e cient solutions) or from a set, in which no one element could be improved with respect to all criteria at once (Slater-optimal or weakly e cient solutions). The latter requirement is weaker, and all Pareto-optimal solutions are the Slater-optimal ones as well.
To nd the complete set of e cient or weakly e cient points is the most computationally complex problem, however it provides a wide choice of possible compromised solutions. To nd these sets a plenty of approaches have been developed: the application of the genetic algorithms to the multi-objective problem directly [4], the use of the parametric convolutions reducing the problem to a series of the scalar global optimization problems [5], various approaches to the solving the problems with the convex [11] or linear [3] objectives. The main problem in the using of the most of these methods is the absence of the theoretical guarantee of the uniform convergence to the whole sought set of the Pareto-optimal solutions on a wide class of problems including the ones with the non-convex multiextremal criteria. A method having this property in the case, when all criteria satisfy the Lipschitz condition has been developed on the basis of the information global search algorithm [8]. In the paper there is considered the parallel modi cation of this method accelerated due to the local re nement technique [10](chapter 3). 2
The multi-objective optimization problems are stated in the following way:
minff (y) : y 2 Dg; D = fy 2 Rn : ai 6 yi 6 bi; 1 6 i 6 ng:
(
y2k; y1; y2 2 D; 0 < Li < 1; 1 6 i 6 m
The set S(D) 2 D of strictly non-dominated points from the search domain
is usually accepted as the solution of the problem (
S(D) = fy 2 D : @z 2 D; fi(z) < fi(y); 1 6 i 6 mg;
(
The use of the space- lling curve (evolvent ) y(x)
fy 2 RN : 2 1 6 yi 6 2 1; 1 6 i 6 N g = fy(x) : 0 6 x 6 1g
is a classic dimensionality reduction scheme for global optimization algorithms [9].
Such a mapping allows to reduce the problem (
1
x2j N ; x1; x2 2 [0; 1];
(
p Hi = 4Lid N ; d = maxfbi ai : 1 6 i 6 ng:
Without losing generality one can, one can consider the solving of the onedimensional problem minff (y(x)) : x 2 [0; 1]g, satisfying the Holder condition. The issues of the numerical building the mapping like a Peano curve and the corresponding theory have been considered in detail in [9]. Here we would note that an evolvent built numerically approximates the theoretical Peano curve with a precision of the order 2 m, where m is the building parameter of the evolvent.
Let us consider a scalarization scheme for the reduced problem (
' = minf'(x) : x 2 [0; 1]g:
As it has been shown in [8], the set of weakly e cient solutions of the reduced
problem (
S([0; 1]) = fx 2 [0; 1] : '(x) = ' g:
Also, it has been shown in [8] that the function '(x) satis es the Holder condition
when the requirements (
The algorithm for solving problem (
The rst two iterations are performed at the boundary points x0 = 0 and x1 = 1 of the interval [0; 1]. The choice of the points xk+j ; 1 6 j 6 p, is performed according to the following rules:
Step 1. Renumber the points in the set Xk = fx1; : : : ; xkg [ f0g [ f1g, which
includes the boundary points of the interval [0; 1] as well as the points of
preceding trials, by the lower indices in order of increasing coordinate values, i.e.
(
Step 2. Compute the lower bound objective function f (x); 1 6 6 m: for the Lipschitz constant for each = max jf (xi) 16i6k i = (xi f (xi 1)j ; 1 6 i
1 xi 1) N : 6 m;
Step 3. To each point xi, 0 6 i 6 k, juxtapose the value where
zi = maxfh(xi; xj ) : 0 6 j 6 kg;
h(xi; xj ) = min
f (xi)
f (xj ) : 1 6
6 m
; 0 6 i; j 6 k
(
i + R (i) = (zi
zi 1)2 r2 i
R(i)
zi + zi 1
2r
;
;
p(zi
z )(zi 1
z ) + 1:5
where i is from (
Step 5. If q 6= 0 and s mod q 6= 0, then arrange the characteristics R(i), 1 6 i 6 k + 1 in the decreasing order
R(t1) > R(t2) > > R(tk) > R(tk+1) and select p maximum characteristics with the indices of the intervals tj , 1 6 j 6 p. Otherwise do the same with the characteristics R (i); 1 6 i 6 k + 1. Here s is the index of current iteration and integer q is the parameter of the method responsible for the degree of intensity of the local re nement. The less q, the more frequent the characteristics R are used making the method to choose the next points near the current minimum found.
Step 6. Perform the new trials at the points xk+j , 1 6 j 6 p: xk+j = xtj + xtj 1 2 sign(ztj ztj 1) jztj ztj 1jn 2r (12) All p trials within this step can be performed in parallel on p computing devices.
The algorithm is terminated if the condition tj 6 " is ful lled at least for
one of the indices tj , 1 6 j 6 p; here " > 0 is the prede ned accuracy. After the
search is terminated, the set S(fx0; : : : ; xkg) of all non-dominated points of the
truncated sequence fx0; : : : ; xkg is accepted as an estimation for S from (
The theoretical substantiation of this method when p = 1 and q = 0 is presented in [10](chapter 3).
To evaluate the degree of speedup of the convergence of the modi ed algorithm from Section 3, the following problems were used: 1. Markin-Strongin problem [8]: f1(y) = minfpy12 + y2; p(y1
2 f2(y) = p(y1 + 0:5)2 + (y2 2. Fonseca and Fleming problem [6]: 3. Viennet function [6]:
8 >>< f1 (y) = 1 >>: f2 (y) = 1 exp exp
Pn
i=1 yi
1
pn
Pn
i=1 yi + p1n
2
2
>8 f1 (y) = 0:5(y12 + y2) + sin(y12 + y2)
< f2 (y) = (3y1 2y2+42)2 + (y1 y2+1)22+ 15
>: f3 (y) = y12+1y22 +81 1:1 expf 27(y12 + y22)g
where
8A1 = 0:5 sin (
The computational experiments have been carried out on the Lobachevsky supercomputer at State University of Nizhny Novgorod. A computational node included 2 Intel Sandy Bridge E5-2660 2.2 GHz processors, 64 GB RAM. The CPUs had 8 cores (i.e. total 16 cores were available per a node). C++ language and OpenMP parallel framework were used to implement the considered algorithm.
In this section, we will understand the speedup of the method as the speedup
in the number of executed iterations, not in the time of execution. If the problem
criteria (
Below, MOAR with q = 4 was used for all experiments.
Parallel method results. In order to demonstrate the speedup in iterations, which MOAR provides when p > 1, all problems from Section 4 have been solved for the values p = 1; 2; 4; 8; 16. The parameters of the method were the following: r = 4:5, " = 0:01, = 15. The number of iterations is presented in Table 1 (in the braces, the cardinality of the set S is given) and the speedup in iterations is presented in in Table 2. As it is evident form Table 1, the cardinality of the weak-optimal solutions set changed insu ciently when varying p i. e. the quality of the obtained estimates remained the same. At the same time, the number of iterations decreased linearly with increasing value of p (Table 2). Thus, the parallel algorithm reduces the number of iterations almost in p times comparing to the sequantal one. In Fig. 2, the examples of the numerical solutions of the considered problems are given. Parallel method time speedup. The objective functions of all problems listed in this section are featured by low computational complexity. In order to demonstrate the possibility to obtain a speedup in time for the problems with the time-consuming criteria, additional intensive oating point computations not a ecting the resulting values were introduced into the criteria. The speedups obtained are given in Table 3. In all cases, the speedup in time was less than the speedup in iterations because the operation of the optimization method itself takes a part of the execution time. However, in most cases the parallelization was e cient enough even in the case of 16 CPU threads. For more computation costly criteria, one can expect the increasing of the speedup in time for a large number of threads.
Problem Markin-Strongin Fonseca and Fleming 2d Fonseca and Fleming 3d Viennet problem Poloni's problem 3.0 2.5 2.0 f21.5 1.0 0.5 In the work a method for solving the multi-objective optimization problem has been considered which allows to nd a uniform estimate of the set of the weaklyoptimal points. The techniques of parallelization and of the acceleration of convergence common for all algorithms of similar structure have been applied. The numerical experiments performed have demonstrated a speedup in convergence when using the local re nement. Also, the parallelization based on the characteristics was found to be e cient for this method. The speedup in iterations at the parallelization based on the characteristics appeared to be linear in most cases as for the information methods of scalar optimization (see the results of the parallelization of the scalar optimization method, for example, in [1]). From the results of the experiments, one can conclude that it is expedient to apply the parallel MOAR in the problems of low dimensionality (1 to 3) with the computation-costly criteria. Moreover, the property of uniform convergence of the considered algorithm to the whole set of the weakly-optimal solutions has been demonstrated on the numerical examples.
Acknowledgments. The study was supported by the Russian Science Foundation, project № 16-11-10150.