Random Search Optimization

Learn to implement the random search optimization algorithm.

We'll cover the following

What is random search optimization?

Random search optimization is a brute-force algorithm that finds the x∗x^*optimum by generating and evaluating random inputs to the objective function. This algorithm doesn’t assume anything about the nature or structure of the objective function, i.e., it treats it as an opaque box. This makes it applicable to functions that are not continuous or differentiable.

Let’s consider an interview process to find a suitable candidate for a particular role without prescreening. Let’s say xx represents a candidate and g(x)g(x) measures the skill difference of candidate xx compared to the desired skills—the lower the difference, the better.

The random search algorithm will first sample NN random points (candidates in our case) xi∈[a,b]x_i \in [a , b] uniformly within a specified range (for example, having a college CGPA between 8 and 10) and then find the optimum x∗x^* (i.e., the best candidate) as the data point that minimizes the objective function g(x)g(x). In other words,

The figure given below illustrates how random search works. Random search optimization tries to find the best solution for a problem by randomly sampling points within a range and evaluating the objective function over them.

Press + to interact
Illustration of random search optimization
Illustration of random search optimization

Note: The time complexity of random search is O(N)O(N) because the algorithm evaluates the objective function over all NN data points to decide the optimal solution.

Implementing random search

Let’s consider a scenario where a company wants to find the optimal salary raise for their employees so that their overall investment is minimized and, at the same time, employees are satisfied and productive.

Providing a high salary raise can overshoot the budget and overall investment. Providing a low raise can lower the productivity of individual workers, compelling the organization to hire more and spend more than expected. The company hypothesizes that the relationship between salary raise xx (in %) and the overall investment yy (in million dollars) is given as y=g(x)=(x+2)(x−5)+15y = g(x) = (x+2)(x-5) + 15.

One way to come up with the function above is to use some data points that represent the possible outcomes of different salary raises and their corresponding investments. For example, the company could conduct a survey or an experiment to estimate how the productivity, turnover, and demand of the employees change with different salary raises. Then, they could use these data points to fit a quadratic function that best describes the trend of the data. 

Note: It is important to note that the values 2,−5,152, -5, 15 are not unique or optimal for the equation y=(x+2)∗(x−5)+15y=(x+2)*(x-5) + 15. There are many other possible values that could produce a different quadratic function that also model the relationship between salary raise and overall investment. The choice of these values depends on the accuracy, simplicity, and validity of the function that the company wants to use.

The code snippet given below implements the random search algorithm to optimize the function y=(x+2)(x−5)+15y = (x+2)(x-5) + 15 using N=1000N=1000. We can plug in different objective functions and play with the values of the parameters N,a,bN, a, b to understand the algorithm better.

Press + to interact
import numpy as np
import matplotlib.pyplot as plt
# objective function
def objective(x):
 return (x+2)*(x-5) + 15
 
a, b = -10.0, 10.0 # range of random points to be sampled
N = 1000
datapoints = a + np.random.rand(N) * (b-a) # generate 100 random points between [a,b]
outputs = objective(datapoints) # evaluate objective on random data points
index = np.argmin(outputs)
# summarize best solution
print('Best: f(%.5f) = %.5f' % (datapoints[index], outputs[index]))
# plot the curve for graphic visualization
plt.figure(figsize=(10,10))
plt.rcParams.update({'font.size': 22})
x = np.arange(-10, 10, 0.1)
plt.plot(x, objective(x), linewidth=2)
# plot the random datapoints sample
plt.axvline(x=datapoints[index], ls='--', color='red', label='optimum')
plt.axhline(y=0, ls='-', color='black')
plt.axvline(x=0, ls='-', color='black')
plt.legend()
plt.savefig('./output/plot.png')

  • Lines 1–2: We import the NumPy and Matplotlib Python libraries.

  • Lines 5–6: We define our objective() objective function that takes the input x and returns the value of the objective at that point.

  • Lines 8–9: We set the parameter a as −10-10, b as 1010, and N as 10001000.

  • Line 11: We sample N random datapoints uniformly between [a, b].

  • Lines 13–14: We evaluate the sampled datapoints to the objective function and pick the data point that returns the minimum value.

  • Lines 20–23: We plot and visualize the objective function over the Matplotlib canvas.

  • Lines 26–30: We plot and visualize the optimal data point over the graph of the objective function.

As can be seen in the illustration, the algorithm returns a value close to the actual optimal value, x∗=1.5x ^*= 1.5 , which minimizes the overall investment (approx. 2.752.75million dollars). In general, the random search algorithm is simple and easy to implement and works for noncontinuous and nondifferentiable functions.

However, the algorithm can be inefficient and slow to converge to the optimal solution because it employs a brute-force approach. It can also be sensitive to the number of data points NN and the range [a,b][a,b], which affects the balance between exploration and exploitation.

For example, if we choose a range of [a,b]=[2,10][a,b]= [2,10], the algorithm will return x=2.0x = 2.0 as the optimal value, which is very far from the actual optimum. Similarly, while choosing a small value of NN (let’s say 20), it might be possible that the no data point is sampled close to 1.5. Additionally, if we never sample 1.5, the algorithm won’t evaluate the objective at that point and return it as the optimal value.