PartitionOptimizationContext Class

public sealed class PartitionOptimizationContext : SystemPerformanceOptimizationContext

Public NotInheritable Class PartitionOptimizationContext
	Inherits SystemPerformanceOptimizationContext

public ref class PartitionOptimizationContext sealed : public SystemPerformanceOptimizationContext

[<SealedAttribute>]
type PartitionOptimizationContext = 
    class
        inherit SystemPerformanceOptimizationContext
    end

Inheritance

Object    CrossEntropyContext    SystemPerformanceOptimizationContext    PartitionOptimizationContext

Class PartitionOptimizationContext derives from SystemPerformanceOptimizationContext, and defines a Cross-Entropy context able to solve combinatorial problems aimed to identify the optimal partition of a set, given a specified criterion.

Class SystemPerformanceOptimizationContext thoroughly defines a system whose performance must be optimized. Class PartitionOptimizationContext specializes the system by assuming that its performance, say , has domain included in the family of those partitions in which the items of a given collection can be split.

The system's state-space , i.e. the domain of , can thus be represented as the Cartesian product of copies of the set , where is the number of available items, and is the maximum number of parts allowed in the partitions under study. An argument defines a partition by signaling that the -th item is included in the -th part by setting , with .

Notice that represents a maximum number of parts. It means that there exist arguments in which, for a given , no entries will be equal to .

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



where is a possible argument of , 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.

Implementing a context for optimizing on set partitions

The Cross-Entropy method provides an iterative multi step procedure. In the context of combinatorial optimization, at each iteration a sampling step is executed in order to generate diverse candidate arguments of the objective function, sampled from a distribution characterized by the reference parameter of the iteration, say . Such sample is thus exploited in the updating step in which a new reference parameter is identified to modify the distribution from which the samples will be obtained in the next iteration: such modification is executed in order to improve the probability of sampling relevant arguments, i.e. those arguments corresponding to the function values 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 have been implemented as follows.

Sampling step

In a PartitionOptimizationContext, the parametric family is outlined as follows. Each component of an argument of is attached to a independent finite discrete distribution having parameter , where, for , is the probability of including the -th item to the -th part. The Cross-Entropy sampling parameter can thus be represented as the matrix



.

The parametric space should include a parameter under which all possible states must have a real chance of being selected: this parameter is specified as the initial reference parameter . A PartitionOptimizationContext defines as a constant matrix whose entries are all equal to .

Updating step

At iteration , let us represent the sample drawn as , where is the Cross-Entropy sample size, and the -th sample point is the sequence . The parameter's updating formula is, for and ,



where is the elite sample in this context, i.e. the set of sample points having the lowest performances observed during the -th iteration, if minimizing, the highest ones, otherwise, while the functions are indicators of the specified sets.

Applying a smoothing scheme to updated parameters

In a PartitionOptimizationContext, the sampling parameter is smoothed applying the following formula (See Rubinstein and Kroese, Remark 5.2, p. 189^[1]):



where .

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 is 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 follows. For each , the probabilities are sorted in increasing order, say obtaining the following ordering:



with the corresponding sequence of indexes , such that



Hence will return



where is . This is equivalent to include, in the optimal partition, the -th item to the part having the maximum probability of being assigned to given parameter .

Stopping criterion

A PartitionOptimizationContext never stops before executing a number of iterations less than MinimumNumberOfIterations, and always stops if such number is greater than or equal to 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.

In a PartitionOptimizationContext, the method analyzes the currently updated reference parameter, say



as follows. Define the sequence such that, for ,



If condition



can be verified, the method returns true; otherwise false is returned. Equivalently, the algorithm converges if the indexes of the largest probabilities in each of the columns of the reference parameter coincide times in a row of iterations.

Instantiating a context for optimizing on set partitions

At instantiation, the constructor of a PartitionOptimizationContext object will receive information about the optimization under study by means of parameters representing the objective function , the number of items , the maximum number of parts , the extremes of the allowed range of intermediate iterations, and , and a constant stating if the optimization goal is a maximization or a minimization. In addition, the smoothing parameter is also passed to the constructor.

After construction, and can be inspected, respectively, via properties MinimumNumberOfIterations and MaximumNumberOfIterations. The smoothing coefficient is also available via property ProbabilitySmoothingCoefficient. Combination constants and are returned by StateDimension and PartitionDimension, respectively. In addition, 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.

To evaluate the objective function at a specific argument, one can call method Performance(DoubleMatrix) passing the argument as a parameter. It is expected that the objective function will accept a row vector having entries included in as a valid representation of an argument.

In the following example, an optimal partition of 12 items is discovered given an artificial data set regarding the items under study.

The optimality criterion is defined as the minimization of the Davies-Bouldin Index.

using System;
using Novacta.Analytics.Advanced;

