Abstract
Combinatorial designs provide an interesting source of optimization problems. Among them, permutation codes are particularly interesting given their applications in powerline communications, flash memories, and block ciphers. This paper addresses the design of permutation codes by evolutionary algorithms (EA) by developing an iterative approach. Starting from a single random permutation, new permutations satisfying the minimum distance constraint are incrementally added to the code by using a permutation-based EA. We investigate our approach against four different fitness functions targeting the minimum distance requirement at different levels of detail and with two different policies concerning code expansion and pruning. We compare the results achieved by our EA approach to those of a simple random search, remarking that neither method scales well with the problem size.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Framework available at http://ecf.zemris.fer.hr/.
References
Banzhaf, W.: The “molecular’’ traveling salesman. Biol. Cybern. 64(1), 7–14 (1990)
Chu, W., Colbourn, C.J., Dukes, P.: Constructions for permutation codes in powerline communications. Des. Codes Cryptogr. 32(1–3), 51–64 (2004)
Colbourn, C.J., Dinitz, J.H.: Combinatorial designs. In: Rosen, K.H., Michaels, J.G., Gross, J.L., Grossman, J.W., Shier, D.R. (eds.) Handbook of Discrete and Combinatorial Mathematics. CRC Press (1999)
Colbourn, C.J., Kløve, T., Ling, A.C.H.: Permutation arrays for powerline communication and mutually orthogonal Latin squares. IEEE Trans. Inf. Theory 50(6), 1289–1291 (2004)
Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, Grundlehren der mathematischen Wissenschaften, vol. 290. Springer (1988). https://doi.org/10.1007/978-1-4757-6568-7
Daemen, J., Rijmen, V.: The Design of Rijndael - The Advanced Encryption Standard. AES), Second Edition. Springer (2020). https://doi.org/10.1007/978-3-662-04722-4
Ferreira, H.C., Vinck, A.H.: Interference cancellation with permutation trellis codes. In: IEEE 52nd Vehicular Technology Conference Fall 2000, vol. 5, pp. 2401–2407. IEEE (2000)
Fogel, D.B.: Applying evolutionary programming to selected traveling salesman problems. Cybern. Syst. 24(1), 27–36 (1993)
Goldberg, D.E., Jr., R.L.: Alleles, loci and the traveling salesman problem. In: Grefenstette, J.J. (ed.) Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA, July 1985, pp. 154–159. Lawrence Erlbaum Associates (1985)
Han Vinck, A.: Coded modulation for powerline communications. AEU Int. J. Eletron. Commun. 54(1), 45–49 (2000)
Jiang, A., Mateescu, R., Schwartz, M., Bruck, J.: Rank modulation for flash memories. In: Kschischang, F.R., Yang, E. (eds.) 2008 IEEE International Symposium on Information Theory, ISIT 2008, Toronto, ON, Canada, 6–11 July 2008, pp. 1731–1735. IEEE (2008)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the complexity of computer computations, held 20–22 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85–103. The IBM Research Symposia Series, Plenum Press, New York (1972)
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Knezevic, K., Picek, S., Mariot, L., Jakobovic, D., Leporati, A.: The design of (almost) disjunct matrices by evolutionary algorithms. In: Fagan, D., Martín-Vide, C., O’Neill, M., Vega-Rodríguez, M.A. (eds.) Theory and Practice of Natural Computing - 7th International Conference, TPNC 2018, Dublin, Ireland, December 12-14, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11324, pp. 152–163. Springer (2018). https://doi.org/10.1007/978-3-030-04070-3_12
Liu, M., Sim, S.M.: Lightweight MDS generalized circulant matrices. In: Peyrin, T. (ed.) Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, 20–23 March 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9783, pp. 101–120. Springer (2016). https://doi.org/10.1007/978-3-662-52993-5_6
Mariot, L., Picek, S., Jakobovic, D., Leporati, A.: Evolutionary algorithms for the design of orthogonal Latin squares based on cellular automata. In: Bosman, P.A.N. (ed.) Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2017, Berlin, Germany, 15–19 July 2017, pp. 306–313. ACM (2017)
Mariot, L., Picek, S., Jakobovic, D., Leporati, A.: Evolutionary search of binary orthogonal arrays. In: Auger, A., Fonseca, C.M., Lourenço, N., Machado, P., Paquete, L., Whitley, L.D. (eds.) Parallel Problem Solving from Nature - PPSN XV - 15th International Conference, Coimbra, Portugal, 8–12 September 2018, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11101, pp. 121–133. Springer (2018). https://doi.org/10.1007/978-3-319-99253-2_10
Montemanni, R., Barta, J., Smith, D.H.: Graph colouring and branch and bound approaches for permutation code algorithms. In: Rocha, Á., Correia, A.M.R., Adeli, H., Reis, L.P., Teixeira, M.M. (eds.) New Advances in Information Systems and Technologies - Volume 1 [WorldCIST’16, Recife, Pernambuco, Brazil, March 22–24, 2016]. Advances in Intelligent Systems and Computing, vol. 444, pp. 223–232. Springer (2016). https://doi.org/10.1007/978-3-319-31232-3_21
Oliver, I.M., Smith, D.J., Holland, J.R.C.: A study of permutation crossover operators on the traveling salesman problem. In: Grefenstette, J.J. (ed.) Proceedings of the 2nd International Conference on Genetic Algorithms, Cambridge, MA, USA, July 1987, pp. 224–230. Lawrence Erlbaum Associates (1987)
Smith, D.H., Montemanni, R.: A new table of permutation codes. Des. Codes Cryptogr. 63(2), 241–253 (2012)
Smith, D.H., Montemanni, R.: Permutation codes with specified packing radius. Des. Codes Cryptogr. 69(1), 95–106 (2013)
Stinson, D.R.: Combinatorial designs - constructions and analysis. Springer (2004). https://doi.org/10.1007/b97564
Syswerda, G., Palmucci, J.: The application of genetic algorithms to resource scheduling. In: Belew, R.K., Booker, L.B. (eds.) Proceedings of the 4th International Conference on Genetic Algorithms, San Diego, CA, USA, July 1991, pp. 502–508. Morgan Kaufmann (1991)
De la Torre, D., Colbourn, C., Ling, A.: An application of permutation arrays to block ciphers. Congressus Numerantium, pp. 5–8 (2000)
Vaudenay, S.: On the need for multipermutations: cryptanalysis of MD4 and SAFER. In: Preneel, B. (ed.) Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings. Lecture Notes in Computer Science, vol. 1008, pp. 286–297. Springer (1994). https://doi.org/10.1007/3-540-60590-8_22
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Mariot, L., Picek, S., Jakobovic, D., Djurasevic, M., Leporati, A. (2022). On the Difficulty of Evolving Permutation Codes. In: Jiménez Laredo, J.L., Hidalgo, J.I., Babaagba, K.O. (eds) Applications of Evolutionary Computation. EvoApplications 2022. Lecture Notes in Computer Science, vol 13224. Springer, Cham. https://doi.org/10.1007/978-3-031-02462-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-02462-7_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-02461-0
Online ISBN: 978-3-031-02462-7
eBook Packages: Computer ScienceComputer Science (R0)