1 Introduction

It has been seen for sorting problems, depending on the length and order of the sequence, there are algorithms that perform better than the rest [1]. Also, for NP-hard combinatorial optimization problems, the deterministic algorithms are considered adequate for smaller instances of such problems [2]. Intuition says that the difficulty of a problem instance varies with its size: large instances are usually more difficult to solve than smaller ones. However, in practice, recognizing the measuring difficulty only in terms of the instance size implies overlooking any structural property or feature of the instance, which could affect the problem complexity [3] and the algorithm performance. For example, classification problems show that some learning algorithms perform very well on certain problem instances depending on a set of specific features [4]. The scientific community of different disciplines, such as combinatorial optimization, machine learning, artificial intelligence and other fields of knowledge has worked for describing and analyzing the experimental relation between problem-algorithm, with the objective of solving a real problem optimally. However, its analysis has been conducted, in most cases, in descriptive and predictive understanding levels (for a major compression of this concept [5]) and it is necessary deepening more in this objective, in the explanatory understanding level, answering why the relation of certain problem instances and an algorithm produces best solutions (algorithm is very good) and why it is not good with other problem instances. Under the scope of this research (combinatorial optimization area and search algorithms), this paper contains: previous questions and formulations of reviewed literature, so too, the phenomenon is formulated as a question and a formal problem statement in the explanatory level, using and supplementing the Rice's formal nomenclature (Sect. 2); a proposed composite function to solve the stated problem (Sect. 3); a framework for the performance of the proposed composite function over the One Dimension Bin-Packing problem and Tabu Search algorithm (Sect. 4); Development of the proposed composite function, using a instances set P (Sect. 5), the discovered knowledge is used for answering how and why certain problem instances (describing structure and problem solutions space), algorithms features (describing operative and searching behavior); and the algorithm logical design contribute toward a better relation between problem-algorithm (in majority cases of reviewed literature, not all information are taken into account at the same time, problem, algorithm, logical area). A new self-adaptive search algorithm is designed for each case of study. Section 6 describes the results of self-adaptive search algorithms over instances sets P and P’ (P’ ≠ P)). Conclusions and future works are drawn in Sect. 7.

2 Reviewing State of Art and Setting the Problem Statement

Using and supplementing the Rice’s formal Nomenclature,

P = {x1, x2,…, xm} a set of problem instances or space for analysis.

F = the problem features space generated by a description process applied to P.

A = {a1, a2,…, an} a set of algorithms.

Y = the performance space, it represents the mapping of each algorithm to a set to a set of performance metrics.

C = {C1, C2,…,Cn} a partition of P, where |A|=|C|.

\({\varvec{W}} = \{ \left. {(a_{q} \in {\varvec{A}},C_{q} \in {\varvec{C}})} \right|Y_{aq,x} > Y_{\alpha ,x} \cdot \forall \cdot \alpha \in (A - \{ a_{q} \} ),\forall \cdot x \in C_{q} \}\) is a set of ordered pairs (aq, Cq), where each dominant algorithm aq ∈ A is associated with one element Cq of partition C, because this gives the best solution to partition Cq, considering a set of performance metrics mapped in set Y.

L = the algorithm features space.

In descriptive traditional level, the next first research question arises from experimental relation between problem-algorithm:

  1. 1.

    What is the performance of algorithm aq ∈ A to solve the problem P?

For this, a set of algorithms A is run over a set of instances P. The general performance of each algorithm is measured by some performance metric y ∈ Y in order to obtain a quantifiable value that could be used for performing a comparison of algorithms by means statistical analysis (statistical tests The Sign, Wilcoxon and Friedman tests, among others) or tabular analysis or graphical analysis; after that performing a results interpretation. One classic example of related work in this understanding level is [6]. Nevertheless, the results of the solution algorithms on an instance set of a problem could be incorrectly interpreted, this is, one might expect that there are pairs of search algorithms aq and α such that aq performs better than α on average, even if outperforms aq at times. Such expectation could be incorrect. Wolpert describes two No Free Lunch (NFL) theorems in [7]. In general terms, it establishes that for any algorithm, a high performance over a set of problems is paid in performance over another set. The existence of instances subsets for specific problem and an algorithm for each subset is suggested by NFL theorems. For the purpose of exemplification in the reviewed literature, other classic examples of related works identified different performances of algorithms on different problem instance sets, based on the construction of an association table, where each set had one or several similar features in the context of the problem structure description [8, 9]. A few of other related works are [1, 2, 4, 10, 11]. The above indicates that one algorithm can be associated to a problem instances subset, where it is the one that solves these instances in the best way possible, for a specific problem domain. The phenomenon observed could be described by means of some set W that includes pairs in the form (aq, Cq), where instances subset Cq better correspond to aq for instances set P for a specific problem (see nomenclature for a major description).

In predictive level, a general research question arises:

  1. 2.

    What is the best way to learn W (pairs (aq, Cq)) in order to predict algorithm aq that will give the best solution for a new instance from a problem?

The above question needs to consider information from the experimental relation between problem-algorithm, which is significant and has a predictive value. If this question is answered, the solution to the algorithm selection problem can be found. The algorithm selection problem (ASP) is originally formulated in [12], which is stated as:

For a given problem instance x ∈ P, with features f(x) ∈ F, find the selection mapping S(f(x)) into algorithm space A, such that the selected algorithm maximizes the performance mapping .

It can be said that the phenomenon mentioned in this paper, can be analyzed and learned in the predictive understanding level of an implicitly manner when problem ASP is being solved. ASP was generalized through different research disciplines in [13], where its solution is important. Two known approaches that are utilized by related works in solving problem ASP are algorithm portfolio and supervised learning. In the case of algorithm portfolio, the algorithm performance is characterized and adjusted to a model (model-based portfolio) either by a regression model [14] or a probability distribution model [15, 16]; other related works have also shown that some problem features are considered in the building of a model (feature-based portfolio), for example, applying supervised learning [17, 18]. In this case, many related works exhibit learning patterns (corresponding to set W in the context of this paper) from data by means of a supervised algorithm and use them for predicting the best algorithm for an unseen problem instance. Examples: Case-base reasoning [19, 20], decision trees [21, 22], Neural Networks [23] and Random Forest [24,25,26]. A discussion of machine learning methods applied to ASP problem can be found in [27]. Nevertheless, the principal disadvantage is that the phenomenon identified in the predictive understanding level is analyzed and studied without being fully understood. Two principal reasons: the information considered in analyses is only derived from a problem, or an algorithm, or a logical design (initializing parameter); and the built models are found to be difficult in interpreting the acquired knowledge by nature of its own structure; these are used for predictions.

In the explanatory understanding level, there are different guidelines. For example, some related works focused their analysis on problem difficulty, considering the problem structure, significant features or parameters, identifying important values from them to determine when problem is difficult and when is easy (known as Transition Phase Analysis) through the use of graphical or statistical analysis or unsupervised learning [23,24,25, 28, 29]. Other related works focused on algorithm performance, some deeply on the searching behavior, considering metrics that measures the trajectory, identifying when it is flat or rugged (there are fluctuations), determining whether the problem is difficult or easy for algorithm (Known as Landscape Analysis) [30,31,32]; others deeply focused on algorithm logical design [33, 34]; some focused on both [30, 35], for example, obtain important explanations which permit to configure the algorithm in a way that it can produce the better results. However, these explanations are not very clear, in the regard which kind of problem instances will produce better results. What are the specific features of the problem structure that help the configured algorithm better adjust to these problem instances? In [36], this information is considered important in order to adapt the algorithm logical design to the problem structure. A few related works focused on problem and algorithm [37,38,39,40], developing some visual tool or performing a graphical, or statistical, or data exploratory, or causal analysis. The reviewing of this literature indicates much effort has been taken to characterize and analyze the experimental relation of problem-algorithm under different understanding levels. However, we believe that it is necessary to pave the way in the comprehension of explanatory understanding level with a starting point, something very essential, simple, and important. Therefore, considering past efforts of the reviewed literature, the experience for previous works [41, 42], and continuing with observed in descriptive and predictive understanding levels, a simple research question arises for a domain specific:

  1. 3.

    Why does a problem instance subset Cq correspond better to an algorithm aq than other instances in a specific problem domain?

