Gradient search is a classical technique for optimizing differentiable functions that has gained much relevance recently due to its application on Neural Network training. Despite its popularity, the application of gradient search has been limited to the continuous optimization and its usage in the combinatorial case is confined to a few works, all which tackle the binary search space. In this paper, we present a new approach for applying Gradient Search to the space of permutations. The idea consists of optimizing the expected objective value of a random variable defined over permutations. Such a random variable is distributed according to the Plackett-Luce model, and a gradient search over its continuous parameters is performed. Conducted experiments on a benchmark of the linear ordering problem confirm that the Gradient Search performs better than its counterpart Estimation of Distribution Algorithm: the Plackett-Luce EDA. Moreover, results reveal that the scalability of the Gradient Search is better than that of the PL-EDA.

Gradient search in the space of permutations

Santucci, Valentino
;
2020

Abstract

Gradient search is a classical technique for optimizing differentiable functions that has gained much relevance recently due to its application on Neural Network training. Despite its popularity, the application of gradient search has been limited to the continuous optimization and its usage in the combinatorial case is confined to a few works, all which tackle the binary search space. In this paper, we present a new approach for applying Gradient Search to the space of permutations. The idea consists of optimizing the expected objective value of a random variable defined over permutations. Such a random variable is distributed according to the Plackett-Luce model, and a gradient search over its continuous parameters is performed. Conducted experiments on a benchmark of the linear ordering problem confirm that the Gradient Search performs better than its counterpart Estimation of Distribution Algorithm: the Plackett-Luce EDA. Moreover, results reveal that the scalability of the Gradient Search is better than that of the PL-EDA.
9781450371278
File in questo prodotto:
File Dimensione Formato  
3377929.3398094.pdf

non disponibili

Descrizione: Versione editoriale
Tipologia: Versione Editoriale (PDF)
Licenza: NON PUBBLICO - Accesso chiuso
Dimensione 1.09 MB
Formato Adobe PDF
1.09 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
_ECPERM_GECCO_2020__GRADIENT_SEARCH.pdf

accesso aperto

Descrizione: preprint
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 1.2 MB
Formato Adobe PDF
1.2 MB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/20.500.12071/20769
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact