The global optimization method with selective averaging of the discrete decision variables.pdf The problem of search of a global extremum of objective functions on admissible set of decision variables (continuous, discrete or continuous-discrete) belongs to the very complex class [1-27]. The specificity of global optimization is caused by multiextremal view of the objective functions, their discontinuous nature, very different sensitivity of objective functions in relation to decision variables, the discrete nature of part or all the variables, the presence of noises, the presence of a considerable quantity of decision variables and constraints of inequalities type and equalities type. If objective functions are not calculated, they are measured in points of admissible set of decision variables. The majority of algorithms is oriented only on cases of continuous decision variables and on elemental constraints of inequalities type. The comparative analysis of base algorithm of a method with selective averaging of continuous decision variables [6, 7, 10, 14, 24] in relation to existing heuristic algorithms showed its advantages on the rate of convergence, a noise stability and total computing complexity. In [27] the variant of base algorithm of a solution of a problem of global optimization on set of continuous-discrete variables is proposed. It is rational to develop this effective method of global optimization on the set of discrete variables. In this paper for a solution of global optimization problems on a set of discrete variables the approach based on the selective averaging of decision variables with adaptive reorganization of an admissible set of trial movements is proposed. It is constructed the functional of selective averaging of discrete decision variables. The selectivity coefficient is entered into kernel of functional. With an increase in the core selectivity coefficient, it becomes possible for the functional to distinguish the positions of the global minimum. It is shown that when selectivity coefficient of kernel tends to infinity the averaging gives optimal value of decision discrete variables. The computing scheme of base algorithm of global optimization at continuous variables is transformed to the similar scheme at discrete variables. The base algorithm of global optimization on a set of discrete variables with ordered possible values at the presence of inequalities constraints is synthesized. Trial and working steps are also separated in time. Before performance of each working step the series of calculations of the minimized function in the sampling points is carried out. Based on this information at the fixed selectivity coefficient of kernel, the selective averaging of decision variables will be executed numerically. For each discrete variable the continuous auxiliary non-dimension variable which contains numbers of possible values of a discrete variable and the identical the adjoining each other subintervals covering these numbers is put in compliance. Due to one-to-one compliance the transition in the sampling points from continuous variables to discrete possible values is carried out. The same (but already reverse) transition occurs for received averaged values of decision variables. Also, the adaptive reorganization of sizes of a set of possible trial movements is carried out and functions of inequalities constraints are considered. The example shows the high convergence rate and noise stability of the base algorithm. It also provides near-to-one the estimate of the probability of obtaining a true solution. 1. Statement of problem The problem of search of a global minimum of objective function f (y) on a set of discrete variables with ordered possible values at the presence of inequalities constraints is solving: f(y) = globmin, ф7. (y) < 0, j = 1,m, (1) where y = (y,...,yh) is vector h of discrete variables. Each discrete variable yt has rt possible ordered values yt^..^ yt^ . Inequalities constraints select (narrow) admissible set of possible values in which search of minimum of global minimum is carried out. It’s required to define the position ymm of global minimum of objective function f (y) on limited set of change of its variables. Function f ( y) is multiextreme and can be distorted by noises. Functions of constraints can be nonconvex. Search of extremum is carried out on basis only measurements or calculations of specified functions f (y), ф (y), j = 1,m in the selected sampling points which satisfy to the inequalities constraints: фj (y) < 0, j = 1, m. We assume that a global minimum of function f ( y) on an admissible set of points with discrete values of variables is unique. 2. The selective averaging of discrete decision variables The selective averaging of decision continuous variables [6, 7, 10, 14, 24] is a mathematical expectation with special probability density function of these variables. Probability density function at a decreasing kernel (with increase of its normalized argument from 0 to 1) allows to approach with growth of selectivity coefficient of a kernel to the specified average value of decision variables i.e. to the true position of global minimum. This theoretical result gave to chance of construct the structure of a base numerical algorithm, which successfully applied at the presence of inequalities constraints. Due to the expansion of possibilities of this algorithm, the algorithms of single-objective global optimization at the constraints such as inequalities and equalities are synthesized. The algorithms of the solution of other extreme problems are obtained: multiobjective and minimax global optimization, search of the main minima of multiextremal functions [14]. Let’s transfer idea of selective averaging [14] on solution the problem of global optimization (1) on set of possible values of the discrete decision variables which satisfy the inequalities constraints (1). At first we will consider the one-dimensional version of optimization problem (1). Discrete variable y has r possible ordered values (yx,...,yr). We enter the notation: /mm, /max are smallest and largest values of minimized function on an admissible set of possible values; ymm is admissible value of discrete variable at which function f (y) is reaching the minimum value: f Omn) = fmm . The averaged value (mathematical expectation) of decision variable is equal to value: (2) [yl = I PsigJy, Ц=1 k=1 where Hg„) = Ps(gu)/ Z Ps(gk) is normalized (on 1) positive decreasing kernel (analog of probability of a random event): ^ps(gp) = 1; kernels ps(gp) and ps(gp) lie in interval [0; 1]; s is selectivity coeffi- P=1 cient of kernel (1 ф(ymin) .... yh,mln) is the same as for one-dimensional case. We take the h functions ф(y) = y, t = 1, h and we receive limit values for all coordinates Ik/l ^oo >-kf,min? t = \\ h , _ R _ where [yt\\s = ^ /)s(gLl )У, Ll- t = \\,h, у LL is coordinate with number t in point with number p. This is cop=i ordinate-wise averaging. It’s written in vector form: [y > ymin (y1,min,..., yh,min) , - R ^ where [y]x = Z Ps (gLi )>'ll • Л is admissible point with number p at one of combinations of possible values p=1 of its variables. By search of a maximum of function f the arguments of kernels are calculated on another: gp = (fmax - f (Ур)V(/max - fmin) and the point Утах corresponds to global maximum value: f Cy^ = fmax and gmax = °. 3. Basic algorithm of optimization The method is based on separation in time of trial and working steps, uniform distribution of sampling points on admissible set of possible values of discrete decision variables, numerical selective averaging (calculation of mathematical expectation) of decision variables by results of calculated (or measured) values of optimized function in sampling points. Adaptive reorganization of the sizes of the set of sampling points is carried out also on each working step. The basic algorithm of global optimization based on selective averaging of decision continuous variables allows implementation on a set of discrete and continuous-discrete variables. In [27] the specified algorithm was generalized on a case of continuous and discrete variables with ordered possible values. Based on the scheme presented in [27], in this work the algorithm for a case only of discrete variables is constructed. The solution of problem of optimization with discrete variables is based on transition from each discrete variable yt to the corresponding auxiliary continuous variable xt. From possible values of a discrete variable yt transition to their numbers are carries out. Calculations on each working step are conducted for the number x(possible values of discrete variables yt. Averaged values of variables (estimates of mathematical expectation) and the sizes (also averaged) the variation sets of variables are calculated. For receiving of n sampling points y(i), i = 1, n consistently by uniform distribution are generated on a «rectangular» set of a points and from them only those which satisfy inequalities constraints are left. After the l -th working step the generation of sampling points is carried out equally: (3) x() = xt + AXtuX, uX) e [-1; 1], t = 1,h, i = 1,n, In a formula (3) uis elements of pseudo-random sequence of uniform distributed of the continuous random value. This uniform law of distribution causes identical probabilities of emergence of possible values (and their numbers) all discrete variables. In the received sampling points value of minimized function f(i) = f (y(i)), i = 1,n is calculated. Further, the position of the minimum is specified. New value xl+1 on auxiliary variables and the sizes AXl+1 of «rectangular» set of trial movements are calculated by the following formulas: -1+1 _ ^ -(i) -(i) (4) = у X(i) p() t = 1 h = A xt,Nps,min ,1 = 1,h , x, 7=1 1/q f{l) - f • a(0 _J_J min ’ о min - 'r 'r J max J mir P() ■ = r s,min » Axl+1 =Yq I A | X(N - x}'q"(i) t = 1, h, (j) min i=1 ) A Ps (g, j=1 / = 0,1, 2,[0

Скачать электронную версию публикации