The Cross-Entropy Method | springerprofessional.de

Springer Professional

Top

2004 | Book

Read chapter Read first chapter

The Cross-Entropy Method

A Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning

Authors: Reuven Y. Rubinstein, Dirk P. Kroese

Publisher: Springer New York

Book Series : Information Science and Statistics

Included in: Professional Book Archive

Login to get access

About this book

This book is a comprehensive and accessible introduction to the cross-entropy (CE) method. The CE method started life around 1997 when the first author proposed an adaptive algorithm for rare-event simulation using a cross-entropy minimization technique. It was soon realized that the underlying ideas had a much wider range of application than just in rare-event simulation; they could be readily adapted to tackle quite general combinatorial and multi-extremal optimization problems, including many problems associated with the field of learning algorithms and neural computation. The book is based on an advanced undergraduate course on the CE method, given at the Israel Institute of Technology (Technion) for the last three years. It is aimed at a broad audience of engineers, computer scientists, mathematicians, statisticians and in general anyone, theorist or practitioner, who is interested in smart simulation, fast optimization, learning algorithms, image processing, etc. Our aim was to write a book on the CE method which was accessible to advanced undergraduate students and engineers who simply want to apply the CE method in their work, while at the same time accentu ating the unifying and novel mathematical ideas behind the CE method, so as to stimulate further research at a postgraduate level.

Advertisement

Table of Contents

Frontmatter

1. Preliminaries

Abstract

The purpose of this preparatory chapter is to provide some initial background for this book, including a summary of the relevant definitions and concepts in probability, statistics, simulation and information theory. Readers familiar with these ideas may wish to skip through this chapter and proceed to the tutorial on the cross-entropy method in Chapter 2.

Reuven Y. Rubinstein, Dirk P. Kroese

2. A Tutorial Introduction to the Cross-Entropy Method

Abstract

The aim of this chapter is to provide a gentle and self-contained introduction to the cross-entropy (CE) method. We refer to Section 1.1 for additional background information on the CE method, including many references.

Reuven Y. Rubinstein, Dirk P. Kroese

3. Efficient Simulation via Cross-Entropy

Abstract

The performance of modern systems, such as coherent reliability systems, inventory systems, insurance risk, storage systems, computer networks and telecommunication networks is often characterized by probabilities of rare events and is frequently studied through simulation. Analytical solutions or accurate approximations for such rare-event probabilities are only available for a very restricted class of systems. Consequently, one often has to resort to simulation. However, estimation of rare-event probabilities with crude Monte Carlo techniques requires a prohibitively large numbers of trials, as illustrated in Example 1.3. Thus, new techniques are required for this type of problem. Two methods, called splitting/RESTART and importance sampling (IS) have been extensively investigated by the simulation community in the last decade.

Reuven Y. Rubinstein, Dirk P. Kroese

4. Combinatorial Optimization via Cross-Entropy

Abstract

In this chapter we show how the CE method can be easily transformed into an efficient and versatile randomized algorithm for solving optimization problems, in particular combinatorial optimization problems.

Reuven Y. Rubinstein, Dirk P. Kroese

5. Continuous Optimization and Modifications

Abstract

In this chapter we discuss how the CE method can be used for continuous multi-extremal optimization, and provide a number of modifications of the basic CE algorithm, applied to both combinatorial and continuous multiextremal optimization. Specific modifications include the use of alternative “reward/loss” functions (Section 5.2), and the formulation of a fully automated version of the CE algorithm (Section 5.3). This modified version allows automatic tuning of all the parameters of the CE algorithm. Numerical results for continuous multi-extremal optimization problems and the FACE modifications are given in Sections 5.4, and 5.5, respectively.

Reuven Y. Rubinstein, Dirk P. Kroese

6. Noisy Optimization with CE

Abstract

In this chapter we show how the CE method optimizes noisy objective functions, that is, objective functions corrupted with noise. Noisy optimization, also called stochastic optimization, can arise in various ways. For example, in the analysis of data networks [24], a well-known problem is to find a routing table that minimizes the congestion in the network. Typically this problem is solved under deterministic assumptions. In particular, the stream of data is represented by a constant “flow,” and the congestion at a link is measured in terms of a constant arrival rate to the link, which is assumed to depend on the routing table only. These assumptions are reasonable only when the arrival process changes very slowly relative to the average time required to empty the queues in the network. In a more realistic setting however, using random arrival and queueing processes, the optimization problem becomes noisy. Other examples of noisy optimization include stochastic scheduling and stochastic shortest/longest path problems. References on noisy optimization include [9, 26, 36, 37, 60, 78].

Reuven Y. Rubinstein, Dirk P. Kroese

7. Applications of CE to COPs

Abstract

In this chapter we show how CE can be employed to solve combinatorial optimization problems (COPs) from various fields. Our goal is to illustrate the flexibility and efficiency of the CE algorithm. We believe that the CE approach could open up a whole range of possible applications, for example in computational biology, graph theory, and scheduling Section 7.1 deals with an application of the CE method concerning the alignment of DNA sequences; this section is based partly on [98]. In Sections 7.2–7.4, adapted from [113], the CE method is used to solve the single machine total weighted tardiness problem (SMTWTP), the single machine common due date problem (SMDDP), and the capacitated vehicle routing problem (CVRP). Finally, in Section 7.5 we consider various CE approaches for solving the maximum clique and related graph problems.

Reuven Y. Rubinstein, Dirk P. Kroese

8. Applications of CE to Machine Learning

Abstract

In this chapter we apply the CE method to several problems arising in machine learning, specifically with respect to optimization. In Section 8.1, adapted from [50], we apply CE to the well-known mastermind game. Section 8.2, based partly on [112], describes the application of the CE method to Markov decision processes. Finally, in Section 8.3 the CE method is applied to clustering problems. In addition to its simplicity, the advantage of using the CE method for machine learning is that it does not require direct estimation of the gradients, as many other algorithms do (for example, the stochastic approximation, steepest ascent, or conjugate gradient method). Moreover, as a global optimization procedure the CE method is quite robust with respect to starting conditions and sampling errors, in contrast to some other heuristics, such as simulated annealing or guided local search.

Reuven Y. Rubinstein, Dirk P. Kroese

Backmatter

Title: The Cross-Entropy Method
Authors: Reuven Y. Rubinstein
Dirk P. Kroese
Copyright Year: 2004
Publisher: Springer New York
Electronic ISBN: 978-1-4757-4321-0
Print ISBN: 978-1-4419-1940-3
DOI: https://doi.org/10.1007/978-1-4757-4321-0