CombinationOptimizationContext Class

Class CombinationOptimizationContext derives from SystemPerformanceOptimizationContext, and defines a Cross-Entropy context able to solve combinatorial optimization problems regarding the selection of fixed size subsets from a collection of items.

Class SystemPerformanceOptimizationContext thoroughly defines a system whose performance must be optimized. Class CombinationOptimizationContext specializes that system by assuming that its performance, say , is defined on the set of combinations, having the specified size, available from a given collection of items.

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. An argument defines a combination by signaling that the -th item is included in the combination if , otherwise setting .

If the combinations under study have fixed size equal to , then each argument will have exactly nonzero entries.

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 combinations

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 CombinationOptimizationContext, the parametric family is outlined as follows. Each component of an argument of is attached to a independent Bernoulli distribution having parameter , and is defined as the distribution of the sum of the corresponding Bernoulli trials, conditional to having exactly successes. The Cross-Entropy sampling parameter can thus be represented as the vector .

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 CombinationOptimizationContext defines as a constant vector 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 ,



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 is its indicator function.

Applying a smoothing scheme to updated parameters

In a CombinationOptimizationContext, 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. The probabilities are sorted in increasing order, say obtaining the following ordering:



and the corresponding sequence of indexes such that



is taken into account by defining the set and returning



where is one if ; zero otherwise. This is equivalent to include in the optimal combination those items having the greatest probabilities in parameter .

Stopping criterion

A CombinationOptimizationContext 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 CombinationOptimizationContext, the method analyzes the currently updated reference parameter, say as follows. If condition



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

Instantiating a context for optimizing on combinations

At instantiation, the constructor of a CombinationOptimizationContext object will receive information about the optimization under study by means of parameters representing the objective function , the combination constants and , 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 CombinationDimension, 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 binary entries as a valid representation of an argument.

In the following example, an existing partition of twelve items is explained by selecting two features out of the seven ones available in an artificial data set regarding the items under study.

The selection criterion is defined as the maximization of the Dunn Index in the domain of selectable sub data sets.

using System;
using Novacta.Analytics.Advanced;

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

            // Define a partition that must be explained.
            // Three parts (clusters) are included,
            // containing, respectively, items 0 to 3,
            // 4 to 7, and 8 to 11.
            var partition = IndexPartition.Create(
                new double[numberOfItems]
                    { 0 ,0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2 });

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

            // The first 5 features are built to be almost
            // surely non informative, since they result
            // as samples drawn from a same distribution.
            var g = new GaussianDistribution(mu: 0, sigma: .01);
            for (int j = 0; j < 5; j++)
            {
                data[":", j] = g.Sample(sampleSize: numberOfItems);
            }

            // Features 5 to 6 are instead built to be informative,
            // since they are sampled from different distributions
            // while filling rows whose indexes are in different parts
            // of the partition to be explained.
            var partIdentifiers = partition.Identifiers;
            double mu = 1.0;
            for (int i = 0; i < partIdentifiers.Count; i++)
            {
                var part = partition[partIdentifiers[i]];
                int partSize = part.Count;
                g.Mu = mu;
                data[part, 5] = g.Sample(sampleSize: partSize);
                mu += 2.0;
                g.Mu = mu;
                data[part, 6] = g.Sample(sampleSize: partSize);
                mu += 2.0;
            }

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

            // Define the selection problem as
            // the maximization of the Dunn Index.
            double objectiveFunction(DoubleMatrix x)
            {
                // An argument x has entries equal to one,
                // signaling that the corresponding features 
                // are selected at x. Otherwise, the entries
                // are zero.
                IndexCollection selected = x.FindNonzero();

                double performance =
                    IndexPartition.DunnIndex(
                        data: data[":", selected],
                        partition: partition);

                return performance;
            }

            var optimizationGoal = OptimizationGoal.Maximization;

            // Define how many features must be selected
            // for explanation.
            int numberOfExplanatoryFeatures = 2;

            // Create the required context.
            var context = new CombinationOptimizationContext(
                objectiveFunction: objectiveFunction,
                stateDimension: numberOfFeatures,
                combinationDimension: numberOfExplanatoryFeatures,
                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 = 1000;

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

            IndexCollection optimalExplanatoryFeatureIndexes =
                results.OptimalState.FindNonzero();

            // 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 maximizer of the performance is:");
            Console.WriteLine(results.OptimalState);

            Console.WriteLine();
            Console.WriteLine(
                "The {0} features best explaining the given partition have column indexes:",
                numberOfExplanatoryFeatures);
            Console.WriteLine(optimalExplanatoryFeatureIndexes);

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

            Console.WriteLine();
            Console.WriteLine("This is the Dunn Index for the selected features:");
            var di = IndexPartition.DunnIndex(
                data[":", optimalExplanatoryFeatureIndexes],
                partition);
            Console.WriteLine(di);
        }
    }
}

// Executing method Main() produces the following output:
// 
// The data set:
// 0.00443412891    0.00269053161    0.00413587912    -0.00765022961   -0.00516230961   1.00663787       3.01053155       
// -0.00206677161   0.0208840727     -0.00323082941   -0.00939014629   0.00144991289    0.999318094      3.01264231       
// 0.0115714825     0.00980880513    0.00490173372    0.00327885751    0.0157818959     0.990821676      3.01207396       
// -0.0156854205    -0.00757566326   -0.00972832587   -0.00217925897   0.0107421304     0.992541729      2.99695621       
// 0.0022067431     -0.00321077809   -0.00611898592   0.00720305793    0.0128767272     4.99440474       6.99892958       
// -0.00637438188   0.00505242911    -0.0040927039    0.00210944391    -0.0152463979    4.9974367        6.99460151       
// -0.00662648185   -0.0149292848    0.00236975765    0.0103282087     -0.0108846478    4.99249371       6.98860335       
// -0.0219354054    0.012282089      0.01095691       -0.0108910034    0.00275269084    5.02268395       6.99732006       
// -0.00172760645   0.000890969089   -0.0121749937    -0.0060896535    -0.0125774475    9.00956698       10.9938497       
// 0.0157657881     0.00840849213    0.00295384061    -0.00358519597   0.00447359706    8.98856241       11.0013196       
// 0.0129253424     -0.000948574239  0.00235032211    -0.0135124598    -0.023309088     9.00738398       10.9891406       
// -0.00848136345   -0.00459883434   -0.0148632861    0.0223964956     -0.00259506386   9.00721897       11.005672        
// 
// 
// The Cross-Entropy optimizer has converged: True.
// 
// Initial guess parameter:
// 0.5              0.5              0.5              0.5              0.5              0.5              0.5              
// 
// 
// 
// The maximizer of the performance is:
// 0                0                0                0                0                1                1                
// 
// 
// 
// The 2 features best explaining the given partition have column indexes:
// 5, 6
// 
// The maximum performance is:
// 179.2086694228848
// 
// This is the Dunn Index for the selected features:
// 179.2086694228848

Reference

Other Resources