SystemPerformanceOptimizationContext Class

public abstract class SystemPerformanceOptimizationContext : CrossEntropyContext

Public MustInherit Class SystemPerformanceOptimizationContext
	Inherits CrossEntropyContext

public ref class SystemPerformanceOptimizationContext abstract : public CrossEntropyContext

[<AbstractClassAttribute>]
type SystemPerformanceOptimizationContext = 
    class
        inherit CrossEntropyContext
    end

Inheritance

Object    CrossEntropyContext    SystemPerformanceOptimizationContext

Derived

Novacta.Analytics.AdvancedCategoricalEntailmentEnsembleOptimizationContext

Novacta.Analytics.AdvancedCombinationOptimizationContext

Novacta.Analytics.AdvancedContinuousOptimizationContext

Novacta.Analytics.AdvancedPartitionOptimizationContext

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 is traversed iteratively by sampling, at each iteration, from a specific density function, member of a parametric family



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

The parametric space 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 .

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



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

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

After construction, property InitialParameter represents , while and 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 , 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 . Such sample is thus exploited in the updating step as follows. Firstly, an extreme level is computed to define the elite sampled points, i.e. those points having the lowest performances (less than ) in case of a minimization, or the highest ones in case of a maximization (greater than ). Secondly, a new reference parameter 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 of the system can be represented as a vector of length , as in , then 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 must be defined via method Performance(DoubleMatrix), and method UpdateParameter(LinkedListDoubleMatrix, DoubleMatrix) also needs to be overridden. Given and , this method is expected to return the solution to the following program:



where is the set of elite sample positions (row indexes of the matrix returned by method Sample, with being the -th row of such matrix and 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 . 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 , a corresponding reasonable value could be guessed for the optimizing argument of , say , with a function from to . Function must be defined by overriding method GetOptimalState(DoubleMatrix) that should return given a specific reference parameter .

Given the optimal parameter , (the parameter corresponding to the last iteration 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 .

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 or values too quickly, in the early iterations of the program.

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



where .

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.

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 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 can be represented as a vector of length 2:



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

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

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

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



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

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



where , and



with and .

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

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,
                        [-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:
// 1.00035159       1.00074794       
// 
// 
// 
// The minimum performance is:
// 3.229304809674981E-07

Reference