Low budget black-box optimization is a relevant topic in many practical applications with expensive objective functions or tight real-time constraints. Recently, there has been a growing interest in addressing combinatorial permutation problems in a low budget and black-box scenario. In this context, most of the previously proposed algorithms learn a probabilistic model which guides the search by trying to somehow indicate the most effective areas of the permutation search space. However, the large size and the inherent discontinuity of the permutation space may lessen the effectiveness of this approach when a low, or very low, budget of evaluations is considered. Moving from this consideration, in this work we present a simpler elitist trajectory-based algorithm for low budget black-box optimization of permu-tation problems. The proposed algorithm, namely FAT-RLS, is based on three core ideas: a randomized local search scheme, an adaptive perturbation strength and the use of a tabu structure. A series of experiments held on commonly adopted benchmark problems clearly shows that FAT-RLS obtains better or compara-ble effectiveness with respect to the previous proposals. Moreover, its negligible computational overhead is of particular interest in mission critical situations where tight real-time constraints have to be matched.

A Fast Randomized Local Search for Low Budget Optimization in Black-Box Permutation Problems

Santucci, Valentino
;
2022

Abstract

Low budget black-box optimization is a relevant topic in many practical applications with expensive objective functions or tight real-time constraints. Recently, there has been a growing interest in addressing combinatorial permutation problems in a low budget and black-box scenario. In this context, most of the previously proposed algorithms learn a probabilistic model which guides the search by trying to somehow indicate the most effective areas of the permutation search space. However, the large size and the inherent discontinuity of the permutation space may lessen the effectiveness of this approach when a low, or very low, budget of evaluations is considered. Moving from this consideration, in this work we present a simpler elitist trajectory-based algorithm for low budget black-box optimization of permu-tation problems. The proposed algorithm, namely FAT-RLS, is based on three core ideas: a randomized local search scheme, an adaptive perturbation strength and the use of a tabu structure. A series of experiments held on commonly adopted benchmark problems clearly shows that FAT-RLS obtains better or compara-ble effectiveness with respect to the previous proposals. Moreover, its negligible computational overhead is of particular interest in mission critical situations where tight real-time constraints have to be matched.
978-1-6654-6708-7
low budget optimization, optimization under real-time constraints, black-box permutation problems, randomized local search
File in questo prodotto:
File Dimensione Formato  
_IEEE_WCCI_2022____Low_Budget_Permutation.pdf

accesso aperto

Descrizione: Preprint
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 354.65 kB
Formato Adobe PDF
354.65 kB Adobe PDF Visualizza/Apri
paper_wcci2022_no477_versione_editoriale.pdf

non disponibili

Descrizione: Versione Editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 927.15 kB
Formato Adobe PDF
927.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12071/31988
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact