论文部分内容阅读
Abstract: In two recent decades, approaches with the use of vectorial criteria as mathematical models of choosing find a wide utility in numerous applications. It will suffice to mention some problems of identification and diagnostics of complex systems, optimal design, control, saving of safety. The goal of multiple criteria numerical strategies is to compute a set of non-dominated solutions which constitute Pareto-optimal front approximations. Generally individual criteria are multiextremal not everywhere differentiable functions. Under these conditions searching for a global solution for the criterion is an independent challenging problem. Account must be taken of that the effectiveness of deterministic global optimization algorithms is quickly reduces with increasing the dimension of the search space. On the other hand, stochastic global optimization algorithms are computation-intensive. These considerations motivate a topicality of the development of hybrid methods for solving multiobjective optimization problems with multiextremal nonsmooth criteria. Two novel hybrid vector optimization algorithms combining a Metropolis-based stochastic algorithm and deterministic gradient techniques or a space-filling curve method are introduced. Implementations of the hybrid algorithms are discussed. Results of successful computational experiments are presented to illustrate the efficiency of the approach.
Key words: Vectorial criterion, non-dominated solution, multiextremal function, global optimization, hybrid algorithm.
1. Introduction
In many practical cases optimization problems must be formulated as problems with multiple criteria. One of the approaches suggests converting the initial vector optimization problem into a scalarized single-objective problem. More general methods are founded on the concept of Pareto-dominance, where they need to find trade-off solutions for criteria being in conflict. When individual criteria are multiextremal not everywhere differentiable functions, the vector optimization problem becomes highly complicated and computationally expensive one [1-2]. Most problems of this type cannot be solved exactly owing to highly complex and large dimensional search space. The goal is to find the set of non-dominated solutions[3]. The vector linearization method is one of the effective methods for numerical solutions of the multiobjective problems [4]. An introduction of biparametric smoothing approximations makes it possible to extend the method on the class of nondifferentiable problems [5]. In the context of the vector problem under consideration, it is necessary to solve global optimization subproblems for individual criteria. Properties of deterministic global optimization algorithms are well-studied. It is common knowledge that the performance of deterministic algorithms essentially depends on the problem dimension. On the other hand, stochastic global optimization algorithms are generally computation-intensive. A hybrid global optimization algorithm NMPCA that combines the recent stochastic algorithm PCA and Nelder-Mead simplex method is presented in Ref. [6]. The NMPCA (Nelder-Mead simplex method combined with Particle Collision Algorithm) was applied to a nuclear reactor core design optimization problem. During processing two
procedures are performing: A wide search in the solution space using the stochastic PCA and a local search in the promising areas with the deterministic simplex algorithm. The local search procedure is performed iteratively until a certain number of fitness function evaluations being reached. It is pertinent to note that the convergence theory for Nelder-Mead simplex method is far from completion; so the method can fail to converge or converge to non-stationary points [7]. By this is meant that the question of reliability of the algorithm as a whole is still an open question. As an alternative to the NMPCA a novel hybrid algorithm may be introduced. In this version of the global optimization algorithm the local search mechanism is a standard deterministic linearization method. Inverse problems are considered to be substantially difficult because of the kinks connected with presence of the repeated or very close frequencies in registered spectra for the computational model under updating. The difficulty motivated the development of algorithms for the solution of the minimization problem via some smooth approximation, which could be minimized by using any of the efficient classical approaches for smooth optimization. Several approximations to smooth out the kinks may be introduced. One of them results in a continuously differentiable approximate fitness function, whereas another one leads to a twice continuously differentiable approximate function. These approximations replace the original function in some neighborhoods of directional differentiability points. Moreover, this approach preserves such important property of the original function as its convexity. It is clear that the approach makes it possible to implement efficient gradient techniques in the solution process [8]. Computational experiments show the principal applicability of the proposed hybrid algorithm PCAHS (PCA Hybridized with gradient method and Smoothing approximations) for solving the global optimization problems. Some powerful algorithms for multiextremal non-convex optimization problem are based on reducing the initial multi-dimensional problem to the equivalent problem of one dimension. This reduction can be executed by applying Peano-type space-filling curves mapping a unit interval on the real axis onto a multi-dimensional hypercube [9]. The approach needs not any derivatives of the function to be minimized with updating parameters.
The plan of the remainder of this paper is as follows: The section followed contains statement of the multiobjective optimization problem. Section 3 provides brief description of hybrid vector optimization algorithms for solving problems with multiextremal nonsmooth criteria. In section 4 successful computational experiments for two model multiobjective optimization problems are presented to illustrate peculiarities of the proposed approach. Section 5 gives conclusions and discussion on further work.
Optimization of the individual criteria is performed by use of the hybrid global optimization algorithm combining the stochastic algorithm PCA [6] and the linearization method during the local search. For the functions that are not everywhere differentiable the smoothing approximations are introduced. The implementation of the recent stochastic algorithm PCA is based on the analogy with physical processes of absorption and scattering of particles during nuclear reactions. The algorithm PCA uses only one particle for scanning the search space. The hybrid algorithm for solving a global optimization subproblem for an individual criterion is proposed in Ref. [8]. The convergence of the algorithm is proved for the case of simple constraints. The hybrid algorithm V-PCALMS(Vectorial PCA combined with Linearization Method and Smoothing approximations) implements the above main steps and makes it possible to find global minima of individual criteria when solving the multiobjective problem.
3.2 The Hybrid Algorithm V-PCASFC
The second hybrid algorithm V-PCASFC (Vectorial PCA combined with Space-Filling Curve method) for multiobjective optimization implements the deterministic space-filling curve method for solving the global optimization subproblem for the individual
algorithm and deterministic linearization method or space-filling curve method for local search are presented. Smoothing approximations are introduced during the local search that makes it possible to expand the V-PCALMS algorithm on the class of non-differentiable problems. The V-PCASFC algorithm being introduced here does not require any gradient information. Both the algorithms were used for solving bicriterial model problems connected to choosing parameters of ?Πshaped rod system with a compensator of axial deformations and with computational model updating for the two-phase coolant flow in the nuclear reactor primary circuit. Numerical experiments show the principal applicability of the proposed hybrid algorithms for solving the above model multiobjective optimization problems. The future work will be devoted to increasing the computational efficiency of tools for solution the model updating problems with regard to noisy data using multiple criteria representation.
Acknowledgment
This research is partially supported by the program“Leading Scientific Schools” of Russian Federation(Grant NSh-5271.2010.8).
References
[1] J. Gao, J. Wang, A hybrid quantum-inspired immune algorithm for multiobjective optimization, Applied Mathematics and Computation 217 (2011) 4754-4770.
[2] C. Gil, A. Márques, R. Ba?os, M.G. Montoya, J. Gómez, A hybrid method for solving multi-objective global optimization problems, Journal of Global Optimization 38 (2007) 265-281.
[3] V.V. Podinovskij, V.D. Nogin, Pareto-Optimal Solutions of Multicriterial Problems (in Russian), 2nd ed., FIZMATLIT, Moscow, 2007.
[4] B.N. Pschenichnyj, R.B. Sosnovskij, A linearization method for multiple criteria problem solution (in Russian), Kybernetika 6 (1987) 107-109.
[5] V.D. Sulimov, P.M. Shkapov, A smoothing approximation in vector non-differentiable optimization problems for mechanical and hydro-mechanical systems(in Russian), Vestnik MGTU, Estestvennye Nauki 2 (21)(2006) 17-30,.
[6] W.F. Sacco, H.A. Filho, N. Henderson, C.R.E. Oliveira, A metropolis algorithm combined with Nelder-Mead simplex applied to nuclear reactor core design, Annals of Nuclear Energy 35 (2008) 861-867.
[7] K.I.M. McKinnon, Convergence of the Nelder-Mead simplex method to a non-stationary point, SIAM J. Optimization 9 (1998) 148-158.
[8] V.D. Sulimov, A local smoothing approximation in a hybrid algorithm for optimization of hydro-mechanical systems (in Russian), Vestnik MGTU, Estestvennye Nauki 3 (38) (2010) 3-14.
[9] R.G. Strongin, Y.D. Sergeev, Global optimization: Fractal approach and non-redundant parallelism, Journal of Global Optimization 27 (2003) 25-50.
[10] V.G. Kinelev, P.M. Shkapov, V.D. Sulimov, Application of global optimization to VVER-1000 reactor diagnostics, Progress in Nuclear Energy 43 (2003) 51-56.
Key words: Vectorial criterion, non-dominated solution, multiextremal function, global optimization, hybrid algorithm.
1. Introduction
In many practical cases optimization problems must be formulated as problems with multiple criteria. One of the approaches suggests converting the initial vector optimization problem into a scalarized single-objective problem. More general methods are founded on the concept of Pareto-dominance, where they need to find trade-off solutions for criteria being in conflict. When individual criteria are multiextremal not everywhere differentiable functions, the vector optimization problem becomes highly complicated and computationally expensive one [1-2]. Most problems of this type cannot be solved exactly owing to highly complex and large dimensional search space. The goal is to find the set of non-dominated solutions[3]. The vector linearization method is one of the effective methods for numerical solutions of the multiobjective problems [4]. An introduction of biparametric smoothing approximations makes it possible to extend the method on the class of nondifferentiable problems [5]. In the context of the vector problem under consideration, it is necessary to solve global optimization subproblems for individual criteria. Properties of deterministic global optimization algorithms are well-studied. It is common knowledge that the performance of deterministic algorithms essentially depends on the problem dimension. On the other hand, stochastic global optimization algorithms are generally computation-intensive. A hybrid global optimization algorithm NMPCA that combines the recent stochastic algorithm PCA and Nelder-Mead simplex method is presented in Ref. [6]. The NMPCA (Nelder-Mead simplex method combined with Particle Collision Algorithm) was applied to a nuclear reactor core design optimization problem. During processing two
procedures are performing: A wide search in the solution space using the stochastic PCA and a local search in the promising areas with the deterministic simplex algorithm. The local search procedure is performed iteratively until a certain number of fitness function evaluations being reached. It is pertinent to note that the convergence theory for Nelder-Mead simplex method is far from completion; so the method can fail to converge or converge to non-stationary points [7]. By this is meant that the question of reliability of the algorithm as a whole is still an open question. As an alternative to the NMPCA a novel hybrid algorithm may be introduced. In this version of the global optimization algorithm the local search mechanism is a standard deterministic linearization method. Inverse problems are considered to be substantially difficult because of the kinks connected with presence of the repeated or very close frequencies in registered spectra for the computational model under updating. The difficulty motivated the development of algorithms for the solution of the minimization problem via some smooth approximation, which could be minimized by using any of the efficient classical approaches for smooth optimization. Several approximations to smooth out the kinks may be introduced. One of them results in a continuously differentiable approximate fitness function, whereas another one leads to a twice continuously differentiable approximate function. These approximations replace the original function in some neighborhoods of directional differentiability points. Moreover, this approach preserves such important property of the original function as its convexity. It is clear that the approach makes it possible to implement efficient gradient techniques in the solution process [8]. Computational experiments show the principal applicability of the proposed hybrid algorithm PCAHS (PCA Hybridized with gradient method and Smoothing approximations) for solving the global optimization problems. Some powerful algorithms for multiextremal non-convex optimization problem are based on reducing the initial multi-dimensional problem to the equivalent problem of one dimension. This reduction can be executed by applying Peano-type space-filling curves mapping a unit interval on the real axis onto a multi-dimensional hypercube [9]. The approach needs not any derivatives of the function to be minimized with updating parameters.
The plan of the remainder of this paper is as follows: The section followed contains statement of the multiobjective optimization problem. Section 3 provides brief description of hybrid vector optimization algorithms for solving problems with multiextremal nonsmooth criteria. In section 4 successful computational experiments for two model multiobjective optimization problems are presented to illustrate peculiarities of the proposed approach. Section 5 gives conclusions and discussion on further work.
Optimization of the individual criteria is performed by use of the hybrid global optimization algorithm combining the stochastic algorithm PCA [6] and the linearization method during the local search. For the functions that are not everywhere differentiable the smoothing approximations are introduced. The implementation of the recent stochastic algorithm PCA is based on the analogy with physical processes of absorption and scattering of particles during nuclear reactions. The algorithm PCA uses only one particle for scanning the search space. The hybrid algorithm for solving a global optimization subproblem for an individual criterion is proposed in Ref. [8]. The convergence of the algorithm is proved for the case of simple constraints. The hybrid algorithm V-PCALMS(Vectorial PCA combined with Linearization Method and Smoothing approximations) implements the above main steps and makes it possible to find global minima of individual criteria when solving the multiobjective problem.
3.2 The Hybrid Algorithm V-PCASFC
The second hybrid algorithm V-PCASFC (Vectorial PCA combined with Space-Filling Curve method) for multiobjective optimization implements the deterministic space-filling curve method for solving the global optimization subproblem for the individual
algorithm and deterministic linearization method or space-filling curve method for local search are presented. Smoothing approximations are introduced during the local search that makes it possible to expand the V-PCALMS algorithm on the class of non-differentiable problems. The V-PCASFC algorithm being introduced here does not require any gradient information. Both the algorithms were used for solving bicriterial model problems connected to choosing parameters of ?Πshaped rod system with a compensator of axial deformations and with computational model updating for the two-phase coolant flow in the nuclear reactor primary circuit. Numerical experiments show the principal applicability of the proposed hybrid algorithms for solving the above model multiobjective optimization problems. The future work will be devoted to increasing the computational efficiency of tools for solution the model updating problems with regard to noisy data using multiple criteria representation.
Acknowledgment
This research is partially supported by the program“Leading Scientific Schools” of Russian Federation(Grant NSh-5271.2010.8).
References
[1] J. Gao, J. Wang, A hybrid quantum-inspired immune algorithm for multiobjective optimization, Applied Mathematics and Computation 217 (2011) 4754-4770.
[2] C. Gil, A. Márques, R. Ba?os, M.G. Montoya, J. Gómez, A hybrid method for solving multi-objective global optimization problems, Journal of Global Optimization 38 (2007) 265-281.
[3] V.V. Podinovskij, V.D. Nogin, Pareto-Optimal Solutions of Multicriterial Problems (in Russian), 2nd ed., FIZMATLIT, Moscow, 2007.
[4] B.N. Pschenichnyj, R.B. Sosnovskij, A linearization method for multiple criteria problem solution (in Russian), Kybernetika 6 (1987) 107-109.
[5] V.D. Sulimov, P.M. Shkapov, A smoothing approximation in vector non-differentiable optimization problems for mechanical and hydro-mechanical systems(in Russian), Vestnik MGTU, Estestvennye Nauki 2 (21)(2006) 17-30,.
[6] W.F. Sacco, H.A. Filho, N. Henderson, C.R.E. Oliveira, A metropolis algorithm combined with Nelder-Mead simplex applied to nuclear reactor core design, Annals of Nuclear Energy 35 (2008) 861-867.
[7] K.I.M. McKinnon, Convergence of the Nelder-Mead simplex method to a non-stationary point, SIAM J. Optimization 9 (1998) 148-158.
[8] V.D. Sulimov, A local smoothing approximation in a hybrid algorithm for optimization of hydro-mechanical systems (in Russian), Vestnik MGTU, Estestvennye Nauki 3 (38) (2010) 3-14.
[9] R.G. Strongin, Y.D. Sergeev, Global optimization: Fractal approach and non-redundant parallelism, Journal of Global Optimization 27 (2003) 25-50.
[10] V.G. Kinelev, P.M. Shkapov, V.D. Sulimov, Application of global optimization to VVER-1000 reactor diagnostics, Progress in Nuclear Energy 43 (2003) 51-56.