Click or drag to resize

SystemPerformanceOptimizationContext Class

Represents a Cross-Entropy context in which the optimization of the performance of a system is obtained by exploiting a SystemPerformanceOptimizer instance.
Inheritance Hierarchy

Namespace:  Novacta.Analytics.Advanced
Assembly:  Novacta.Analytics (in Novacta.Analytics.dll) Version: 2.0.0
Syntax
public abstract class SystemPerformanceOptimizationContext : CrossEntropyContext

The SystemPerformanceOptimizationContext type exposes the following members.

Constructors
  NameDescription
Protected methodSystemPerformanceOptimizationContext
Initializes a new instance of the SystemPerformanceOptimizationContext class having the specified state dimension, initial parameter, optimization goal, and range of iterations.
Top
Properties
  NameDescription
Protected propertyEliteSampleDefinition
Gets the elite sample definition for this context.
(Overrides CrossEntropyContextEliteSampleDefinition.)
Public propertyInitialParameter
Gets the parameter initially exploited to sample from the state-space of the system defined by this context.
(Inherited from CrossEntropyContext.)
Public propertyMaximumNumberOfIterations
Gets the maximum number of iterations allowed by this context.
Public propertyMinimumNumberOfIterations
Gets the minimum number of iterations required by this context.
Public propertyOptimizationGoal
Gets a constant specifying if the performance function in this context must be minimized or maximized.
Public propertyStateDimension
Gets or sets the dimension of a vector representing a system's state when a CrossEntropyProgram executes in this context.
(Inherited from CrossEntropyContext.)
Public propertyTraceExecution
Gets or sets a value indicating whether the execution of this context must be traced.
(Inherited from CrossEntropyContext.)
Top
Methods
  NameDescription
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Protected methodGetOptimalState
Gets the argument that optimizes the performance function in this context, according to the specified Cross-Entropy sampling parameter.
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Protected methodCode exampleOnExecutedIteration
Called after completion of each iteration of a CrossEntropyProgram executing in this context.
(Overrides CrossEntropyContextOnExecutedIteration(Int32, DoubleMatrix, LinkedListDouble, LinkedListDoubleMatrix).)
Protected methodPartialSample
Draws the specified subset of a sample from a distribution characterized by the given parameter, using the stated random number generator. Used when executing the sampling step of a CrossEntropyProgram running in this context.
(Inherited from CrossEntropyContext.)
Protected methodPerformance
Defines the performance of a specified state in this context.
(Inherited from CrossEntropyContext.)
Protected methodCode exampleSmoothParameter
Provides the smoothing of the updated sampling parameter of a SystemPerformanceOptimizer executing in this context.
Protected methodStopAtIntermediateIteration
Specifies conditions under which a SystemPerformanceOptimizer executing in this context should be considered as terminated after completing an intermediate iteration.
Protected methodStopExecution
Specifies conditions under which a CrossEntropyProgram executing in this context should be considered as terminated.
(Overrides CrossEntropyContextStopExecution(Int32, LinkedListDouble, LinkedListDoubleMatrix).)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Protected methodUpdateLevel
Updates the performance level for the current iteration of a CrossEntropyProgram executing in this context and determines the corresponding elite sample.
(Overrides CrossEntropyContextUpdateLevel(DoubleMatrix, DoubleMatrix, EliteSampleDefinition, Double, DoubleMatrix).)
Protected methodUpdateParameter
Updates the sampling parameter attending the generation of the sample in the next iteration of a CrossEntropyProgram executing in this context.
(Inherited from CrossEntropyContext.)
Top
Remarks

A SystemPerformanceOptimizer is executed by calling its Optimize method. This is a template method, in the sense that it defines the invariant parts of a Cross-Entropy program for system's performance optimization. Such method relies on an instance of class SystemPerformanceOptimizationContext, which is passed as a parameter to it and specifies the primitive operations of the template method, i.e. those varying steps of the algorithm that depends on the problem under study.

