Genetic algorithms with permutation-based representation for computing the distance of linear codes
Metadatos
Mostrar el registro completo del ítemAutor
Pegalajar Cuéllar, Manuel; Gómez Torrecillas, José; Lobillo Borrero, Francisco Javier; Navarro Garulo, GabrielEditorial
Elsevier
Fecha
2020-10-30Referencia bibliográfica
Published version: M.P. Cuéllar...[et al.]. Genetic algorithms with permutation-based representation for computing the distance of linear codes, Swarm and Evolutionary Computation, Volume 60, 2021, 100797, ISSN 2210-6502, [https://doi.org/10.1016/j.swevo.2020.100797]
Patrocinador
Agencia Estatal de Investigacion (AEI) PID2019-110525GB-I00; European Commission; Junta de Andalucia A-FQM-470-UGR18; Programa Operativo FEDER 2014-2020Resumen
Finding the minimum distance of linear codes is an NP-hard problem. Traditionally, this computation
has been addressed by means of the design of algorithms that find, by a clever exhaustive search, a linear
combination of some generating matrix rows that provides a codeword with minimum weight. Therefore, as
the dimension of the code or the size of the underlying finite field increase, so it does exponentially the run
time. In this work, we prove that, given a generating matrix, there exists a column permutation which leads
to a reduced row echelon form containing a row whose weight is the code distance. This result enables the
use of permutations as representation scheme, in contrast to the usual discrete representation, which makes
the search of the optimum polynomial time dependent from the base field. In particular, we have implemented
genetic and CHC algorithms using this representation as a proof of concept. Experimental results have been
carried out employing codes over fields with two and eight elements, which suggests that evolutionary algorithms
with our proposed permutation encoding are competitive with regard to existing methods in the literature. As
a by-product, we have found and amended some inaccuracies in the Magma Computational Algebra System
concerning the stored distances of some linear codes.