In order to formulate this question as a formal problem, should be considered: as first instance, all significant information from problem (structure, solutions space) and algorithm (operative and searching behaviour), during and after execution, limitations of explanatory and predictive levels; as second instance, a methodology as guide to help obtain a formal model that can discover latent knowledge and explain the phenomenon in question for a specific problem. Following a step beyond to algorithm selection problem (ASP), considering the above, and continuing in the improving of previous works, the phenomenon could be formulated as the next statement.

For a set of algorithms A applied to a set of problem instances P, with problem features F, algorithm features L, the algorithms performance space Y, the algorithms performance partitions W, according to Y and an ordered pair (aq, Cq) ∈ W; find the composite function E(aq, P, A, F, L, Y) that discovers an explanation formal model M, such that M, represents the latent knowledge from relations between features that describe: the problem features F; interest algorithm L; and provides solid foundations to explain, why certain problem instances, being the partition Cq correspond better to interest algorithm aq, according to performance space Y, and why other partitions (Cq)c do not correspond to algorithm aq.

3 Proposed Solution

The solution to the above problem statement, is to discover a formal model that can acquire latent knowledge, structured in some way as cause-effect relations from problem, algorithm features, which can help explain such formulation. The process is known as the discovery of causal structure of data [43] (causal model). A causal model can be defined as a causal Bayesian network [43]. It is described by expression 1.

$$ M = \, \left( {V,G,Z} \right) $$
(1)

Specifically,

  • V = {v1, v2,..,vn} is a set of observed features.

  • G is a directed acyclic graph with nodes corresponding to the elements of V that represents a causal structure (V, EC); i.e.,

    EC = {EC1, EC2,…, ECn}, where each ECi ∈ EC is a set of ordered pairs,

    ECi = {(vi, y1), (vi, y2), …, (vi, yn)},it is

    ECi = {(vi ∈ V, yk ∈ V)|vi ≠ yk, yk is a direct cause of vi relative to V and there is a directed edge from yk to vi in G}

    Pa(vi) = {yk ∈ V | (vi, yk) ∈ ECi} is a set of all direct causes of vi.

  • Z = P(vi = j | y1 = α, y2 = β, ..., yp = γ), is a function of conditional probability of vi in the range of values j given the direct causes of vi {y1, y2,…,yp} ∈ Pa(vi), which are in the ranges of values y1 = α, y2 = β,…, yp = γ.

3.1 Composite Function E

In general terms, the composite function E (see Fig. 1) consists of analyzing the experimental relation between the problem (instances set P) – algorithm (interest algorithm aq, aq ∈ A) considering the space of features from problem F, the space of features L and performance Y from algorithms during execution, for discovering latent knowledge about this relation (represented by explanation model M).

Fig. 1.
figure 1

General diagram of the composite function

Full size image

The domain of proposed composite function E (Expression 2), are parameters: the interest algorithm aq, a set of algorithms A, applied to a set of problem instances P, the set F obtained by f (P), the set L obtained by l(A), the performance space Y, obtained by y(A). The functions f and l perform a description process, before and during execution of algorithms, to obtain features that represent information about set P and A.

$$ \left( {{\varvec{E}} \cdot fz \cdot fg \cdot fv \cdot fd \cdot fc} \right)\left( {a_{q} ,P,A,F,L,Y} \right) \equiv E\left( {fz\left( {fg\left( {fv\left( {fd\left( {fc\left( {a_{q} ,P,A,F,L,Y} \right)} \right)} \right)} \right)} \right)} \right) $$
(2)

The function y evaluates the algorithms A, by means a set of performance metrics. The acquisition of latent knowledge from experimental relation between problem-algorithm is formalized by means of the proposed composite function E, which, evaluated in each iteration, obtains the values of a set of significant features, causal relations between these, and estimations, represented by the sets V, G, Z (codomain-causal model M).

4 Framework for Proposed Composite Function E

