Comparison of Four Randomized Optimization Methods

This post compares the performance of 4 different randomized optimization (RO) methods in the context of problems designed to highlight their strengths and weaknesses.

Randomized Optimization Methods

The four RO methods explored were:

• Random Hill Climbing - a standard hill climbing approach where optima are found by exploring a solution space and moving in the direction of increased fitness on each iteration.

• Simulated Annealing - a variant on random hill climbing that focuses more on the exploration of a solution space, by randomly choosing sub-optimal next-steps with some probability. This increases the likelihood of finding global optima instead of getting stuck in local optima.

• Genetic Algorithms - a subset of evolutionary algorithms that produce new generations based on fitness of prior generations.

• MIMIC - An RO approach created by professor Isbel of Georgia Tech, that attempts to exploit the underlying “structure” of a problem to eliminate re-exploration of sub-optimal portions of the solution space on future iterations.

Problem Contexts

The 3 problems I chose, which highlight the strengths and weaknesses of these algorithms, were:

• count ones - a simple problem with a single global optima with large basin of attraction. SA and RHC should excel here, since their evaluation functions are inexpensive to compute and there are no local optima in which to get stuck.

• four peaks - A problem with two local optima with wide basins of attraction designed to catch simulated annealing and random hill climbing, and two sharp global optima at the edges of the problem space. Genetic Algorithms are more likely to find these global optima than other methods.

• knapsack - a classic NP-Hard optimization problem with no polynomial time solution. The strength of MIMIC was highlighted in this context, as it exploited the underlying structure of the problem space that was learned from previous iterations.

The implementations of these algorithms and problem scenarios were pulled from the ABIGAIL library, which is maintained by Pushkar Kohle of Georgia Tech.

Analysis

Click here for the full paper with more detail and analysis, or view it below.