Population-based iterated greedy algorithm for the S-labeling problem

doi:10.1016/j.cor.2023.106224

Population-based iterated greedy algorithm for the S-labeling problem

2023-07-01

2

PRE

AI

M

Manuel Lozano *

E

Eduardo Rodríguez-Tello *

DOI：10.1016/j.cor.2023.106224

Original

Original request for help

Save

Abstract

En 中文

The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, it has been employed to solve a considerable number of optimization problems; however, it has never been explored as a solver for graph labeling problems. Hence, in this paper, we contribute to bridging this gap by proposing a population-based iterated greedy to solve the S-labeling problem. The construction phase invokes a novel greedy algorithm for the problem and the destruction phase engages a destructive strength that is attenuated as the algorithm progresses. In addition, it incorporates a restart operator that is activated according to an innovative criterion for detecting convergence. Extensive experiments verify that the proposal can achieve better solution quality than the state-of-the-art optimizer for this optimization problem and other competing algorithms. We have completed the study about the potential of the iterated greedy metaheuristic for graph labeling problems by evaluating experimentally the performance of an extension of the proposed algorithm that solves the Antibandwidth problem. Remarkably, it provides comparable results to those of the best algorithms in the literature for this complex case of labeling problem.

Keywords:

Iterated greedy metaheuristic

S-labeling problem

Antibandwidth problem

Graph labeling

Combinatorial optimization

Population-based iterated greedy algorithm for the S-labeling problem

Abstract

Journal

Organization