namespace Novacta.Analytics.CodeExamples.Advanced
{
    public class PartitionOptimizationContextExample0  
    {
        public void Main()
        {
            // Set the number of items and features under study.
            const int numberOfItems = 12;
            int numberOfFeatures = 7;

            // Create a matrix that will represent
            // an artificial data set,
            // having 12 items (rows) and 7 features (columns).
            // This will store the observations which
            // partition discovery will be based on.
            var data = DoubleMatrix.Dense(
                numberOfRows: numberOfItems,
                numberOfColumns: numberOfFeatures);

            // Fill the data rows by sampling from a different 
            // distribution while, respectively, drawing observations 
            // for items 0 to 3, 4 to 7, and 8 to 11: these will be the 
            // three different parts expected to be included in the 
            // optimal partition.
            double mu = 1.0;
            var g = new GaussianDistribution(mu: mu, sigma: .01);

            IndexCollection range = IndexCollection.Range(0, 3);
            for (int j = 0; j < numberOfFeatures; j++)
            {
                data[range, j] = g.Sample(sampleSize: range.Count);
            }

            mu += 5.0;
            g.Mu = mu;
            range = IndexCollection.Range(4, 7);
            for (int j = 0; j < numberOfFeatures; j++)
            {
                data[range, j] = g.Sample(sampleSize: range.Count);
            }

            mu += 5.0;
            g.Mu = mu;
            range = IndexCollection.Range(8, 11);
            for (int j = 0; j < numberOfFeatures; j++)
            {
                data[range, j] = g.Sample(sampleSize: range.Count);
            }

            Console.WriteLine("The data set:");
            Console.WriteLine(data);

            // Define the optimization problem as
            // the minimization of the Davies-Bouldin Index
            // of a candidate partition.
            double objectiveFunction(DoubleMatrix x)
            {
                // An argument x has 12 entries, each belonging
                // to the set {0,...,k-1}, where k is the
                // maximum number of allowed parts, so
                // x[j]==i signals that, at x, item j
                // has been assigned to part i.
                IndexPartition<double> selected =
                    IndexPartition.Create(x);

                var performance = IndexPartition.DaviesBouldinIndex(
                    data: data,
                    partition: selected);

                return performance;
            }

            var optimizationGoal = OptimizationGoal.Minimization;

            // Define the maximum number of parts allowed in the
            // partition to be discovered.
            int maximumNumberOfParts = 3;

            // Create the required context.
            var context = new PartitionOptimizationContext(
                objectiveFunction: objectiveFunction,
                stateDimension: numberOfItems,
                partitionDimension: maximumNumberOfParts,
                probabilitySmoothingCoefficient: .8,
                optimizationGoal: optimizationGoal,
                minimumNumberOfIterations: 3,
                maximumNumberOfIterations: 1000);

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

            // Set optimization parameters.
            double rarity = 0.01;
            int sampleSize = 2000;

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

            IndexPartition<double> optimalPartition =
                IndexPartition.Create(results.OptimalState);

            // 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 optimal partition is:");
            Console.WriteLine(optimalPartition);

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

            Console.WriteLine();
            Console.WriteLine("The Dunn Index for the optimal partition is:");
            var di = IndexPartition.DunnIndex(
                data,
                optimalPartition);
            Console.WriteLine(di);
        }
    }
}

// Executing method Main() produces the following output:
// 
// The data set:
// 1.00443413       1.00220674       0.998272394      1.00269053       0.996789222      1.00089097       1.00413588       
// 0.997933228      0.993625618      1.01576579       1.02088407       1.00505243       1.00840849       0.996769171      
// 1.01157148       0.993373518      1.01292534       1.00980881       0.985070715      0.999051426      1.00490173       
// 0.984314579      0.978064595      0.991518637      0.992424337      1.01228209       0.995401166      0.990271674      
// 5.99388101       5.98782501       5.99234977       6.00720306       5.99391035       5.99483769       6.01287673       
// 5.9959073        6.00295384       5.99060985       6.00210944       5.9964148        6.00144991       5.9847536        
// 6.00236976       6.00235032       6.00327886       6.01032821       5.98648754       6.0157819        5.98911535       
// 6.01095691       5.98513671       5.99782074       5.989109         6.0223965        6.01074213       6.00275269       
// 10.9874226       11.0066379       11.0105315       10.9944047       10.9989296       11.009567        10.9938497       
// 11.0044736       10.9993181       11.0126423       10.9974367       10.9946015       10.9885624       11.0013196       
// 10.9766909       10.9908217       11.012074        10.9924937       10.9886034       11.007384        10.9891406       
// 10.9974049       10.9925417       10.9969562       11.0226839       10.9973201       11.007219        11.005672        
// 
// 
// The Cross-Entropy optimizer has converged: True.
// 
// Initial guess parameter:
// 0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      
// 0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      
// 0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      0.333333333      
// 
// 
// 
// The minimizer of the performance is:
// 2                2                2                2                2                2                2                2                0                0                0                0                
// 
// 
// 
// The optimal partition is:
// [(0),  8, 9, 10, 11]
// [(2),  0, 1, 2, 3, 4, 5, 6, 7]
// 
// 
// The minimum performance is:
// 0.3343841188131412
// 
// The Dunn Index for the optimal partition is:
// 0.9961176310964293

Reference

Other Resources