Electromagnetic metasurfaces are planar two-dimensional metamaterials, typically of subwavelength thickness. Unit cell elements of different shapes have been widely explored, including electric and magnetic dipoles, patches, arbitrary geometries and pixelated surfaces. Although pixelated metasurfaces have a great advantage of geometric versatility, their design and analysis requires algorithmic approach. One of the techniques for their design is via evolutionary simulation-driven optimization. Since full-wave electromagnetic simulations are time-consuming, optimization methods with fast convergence properties are preferable. In this article, we demonstrate the application of the cross-entropy optimization method to design of artificial magnetic conductors (AMCs) and thin printed phase shifters. Single-frequency AMCs at 10 GHz (X band) and dual-frequency AMCs at 8 and 12 GHz (X and Ku band) were produced that are more manufacturing-friendly, and thus cost effective, than previously reported AMCs. We also show that phase-shifting unit cells with transmission magnitudes over 0.9 (linear) can be designed using the proposed optimization technique. Other potential applications of these unit cells are in phase-correcting and beam-steering metasurfaces.