Exhaustive Enumeration


Exhaustive Enumeration is a method for finite search spaces

It enumerates all possible solutions.

It will definitely find the global optimum $x$.

Usually it has exponential complexity: the number of possible solutions usually rises exponentially with input size

If lower bound $y$ for objective values is known, we can maybe stop earlier: If an element $x$ with $f(x) = y$ is discovered, it is the global optimum and we can stop

In general, however, this method is not feasible because it takes too long


$$f \gets \text{the objective/fitness function}$$ $$y \gets \text{the lowest possible objective value, −∞ if unknown}$$ $$x \gets \text{the current candidate solution}$$ $$\textit{Best} \gets \text{the best individual ever discovered}$$


Thomas Weise - Metaheuristic Optimization

Pseudo Code
\caption{EE Algorithm}
                \STATE $\textit{Best} \gets Null$
                \WHILE{not all solutions checked or $f(\textit{Best})>y$}
                    \STATE $x \gets \text{next candidate solution}$
                    \IF{$f(\textit{Best}) > f(x)$ or $\textit{Best} == Null$}
                        \STATE $\textit{Best} \gets x$
                \RETURN $\textit{Best}$