Symmetry has hitherto been studied piecemeal in a variety of evolutionary computation domains, with little consistency between the definitions. Here we provide formal definitions of symmetry that are consistent across the field of evolutionary computation. We propose a number of evolutionary and estimation of distribution algorithms suitable for variable symmetries in Cartesian power domains, and compare their utility, integration of the symmetry knowledge with the probabilistic model of an EDA yielding the best outcomes. We test the robustness of the algorithm to inexact symmetry, finding adequate performance up to about 1% noise. Finally, we present evidence that such symmetries, if not known a priori, may be learnt during evolution.