Class SystemPerformanceOptimizationContext thoroughly defines the system whose performance must be optimized, and supplies the primitive operations as abstract or virtual methods, that its subclasses will override to provide the concrete behavior of the optimizer.

A Cross-Entropy optimizer is designed to identify the optimal arguments at which the performance function of a complex system reaches its minimum or maximum value. To get the optimal state, the system's state-space LaTeX equation is traversed iteratively by sampling, at each iteration, from a specific density function, member of a parametric family

LaTeX equation

where LaTeX equation is a vector representing a possible state of the system, and LaTeX equation is the set of allowable values for parameter LaTeX equation. The parameter exploited at a given iteration LaTeX equation is referred to as the reference parameter of such iteration and indicated as LaTeX equation. A minimum number of iterations, say LaTeX equation, must be executed, while a number of them up to a maximum, say LaTeX equation, is allowed.

The parametric space LaTeX equation should include a parameter under which all possible states must have a real chance of being selected: this parameter must be specified as the initial reference parameter LaTeX equation.

A Cross-Entropy optimizer can solve one of the following optimization programs:

LaTeX equation

where LaTeX equation is the state space of the system and LaTeX equation is the function returning the system performance at state LaTeX equation.

At instantiation, the constructor of a SystemPerformanceOptimizationContext object will receive information about the optimization under study by means of parameters representing LaTeX equation, LaTeX equation, LaTeX equation, and a constant stating if the optimization goal is a maximization or a minimization.

After construction, property InitialParameter represents LaTeX equation, while LaTeX equation and LaTeX equation can be inspected, respectively, via properties MinimumNumberOfIterations and MaximumNumberOfIterations. Lastly, property OptimizationGoal signals that the performance function must be maximized if it evaluates to the constant Maximization, or that a minimization is requested if it evaluates to the constant Minimization.

Implementing a context for combinatorial and multi-extremal optimization

The Cross-Entropy method provides an iterative multi step procedure. At each iteration LaTeX equation, the sampling step is executed in order to generate diverse candidate states of the system, sampled from a distribution characterized by the reference parameter of the iteration, say LaTeX equation. Such sample is thus exploited in the updating step as follows. Firstly, an extreme level LaTeX equation is computed to define the elite sampled points, i.e. those points having the lowest performances (less than LaTeX equation) in case of a minimization, or the highest ones in case of a maximization (greater than LaTeX equation). Secondly, a new reference parameter LaTeX equation is identified to modify the distribution from which the samples will be obtained in the next iteration: such modification is based on the elite sample points only, in order to improve the probability of sampling relevant states, i.e. those states corresponding to the performance excesses of interest (See the documentation of class CrossEntropyProgram for a thorough discussion of the Cross-Entropy method).

When the Cross-Entropy method is applied in an optimization context, a final optimizing step is executed, in which the argument corresponding to the searched extremum is effectively identified.

These steps must be implemented as follows.

Sampling step

Since class SystemPerformanceOptimizationContext derives from CrossEntropyContext, property StateDimension will return the dimension of the points in the Cross-Entropy samples. If a state LaTeX equation of the system can be represented as a vector of length LaTeX equation, as in LaTeX equation, then LaTeX equation should be returned. In addition, method PartialSample(Double, TupleInt32, Int32, RandomNumberGenerator, DoubleMatrix, Int32) must be overriden to determine how to draw the sample locally to a given thread when processing in parallel the sampling step.

Updating step

Class SystemPerformanceOptimizationContext overrides for you the methods required for ordering the system performances of the states sampled in the previous step, for updating the iteration levels and identifying the corresponding elite sample points. However, to complete the implementation of the updating step, function LaTeX equation must be defined via method Performance(DoubleMatrix), and method UpdateParameter(LinkedListDoubleMatrix, DoubleMatrix) also needs to be overridden. Given LaTeX equation and LaTeX equation, this method is expected to return the solution to the following program:

