How Predictable are Fitness Landscapes with Machine Learning? A Traveling Salesman Ruggedness Study

The notion of fitness landscape (FL) has shown promise in terms of optimization. In this paper we propose a machine learning (ML) prediction approach to quantify FL ruggedness by computing the entropy. The approach aims to build a model that could reveal information about the ruggedness of unseen instances. Its contribution is attractive in many cases like black-box optimization and in case we can rely on the information of small instances to discover the features of larger and time-consuming ones. The experiment consists in evaluating multiple ML models for the prediction of the ruggedness of the traveling salesman problem (TSP). The results show that ML can provide, for instances of a similar problem, acceptable predictions and that it can help to estimate ruggedness of large instances in that case. However, the inclusion of several features is necessary to have a more predictable landscape, especially when dealing with different TSP instances.

@article{Amrani2024,
  title     = {How Predictable are Fitness Landscapes with Machine Learning? A Traveling Salesman Ruggedness Study},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {15},
  number    = {11},
  year      = {2024},
  publisher = {The Science and Information Organization},
  author    = {Mohammed El Amrani and Khaoula Bouanane and Youssef Benadada},
  doi       = {10.14569/IJACSA.2024.01511118},
  url       = {https://doi.org/10.14569/IJACSA.2024.01511118}
}