The instance sets P and P’ (P ≠ P’) were randomly selected (324) from Beasley’s OR-Library [44], the Operational Research Library [45]. The objective of each case of study is to explain the description process and the composite function of the latent relation between problem (One Dimension Bin-Packing - BPP) and algorithm (Tabu Search); an insight into the problem structure, problem solution space, the algorithm logical design, its operative behaviour, and behaviour during its searching and performance. Due to the above, four versions of Tabu Search algorithm were implemented, where each one had a specific logical design (Table 1). The methodology for initializing control parameter (PM) is applied to size of Tabu list (nLTabu). The static procedure is to set it as 7 [46]. The dynamic procedure is to set it as \(\sqrt{n}\), where n represents the number of the objects or items of the problem instance. The methodology for the generation of an initial solution (IM) can be conducted by a random or deterministic procedure. The methodology for building the neighbourhood of a solution (NM) can achieved through one or several methods, which were proposed in [47]. The candidate list (LCANDI) size was fixed to 4*(nLTabu * 0.25) for all the study cases. As well as, the methodology to stop the algorithm execution (SM) was the same; after 4000 iterations or there was no improvement in the solution. Table 2 shows the study cases.

Table 1. Set of algorithms A
Full size table
Table 2. Cases of study
Full size table

5 Performing Composite Function E

The function f(P) performs description process for the instances set P, where the set F is obtained. After that, the set of algorithms A(a1, a2, a3, a4) is applied to solve the problem instances set P. During the search and solution process, the functions l(A) and y(A) perform description process to obtain the algorithm features space, set L and set performance space Y. This process (f(P), l(A), y(A)), for all cases of study, is described in greater detail only for those features that were significant in next sections.

5.1 Problem Instances Structure Description: Function f(P)

There are three features, (b, d) [21] and cu proposed in this paper; b describes the proportion of the total weights of the objects that can be assigned to one container; d describes the dispersion of the quotient between the object weight and the container capacity; cu is the kurtosis of object weights (w weights and de standard deviation).

$$ cu = \frac{{\sum\nolimits_{i = 1}^{n} {\left( {w_{i} - \overline{w}} \right)^{2} } }}{{de^{4} }} $$
(3)

The problem solution space for each instance, os, is described in past works [38, 41, 42]. It is the variability of ms randomly generated solutions (ms = 100 produced better results). The codomain of function f is the set F (expression 4), where rows represent the problem instances and columns are the values of these features.

$$F=\left\{\left\{{b}_{1},{d}_{1},{cu}_{1},{os}_{1}\right\},\left\{{b}_{2},{d}_{2},{cu}_{2},{os}_{2}\right\},\dots ,\left\{{b}_{m},{d}_{m},{cu}_{m},{os}_{m}\right\}\right\}$$
(4)

5.2 Algorithm Behavior Description: Function l(A)

The algorithm operative behaviour is described by features (nn, fn, vf), proposed in past works [38, 41, 42]. The number of neighbours built by algorithm during its search process per instance is given by nn. The number and variability of feasible solutions are given by fn, vf. The algorithm searching behaviour is described by features pn (number of inflection points), vn (number of valleys), vs (size of valleys) proposed in past works [38, 41, 42] and vd proposed in this paper. These features are obtained from the algorithm searching path. The searching inflections are the changes in the direction of fitness function from two consecutive solutions during one algorithm run; pn is the average of these for all algorithm runs (16); vn is concerned if there exists a searching pattern that refers to our concept, Valley. It is considered when there is a sequence major to sm solutions, where their fitness function values keep on decreasing (sm = 6 indicated be significant in past works). Then, the feature vn is the average of Valleys identified from algorithm runs. The inflection point located in an identified Valley is considered as the location point, for example one run has location points p1, p2, p3 and p4; the distance between each point is calculated, dd1, dd2 and dd3. The standard deviation of these is calculated (expression 5). The average of Valleys dispersion for all algorithm runs is calculated, vd. The set L is built with the specific order as Expression, 6. Here, L1,1 means algorithm a1 for problem instance x1 has the elements, nn11, fn11, vf11, pn11, vn11, vs11, vd11 (algorithm behaviour features) and so on.