LaTeX equation

where LaTeX equation is the set of elite sample positions (row indexes of the matrix returned by method Sample, with LaTeX equation being the LaTeX equation-th row of such matrix and LaTeX equation being its number of rows. Method UpdateParameter receives two parameters. The first is a LinkedListT of DoubleMatrix instances, representing the reference parameters applied in previous iterations. The instance returned by property Last corresponds to parameter LaTeX equation. The second method parameter is a DoubleMatrix instance whose rows represent the elite points sampled in the current iteration.

Optimizing step

The optimizing step is executed after that the underlying Cross-Entropy program has converged. In a specified context, it is expected that, given a reference parameter LaTeX equation, a corresponding reasonable value could be guessed for the optimizing argument of LaTeX equation, say LaTeX equation, with LaTeX equation a function from LaTeX equation to LaTeX equation. Function LaTeX equation must be defined by overriding method GetOptimalState(DoubleMatrix) that should return LaTeX equation given a specific reference parameter LaTeX equation.

Given the optimal parameter LaTeX equation, (the parameter corresponding to the last iteration LaTeX equation executed by the algorithm before stopping), the argument at which the searched extremum is considered as reached according to the Cross-Entropy method will be returned as LaTeX equation.

Additional overridable methods

Applying a smoothing scheme to parameters

Especially when a sampling parameter consists of probabilities, a SystemPerformanceOptimizer could converge to a wrong solution if such parameter is updated without applying a smoothing scheme, so preventing the probabilities to reach LaTeX equation or LaTeX equation values too quickly, in the early iterations of the program.

Let LaTeX equation the reference parameter exploited in the last iteration, and let LaTeX equation the previous one. By default, this method applies the following smoothing scheme:

LaTeX equation

where LaTeX equation.

You can override method SmoothParameter(LinkedListDoubleMatrix) in order to apply a smoothing scheme specific to a given context.

Stopping criterion

An iteration is defined as intermediate for a SystemPerformanceOptimizationContext if it is greater than MinimumNumberOfIterations, and less than MaximumNumberOfIterations.

For intermediate iterations, method StopAtIntermediateIteration(Int32, LinkedListDouble, LinkedListDoubleMatrix) is called to check if a Cross-Entropy program executing in this context should stop or not.

By default, the method controls if, in the last MinimumNumberOfIterations iterations, the levels achieved by the program remain constant, and, if so, return true; otherwise returns false.

You can override StopAtIntermediateIteration in order to apply a specific stopping criterion for intermediate iterations.

Examples

The following example is based on Section 5.1 proposed by Rubinstein and Kroese (Section 2.2.1)[1] .

A Cross-Entropy optimizer is exploited to minimize the bi-dimensional Rosenbrock function, showed in the following figure.

100%Bi-dimensional Rosenbrock functionOptimizationExample.png

The global minimum at LaTeX equation is indicated by a red dot.

In order to solve such problem, we define a Cross-Entropy context as follows. Since the function under study has two arguments, we analyze a system whose generic state LaTeX equation can be represented as a vector of length 2:

LaTeX equation

while the Rosenbrock function is interpreted as the performance of the system, i.e.

LaTeX equation

The sampling step is accomplished as follows. Each component LaTeX equation of a state LaTeX equation is attached to a Gaussian distribution, say LaTeX equation, and the j-th entry of a state is sampled from LaTeX equation, independently from the other. The Cross-Entropy sampling parameter can thus be represented as a LaTeX equation matrix LaTeX equation, whose first row stores the means of the Gaussian distributions, while the second row contains their standard deviations, so that LaTeX equation and LaTeX equation.

The initial parameter sets (arbitrarily) the Gaussian means to LaTeX equation. More importantly, the standard deviations are set equal to LaTeX equation: in this way, during the first execution of the sampling step each argument will have a good likelihood of being drawn.

At iteration LaTeX equation, the parameter's first row updating formula is, for LaTeX equation,

LaTeX equation

where LaTeX equation is the set of elite sample in this context, i.e. the set of sample points having the lowest performances observed during the LaTeX equation-th iteration. The parameter's second row, that containing the standard deviations, is instead updated as follows:

LaTeX equation

The so-updated parameter is thus smoothed applying the following formulas (See Rubinstein and Kroese, Remark 5.2, p. 189[1] .):

LaTeX equation

where LaTeX equation, and

LaTeX equation

with LaTeX equation and LaTeX equation.

The algorithm will stop if each standard deviation in a Cross-Entropy parameter will be less than LaTeX equation.

Minimizing the bi-dimensional Rosenbrock function.
using System;
using System.Collections.Generic;
using Novacta.Analytics.Advanced;

namespace Novacta.Analytics.CodeExamples.Advanced
{
    public class CrossEntropyOptimizerExample0  
    {
        class RosenbrockFunctionMinimizationContext
            : SystemPerformanceOptimizationContext
        {
            public RosenbrockFunctionMinimizationContext()
                : base(
                    // The function to be optimized is the bi-dimensional
                    // Rosenbrock function, hence it has two arguments.
                    // Thus it can be interpreted as the performance of
                    // a system whose state can be represented as a vector
                    // of length 2.
                    stateDimension: 2,
                    // Set the optimization goal to minimization.
                    optimizationGoal: OptimizationGoal.Minimization,
                    // Define the initial parameter of the distribution
                    // from which samples are drawn while searching
                    // for the optimizer (sampling the state-space
                    // of the system, i.e. the domain of the function).
                    // The parameter is a matrix of two rows.
                    // Its first row represents the means, its second one 
                    // the standard deviations of two Gaussian distributions
                    // from which the two arguments of the optimizing function,
                    // respectively, are sampled while searching 
                    // for the optimizer.
                    initialParameter: DoubleMatrix.Dense(2, 2,
                        new double[] { -1.0, 10000.0, -1.0, 10000.0 }),
                    minimumNumberOfIterations: 3,
                    maximumNumberOfIterations: 10000)
            {
            }

            // Define the performance function of the 
            // system under study (in this context, 
            // a bi-dimensional Rosenbrock function to be minimized).
            protected override double Performance(DoubleMatrix x)
            {
                double performance = 0.0;
                for (int i = 0; i < this.StateDimension - 1; i++)
                {
                    var x_i = x[i];
                    var squared_x_i = Math.Pow(x[i], 2.0);
                    performance += 100.0 * (Math.Pow(x[i + 1] - squared_x_i, 2.0));
                    performance += Math.Pow(1.0 - x_i, 2.0);
                }
                return performance;
            }

            // Set how to sample system states
            // given the specified parameter. 
            protected override void PartialSample(
                double[] destinationArray,
                Tuple<int, int> sampleSubsetRange,
                RandomNumberGenerator randomNumberGenerator,
                DoubleMatrix parameter,
                int sampleSize)
            {
                // Must be Item1 included, Item2 excluded
                int subSampleSize =
                    sampleSubsetRange.Item2 - sampleSubsetRange.Item1;

                int leadingDimension = Convert.ToInt32(sampleSize);

                for (int j = 0; j < this.StateDimension; j++)
                {
                    var distribution = new
                        GaussianDistribution(
                            mu: parameter[0, j],
                            sigma: parameter[1, j])
                    {
                        RandomNumberGenerator = randomNumberGenerator
                    };
                    distribution.Sample(
                         subSampleSize,
                         destinationArray, j * leadingDimension + sampleSubsetRange.Item1);
                }
            }

            // Define how to get the optimal state given
            // a Cross-Entropy parameter.
            protected override DoubleMatrix GetOptimalState(
                DoubleMatrix parameter)
            {
                // The optimal state is the vector of
                // means.
                return parameter[0, ":"];
            }

            // Set how to update the parameter via 
            // the elite sample.
            protected override DoubleMatrix UpdateParameter(
                LinkedList<DoubleMatrix> parameters,
                DoubleMatrix eliteSample)
            {
                var newParameter = DoubleMatrix.Dense(2, this.StateDimension);
                newParameter[0, ":"] =
                    Stat.Mean(
                        data: eliteSample,
                        dataOperation: DataOperation.OnColumns);
                newParameter[1, ":"] =
                    Stat.StandardDeviation(
                        data: eliteSample,
                        dataOperation: DataOperation.OnColumns,
                        adjustForBias: false);

                return newParameter;
            }

            // Provide a smoothing scheme for updated sampling
            // parameters.
            protected override void SmoothParameter(
                LinkedList<DoubleMatrix> parameters)
            {
                double iteration = Convert.ToDouble(parameters.Count);
                if (iteration > 1)
                {
                    DoubleMatrix currentParameter = parameters.Last.Value;
                    DoubleMatrix previousParameter = parameters.Last.Previous.Value;

                    // Smoothing means
                    double meanAlpha = .7;
                    var previousMeans = previousParameter[0, ":"];
                    var currentMeans = currentParameter[0, ":"];
                    currentParameter[0, ":"] =
                        meanAlpha * currentMeans + (1.0 - meanAlpha) * previousMeans;

                    // Smoothing standard deviations
                    var previousStdDevs = previousParameter[1, ":"];
                    var currentStdDevs = currentParameter[1, ":"];
                    double q = 6.0;
                    double beta = .9;
                    double stdDevAlpha = beta * (1.0 - Math.Pow(1.0 - 1.0 / iteration, q));

                    currentParameter[1, ":"] =
                        stdDevAlpha * currentStdDevs + (1.0 - stdDevAlpha) * previousStdDevs;
                }
            }

            protected override bool StopAtIntermediateIteration(
                int iteration,
                LinkedList<double> levels,
                LinkedList<DoubleMatrix> parameters)
            {
                // Stop the program when each 
                // standard deviation is less than .05.
                var stdDevs = parameters.Last.Value[1, ":"];
                for (int j = 0; j < stdDevs.Count; j++)
                {
                    if (stdDevs[j] >= .05)
                    {
                        return false;
                    }
                }

                return true;
            }
        }

        public void Main()
        {
            // Create the context.
            var context = new RosenbrockFunctionMinimizationContext();

            // Create the optimizer.
            var optimizer = new SystemPerformanceOptimizer()
            {
                PerformanceEvaluationParallelOptions = { MaxDegreeOfParallelism = -1 },
                SampleGenerationParallelOptions = { MaxDegreeOfParallelism = -1 }
            };

            // Set optimization parameters.
            double rarity = 0.1;
            int sampleSize = 1000;

            // Solve the problem.
            var results = optimizer.Optimize(
                context,
                rarity,
                sampleSize);

            // Show the results.
            Console.WriteLine(
                "The Cross-Entropy optimizer has converged: {0}.",
                results.HasConverged);

            Console.WriteLine();
            Console.WriteLine("Initial guess parameter:");
            Console.WriteLine(context.InitialParameter);

            Console.WriteLine();
            Console.WriteLine("The minimizer of the performance is:");
            Console.WriteLine(results.OptimalState);

            Console.WriteLine();

            Console.WriteLine("The minimum performance is:");
            Console.WriteLine(results.OptimalPerformance);
        }
    }
}

// Executing method Main() produces the following output:
// 
// The Cross-Entropy optimizer has converged: True.
// 
// Initial guess parameter:
// -1               -1               
// 10000            10000            
// 
// 
// 
// The minimizer of the performance is:
// 0.99860578       0.997553876      
// 
// 
// 
// The minimum performance is:
// 1.3529163162538295E-05

Bibliography
[1] Rubinstein, R.Y. and Kroese, D.P., The Cross-Entropy Method, A unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning, Springer, New York. (2004)
See Also