Optimization Methods: Random Search

What is random search?

Random search is a simple and straightforward optimization algorithm that involves randomly generating potential solutions to a problem and evaluating their performance. It is a widely used optimization method in machine learning, engineering, and other fields where optimization problems arise.

In random search, the optimization process begins by defining a search space, which is the set of all possible solutions to the problem. The search space can be continuous, discrete, or a combination of both. Random search then randomly generates a set of candidate solutions from the search space. The number of candidate solutions and the range of values for each solution can be set by the user.

Each candidate solution is then evaluated using an objective function that measures how well the solution performs on the problem at hand. The objective function can be a simple performance metric or a more complex measure that takes multiple factors into account.

After evaluating all the candidate solutions, random search selects the solution with the best objective function value as the current best solution. This best solution is then used as the starting point for the next iteration of random search.

The optimization process continues for a predetermined number of iterations or until a stopping criterion is met. The stopping criterion can be based on the number of iterations, the improvement in the objective function value, or other factors.

Explaining random search

Let’s look at an example. In the following image, we are at point A and want to move ahead to point B.

Now, for this journey, there are different paths that we can take. For example:

• We can take a straight path (path 1) from point A to point B.

• We can move along the grid squares (path 2) to move from point A to point B.

• We can take any random path (path 3) from point A to point B.

In all these paths, from point A to point B, the best path is one with the shortest time. To find that path, we can go with either of the two approaches:

• Approach A: We find all the paths, calculate all the travel times, and find the smallest path.

• Approach B: We find paths on the basis of the grid where we select some points in the journey, go along all the grid-based paths, and calculate the value of travel time for each path.

These are two approaches and we might think of going for the first one. Well, that’s fine. However, if we go with approach A, it soon becomes impractical. As the number of cases increases, it is impossible to find all the cases and solve them all. The entire process is so computationally expensive that the overall benefit is lost.

The second approach where we formulate a grid for the paths seems feasible and it is generally adopted in most optimizations. However, there is a common problem with this. The selection of the parameters for the grid could be tricky and could alter the overall performance of the search space. Another thing is that we might be looking in various grid settings and the optimal path might remain in some other grid level. So in all those cases, we would consume power to select the grid and then find the solution for each of the components of the grid individually. However, this whole process is not very feasible.

So, what happens next? We modify the two approaches and combine them:

1. We define a space and select a random number of paths from point A to point B.

2. We then calculate the time for all these paths and check the best time.

3. We keep this solution as our current best solution.

4. Now, we run the algorithm again and check for other random samples of paths.

For this new sample of paths, we repeat this process again and again until we find the optimal or near-optimal solution. This process is what random search in its essence is. The algorithm is further explained in detail in the next section.

Random search algorithm

The algorithm can be summarized using the following mathematical principles:

• Search space: We define a search space $S$ that includes all possible solutions to the problem.

• Objective function: We define an objective ...