boost/math
2
0
Fork 0
mirror of https://github.com/boostorg/math.git synced 2026-01-19 04:22:09 +00:00
Code Issues Projects Releases Wiki Activity
Files
develop
math/doc/html/math_toolkit/random_search.html
jzmaddock 4c2cdc2cf6 Regenerate docs.
2024-08-06 13:18:32 +01:00

198 lines
20 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Random Search</title>
<link rel="stylesheet" href="../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../optimization.html" title="Chapter 11. Optimization">
<link rel="prev" href="jso.html" title="Algorithm jSO">
<link rel="next" href="cma_es.html" title="Evolution Strategy with Covariance Matrix Adaptation">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="jso.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../optimization.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cma_es.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="math_toolkit.random_search"></a><a class="link" href="random_search.html" title="Random Search">Random Search</a>
</h2></div></div></div>
<h4>
<a name="math_toolkit.random_search.h0"></a>
<span class="phrase"><a name="math_toolkit.random_search.synopsis"></a></span><a class="link" href="random_search.html#math_toolkit.random_search.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">optimization</span><span class="special">/</span><span class="identifier">random_search</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
<span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">optimization</span> <span class="special">{</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;</span> <span class="keyword">struct</span> <span class="identifier">random_search_parameters</span> <span class="special">{</span>
<span class="keyword">using</span> <span class="identifier">Real</span> <span class="special">=</span> <span class="keyword">typename</span> <span class="identifier">ArgumentContainer</span><span class="special">::</span><span class="identifier">value_type</span><span class="special">;</span>
<span class="identifier">ArgumentContainer</span> <span class="identifier">lower_bounds</span><span class="special">;</span>
<span class="identifier">ArgumentContainer</span> <span class="identifier">upper_bounds</span><span class="special">;</span>
<span class="identifier">size_t</span> <span class="identifier">max_function_calls</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span>
<span class="identifier">ArgumentContainer</span> <span class="keyword">const</span> <span class="special">*</span> <span class="identifier">initial_guess</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">;</span>
<span class="special">};</span>
<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">ArgumentContainer</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Func</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">URBG</span><span class="special">&gt;</span>
<span class="identifier">ArgumentContainer</span> <span class="identifier">random_search</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Func</span> <span class="identifier">cost_function</span><span class="special">,</span>
<span class="identifier">random_search_parameters</span><span class="special">&lt;</span><span class="identifier">ArgumentContainer</span><span class="special">&gt;</span> <span class="keyword">const</span> <span class="special">&amp;</span><span class="identifier">params</span><span class="special">,</span>
<span class="identifier">URBG</span> <span class="special">&amp;</span><span class="identifier">gen</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;</span> <span class="identifier">value_to_reach</span>
<span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;::</span><span class="identifier">quiet_NaN</span><span class="special">(),</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">bool</span><span class="special">&gt;</span> <span class="special">*</span><span class="identifier">cancellation</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">atomic</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;</span> <span class="special">*</span><span class="identifier">current_minimum_cost</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">ArgumentContainer</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;&gt;</span> <span class="special">*</span><span class="identifier">queries</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">);</span>
<span class="special">}</span> <span class="comment">// namespaces</span>
</pre>
<p>
The <code class="computeroutput"><span class="identifier">random_search</span></code> function
searches for a global minimum of a function. There is no special sauce to this
algorithm-it merely blasts function calls over threads. It's existence is justified
by the "No free lunch" theorem in optimization, which "establishes
that for any algorithm, any elevated performance over one class of problems
is offset by performance over another class." In practice, it is not clear
that the conditions of the NFL theorem holds, and on test cases, <code class="computeroutput"><span class="identifier">random_search</span></code> is slower and less accurate
than (say) differential evolution, jSO, and CMA-ES. However, it is often the
case that rapid convergence is not the goal: For example, we often want to
spend some time exploring the cost function surface before moving to a faster
converging algorithm. In addition, random search is embarrassingly parallel,
which allows us to avoid Amdahl's law-induced performance problems.
</p>
<h4>
<a name="math_toolkit.random_search.h1"></a>
<span class="phrase"><a name="math_toolkit.random_search.parameters"></a></span><a class="link" href="random_search.html#math_toolkit.random_search.parameters">Parameters</a>
</h4>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<code class="computeroutput"><span class="identifier">lower_bounds</span></code>: A container
representing the lower bounds of the optimization space along each dimension.
The <code class="computeroutput"><span class="special">.</span><span class="identifier">size</span><span class="special">()</span></code> of the bounds should return the dimension
of the problem.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">upper_bounds</span></code>: A container
representing the upper bounds of the optimization space along each dimension.
It should have the same size of <code class="computeroutput"><span class="identifier">lower_bounds</span></code>,
and each element should be &gt;= the corresponding element of <code class="computeroutput"><span class="identifier">lower_bounds</span></code>.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">max_function_calls</span></code>: Defaults
to 10000*threads.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">initial_guess</span></code>: An optional
guess for where we should start looking for solutions. This is provided
for consistency with other optimization functions-it's not particularly
useful for this function.
</li>
</ul></div>
<h4>
<a name="math_toolkit.random_search.h2"></a>
<span class="phrase"><a name="math_toolkit.random_search.the_function"></a></span><a class="link" href="random_search.html#math_toolkit.random_search.the_function">The
function</a>
</h4>
<pre class="programlisting"><span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">typename</span> <span class="identifier">ArgumentContainer</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">Func</span><span class="special">,</span> <span class="keyword">class</span> <span class="identifier">URBG</span><span class="special">&gt;</span>
<span class="identifier">ArgumentContainer</span> <span class="identifier">random_search</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">Func</span> <span class="identifier">cost_function</span><span class="special">,</span>
<span class="identifier">random_search_parameters</span><span class="special">&lt;</span><span class="identifier">ArgumentContainer</span><span class="special">&gt;</span> <span class="keyword">const</span> <span class="special">&amp;</span><span class="identifier">params</span><span class="special">,</span>
<span class="identifier">URBG</span> <span class="special">&amp;</span><span class="identifier">gen</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;</span> <span class="identifier">value_to_reach</span>
<span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">numeric_limits</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;::</span><span class="identifier">quiet_NaN</span><span class="special">(),</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">atomic</span><span class="special">&lt;</span><span class="keyword">bool</span><span class="special">&gt;</span> <span class="special">*</span><span class="identifier">cancellation</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">atomic</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;</span> <span class="special">*</span><span class="identifier">current_minimum_cost</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">,</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special">&lt;</span><span class="identifier">ArgumentContainer</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">invoke_result_t</span><span class="special">&lt;</span><span class="identifier">Func</span><span class="special">,</span> <span class="identifier">ArgumentContainer</span><span class="special">&gt;&gt;&gt;</span> <span class="special">*</span><span class="identifier">queries</span> <span class="special">=</span> <span class="keyword">nullptr</span><span class="special">)</span>
</pre>
<p>
Parameters:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<code class="computeroutput"><span class="identifier">cost_function</span></code>: The cost
function to be minimized.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">params</span></code>: The parameters
to the algorithm as described above.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">gen</span></code>: A uniform random bit
generator, like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">mt19937_64</span></code>.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">value_to_reach</span></code>: An optional
value that, if reached, stops the optimization. This is the most robust
way to terminate the calculation, but in most cases the optimal value of
the cost function is unknown. If it is, use it! Physical considerations
can often be used to find optimal values for cost functions.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">cancellation</span></code>: An optional
atomic boolean to allow the user to stop the computation and gracefully
return the best result found up to that point. N.B.: Cancellation is not
immediate; the in-progress generation finishes.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">current_minimum_cost</span></code>: An
optional atomic variable to store the current minimum cost during optimization.
This allows developers to (e.g.) plot the progress of the minimization
over time and in conjunction with the <code class="computeroutput"><span class="identifier">cancellation</span></code>
argument allow halting the computation when the progress stagnates.
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">queries</span></code>: An optional vector
to store intermediate results during optimization. This is useful for debugging
and perhaps volume rendering of the objective function after the calculation
is complete.
</li>
</ul></div>
<p>
Returns:
</p>
<p>
The <code class="computeroutput"><span class="identifier">ArgumentContainer</span></code> corresponding
to the minimum cost found by the optimization.
</p>
<h5>
<a name="math_toolkit.random_search.h3"></a>
<span class="phrase"><a name="math_toolkit.random_search.examples"></a></span><a class="link" href="random_search.html#math_toolkit.random_search.examples">Examples</a>
</h5>
<p>
An example exhibiting graceful cancellation and progress observability can
be studied in <a href="../../../example/random_search_example.cpp" target="_top">random_search_example.cpp</a>.
</p>
<h5>
<a name="math_toolkit.random_search.h4"></a>
<span class="phrase"><a name="math_toolkit.random_search.references"></a></span><a class="link" href="random_search.html#math_toolkit.random_search.references">References</a>
</h5>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
D. H. Wolpert and W. G. Macready, <span class="emphasis"><em>No free lunch theorems for
optimization.</em></span> IEEE Transactions on Evolutionary Computation,
vol. 1, no. 1, pp. 67-82, April 1997, doi: 10.1109/4235.585893.
</li></ul></div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
Walker and Xiaogang Zhang<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="jso.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../optimization.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="cma_es.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink