\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A novel genetic search scheme based on nature-inspired evolutionary algorithms for binary self-dual codes

  • * Corresponding author: Deniz Ustun

    * Corresponding author: Deniz Ustun
Abstract / Introduction Full Text(HTML) Figure(6) / Table(9) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 11T71, 94B05; Secondary: 94B60.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The Initial Phase

    Figure 2.  The Crossover Phase

    Figure 3.  The Mutation Phase

    Figure 4.  Pseudo-code of the genetic algorithm

    Figure 5.  Flowchart of the genetic algorithm

    Figure 6.  An application of the genetic algorithm to the problem of computing binary self-dual codes of length 72 with minimum distance 12

    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}) $
     | Show Table
    DownLoad: CSV

    Table 2.  New Type I $ [68, 34, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV

    Table 3.  New Type I $ [72, 36, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV

    Table 4.  New Type I $ [72, 36, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV

    Table 5.  New Type I $ [72, 36, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV

    Table 6.  New Type II $ [72, 36, 12] $ Codes

    $ 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 $
     | Show Table
    DownLoad: CSV

    Table 7.  New Type I $ [72, 36, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV

    Table 8.  New Type II $ [72, 36, 12] $ Codes

    $ 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 $
     | Show Table
    DownLoad: CSV

    Table 9.  New Type I $ [72, 36, 12] $ Codes

    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 $
     | Show Table
    DownLoad: CSV
  • [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. BortosJ. GildeaA. KayaA. 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. BosmaJ. 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. DontchevaA. 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. DoughertyJ. GildeaA. 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. DoughertyJ. GildeaA. 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. DoughertyJ. GildeaR. 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. DoughertyT. 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. DoughertyJ.-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. GildeaA. KayaR. 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. GildeaA. KorbanA. 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. HollandAdaptation 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. KayaB. 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. WaterhouseF. 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. YankovM. H. LeeM. 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.
  • 加载中

Figures(6)

Tables(9)

SHARE

Article Metrics

HTML views(3558) PDF downloads(811) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return