We present an algebraic approach for dealing with combinatorial optimization problems based on permutations with repetition. The approach is an extension of an algebraic framework defined for combinatorial search spaces which can be represented by a group (in the algebraic sense). Since permutations with repetition does not have the group structure, in this work we derive some definitions and we devise discrete operators that allow to design algebraic evolutionary algorithms whose search behavior is in line with the algebraic framework. In particular, a discrete Differential Evolution algorithm which directly works on the space of permutations with repetition is defined and analyzed. As a case of study, an implementation of this algorithm is provided for the Job Shop Scheduling Problem. Experiments have been held on commonly adopted benchmark suites, and they show that the proposed approach obtains competitive results compared to the known optimal objective values.

An Algebraic Approach for the Search Space of Permutations with Repetition

Santucci, Valentino
2020-01-01

Abstract

We present an algebraic approach for dealing with combinatorial optimization problems based on permutations with repetition. The approach is an extension of an algebraic framework defined for combinatorial search spaces which can be represented by a group (in the algebraic sense). Since permutations with repetition does not have the group structure, in this work we derive some definitions and we devise discrete operators that allow to design algebraic evolutionary algorithms whose search behavior is in line with the algebraic framework. In particular, a discrete Differential Evolution algorithm which directly works on the space of permutations with repetition is defined and analyzed. As a case of study, an implementation of this algorithm is provided for the Job Shop Scheduling Problem. Experiments have been held on commonly adopted benchmark suites, and they show that the proposed approach obtains competitive results compared to the known optimal objective values.
2020
978-3-030-43679-7
978-3-030-43680-3
File in questo prodotto:
File Dimensione Formato  
evocop2020_santucci.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 259.38 kB
Formato Adobe PDF
259.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
evocop2020_paper130.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 333.33 kB
Formato Adobe PDF
333.33 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/18710
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact