1. Complete title: Evolutionary Strategies for the Design of Binary Linear Codes --------------------- 2. Authors' names, addresses, e-mails and phone numbers: Claude Carlet University of Bergen, Bergen, Norway and Université Paris 8, Département de mathématiques, 2 rue de la liberté, 93526 Saint-Denis, Cedex, France claude.carlet@gmail.com +33 630 389 528 Luca Mariot Semantics, Cybersecurity and Services Group, University of Twente, Drienerlolaan 5, 7522 NB Enschede, The Netherlands l.mariot@utwente.nl +31 623 952 460 Luca Manzoni Department of Mathematics and Geosciences, University of Trieste, Via Valerio 12/1, Trieste, Italy lmanzoni@units.it +39 040 558 2674 Stjepan Picek Digital Security Group, Radboud University, PO Box 9010, Nijmegen, The Netherlands stjepan.picek@ru.nl +385 9822 6407 --------------------- 3. Corresponding author Luca Mariot --------------------- 4. Abstract The design of binary error-correcting codes is a challenging optimization problem with several applications in telecommunications and storage, which has been addressed with metaheuristic techniques such as evolutionary algorithms. Still, all these efforts are 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. 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 codes start to drop, with the extreme case of (16,8,5) codes which all turn out to be equivalent to MAGMA's BKLC. --------------------- 5. Relevant criteria B, C, D, G --------------------- 6. Criteria statement (B) Our results show that Evolutionary Strategies (ES) are able to construct binary linear codes with optimal minimum distance, with full success rate in almost all considered problem instances. The only exception is the largest instance of length n=16, where anyway at least one tested ES variant achieves a very high success rate (92%). The optimality of the minimum distance is theoretically guaranteed, since for the considered lengths and dimensions the theoretical lower and upper bounds coincide. Other optimal linear codes for the considered parameters have been constructed in the literature: nowadays, the standard way to obtain them is through the Best Known Linear Code (BKLC) provided by the MAGMA computer algebra system. Most of these codes returned by MAGMA come from the computational search effort published in 2006 in [1]. Since our ES approach is able to obtain error correcting codes with the same optimal distance for the considered problem instances, we think that our work fully qualifies for the criterion (B). (C) There exist several tables with the optimal minimum distances achievable by binary codes, depending on their length and dimension. In the last decade, the tables maintained by Grassl [2] became the standard reference for this problem, since they constitute the most comprehensive database for error-correcting codes publicly available. Through this database, it is quite easy to check if a particular code obtained by some construction meets the lower or upper bounds known in the literature, and therefore to establish if the code is optimal. Further, one can check for each combination of optimal parameters what is the corresponding code construction provided by MAGMA. In our work, we use the optimal minimum distance as a parameter that defines the problem instance solved by ES. The values of the optimal minimum distance were taken from the database [2], and in all those cases the lower and upper bounds coincide. Since ES almost always converge to an optimal solution, we can conclude that our results are equal to the results that were placed in the database [2] maintained by an expert of the field, and used as a reference by researchers in that field. Thus, we deem our work to be completely fitting for criterion (C). (D) Researchers working in coding theory are always interested in finding new constructions of optimal linear codes, even if previous examples already exist. This is especially true if the new construction yields codes that are inequivalent to previously known ones. Inequivalence is defined in terms of code isomorphism, and can be easily checked through the IsIsomorphic function in MAGMA. In our work, we compared all codes evolved by our ES algorithm against the Best Known Linear Code (BKLC) provided by MAGMA for the corresponding parameters, and checked for isomorphism (see Table 3 in the paper for a summary of the results). Interestingly, for three instances out of the five considered ones, all codes generated by the simplest ES variant are inequivalent to MAGMA's BKLC. For the fourth instance (15, 7, 5) the simplest ES variant is still able to find inequivalent codes in 72% of the cases. Finally, for the largest instance (16, 8, 5), all ES variants produce optimal codes that are equivalent to MAGMA's BKLC. We believe this stark difference to be very interesting for the coding theory community, since it might indicate that the (16, 8, 5) instance is characterized by a single optimal code up to isomorphism. So far, there have been no results in this direction, and we think that for this reason our work qualifies also for criterion (D), since this experimental findings are independent of the fact that they were created through ES. (G) Finding an optimal linear error correcting code is recognized to be a hard combinatorial optimization problem. As a matter of fact, except for very small instances where all possible codes of a given length and dimension can be exhaustively generated and checked for the optimality of their distance, in general one needs to resort either to algebraic constructions or heuristic techniques. Algebraic constructions can be considered as the state-of-the-art method for this problem, since most of the optimal codes reported in the database [2] have been generated in this way. However, the problem with algebraic constructions is that they always yield the same classes of codes, up to isomorphism. Indeed, finding optimal codes that are inequivalent to the known ones in the literature can be regarded as a very difficult problem. Before our work, heuristic techniques were nowhere near to match algebraic cosntructions, not for the optimality of the distance but rather on the linearity of the resulting codes. As a matter of fact, our work is the first one to produce a heuristic construction of binary codes that are linear, with a prescribed dimension. Moreover, as we remarked above for criterion (D), our ES is often able to find codes that are inequivalent to those obtained by algebraic constructions in terms of isomorphism. Hence, we think that our results qualify for criterion (G) as well. --------------------- 7. Full citation Carlet C., Mariot L., Manzoni L., Picek S. (2023) Evolutionary Strategies for the Design of Binary Linear Codes. In: Pérez Cáceres L., Stutzle T. (eds.) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2023. Lecture Notes in Computer Science, vol. 13987, pp. 114-129. Springer, Cham @inproceedings{cmmp-evocop2023, author = {Claude Carlet and Luca Mariot and Luca Manzoni and Stjepan Picek}, editor = {Leslie P{\'{e}}rez C{\'{a}}ceres and Thomas St{\"{u}}tzle}, title = {Evolutionary Strategies for the Design of Binary Linear Codes}, booktitle = {Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Brno, Czech Republic, April 12-14, 2023, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {13987}, pages = {114--129}, publisher = {Springer}, year = {2023} doi = {10.1007/978-3-031-30035-6\_8} } 8. Prize statement Any prize money, if any, is to be divided equally among the co-authors. --------------------- 9. Best statement We believe that our work is the best entry for two reasons. The first one concerns the techniques developed in the paper: as we mention in its introduction, several works in the existing literature addressed the design of binary error correcting codes via evolutionary algorithms. However, none of them considered the linearity constraint of the evolved codes, which is often very important for practical applications, in order to achieve low-cost implementation using feedback shift registers and similar devices. Our work is the first one to propose an evolutionary algorithm (specifically ES) that searches directly in the space of linear codes, using innovative genetic operators which preserve the dimension of the linear mapping encoded by an individual in the population. Thus, we think that this part already represents a significant improvement over existing works that construct error correcting codes with heuristic techniques. The second reason concerns instead the obtained results: as we discussed above in the criteria statements, ES turned out to yield many optimal linear codes that are also new. The optimality of such codes can be easily checked using the code tables in [2]. The "novelty" aspect of these codes is that many of them are inequivalent to the best linear codes known so far, as verified through MAGMA. Such inequivalent codes could be in turn studied to see whether they yield new algebraic constructions. The same interest applies also for the largest instance, where all codes actually turned out to be equivalent to MAGMA's BKLC: far from considering it a setback, we believe that these results could be very useful to shed light on the mathematical structure of the space of (16, 8, 5) linear codes, since they seem to indicate that there is only a single optimal code up to isomorphism. All in all, we think that the results presented in this paper indicate that ES (and evolutionary algorithms in general) represent an interesting tool to perform experimental mathematics. --------------------- 10. Methods used ES (Evolutionary Strategies) --------------------- 11. Publication date 31 March 2023 --------------------- References [1] Grassl, Markus. Searching for linear codes with large minimum distance. Discovering Mathematics with Magma: Reducing the Abstract to the Concrete. Springer Berlin Heidelberg, 2006. [2] Grassl, Markus. Code Tables: Bounds on the parameters of various types of codes. URL: http://www.codetables.de/