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

Adrian Korban; Serap Şahinkaya; Deniz Ustun

doi:10.3934/amc.2022033

Article Contents

2024, Volume 18, Issue 4: 892-908. Doi: 10.3934/amc.2022033

This issue Previous Article New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm Next Article Differential faultt attack on DEFAULT

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

1.
University of Chester, Department of Physical, Mathematical and Engineering Sciences University of Chester, England
2.
Tarsus University, Faculty of Engineering, Department of Natural and Mathematical Sciences, Turkey
3.
Tarsus University, Faculty of Engineering, Department of Computer Engineering, Turkey

^* Corresponding author: Deniz Ustun
^* Corresponding author: Deniz Ustun

Received: December 2021

Revised: April 2022

Early access: May 5, 2022

Published online: May 5, 2022

Abstract / Introduction Full Text(HTML) Figure(6) / Table(9) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. The Initial Phase

Download: Full-size image PowerPoint slide

Figure 2. The Crossover Phase

Download: Full-size image PowerPoint slide

Figure 3. The Mutation Phase

Download: Full-size image PowerPoint slide

Figure 4. Pseudo-code of the genetic algorithm

Download: Full-size image PowerPoint slide

Figure 5. Flowchart of the genetic algorithm

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Related Papers

Cited by

References

[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.