$$ vd_{run} = \sqrt {\frac{{\sum\nolimits_{i = 1}^{pn - 1} {\left( {dd_{i} - \overline{dd} } \right)^{2} } }}{pn - 2}} $$
(5)
$$L=\left\{\begin{array}{c}\left\{{nn}_{11},{vf}_{11},{pn}_{11},{vn}_{11},{vs}_{11},{vd}_{11}\right\},\dots ,\left\{{nn}_{1m},\dots ,{vd}_{1m}\right\}\\ \left\{{nn}_{21},{vf}_{21},{pn}_{21},{vn}_{21},{vs}_{21},{vd}_{21}\right\},\dots ,\left\{{nn}_{2m},\dots ,{vd}_{2m}\right\}\\ \left\{{nn}_{n1},{vf}_{n1},{pn}_{n1},{vn}_{n1},{vs}_{n1},{vd}_{n1}\right\},\dots ,\left\{{nn}_{nm},\dots ,{vd}_{nm}\right\}\end{array}\right\}$$
(6)

5.3 Performance Space Description: Function Y(A)

The function, y, evaluates the algorithm performance according to metrics time and quality. The metric time is the total of feasible and infeasible solutions built during algorithm execution. The metric quality is the ratio between found solution and theoretical solution [41, 42]. The codomain of the function, y, is the set, Y (performance space) which is built with the specific order as Expression 7. Here, Y1,1 means algorithm a1 for problem instance x1 has the elements, quality11 and time11, Y1,m means algorithm a1 for problem instance xm has the elements quality; time, and so on.

$$Y=\left\{\begin{array}{c}\left\{{quality}_{11},{time}_{11}\right\},\dots ,\left\{{quality}_{1m},{time}_{1m}\right\}\\ \left\{{quality}_{21},{time}_{21}\right\},\dots ,\left\{{quality}_{2m},{time}_{2m}\right\}\\ \left\{{quality}_{n1},{time}_{n1}\right\},\dots ,\left\{{quality}_{nm},{time}_{nm}\right\}\end{array}\right\}$$
(7)

5.4 Discovering Knowledge: Functions fc, fd (TC), fv(D), fz(G)

The proposed composite function, E, is applied to one algorithm of interest aq for each case of study (1, 2, 3). The algorithms, a2, a3, a1 were randomly selected. The function, fc identifies the set W, considering performance space Y (based on time and quality metrics). After that, the performance scope of interest algorithm aq is obtained, considering set W. The codomain of function fc is described by set S. Each value indicates the scope of interest algorithm for each problem instance (set P), 1 was the best, 0 otherwise. For example, S = {0, 1,…,1} means that interest algorithm had scope: 0 for instance 1, 1 for instance 2, 1 for instance m and so on. A sets family SF = {F, L, Y, S} is built for interest algorithm aq and is represented by dataset TC, where TC =  ∪ SF; the tuples are instances and columns are features that describe: the structure and problem solutions space F = f(P); the operative and searching behaviours of interest algorithm, obtained from set L; performance space of the interest algorithm, obtained from set Y (time and quality); performance scope from set W, value from set S. The function, fd, first normalizes the values of each by means of method min-max; values that lie within the closed interval, [0, 1]. After that, the method, MDL [48], is performed to discretize the values. The codomain of function fd is the discretized dataset, D. The function, fv, performs general, graphical and variance analyses of the features from dataset D for selecting the most significant. The general analysis creates bar plots, where the frequencies of the values of the features are analysed with respect to the scope (value s) of aq. The metric quality from dataset TC did not assume a normal distribution; therefore, for the graphical and variance analyses, it was transformed using methods of logarithm or Box-Cox, using values 2 or −2 for λ. The graphical analysis creates box plots for each feature (identified in general analysis) with respect to metric quality, in order to identify features that in influence it in terms of variation and locality. Finally, the function, fv, performs an analysis one variance (ANOVA), with a confidence level of 95% for each feature (identified in graphical analysis) with respect to the quality metric. The function, fv, did not find significant features in the study case 3; for other cases of study, 1 and 2, the codomain of function fv is the significant dataset V1 with proposed features. For example, in case study 1, the dataset, V1, is formed by features b, os, nn, vf, pn, vn, vs, and scope of interest algorithm a2 (S). So too, with the objective of considering metrics known and used by the scientific community (describing the algorithm searching behaviour), the auto-correlation coefficient, (ca), the auto-correlation length, (al) ([49]), and highlight the utility of our proposed features (pn, vn and vs), another dataset, V2, is built with features b, os, nn, vf, metrics ac, al, and scope of interest algorithm a2 (S). The datasets V1 (by means function fv) and V2 are built in case of studies 1 and 2. The function fg performs the process of learning a causal structure (algorithm PC [43]) with a confidence level of 95% for datasets V1 and V2 in case studies; the causal inference software, HUGIN (Hugin Expert, www.hugin.com) was used.

Figure 2 shows the causal structures: a) fg → G1 and b) fg → G2 from datasets V1 and V2 for these cases of study. It is important to emphasize that the causal structure, G1, in these cases represents clearly the direct causes (problem and algorithm significant features) of performance scope for interest algorithm aq in performance space Y, in terms of set W. For case study 1, it is evident that the causal structure, G2, did not yield relevant information about direct causes. In case study 2, G2 did not yield relevant information about direct causes for algorithm performance scope with respect to algorithm behavior during its searching. These structures (G1) were considered for the next analyses. Also, Fig. 2 shows the intervals of direct causes, obtained previously by function fd. Continuing with the composite function, E, the function, fz, referring to parameter learning algorithm Counting [43], estimates the intensity of causal relations (identified in structures G1), see Table 3, the codomain is set Z. The codomain of composite function E for each study case are the sets V1, G1 and Z (causal model M). The problem instance set, P’, was used as an input for each causal structure G1 to obtain the prediction accuracy percentage, using another causal inference software NETICA (Norsys Corporation), where the obtained percentages were %78.04 and %70.37, respectively.

Fig. 2.
figure 2

Discovering knowledge

Full size image
Table 3. Significant features, casual relations and estimations
Full size table

5.5 Analyzing Acquired Knowledge and Self-adapting Algorithms

The results from case studies 1 and 2 are reviewed deeply in Fig. 3 (Analysis 1 and 2). So too, the logical design of the new Tabu Search Self-Adapting Algorithms is shown. On the other hand, another interesting result was obtained in case study 3, where the Tabu Search algorithm was distinguished by methodology in order to generate the initial solution. Though the function, fv, of composite function E could not discover significant features to build a causal explanation model, it is important to highlight the fact that a knowledge was obtained as well. One possible interpretation of this result may be that the method used to generate the initial solution does not impact the algorithm performance, according to set Y, in solving problem instances. One similar result was observed in [31] for another optimization problem and Tabu Search algorithm.

Fig. 3.
figure 3

Analysis of case studies 1, 2 and Tabu Search Self-Adaptive Algorithms

Full size image

6 Results Analysis

In the reviewed literature, there was no related work with the same circumstances for comparing performance of individual results. An example of this can be an improved Tabu Search algorithm for BPP. Therefore, the performance for the self-adaptive algorithms (aa1, aa2) was compared against that of the original analyzed algorithms (a2, a3), it is to say aa1−a2, aa2−a3. The comparative analysis of performance results from the algorithms was performed in two consecutive phases of analysis. The first analysis phase consisted on determining the total scope of new self-adaptive algorithms aa1 (287) aa2 (301); thereafter determining their total scope percentage, example 287/324 = 89% for aa1, aa2 (93%). Analysing the partitions \({C}_{{a}_{a1}}\) and \({C}_{{a}_{a2}}\) in more detail, aa1 wins 159 and aa2 wins 163 instances in quality, 128 and 138 in time, where the quality is the same for both algorithms (see Fig. 4).

Fig. 4.
figure 4

Times of analyzed algorithm and self-adaptive algorithm (same quality)

Full size image

The time differences are too big, it is not necessary to apply a statistical test. The self-adaptive algorithms finishing faster than the interest algorithm (aq) analyzed in study cases. Due the above, the objective of second analysis phase is to verify the values of quality metric, specifically when self-adaptive algorithm has the best quality (159-case 1, 163-case 2). In this sense, for study cases 1 and 2, aa1 had best time in 80 out of 159 problem instances and aa2 had best time in 95 out of 163 problem instances.

