cross_entropy

https://github.com/jdleesmiller/cross_entropy

Implementations of the Cross Entropy Method for several types of problems. Uses NArray for the numerics, to achieve reasonable performance.

It's basically like a genetic algorithm without the biological analogy. Instead, it uses probability distributions. You start by specifying a probability distribution for the optimal values, based on your initial guess. The CEM then

• generates samples based on that distribution,
• scores them according to the objective function, and
• uses the lowest-scoring samples (that is, this library assumes that we want to minimize the objective function) to update the parameters of the probability distribution, so it converges on an optimal value.

It has relatively few tuneable parameters, and it automatically balances diversification and intensification. It is robust to noise in the objective function, so it is very useful for parameter tuning and simulation work.

• MatrixProblem: For discrete optimisation problems. Each variable can take one of a fixed number of states. The sampling distribution is a defined by a probability mass function for each variable. The term "matrix problem" is based on the idea that we can write the PMFs for each variable into the rows (NArray dimension 1) of a matrix. For example:

             value 1 | value 2
  variable 1     0.3 | 0.7
  variable 2     0.9 | 0.1
  

• ContinuousProblem: For continuous unbounded problems. The sampling distribution is a univariate Gaussian.

• BetaProblem: For continous bounded problems. The sampling distribution is a Beta distribution.

For example, here is the Rosenbrock banana function and a custom smooth updater. The function has a global minimum at (a, a^2), but it's hard to find.

# Parameters for the "banana" objective function.
a = 1.0
b = 100.0

# Our initial guess at the optimal solution.
# This is just a guess, so we give it a large standard deviation.
mean = NArray[0.0, 0.0]
stddev = NArray[10.0, 10.0]

# Set up the problem. These are the CEM parameters.
problem = CrossEntropy::ContinuousProblem.new(mean, stddev)
problem.num_samples = 1000
problem.num_elite   = 10
problem.max_iters   = 300
smooth = 0.1

# Objective function.
problem.to_score_sample {|x| (a - x[0])**2 + b*(x[1] - x[0]**2)**2 }

# Do some smoothing when updating the parameters based on new samples.
# This isn't strictly required, but I find it often helps convergence.
problem.to_update {|new_mean, new_stddev|
  smooth_mean = smooth*new_mean + (1 - smooth)*problem.param_mean
  smooth_stddev = smooth*new_stddev + (1 - smooth)*problem.param_stddev
  [smooth_mean, smooth_stddev]
}

# It's all calculation from now on...
problem.solve
# problems.param_mean => NArray[1.0, 1.0]

gem install cross_entropy

• Linted with rubocop
• Improved test coverage
• Added recent rubies in CI
• Improved README

• Initial release after extraction from https://github.com/jdleesmiller/si_taxi
• Added Gaussian and Beta problems

(The MIT License)

Copyright (c) 2014-2017 John Lees-Miller

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.