Features of Application of
Indirect Optimization Method
Based on Self-Organization
The need to develop the complex optimization technology was caused by
such circumstance that availability of mathematical simulators (whatever
complex and precise they are) could not be sufficient for successful designing
and modifying of complex engineering systems. To create competitive models
there was necessary to integrate the mathematical simulators with such
searching analysis methods which were able to give a whole set of alternating
technical solutions which couldn't be improved in whole totality of effectiveness
indicators (Pareto principle). It is important to note that in conformity with
practical problems the mechanical combination of mathematical simulators and
numeric optimization routines as a rule did not allow to derive practically
valuable results. In this case one was to develop some 'optimization
environment', which combined different investigation methods. It is properly
this environment which is named 'optimization technology'.
The
optimization technology was firstly oriented to search the ways to increase the
effectiveness of power plants of different purpose modern and advanced aircraft
by solving optimal designing and control problems. In our subsequent work we
succeeded in expanding of our technology applicability sphere and at present
the technology is successfully used to improve technical systems (or
technological processes) in other fields of science and engineering as well. We
don't see fundamental difficulties in use of this technology, for example, in
ecology, biotechnology, economics etc. with use of corresponding mathematical
simulators and participation of these fields of science experts in
investigations.
One of the
central places of our technology is the new indirect optimization method based
on self-organization (IOSO). Its advantages and disadvantages, as well as that
of any other method can be evaluated properly only in process of solving of
practical problems, so we shall characterize shortly only its main
peculiarities.
1. Mathematical Statement and Basic Algorithm of Problem Solving.
The
mathematical statement of problem in its most common presentation is a typical
statement of non-linear programming problem. Let one have the mathematical
simulator of technical system, which describes the functional dependence (y,w)=f(x),
where y is the criteria vector (the vector of effectiveness indicators which,
for example, are to be minimized); w - the vector of parameters to be
limited; x- the vector of varying parameters. Let one also have a permissible
range of varying parameters variation as xmin<=x<=xmax and
functional limitations as w(x)<0. One has to discover a
set of Pareto-optimal solutions (or a single solution for monocriterion
problem), that corresponds to all limitations.
Let's just
note that IOSO is the heuristic method and mathematically strict proof of its
convergence is seemed to be impossible now. The point is that our method is
based upon a series of heuristic procedures (developed by us and other
authors), some of which (the inductive self-organization method of academician
A.G.Ivakhnenko, for example) have not been proved in spite of their wide use. However
the successful wide-scale IOSO testing and our experience in solving of more
then 300 practical problems allowed us to claim with confidence not only it's
convergence but it's high enough effectiveness as well.
The
algorithms of solving of monocriterion and multicriteria problems in
deterministic and stochastic statements have insignificant difference, so we'll
present here the simplified basic algorithm for monocriterion deterministic
optimization problem.
The main
concept of proposed method is to store and use with maximal effectiveness the
information about goal function, which is being accumulated in the process of
problem solving. This concept is evident enough and is used in many numerical
optimization methods, but the effectiveness of such information use depends
directly upon specific algorithms. In our case the effectiveness is reached by
maximal possible saving (minimization) of number of researched object
mathematical simulator direct calls. The central place of our method is the
presentation of each solution search iteration as two stages: to construct the
functions approximating optimization criterion and functional limitations in
some chosen region and to find these approximating functions extrema with
limitations taken into account. To realize such strategy the unique procedures
have been developed to approximate functions of many variables (using the
inductive self-organization method of academician A.G.Ivakhnenko, which has
been modified, for optimization problems). The effectiveness of these
procedures has been proved by solving of considerable number of testing and
practical optimization problems.
The
initial IOSO procedure is to form the initial experiment plan X, which can be
carried out in passive manner (using the information having been received
before about varying parameters, optimization criterion and constraints) as
well as in active manner, when the X set is generated in initial search region
in correspondence with defined distribution law. For each vector of varying
parameters the values of constrained parameters and optimization criterion are
determined by direct call of researched object mathematical simulator. The
number of points, comprising the initial experiment plan, practically does not
depend on problem dimensionality and is usually 20...40 (even if problem
dimensionality is 100 and more variables).
The basic
algorithm of optimization in greatly simplified form (to illustrate the method
operation logic only) can be presented as following steps sequence.
There is important to note that at initial stage of optimum search the
accuracy of approximation functions can be insufficient because of little
number of points in experiment plan and because of relatively large current
search region. However as the problem solving is in progress the number of
extremum neighboring points is being increased. Meanwhile the size of current
search region is purposefully changed. These tendencies cause the improving
approximation function accuracy and, consequently, increase the algorithm
operation effectiveness.
Within the
optimization method a number of heuristic procedures was developed, which were
to change adaptively such method parameters as maximal number of points in
experiment plan, number of points in current search region, and to make
rational choice of either 7-a or 7-b step in basic optimization algorithm.
The
presented basic algorithm characterizes main peculiarities of IOSO roughly. In
fact the flexible calculating procedure is realized within the method, which
allows changing method parameters and even algorithm structure during problem
solving by program code itself, i.e. without user participation. In other
words, the searching of problem solution can be represented as evolutionary
process of purposeful object research (in a mode of strict economy of direct
mathematical simulator calls number). By it's essence, the method is a
combination of structural-parametric algorithms, which are tuned adaptively on
the object of research. This provides the highly invariant performance of IOSO.
2. Stability and
Main Limitations of IOSO Applicability
As it
follows from presented basic algorithm, no limitations are put upon researched
goal function when one uses IOSO (for example continuity, differentiability,
convexity etc.). One of few limitations on method applicability is a
'computability' of either goal function or constrained parameters in defined
search region. Although, one should note that we have the experience of solving
of practical optimization problems with goal function being impossible to be
calculated in considerable part of search region. Other IOSO applicability
limitation is the sphere of discreet optimization (excepting some special
cases). At last, we can not guarantee a success when optimizing some functions
with solution being in extremely narrow discontinuity zone, such as chink.
There is
important to note that to carry out optimization research of technical object
(process) with use of IOSO, a researcher is not obliged to represent the object
with mathematical simulator. We have the experience of natural object
optimization on experimental facility immediately (VAZ-2110 engine). Moreover,
the optimization is possible also using statistical data (a technological
process of workshop, for example).
The
question about IOSO stability can be interpreted from different points of view
(the calculating procedure stability, the extremum determination stability, the
stability under influence of external and internal disturbances etc.). The
stability of most method's algorithms from calculation point of view is
absolute because we had been working for 10 years with some of them and all of
such problems have been overcome long ago.
In
addition we can claim with full authority that IOSO allows to find absolutely
constantly the extrema of unimodal functions (almost all of universally
recognized test functions have been researched). We have not have any problem
with optimization of wide class of non-differentiatable functions (even if
solutions have been just at discontinuity boundary). The method allows to
determine confidently the extremum region under influence of disturbances of
different kind upon goal function as well.
We can
note that for most of multiextrema goal functions that were researched we
succeeded in determination of global extremum. Though we can not claim that the
problem of multiextremality can be solved by us in all possible cases, the
probability of global extremum determination using IOSO is high enough.
Moreover,
the special research of IOSO stability was conducted for different initial
search conditions as well as for cases of artificial put of incorrect goal
function values into experiment plan (for goal functions values worse then that
of extremum only) or for cases of extremely permissible search region comparing
with initial search region etc. For all of these cases IOSO was able to find
the solutions.
At last
the 'IOSO stability' term can be related with such fact that we had not a
result, when solving a practical optimization problem we did not succeeded in
improving of initial variant (prototype).
3. IOSO and Other
Optimization Methods Combination Possibilities.
The
ability to combine IOSO with other optimization methods can be considered in
two ways: to combine IOSO with simulating methods as well as with other
optimization methods. For both ways we don't see any limitation. As for
mathematical simulation, we have the great experience of IOSO integration with
mathematical simulators of different level, designed for steady and unsteady
processes research. With such integration optimal design and control problems
were solved, the latter was carried out with both static and dynamic approach.
Due to
IOSO high effectiveness we were not needed to combine it with other
optimization methods, but if necessary such integration can be carried out
without serious difficulties. From one hand, one or more of best points from
experiment plan can be used as initial points to start any other optimization
procedure. From other hand, the information about goal function and constrained
parameters values, which has been stored during operation of other optimization
method, can be used as initial experiment plan to start the IOSO.
The IOSO
main advantages comparing with well known approaches to solve optimization
problems are that practical problems with non-convex, non-differentiative and
stochastic goal functions and constrained parameters are possible to be solved;
the solution can be obtained with relatively little number of mathematical
simulator direct calls; the probability of global extremum determination for
multiextrema problems is high; the large-dimensionality monocriterion and
multicriteria problems can be solved under deterministic and stochastic
formulation. Not of less importance is that during solution determination IOSO
carries out thorough research of goal function and constrained parameters in
extremum neighborhood. These advantages are the reason to use the proposed
method to solve practical optimization problems for the widest class of
engineering systems.
The method
has been realized as FORTRAN software pack. This pack has been developed as a procedure,
typical for standard software, in accordance with requirements of All-Russia
State Fond of Algorithms and Programs. The pack call is carried out by
optimization subroutine call. The program initialization is carried out by
defining of minimal set of initial data, which doesn't oblige a user to be a
professional optimizer. This data set includes:
The initial parameters of optimization routine are defined by program
itself (without user participation) and are adapted for specific problem during
extremum search.
The
optimization criterion and functional constraints calculation for current
varying parameters vector is carried out by call of Fun(x,y,w) subroutine,
which is to be developed by user. Here input information is x- current vector
of varying parameters; the output information is y- the vector of goal function
values, and w- the vector of constrained parameters values.
The
optimization routine doesn't require creating memory blocks, common with object
mathematical simulator, so the optimization pack can be combined with almost
all simulation software realizations.
The use of
this optimization pack does not require user to have special knowledge in the
field of optimization, but the physical formulation of optimization problem
can't be correct without user's deep knowledge about researched object and
user's clear understanding of research purpose.
When the
physical formulation of problem is correct, the user's work input to construct
program code of new optimization problem (or problems class) is to be minimal. We
have the great experience of combination of our software with software packs,
developed by other authors on different algorithmic languages. The time to
combine IOSO and new mathematical simulator depends upon readiness of latter
and user's knowledge of its program realization only. According to our
experience, this time can be from 10 minutes to 2 hours.
Our
software pack is realized on IBM-compatible computers and on VAX systems. The
documentation about most of IOSO algorithms was developed in accordance with
requirements of All-Russia State Fond of Algorithms and Programs in Russian
language.
5. The Level of
Method Approbation.
The IOSO
approbation was carried out in two main directions:
Let's discuss briefly these two directions.
Because of
impossibility to prove theoretically IOSO convergence in now days, as it was
noted before, we carried out wide-scale testing of our method. The purpose of
the testing was:
While IOSO testing the following classes of optimization problems were
taken into consideration:
-
monoextremum differentiatable;
-
monoextremum nondifferentiatable;
-
multiextrema differentiatable;
-
multiextrema nondifferentiatable;
To estimate the effectiveness of developed method the numeric experiments
were carried out in order to solve optimization problems noted before, where we
used test functions as goal ones. The total number of numeric experiments has
exceeded 60,000 optimization problems.
The method
effectiveness in most global scope was tested with 16 test functions, series of
which were either generally known functions or their modifications, or these
functions were multimeasure analogues of generally-known functions. Note, that
test functions were chosen to imitate different types of goal function
topological complexity (non-linearity, component interdependency,
discontinuities, disturbances etc.). The test functions that were used are
presented in table 1, where their
analytical expressions, extremum values and optimal arguments vector as well
are shown.
Comparing
with other optimization routines, IOSO was most effective to be used when goal
function was algorithmically computable (i.e. function gradient in a point was
impossible to be determined analytically), optimization criterion determination
was time expensive, and goal function was topologically complex and
multimeasure. Proceeding from this statement the number of direct function
calls Nfun under defined accuracy of extremum determination was seemed
expedient to be considered as optimization method effectiveness indicator.
The
analysis of testing results allowed us to assert that:
Note that IOSO convergence rate can be estimated by comparative analysis
of optimization results with that of other methods operation, which have
analytical estimations of this indicator. To compare our method with well-known
methods of non-linear programming we solved optimization problems for the same
test functions. In all we tested more then 20 optimization methods, which were
presented in table 2.
The
necessary conditions to include into research one or other well-known nonlinear
programming method was the possibility to use it's well-known and approved
program realization. This condition seemed to provide the correctness of
analysis carrying out, because otherwise any good optimization method can be
realized as bed computer code. So for all used in work nonlinear programming
methods their program realization was not developed by us. We used such program
units, which were well-known and effective as well as accessible.
The most
detailed comparative analysis was carried out for monoextremum differentiable
functions in deterministic and stochastic statements. Let's note some
peculiarities of comparative analysis.
Firstly,
the number of goal function direct calls to find extremum with defined accuracy
was considered as optimization method effectiveness indicator.
Secondly,
for the first order methods the calculation of gradient was carried out by
analytical expression, i.e. in each point where the gradient was required, its
value was determined without approximation errors (with the accuracy of numbers
representation of computer). This circumstance was bounded up with the fact
that numeric calculation of gradient inevitably caused the inclusion of
additional parameters (such as the gradient approximation pattern, the choice
of gradient calculation step etc.), which in it's turn could influence
considerably the optimization process. In a whole, these could considerably
complicate the comparative analysis. In the work we used such assumption that
calculation of single value of goal function and that of it's particular by any
parameter derivative were equivalent by time, necessary for calculations.
Thirdly,
at last, all nonlinear programming methods, presented in table 2, were known to
require a definition of initial approximation to find the extremum. IOSO did
not require it. As the initial search points for other then IOSO methods we
used points, which had been resulting from first IOSO iteration. These points
were same for all optimization methods while they were different for all test
functions.
As the
result of solving of a number of such optimization problems we ascertained that
when optimization problem dimensionality was 4-5 variables the IOSO was
inferior to none of well-known nonlinear programming methods. When the
dimensionality exceeded 5 variables IOSO had evident advantage in convergence
rate for most of test functions. In a number of such cases the traditional
methods did not allow to find the solutions.
In a
process of more then ten-year use of optimization technology a considerable
number of practical optimization problems had been solved.
------------------------
|
"TECHNO-PULSAR"
| Home page