Exhaustive Enumeration

Description

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

Definitions

$$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}$$

References

Thomas Weise - Metaheuristic Optimization

Pseudo Code
\begin{algorithm}
\caption{EE Algorithm}
\begin{algorithmic}
                \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$
                    \ENDIF
                \ENDWHILE
                \RETURN $\textit{Best}$
\end{algorithmic}
\end{algorithm}