Meta-heuristics is a common name for a class of incomplete algorithms that can be used for solving COPs. Some well known meta-heuristics are Ant Colony Optimization , Genetic Algorithms (GA) and Simulated Annealing (SA), as well as others. It is important to note that currently there is no commonly accepted definition of what meta-heuristics are. One way to think of them is as high-level descriptions, or frameworks, for algorithms that can be applied to a variety of combinatorial optimization problems, where each particular problem requires the algorithm to be tailored to it.
Meta-heuristics are approximate, or incomplete, algorithms that try to combine basic heuristic methods in higher level frameworks aimed at efficiently and effectively exploring a search space. This means that meta-heuristics are descriptions of algorithms that need to be adapted so they can be applied to individual problems. All meta-heuristics rely on a balanced use of diversification and intensification, also known as exploration and exploitation. The term diversification refers to the exploration of the search space, while intensification refers to the use of acquired experience or knowledge. Finding a good balance between the two is important in order to quickly find feasible regions that give good solutions but not waste too much time exploring regions of the search space that do not produce good solutions. The details of the search strategy of each meta-heuristic largely depends on the idea behind that particular meta-heuristic.
Although meta-heuristics can be organized into categories in several ways, the most important is to distinguish between single point and population-based search classification. The first category contains algorithms that work on a single solution and includes meta-heuristics based on local search. These algorithms are known as trajectory methods and include Simulated Annealing, Tabu Search, Iterative Local Search and Variable Neighbourhood Search. The second category contains algorithms that perform search processes which describe the evolution of a number of points in the search space. Algorithms in this category include Evolutionary Computation (including Genetic Algorithms) and Ant Colony Optimization. The remainder of this section will examine in detail two members of the meta-heuristics family that will be used in this project, ACO and BOA .