Bi-objective parameter setting problem of a genetic algorithm: an empirical study on traveling salesperson problem


Akduran Y., DAŞDEMİR E., TESTİK M. C.

Applied Intelligence, vol.53, no.22, pp.27148-27162, 2023 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 53 Issue: 22
  • Publication Date: 2023
  • Doi Number: 10.1007/s10489-023-04972-z
  • Journal Name: Applied Intelligence
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, PASCAL, ABI/INFORM, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, Educational research abstracts (ERA), INSPEC, Library, Information Science & Technology Abstracts (LISTA), zbMATH
  • Page Numbers: pp.27148-27162
  • Keywords: Genetic algorithm, Multi-objective optimization, Parameter setting problem, Traveling salesperson problem
  • Hacettepe University Affiliated: Yes

Abstract

Genetic Algorithm (GA) is a widely used metaheuristic for addressing challenging optimization problems. Selecting suitable settings for GA parameters can lead to a considerable improvement in its performance, but this is often difficult due to the larger number of alternatives available and variable performance depending on the problem solved. Furthermore, consideration of multiple performance criteria in parameter selection adds an additional layer of complexity. Therefore, practitioners often rely on their previous experiences or perform trial-and-error experiments when determining suitable parameter settings. In this study, we define the problem of finding suitable settings for GAs as a bi-objective optimization problem with an aim to find efficient settings that will maximize the approximation quality and minimize the run time of the GA. We conduct an empirical study on a GA that solves Traveling Salesperson Problem (TSP). Two evolutionary algorithms are utilized in a nested manner to address the bi-objective parameter setting problem: a GA to solve the TSP instances and a multi-objective evolutionary algorithm to find the bi-objective efficient settings of the GA. We find efficient settings for each instance through an empirical study with 31 TSP instances and identify settings that perform well regardless of the instance solved. The results provide valuable insights into the behavior of efficient settings, demonstrating that some operators and parameters are robust to changes in problem size, while others require adjustment.