The design of symmetric encryption algorithms usually entails the selection of low-level primitives, such as Boolean functions and S-boxes that satisfy specific algebraic properties, in order to thwart certain types of attacks. Interestingly, the construction of such primitives can be cast as a combinatorial optimization problem, which becomes infeasible to solve through exhaustive search as soon as the number of input variables becomes too large. In this talk, we give a broad overview of the nature-inspired metaheuristic optimization algorithms that have been used to efficiently design Boolean functions and S-boxes with good cryptographic properties. In particular, we focus on evolutionary algorithms and the related encodings considered in the literature used to represent the candidate solutions. We show how the tree-based symbolic encoding evolved by Genetic Programming (GP) turned out so far to be the most successful representation, specifically when evolving S-boxes defined by Cellular Automata (CA) rules.