# Combinatorial Optimization Problems and Metaheuristics: Review, Challenges, Design, and Development
## 4 Results: Standardization, Methodology, and Framework for COP and Metaheuristics
### Metaheuristics General Specification
The types considered by this framework proposal (version 1) are the following:  
* Initialization--concerns to create the initial set of solutions;
* Selection--selects solution(s) according to some criteria;
* Navigation--responsible for performing the moves in the search space;
* Replacement--aims to make decisions of how to perform the replacement of a current set of solutions by a new set of solutions which is obtained in each iteration;
* Calculation--responsible for providing calculations to support decisions; and
* Termination--used to finalize the search process and return the best solution. The set of \"search role requests\" defined by \(\Delta=\{\delta_{1},\ \delta_{2},\ \ldots,\ \delta_{1n}\}\) can also been seen as \"placeholders\" that must be occupied by a subordinated heuristic. Since the SH may have variants, they can be replaced by an SH that performs a similar role. Additionally, an SH must belong to the demanded by \"search role requests\". Moreover, a \"role\" is a semantic function defined by a metaheuristic algorithm and it represents a vital aspect of its search metaphor. For example, a Genetic Algorithm requires an SH that will perform the \"mutation role\" that belongs to the type \"navigation\" SH. **Definition 16**. : _Therefore, a \"search role request\" \(\delta\) is defined in the following way:_  
\[\Delta=\{\delta_{1},\ \delta_{2},\ \ldots,\ \delta_{1n}\},\ \ \forall\ \delta\in\Delta\,\ \delta=(\Theta,\gamma\ ) \tag{16}\]  
_where:_  
* \(\Theta\) _represents a search role requested by the metaheuristic cycle; and_
* \(\gamma\) _defines the type of subordinated heuristic required._  
**Definition 17**. : _The \(\gamma\) is defined by the framework as \(\Gamma\), a finite set of SH types \(\Gamma\). Thus, it is defined in the following way:_  
\[\Gamma=\{\text{initialization, selection, navigation, replacement, calculation, termination}\} \tag{17}\]In this context, a subordinated heuristic is a self-contained piece of software that performs a determined function. Consequently, an SH must work by receiving inputs and returning a result in a defined format, independently of who is calling it. Therefore, SH must follow an API definition and each type must specify the same signature. It is the base feature to enable the SH exchange. Moreover, SHs also must have metadata to inform their behaviors, classifying their abilities. For example, to inform solution encoding that the SH knows how to manipulate. Additionally, the metadata is essential to register the SH in a pool (it also applies to MH metadata). It is crucial to support the replacement of SH during the search process and enable the \"search process manager\" to replace SH properly because it knows their behaviors and can select an equivalent. **Definition 18**. : _Therefore, a subordinated heuristic is expressed as:_  
\[H=\{h_{1},\ h_{2},\ \ldots,\ h_{n}\},\forall\ h\in H\,,h=(\sigma,\gamma,\ a\ ) \tag{18}\]  
_where:_  
* \(h\) _is an_ \(SH\) _of a set of all_ \(SH\) _implemented in the framework_ \(H=\{h_{1},\ h_{2},\ \ldots,\ h_{n}\}\)_;_
* \(\sigma\) _represents the metadata that describe some aspects of_ \(SH\) _behaviors; and_
* \(\gamma\) _defines the type of subordinated heuristic; and_
* _a symbolizes the algorithm implementation, the SH itself._  
**Definition 19**. : _A parameter \(k\) is stated in the following way:_  
\[\mathrm{K}=\{k_{1},\ k_{2},\ \ldots,\ k_{n}\},\forall\ k\in\mathrm{K}\,,\ k=(c, \mathrm{t}\ ) \tag{19}\]  
_where:_  
* \(k\) _is a parameter of a set defined by the metaheuristic_ \(K=\{k_{1},\ k_{2},\ \ldots,\ k_{n}\}\)_;_
* \(c\) _defines the parameter name; and_
* \(t\) _is the parameter data type._  
Again, as defined in the problem, there is no metaheuristic superclass that subclasses can follow or extend. In fact, for each metaheuristic algorithm, there must exist only one class that receives a specification that determines its behavior. This class in design time is abstract and only implements the higher-level cycle.