CrossEntropyProgram Class

Instances of the CrossEntropyProgram class represents algorithms based upon the Cross-Entropy method^[1] , useful to analyze the performance of complex systems under extreme conditions. For example, a Cross-Entropy program can be implemented to estimate the probability that the system will perform extremely well, or to determine what state of the system corresponds to a minimal performance.

The Cross-Entropy method raises in the context of rare event probability estimation, but it is also closely related to the optimization of continuous or discrete functions. In fact, optimizing a function can be seen as the problem of estimating the probability of the event represented by the function assuming a value over a given extreme level, an event that can be typically interpreted as rare. A CrossEntropyProgram can thus be designed to solve optimization or estimation problems, provided that such problems can be defined in terms of performance excesses over an exceptionally high or low level.

The Cross-Entropy method

The Cross-Entropy method iteratively executes two main steps.

Sampling step

The first one, the sampling step, is responsible for generating diverse candidate states of the system. In this step, states are interpreted as points of a sample drawn from a parametric statistical distribution, whose definition depends upon the problem under study.

Updating step

The updating step aims to modify the distribution from which the samples will be obtained in the next iteration, in order to improve the probability of sampling relevant states, i.e. those states corresponding to the performance excesses of interest. Let us represent the sampled states in the current iteration as , where is the sample size. The corresponding performances, , are computed and sorted in increasing order, say obtaining the following ordering:



In this way, the states which guarantee the highest performances can be identified as those whose performances occupy the last positions in the ordering.

The updating step relies on the concept of elite sample points. Depending on the excesses being defined over a high or a low level, they can be outlined differently as follows. If the problem under study is defined in terms of performance excesses over an exceptionally high level, the Cross-Entropy method refers to the sample points whose performances occupy the last positions in the ordering as the elite sample points; otherwise, the elite points will be those whose performances occupy the first positions.

A way to define them exactly is as follows. Let be the sampled state such that , , and consider a constant, referred to as the rarity of the program, say , usually set to a value in the interval .

If the elite points refer to the highest performances, then the points occupying a position greater than or equal to are defined as elite ones, with being the ceiling function. In this case, the current iteration is said to reach a performance level equal to .

If the elite points refer to the lowest performances, then they can be defined as those points occupying a position less than or equal to , where is the floor function. Such points are thus , and the current iteration will reach a performance level equal to .

Once that the elite states have been identified, the joint distribution from which the states will be sampled in the next iteration is updated by estimating its parameters using the elite states only. Since they correspond to the performance excesses of interest, this updating mechanism guarantees that states having relevant performances will be included in subsequent samples with greater probabilities.

Executing a Cross-Entropy program

Class CrossEntropyProgram follows the Template Method pattern^[2] by defining in an operation the structure of a Cross-Entropy algorithm. Run is the template method, in which the invariant parts of a Cross-Entropy program are implemented once. The behaviors that can vary are deferred to a CrossEntropyContext object, which is passed as a parameter to the template method.

Methods EvaluatePerformances and Sample can execute their tasks both sequentially and concurrently. You can control their activities by setting properties PerformanceEvaluationParallelOptions and SampleGenerationParallelOptions, respectively. By default, the number of concurrently running operations is unlimited.

Specialized Cross-Entropy programs

It is possible to apply the Cross-Entropy method by exploiting a CrossEntropyProgram instance and deriving directly from class CrossEntropyContext to define the context of interest. However, it is recommended to execute the specialized programs represented by SystemPerformanceOptimizer instances when addressing combinatorial and multi-extremal optimization problems, or by RareEventProbabilityEstimator ones if the estimation of rare event probabilities is required. These programs have corresponding specialized contexts, SystemPerformanceOptimizationContext and RareEventProbabilityEstimationContext respectively, from which one can derive to define the problem under study.

Reference