0.0
No commit activity in last 3 years
No release in over 3 years
Includes solvers for continuous and discrete multivariate optimisation problems.
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
 Dependencies

Development

~> 5.0
~> 0.48.0
~> 0.14.1

Runtime

~> 0.6
 Project Readme

cross_entropy

Build Status Gem Version

https://github.com/jdleesmiller/cross_entropy

SYNOPSIS

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

What is the Cross Entropy method?

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.

Supported problem types

  • 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.

Usage

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]

INSTALLATION

gem install cross_entropy

HISTORY

1.1.0 - 6 May 2017

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

1.0.0 - 2 Jan 2016

LICENSE

(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.