The design of binary error-correcting codes is a challenging optimization problem with several applications in telecommunications and storage, which has also been addressed with metaheuristic techniques and evolutionary algorithms. Still, all these efforts focused on optimizing the minimum distance of unrestricted binary codes, i.e., with no constraints on their linearity, which is a desirable property for efficient implementations. In this paper, we present an Evolutionary Strategy (ES) algorithm that explores only the subset of linear codes of a fixed length and dimension. To that end, we represent the candidate solutions as binary matrices and devise variation operators that preserve their ranks. Our experiments show that up to length n = 14, our ES always converges to an optimal solution with a full success rate, and the evolved codes are all inequivalent to the Best-Known Linear Code (BKLC) given by MAGMA. On the other hand, for larger lengths, both the success rate of the ES, as well as the diversity of the evolved codes, start to drop, with the extreme case of (16, 8, 5) codes which all turn out to be equivalent to MAGMA’s BKLC.

Evolutionary Strategies for the Design of Binary Linear Codes

Mariot L.
;
Manzoni L.;
2023-01-01

Abstract

The design of binary error-correcting codes is a challenging optimization problem with several applications in telecommunications and storage, which has also been addressed with metaheuristic techniques and evolutionary algorithms. Still, all these efforts focused on optimizing the minimum distance of unrestricted binary codes, i.e., with no constraints on their linearity, which is a desirable property for efficient implementations. In this paper, we present an Evolutionary Strategy (ES) algorithm that explores only the subset of linear codes of a fixed length and dimension. To that end, we represent the candidate solutions as binary matrices and devise variation operators that preserve their ranks. Our experiments show that up to length n = 14, our ES always converges to an optimal solution with a full success rate, and the evolved codes are all inequivalent to the Best-Known Linear Code (BKLC) given by MAGMA. On the other hand, for larger lengths, both the success rate of the ES, as well as the diversity of the evolved codes, start to drop, with the extreme case of (16, 8, 5) codes which all turn out to be equivalent to MAGMA’s BKLC.
File in questo prodotto:
File Dimensione Formato  
(Lecture Notes in Computer Science, 13987) Leslie Pérez Cáceres, Thomas Stützle - Evolutionary Computation in Combinatorial Optimization_ 23rd European Conference, EvoCOP 2023 Held as Part of EvoStar -1.pdf

Accesso chiuso

Descrizione: cover, index, cap.
Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 1.18 MB
Formato Adobe PDF
1.18 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
(Lecture+Notes+in+Computer+Science,+13987)+Leslie+Pérez+Cáceres,+Thomas+Stützle+-+Evolutionary+Computation+in+Combinatorial+Optimization_+23rd+European+Conference,+EvoCOP+2023+Held+as+Part+of+EvoStar+-1-Post_print.pdf

Open Access dal 31/05/2024

Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Digital Rights Management non definito
Dimensione 1.53 MB
Formato Adobe PDF
1.53 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

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/11368/3046334
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact