2. General Concepts in Metaheuristic Search

Metaheuristics have become a very popular family of solution methods for optimization problems because they are capable of finding “acceptable” solutions in a “reasonable” amount of time. Most optimization problems in practice are too complex to be approached by exact methods that can guarantee finding global optimal solutions. The time required to find and verify globally optimal solutions is impractical in most applications. An entire computational theory, which we will not discussed here, has been developed around problem complexity. It suffices to say that it is now known that the great majority of the optimization problems found in practice fall within a category that makes them “computationally intractable.” Having accepted the reality that solution methods that yield verifiable globally optimal solutions are not practical, we must apply criteria derived from the problem context to determine what is an acceptable solution and what is reasonable amount of time. For instance, some timetabling problems (e.g., scheduling of courses at University) are notoriously difficult because they include many constraints. Therefore, an acceptable solution in this context could be one that violates the least number of constraints or one that improves a collective preference function value by a relatively small percentage over a solution found by a human scheduler.