Algebraic variants of the Differential Evolution (DE) algorithm have been recently proposed to tackle permutation-based optimization problems by means of an algebraic framework, which allows to directly encode the solutions as permutations. The algebraic DE in the permutation space can be characterized by considering different neighborhood definitions such as swapping two adjacent items, swapping any two items, shifting an item to a given position. Here we propose the Variable Neighborhood Differential Evolution for Permutations (VNDEP), which adaptively searches the three neighborhoods together based on a method of dynamic reward. We provide an extensive and systematic analysis of the theoretical tools required in VNDEP, by studying the complexity of the proposed algorithmic components and by introducing the possibility to use a scale factor parameter larger than one. Experiments have been held on a widely used benchmark suite for the Linear Ordering Problem with Cumulative Costs, where VNDEP has been compared with four known permutation-based DE schemes and with respect to the state-of-the-art results for the considered instances. The experiments clearly show that VNDEP systematically outperforms the competitor algorithms and, most impressively, 32 new best known solutions, of the 50 most challenging instances, have been obtained.

Variable neighborhood algebraic Differential Evolution: An application to the Linear Ordering Problem with Cumulative Costs

Santucci, Valentino
2020

Abstract

Algebraic variants of the Differential Evolution (DE) algorithm have been recently proposed to tackle permutation-based optimization problems by means of an algebraic framework, which allows to directly encode the solutions as permutations. The algebraic DE in the permutation space can be characterized by considering different neighborhood definitions such as swapping two adjacent items, swapping any two items, shifting an item to a given position. Here we propose the Variable Neighborhood Differential Evolution for Permutations (VNDEP), which adaptively searches the three neighborhoods together based on a method of dynamic reward. We provide an extensive and systematic analysis of the theoretical tools required in VNDEP, by studying the complexity of the proposed algorithmic components and by introducing the possibility to use a scale factor parameter larger than one. Experiments have been held on a widely used benchmark suite for the Linear Ordering Problem with Cumulative Costs, where VNDEP has been compared with four known permutation-based DE schemes and with respect to the state-of-the-art results for the considered instances. The experiments clearly show that VNDEP systematically outperforms the competitor algorithms and, most impressively, 32 new best known solutions, of the 50 most challenging instances, have been obtained.
File in questo prodotto:
File Dimensione Formato  
ins2020.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
_INS_2019__VNDEP_for_LOPCC__DA_SOTTOMETTERE_.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 415.66 kB
Formato Adobe PDF
415.66 kB 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: https://hdl.handle.net/20.500.12071/15082
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact