Future generations of satellite and mobile communications at mm-wave frequencies require the use of low-loss and wideband phase-shifting components. Pixelated metasurfaces provide large design versatility and constitute an attractive solution for wave manipulation, such as shifting the phase of an incident wave. However, their design often implies the simultaneous tuning of a large number of geometrical parameters. This article employs an enhanced multi-objective optimization algorithm to design a dynamically reconfigurable metasurface providing ultra-low losses and linear phase response. The presented methodology can be easily employed for different objective functions or technologies, constituting a versatile design strategy for electromechanically reconfigurable devices based on pixelated metasurfaces. A prototype is fabricated based on the optimization outcome, achieving a phase shifter capable of providing a continuous phase shift up to 180∘ between 50 and 65 GHz. A piezo-electric actuator is used to dynamically adjust the phase shift with respect to the position of a metallic ground plane placed in front of the metasurface. A linear evolution of the phase w.r.t. the ground plane displacement is obtained while maintaining the losses around 1 dB for the whole frequency range.