Fig. 5.
figure 5

Times of analyzed algorithm and self-adaptive algorithm (best quality)

Full size image

Figure 5 shows these times. The metric values time for each one of algorithms do not assume a normal distribution. Thus, a nonparametric statistical test of two dependent samples is applied (the two sample two-side wilcoxon signed rank test) for significance levels 95% and 99%. The Dataplot statistical software (www.itl.nist.gov) was used for this test. The test statistic was 7.67 and 8.46 for study cases. The null hypothesis (equal means) is rejected (critical values 1.96, 2.57) and it means that there is a significant difference between times. The self-adaptive algorithms (µ2) finishing faster than the original algorithm (µ1) analyzed in study cases. Continuing with the analysis, it is necessary to verify if there is a statistically significant difference between the means of metric quality. The values of this metric do not assume a normal distribution. Thus, the same statistical test for significance levels was applied (test statistic 10.15 and 9.92). The null hypothesis is rejected, there is a significant difference in terms quality.

6.1 Other Results

The analysed original algorithm and self-adaptive algorithm from cases of study 1 and 2, were executed over set P’ (P’ ≠ P). The self-adaptive algorithms had better quality or time in 166 and 156 problem instances of set P’ than analysed interest algorithm, respectively. Figure 6 shows the time of algorithms when they have the same quality. The same wilcoxon statistical test was applied to time differences. The test statistic was 9.27 and 8.37 for both cases. The null hypothesis is rejected for significance levels 95% and 99% (critical values 1.96, 2.57). The self-adaptive algorithms finishing faster than the analysed interest algorithm. Also, Fig. 7 shows the times when self-adaptive algorithm has less quality than analysed interest algorithm. The quality difference average was 0.025 (very small) for 158 problem instances out of 324 and the self-adaptive algorithms finishing faster than the interest algorithm in most cases over set P’.

Fig. 6.
figure 6

Same quality of both algorithms and best times of self-adaptive algorithm

Full size image
Fig. 7.
figure 7

Less quality and best times of self-adaptive algorithm

Full size image

7 Conclusions

Most of the literature consulted from combinatorial optimization area has been focusing only on problem information or algorithm information or, rarely, on both in order to describe the experimental relation between problem-algorithm. Furthermore, in the analysis of this relation, has been identified in the descriptive understanding level that certain problem instances correspond better to a certain algorithm than other. This phenomenon has been analyzed and learned implicitly in the predictive understanding level (algorithm selection problem). However, it has not been understood at all for a specific problem. This paper goes beyond the predictive level, covering limitations identified. The phenomenon is formally formulated as question and problem at the explanatory understanding level. The composite function, E, is proposed to solve such formulation and performed for a specific domain (One Dimension Bin-Packing problem and Tabu Search algorithm) over an instance set P. A description process for problem structure and space, for algorithm performance and the operative and searching behaviors of the algorithm during execution (significant features) was proposed to build the domain of the composite function. Also, the metrics known by scientific community were used, but these were not significant in the analyses. Three important logical areas were contemplated. The knowledge acquired by the proposed composite function allowed the solving of the stated problem, understanding the phenomenon, answering the “how” and “why” for certain problem instances, algorithm significant features and the algorithm logical design contribute toward a better relation between problem-algorithm. It was applied to design self-adaptive algorithms and improve the performance considering the causal relations according to problem structure or space. On average, a 91% significant advantage of Tabu Search self-adaptive algorithms was obtained over analyzed original algorithms. Other results over set P’ showed that when they obtain the same or less quality of solution, they finish significantly faster than analyzed interest algorithm and the quality difference is very small. As future work is to explore generalized features. The proposed composite function E could act as a guideline to find latent knowledge from relation problem-algorithm of other problem domains and search algorithms; this permits the adapting of logical design as well as operative and searching behaviors of an algorithm (self-adaptive algorithm) to problem structure, solutions space and behavior of algorithms (operative and searching) during execution for providing the best solution to problems.