Search

Although the number of solutions in combinatorial optimization problems (COPs) is finite, some problems grow exponentially and render exact approaches unfeasible. So, approximate methods, such as heuristics, are customary. Each heuristic usually specializes in specific kinds of problems. Hence, other approaches seek to merge their strengths. One of them is selection hyper-heuristics. However, they usually provide scarce information about their sensitivity. Illumination algorithms may fix this issue since they focus on exploration rather than exploitation while preserving the best solutions under different criteria. Still, literature falls short when merging both approaches, representing a knowledge gap. This work tests the feasibility of using an illumination algorithm, MAP-Elites (ME), for tuning a sequence-based selection hyper-heuristic model for Balanced Partition problems. We choose ME since other researchers have successfully applied it to a different COP. So, we may achieve a hyper-heuristic that represents the best combination of heuristics while simultaneously gaining intel on the performance of diverse alternatives. Our approach operates by creating a multi-dimensional map, where each design variable represents the application of a heuristic. Afterward, ME generates mutated sequences and tests them to determine if they represent a better-performing solution. We consider 1500 instances that include easy and hard instances, analyzed under different scenarios to test our approach. We also include limit instances that are neither easy nor hard. Our resulting data support the proposed approach, as it performs toe-to-toe with a synthetic oracle and may even outperform it. This represents an outstanding result, since a brute-force approach is needed to achieve such an oracle. So, merging ME and hyper-heuristics is a path worth pursuing. We also present how each parameter affects the model performance and identify the critical and virtually irrelevant ones. This serves as the groundwork for future works that focus on exploiting the most relevant parameters.

A plethora of combinatorial optimization problems can be linked to real-life decision scenarios. Even nowadays, more diverse and complex problems are popping up. One of these problems is the traveling thief problem (TTP), which combines elements from the knapsack and traveling salesperson problems. Hence, it is paramount to keep improving solvers to tackle combinatorial problems. Among recent proposals, hyper-heuristics have proven useful since they seek to combine the strengths of more straightforward solvers. This paper proposes a sequence-based selection hyper-heuristic and assesses its feasibility when solving the TTP. Our proposal can be represented by an array of operators selecting a city or an item. In the first case, the solution moves to a new city and thus advances the tour. In the second one, the thief agent picks an item within the current city and tries to store it in its knapsack. We generate several sets of TTP instances with different parameters to validate our approach and analyze the model’s performance. Our data reveal that the proposed approach outperforms randomly generated sequences. Moreover, our approach finds general sequences that surpass sequences specialized for each instance. We believe this is noteworthy and represents a stepping stone towards achieving a more robust solver for complex problems.

Hyper-heuristics have arisen as methods that increase the generality of existing solvers. They have proven helpful for dealing with complex problems, particularly those related to combinatorial optimization. Their recent growth in popularity has increased the daily amount of text in the related literature. This information is primarily unstructured, mainly text that traditional computer data systems cannot process. Traditional systematic literature review studies exhibit multiple limitations, including high time consumption, lack of replicability, and subjectivity of the results. For this reason, text mining has become essential for researchers in recent years. Therefore, efficient text mining techniques are needed to extract meaningful information, patterns, and relationships. This study adopts a literature review of 963 journal and conference papers on hyper-heuristic-related works. We first describe the essential text mining techniques, including text preprocessing, word clouds, clustering, and frequent association rule learning in hyper-heuristic publications. With that information, we implement visualization tools to understand the most frequent relations and topics in the hyper-heuristic domain. The main findings highlight the most dominant topics in the literature. We use text mining analysis to find widespread manifestations, representing the significance of the different areas of hyper-heuristics. Furthermore, we apply clustering to provide seven categories showing the associations between the topics related to hyper-heuristic literature. The vast amount of data available that we find opens up a new opportunity for researchers to analyze the status of hyper-heuristics and help create strategic plans regarding the scope of hyper-heuristics. Lastly, we remark that future work will address the limitations of collecting information from multiple data sources and analyze book chapters related to hyper-heuristics.

There is a colourful palette of metaheuristics for solving continuous optimisation problems in the literature. Unfortunately, it is not easy to pick a suitable one for a specific practical scenario. Moreover, oftentimes the selected metaheuristic must be tuned until finding adequate parameter settings. Therefore, this work presents a framework based on a hyper-heuristic powered by Simulated Annealing for tailoring population-based metaheuristics. To do so, we recognise search operators from well-known techniques as building blocks for new ones. The presented framework comprises six main modules coded in Python, which can be used independently, and which help explore new metaheuristics.

Optimisation has been with us since before the first humans opened their eyes to natural phenomena that inspire technological progress. Nowadays, it is quite hard to find a solver from the overpopulation of metaheuristics that properly deals with a given problem. This is even considered an additional problem. In this work, we propose a heuristic-based solver model for continuous optimisation problems by extending the existing concepts present in the literature. We name such solvers ‘unfolded’ metaheuristics (uMHs) since they comprise a heterogeneous sequence of simple heuristics obtained from delegating the control operator in the standard metaheuristic scheme to a high-level strategy. Therefore, we tackle the Metaheuristic Composition Optimisation Problem by tailoring a particular uMH that deals with a specific application. We prove the feasibility of this model via a two-fold experiment employing several continuous optimisation problems and a collection of diverse population-based operators with fixed dimensions from ten well-known metaheuristics in the literature. As a high-level strategy, we utilised a hyper-heuristic based on Simulated Annealing. Results demonstrate that our proposed approach represents a very reliable alternative with a low computational cost for tackling continuous optimisation problems with a tailored metaheuristic using a set of agents. We also study the implication of several parameters involved in the uMH model and their influence over the solver performance.