Metaheuristics: Models, Design and Analysis

In recent years, there have been significant advances in the theory and application of meta-heuristics to the approximate solutions of complex optimization problems. A meta-heuristic is an iterative master process that guides and modifies the operations of subordinate heuristics to produce high-quality solutions efficiently. In this paper, we first present a brief introduction to combinatorial optimization and meta-heuristics. Second, the most common components and attributes of meta-heuristics are identified. A complete graph on the components/attributes is constructed to provide a new framework to classify meta-heuristics. The framework also invites investigators to diversify their over-intensified search to generate new hybrids with the hope of finding the optimal meta-heuristic. Third, the most successful hybrids are reviewed. Fourth, it is often said “my algorithm is better than yours“ using either the computational effort or the quality of solution but not both, among other criteria. A new way to compare meta-heuristics is introduced. It is based on the concept of marginal improvement per unit of computational effort (MIC) which takes into account both quality and time criteria to produce a ranking of compared approaches. Last, we shall conclude with some directions of future research