Genetic algorithms with permutation-based representation for computing the distance of linear codes Pegalajar Cuéllar, Manuel Gómez Torrecillas, José Lobillo Borrero, Francisco Javier Navarro Garulo, Gabriel Research partially supported by grant PID2019-110525GB-I00 from Agencia Estatal de Investigacion (AEI) and from Fondo Europeo de Desarrollo Regional (FEDER), and by grant A-FQM-470-UGR18 from Consejeria de Economia y Conocimiento de la Junta de Andalucia and Programa Operativo FEDER 2014-2020. 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. 2021-07-13T10:28:35Z 2021-07-13T10:28:35Z 2020-10-30 info:eu-repo/semantics/article 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] http://hdl.handle.net/10481/69667 10.1016/j.swevo.2020.100797 eng http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/openAccess Atribución-NoComercial-SinDerivadas 3.0 España Elsevier