Algorithms | Genetic Algorithm | Linear Search |
Time Complexities | $ \mathcal{O}(NPm)=\mathcal{O}(200(500)m) $ | $ \mathcal{O}(L^m)=\mathcal{O}(2^{m}) $ |
In this paper, a genetic algorithm, one of the evolutionary algorithm optimization methods, is used for the first time for the problem of computing extremal binary self-dual codes. We present a comparison of the computational times between the genetic algorithm and a linear search for different size search spaces and show that the genetic algorithm is capable of computing binary self-dual codes significantly faster than the linear search. Moreover, by employing a known matrix construction together with the genetic algorithm, we are able to obtain new binary self-dual codes of lengths 68 and 72 in a significantly short time. In particular, we obtain 11 new binary self-dual codes of length 68 and 17 new binary self-dual codes of length 72.
Citation: |
Table 1. Time Complexities of Genetic Algorithm and Linear Search for Binary Self-Dual Codes
Algorithms | Genetic Algorithm | Linear Search |
Time Complexities | $ \mathcal{O}(NPm)=\mathcal{O}(200(500)m) $ | $ \mathcal{O}(L^m)=\mathcal{O}(2^{m}) $ |
Table 2.
New Type I
Type | $ r_A $ | $ r_B $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_{1} $ | $ W_{68, 2} $ | $ (0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1) $ | $ (1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0) $ | $ 0 $ | $ 34 $ | $ 34 $ |
$ C_2 $ | $ W_{68, 2} $ | $ (1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1) $ | $ (0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1) $ | $ 0 $ | $ 51 $ | $ 34 $ |
$ C_3 $ | $ W_{68, 2} $ | $ (1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0) $ | $ (1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1) $ | $ 0 $ | $ 68 $ | $ 34 $ |
$ C_4 $ | $ W_{68, 2} $ | $ (0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0) $ | $ (0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1) $ | $ 0 $ | $ 85 $ | $ 34 $ |
$ C_5 $ | $ W_{68, 2} $ | $ (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1) $ | $ (0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1) $ | $ 0 $ | $ 119 $ | $ 34 $ |
$ C_6 $ | $ W_{68, 2} $ | $ (0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1) $ | $ (0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0) $ | $ 0 $ | $ 153 $ | $ 34 $ |
$ C_7 $ | $ W_{68, 2} $ | $ (1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1) $ | $ (1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0) $ | $ 0 $ | $ 136 $ | $ 34 $ |
$ C_{8} $ | $ W_{68, 2} $ | $ (0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1) $ | $ (1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1) $ | $ 0 $ | $ 187 $ | $ 34 $ |
$ C_{9} $ | $ W_{68, 2} $ | $ (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0) $ | $ (1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0) $ | $ 0 $ | $ 221 $ | $ 34 $ |
$ C_{10} $ | $ W_{68, 2} $ | $ (0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0) $ | $ (0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1) $ | $ 0 $ | $ 238 $ | $ 34 $ |
$ C_{11} $ | $ W_{68, 2} $ | $ (0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1) $ | $ (1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1) $ | $ 0 $ | $ 255 $ | $ 34 $ |
Table 3.
New Type I
Type | $ r_A $ | $ r_B $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_1 $ | $ W_{72, 1} $ | $ (1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0) $ | $ (0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0) $ | $ 0 $ | $ 201 $ | $ 72 $ |
$ C_2 $ | $ W_{72, 1} $ | $ (1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1) $ | $ (1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0) $ | $ 36 $ | $ 471 $ | $ 72 $ |
Table 4.
New Type I
Type | $ r_A $ | $ r_B $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_3 $ | $ W_{72, 1} $ | $ (1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0) $ | $ (1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1) $ | $ 72 $ | $ 825 $ | $ 72 $ |
Table 5.
New Type I
Type | $ r_A $ | $ r_B $ | $ r_C $ | $ r_D $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_4 $ | $ W_{72, 1} $ | $ (0, 1, 0, 0, 1, 1, 0, 1, 0) $ | $ (1, 0, 0, 1, 1, 1, 1, 0, 0) $ | $ (0, 0, 0, 1, 0, 1, 1, 1, 0) $ | $ (0, 1, 1, 1, 0, 0, 1, 0, 0) $ | $ 36 $ | $ 441 $ | $ 72 $ |
Table 6.
New Type II
$ r_A $ | $ r_B $ | $ r_C $ | $ r_D $ | $ \alpha $ | $ |Aut(C_i)| $ | |
$ C_5 $ | $ (0, 0, 0, 1, 0, 1, 1, 1, 0) $ | $ (1, 0, 0, 1, 1, 0, 1, 1, 0) $ | $ (1, 1, 1, 1, 0, 0, 1, 0, 0) $ | $ (1, 0, 1, 0, 1, 1, 0, 1, 0) $ | $ -2772 $ | $ 72 $ |
Table 7.
New Type I
Type | $ r_A $ | $ r_B $ | $ r_C $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_{6} $ | $ W_{72, 1} $ | $ (1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0) $ | $ (1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0) $ | $ (0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1) $ | $ 36 $ | $ 456 $ | $ 72 $ |
Table 8.
New Type II
$ r_A $ | $ r_B $ | $ r_C $ | $ \alpha $ | $ |Aut(C_i)| $ | |
$ C_7 $ | $ (1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1) $ | $ (1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1) $ | $ (1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0) $ | $ -2106 $ | $ 144 $ |
$ C_8 $ | $ (1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0) $ | $ (0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0) $ | $ (0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0) $ | $ -2322 $ | $ 144 $ |
$ C_9 $ | $ (0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1) $ | $ (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1) $ | $ (0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0) $ | $ -2472 $ | $ 144 $ |
$ C_{10} $ | $ (0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0) $ | $ (0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0) $ | $ (0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0) $ | $ -2520 $ | $ 144 $ |
$ C_{11} $ | $ (0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0) $ | $ (0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0) $ | $ (0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0) $ | $ -2550 $ | $ 144 $ |
$ C_{12} $ | $ (1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0) $ | $ (1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0) $ | $ (0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0) $ | $ -3030 $ | $ 72 $ |
$ C_{13} $ | $ (0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0) $ | $ (0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0) $ | $ (1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1) $ | $ -3954 $ | $ 144 $ |
Table 9.
New Type I
Type | $ r_A $ | $ r_B $ | $ \gamma $ | $ \beta $ | $ |Aut(C_i)| $ | |
$ C_{14} $ | $ W_{72, 1} $ | $ (1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1) $ | $ (0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1) $ | $ 0 $ | $ 354 $ | $ 36 $ |
$ C_{15} $ | $ W_{72, 1} $ | $ (1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0) $ | $ (0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1) $ | $ 18 $ | $ 273 $ | $ 36 $ |
$ C_{16} $ | $ W_{72, 1} $ | $ (0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0) $ | $ (0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0) $ | $ 36 $ | $ 372 $ | $ 36 $ |
$ C_{17} $ | $ W_{72, 1} $ | $ (0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1) $ | $ (1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1) $ | $ 54 $ | $ 669 $ | $ 36 $ |
[1] | K. B. Ajitha Shenoy, S. Biswas and P. P. Kurur, Efficacy of the metropolis algorithm for the minimum-weight codeword problem using codeword and generator search spaces, IEEE Transactions on Evolutionary Computation, 24, (2020), 664–678 |
[2] | P. E. Black, Big-O notation, dictionary of algorithms and data structures [online], U.S. National Institute of Standards and Technology, 2008 (accessed 26 November 2009). Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML/bigOnotation.html |
[3] | J. A. Bland, Local search optimisation applied to the minimum distance problem, Adv. Eng. Informat., 21 (2007), 391-397. |
[4] | J. A. Bland and A. T. Baylis, A tabu search approach to the minimum distance of error-correcting codes, Int. J. Electron., 79 (1995), 829-837. |
[5] | M. Bortos, J. Gildea, A. Kaya, A. Korban and A. Tylyshchak, New self-dual codes of length 68 from a $2 \times 2$ block matrix construction and group rings, Adv. Math. Commun., 16 (2022), 269-284. doi: 10.3934/amc.2020111. |
[6] | W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125. |
[7] | H. Bouzkraoui, A. Azouaoui and Y. Hadi, New ant Colony Optimization for Searching the Minimum Distance for Linear Codes, Advanced Communication Technologies and Networking (CommNet), International Conference on. IEEE, 2018. |
[8] | I. Bouyukliev, V. Fack and J. Winna, Hadamard matrices of order 36, European Conference on Combinatorics, Graph Theory and Applications, (2005), 93–98. |
[9] | S. Buyuklieva and I. Boukliev, Extremal self-dual codes with an automorphism of order $2$, IEEE Trans. Inform. Theory, 44 (1998), 323-328. doi: 10.1109/18.651059. |
[10] | S. Carbas, A. Toktas and D. Ustun, Nature-Inspired Metaheuristic Algorithms for Engineering Optimization Applications, 1, Springer Singapore, 2021. doi: 10.1007/978-981-33-6773-9. |
[11] | N. Chen and Z. Yan, Complexity analysis of ReedSolomon decoding over GF(2m) without using syndromes, EURASIP Journal on Wireless Communications and Networking, Article ID 843634, 2008. doi: 10.1155/2008/843634. |
[12] | R. Dontcheva, New binary self-dual $[70, 35, 12]$ and binary $[72, 36, 12]$ self-dual doubly-even codes, Serdica Math. J., 27 (2001), 287-302. |
[13] | R. A. Dontcheva, A. J. van Zanten and S. M. Dodunekov, Binary self-dual codes with automorphism of composite order, IEEE Trans. Inform. Theory, 50 (2004), 311-318. doi: 10.1109/TIT.2003.822598. |
[14] | S. T. Dougherty, Combinatorics and Finite Geometry, Springer Undergraduate Mathematics Series (SUMS), 2020. doi: 10.1007/978-3-030-56395-0. |
[15] | S. T. Dougherty, J. Gildea, A. Korban and A. Kaya, Composite constructions of self-dual codes from group rings and new extremal self-dual binary codes of length 68, Adv. Math. Commun., 14 (2020), 677-702. doi: 10.3934/amc.2020037. |
[16] | S. T. Dougherty, J. Gildea, A. Korban and A. Kaya, New extremal self-dual codes of length 68 via composite construction, $\mathbb{F}_2+u\mathbb{F}_2$ lifts, extensions and neighbours, Int. J. Inf. Coding Theory, 5 (2018), 211-226. |
[17] | S. T. Dougherty, J. Gildea, R. Taylor and A. Tylshchak, Group rings, $G$-Codes and constructions of self-dual and formally self-dual codes, Des. Codes Cryptogr., 86 (2018), 2115-2138. doi: 10.1007/s10623-017-0440-7. |
[18] | S. T. Dougherty, T. A. Gulliver and M. Harada, Extremal binary self dual codes, IEEE Trans. Inform. Theory, 43 (1997), 2036-2047. doi: 10.1109/18.641574. |
[19] | S. T. Dougherty, J.-L. Kim and P. Solé, Double circulant codes from two class association schemes, Adv. Math. Commun., 1 (2007), 45-64. doi: 10.3934/amc.2007.1.45. |
[20] | J. Gildea, A. Kaya, A. Korban and A. Tylyshchak, Self-dual codes using bisymmetric matrices and group rings, Discrete Math., 343 (2020), 112085, 10 pp. doi: 10.1016/j.disc.2020.112085. |
[21] | J. Gildea, A. Kaya, R. Taylor and B. Yildiz, Constructions for self-dual codes induced from group rings, Finite Fields Appl., 51 (2018), 71-92. doi: 10.1016/j.ffa.2018.01.002. |
[22] | J. Gildea, A. Korban, A. Kaya and B. Yildiz, Constructing self-dual codes from group rings and reverse circulant matrices, Adv. Math. Commun., 15 (2021), 471-485. doi: 10.3934/amc.2020077. |
[23] | D. E. Goldberg, Genetic Algorithm in Search, Optimization, and Machine Learning, Addison Wesley Publishing Company, 1989. |
[24] | D. E. Goldberg, Genetic and evolutionary algorithms come of age, Communications of the ACM, 37 (1994), 113-119. |
[25] | T. A. Gulliver and M. Harada, Classification of extremal double circulant self-dual codes of lengths $64$ to $72$, Des. Codes Cryptogr., 13 (1998), 257-269. doi: 10.1023/A:1008249924142. |
[26] | T. A. Gulliver and M. Harada, On double circulant doubly even self-dual $[72, 36, 12]$ codes and their neighbors, Australas. J. Combin., 40 (2008), 137-144. |
[27] | M. Gürel and N. Yankov, Self-dual codes with an automorphism of order 17, Math. Commun., 21 (2016), 97-101. |
[28] | M. Harada and A. Munemasa, Some restrictions on weight enumerators of singly even self-dual codes, IEEE Trans. Inform. Theory, 52 (2006), 1266-1269. doi: 10.1109/TIT.2005.864416. |
[29] | H. S. He, Forest land scape models: Definitions, characterization, and classification, Forest Ecologyand Management., 254 (2008), 484-498. |
[30] | J. H. Holland, Adaptation in Natural und Artificial Systems, The University of Michigan Press, Ann Arbor, 1975. |
[31] | T. Hurley, Group rings and rings of matrices, Int. Jour. Pure and Appl. Math., 31 (2006), 319-335. |
[32] | A. Kaya and B. Yildiz, New extremal binary self-dual codes from a Baumert-Hall array, Discrete Appl. Math., 271 (2019), 74-83. doi: 10.1016/j.dam.2019.08.003. |
[33] | A. Kaya, B. Yildiz and I. Siap, New extremal binary self-dual codes of length 68 from quadratic residue codes over $\mathbb{F}_2+u\mathbb{F}_2+u^2\mathbb{F}_2$, Finite Fields Appl., 29 (2014), 160-177. doi: 10.1016/j.ffa.2014.04.009. |
[34] | D. E. Knuth, Big omicron and big Omega and big theta, SIGACT News, 8 (1976), 18-24. |
[35] | A. Korban, S. Sahinkaya and D. Ustun, A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes, A Source Code for Magma of the Genetic Algorithm, available online at https://drive.google.com/file/d/11PhB7u92ti8OSKjXJv2aMpDzqGKloH5p/view?usp=sharing |
[36] | F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, Journal of Complexity, 19 (2003), 301-320. doi: 10.1016/S0885-064X(03)00006-2. |
[37] | E. M. Rains, Shadow bounds for self-dual codes, IEEE Trans. Inf. Theory, 44 (1998), 134-139. doi: 10.1109/18.651000. |
[38] | N. Tufekci and B. Yildiz, On codes over $R_{k, m}$ and constructions for new binary self-dual codes, Math. Slovaca, 66 (2016), 1511-1526. doi: 10.1515/ms-2016-0240. |
[39] | B. J. Waterhouse, F. Y. Kuo and I. H. Sloan, Randomly shifted lattice rules on the unit cube for unbounded integrands in high dimensions, J. Complexity, 22 (2006), 71-101. doi: 10.1016/j.jco.2005.06.004. |
[40] | N. Yankov, M. H. Lee, M. Gürel and M. Ivanova, Self-dual codes with an automorphism of order 11, IEEE Trans. Inform. Theory, 61 (2015), 1188-1193. doi: 10.1109/TIT.2015.2396915. |
[41] | A. Zhdanov, New self-dual codes of length 72, arXiv: 1705.05779. |
[42] | A. Zhdanov, Convolutional encoding of 60, 64, 68, 72-bit self-dual codes, arXiv: 1702.05153. |
The Initial Phase
The Crossover Phase
The Mutation Phase
Pseudo-code of the genetic algorithm
Flowchart of the genetic algorithm
An application of the genetic algorithm to the problem of computing binary self-dual codes of length 72 with minimum distance 12