Mutation-Based Algebraic Artificial Bee Colony Algorithm for Computing the Distance of Linear Codes

Year 2022, Volume: 14 Issue: 1, 191 - 200, 30.06.2022

Adrian Korban , Serap Şahinkaya , Deniz Üstün

https://doi.org/10.47000/tjmcs.982426

Abstract

Finding the minimum distance of linear codes is a non-deterministic polynomial-time-hard problem and different approaches are used in the literature to solve this problem.
Although, some of the methods focus on finding the true distances by using exact algorithms, some of them focus on optimization algorithms to find the lower or upper bounds of the distance. In this study,
we focus on the latter approach. We first give the swarm intelligence background of artificial bee colony algorithm, we explain the algebraic approach of such algorithm and call it the algebraic artificial bee colony algorithm (A-ABC). Moreover, we develop the A-ABC algorithm by integrating it with the algebraic differential mutation operator. We call the developed algorithm the mutation-based algebraic artificial bee colony algorithm (MBA-ABC). We apply both; the A-ABC and MBA-ABC algorithms to the problem of finding the minimum distance of linear codes. The achieved results indicate that the MBA-ABC algorithm has a superior performance when compared with the A-ABC algorithm when finding the minimum distance of Bose, Chaudhuri, and Hocquenghem (BCH) codes (a special type of linear codes).

Keywords

Minimum distance, minimum-weight codeword, optimisation, heuristic, artificial bee colony algorithm

References

• Ajitha Shenoy, K.B., Biswas, S., Kurur, P.P., Efficacy of the metropolis algorithm for the minimum-weight codeword problem using codeword and generator search spaces, IEEE Transactions on Evolutionary Computation, 24(4)(2020), 664-678.
• Akdagli, A., Ustun, D., Bandwidth enhancement of rectangular microstrip antenna with a rectangular slot by using a novel hybrid optimization method based on the ABC and DE algorithms, Int J Numer Model., 31(5)(2018).
• Akdagli, A., Ustun, D., Design of bandnotched UWB antenna using a hybrid optimization based on ABC and DE algorithms, AEU - International Journal of Electronics and Communications, 87(2018), 10-21.
• Askali, M., Azouaoui, A., Nouh, S., Belkasmi, M., On the computing of the minimum distance of linear block codes by heuristic methods, Int. J. Commun. Netw. Syst. Sci., 5(2012), 774-84.
• Askali, M., Nouh, S., Belkasmi, M., An efficient method to find the minimum distance of linear block codes, in Proc. IEEE Int. Conf. Multimedia Comput. Signal Process, Tangier, Morocco, (2012), 185-188.
• Augot, D., Charpin, P., Sendrier, N., Studying the locator polynomial of minimum weight codewords of BCH codes, IEEE Trans. Info. Theory, 38(1992), 960-973.
• Betten, A., Braun, M., Fripertinger, H., Kerber, A., Kohnert , A. et al., Error Correcting Linear Codes, Algorithms and Computation in Mathematics, 18, Springer, 2006.
• Bland, J.A., Baylis, A.T., A tabu search approach to the minimum distance of error-correcting codes, Int. J. Electron., 79(6)(1995), 829-837.
• Bland, J.A., Local search optimisation applied to the minimum distance problem, Adv. Eng. Informat., 21(2007), 391-397.
• Bosma, W., Cannon, J., Playoust, C., The Magma algebra system I: The user language, J. Symbolic Comput., 24(1997), 235-265.
• Bouzkraoui, H. , Azouaoui, A., Hadi, Y., New ant colony optimization for searching the minimum distance for linear codes, Advanced Communication Technologies and Networking (CommNet), International Conference on. IEEE, (2018).
• Cuellar, M.P., Gomez-Torrecillas, J. , Lobillo, F.J., Navarro, G., Genetic algorithms with permutation-based representation for computing the distance of linear codes, Swarm and Evolutionary Computation, 60(2021), 100797.
• Gomez-Torrecillas, J., Lobillo, F.J., Navarro, G., Minimum distance computation of linear codes via genetic algorithms with permutation encoding, ACM Communications in Computer Algebra, 52(3)(2019).
• Hogben, L., Handbook of Linear Algebra, Boca Raton, FL, USA, Champman and Hall, 2007.
• Houghten, S.K., Wallis, J.L., A comparative study of search techniques applied to the minimum distance problem of BCH codes, in Proc, 6th IASTED Int. Conf. Artif. Intell. Soft Comput., (2002), 164-169.
• Joundan, I., Nouh, S., Azouazi, M., Namir, A., A new efficient way based on special stabilizer multiplier permutations to attack the hardness of the minimum weight search problem for large BCH codes, Int. J. Electr. Comput.Eng., 9(2019), 1232.
• Karaboga, D., An idea based on honey bee swarm for numerical optimization, Technical Report-TR06, Erciyes University, Kayseri, Turkey, 2005.
• Karaboga, D., Basturk, B., A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, J. Glob. Optim., 39(2007), 459-471.
• Karaboga D., Basturk, B., On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8(2008), 687-697.
• Lisonek, P., Trummer, L., Algorithms for the minimum weight of linear codes, Adv. Math. Commun., 10(2016), 195-207.
• Ling, S., Xing, C., Coding Theory: A First Course, United Kingdom, Cambridge University Press, 2004.
• MacWilliams, F.J., Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam, North-Holland, 1993.
• Santucci, V., Baioletti, M., Milani, A., Algebraic differential evolution algorithm for the permutation flowshop scheduling problem with total flowtime criterion, IEEE Transactions on Evolutionary Computation, 20(5)(2016), 682-694.
• Storn, R., Price, K., Differential evolution a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11(1997), 341-359.
• Toktas, A., Ustun, D., A triple-objective optimization scheme using butterfly-integrated ABC algorithm for design of multi-layer RAM, IEEE Transactions on Antennas and Propagation, 68(7)(2020), 5602-5612.
• Toktas, A., Ustun, D., Erdogan, N., Pioneer Pareto artificial bee colony algorithm for three-dimensional objective space optimization of composite-based layered radar absorber, Applied Soft Computing, 96(2020), 1-11.
• Ustun, D., An enhanced adaptive butterfly optimization algorithm rigorously verified on engineering problems and implemented to ISAR image motion compensation, Engineering Computations, 37(9)(2020), 3543-3566.
• Vardy, A., The intractability of computing the minimum distance of a code, IEEE Transactions on Information Theory, 43(6)(1997), 1757-1766.