Evolutionary-based tailoring of synthetic instances for the Knapsack problem
| Autor: | Santiago Enrique Conant-Pablos, Iván Amaya, Hugo Terashima-Marín, José Carlos Ortiz-Bayliss, Carlos A. Coello Coello, Luis Fernando Plata-González |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Computer science Heuristic business.industry GRASP Evolutionary algorithm Computational intelligence 02 engineering and technology Solver Machine learning computer.software_genre Theoretical Computer Science 020901 industrial engineering & automation Knapsack problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Geometry and Topology Artificial intelligence Heuristics business computer Software |
| Zdroj: | Soft Computing. 23:12711-12728 |
| ISSN: | 1433-7479 1432-7643 |
| Popis: | The assessment of strengths and weaknesses of a solver is often limited by the diversity of the cases where it is tested upon. As such, it is paramount to have a versatile tool which finds the problem instances where such a solver excels/fails. In this manuscript, we propose to use an evolutionary algorithm for creating this tool. To validate our approach, we conducted several tests on four heuristics for the knapsack problem. Although, the process can be extended to other domains with relatively few changes. The tests cover different sets of instances, both favoring the performance of one heuristic while hindering that of the remaining ones, and vice versa. To further test our evolutionary-based model, we also apply it on a recent approach that combines the strengths of different heuristics to improve its performance (usually referred to as a hyper-heuristic). We show that it is possible to tailor instances in which even this more complex model excels/fails. Throughout our approach, a researcher can test a solver under different kinds of scenarios, delving deeper into the conditions that make it perform well/poorly. Therefore, we recommend using the proposed approach as a means to grasp better insights about strengths and weaknesses of different solvers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink