This paper addresses the optimization of the radiation pattern of surface-wave (SW) based metasurface (MTS) antennas. Those antennas are considered as a promising alternative to parabolic reflectors, and phased arrays due to their extremely low profile and their ability to provide high gain, shaped beams and multibeams. However, pattern synthesis with MTS antennas is very challenging because of the single active control point and the need to control surface and leaky-waves through the MTS. An accurate optimization of the radiation pattern, along with the sidelobe level requires a full-wave modelling of the feeding structure, including its coupling with the MTS. MTS synthesis methods existing in the literature usually approximate the feeder model, and neglect its coupling with the MTS. Such approximation may lead to more than 1 dB error in the predicted antenna directivity. This paper presents a technique for optimization of the far-field pattern, built on a Method of Moments (MoM) analysis tool in which the MTS coupling with the feeder, a coax probe, is fully considered. The MTS is modeled as an arbitrarily shaped, spatially modulated electric sheet impedance in a layered medium. At each optimization iteration, the complexity of the underlying analysis is O(N log N) owing to the use of a FFT based acceleration. The effectiveness of the method is demonstrated through the optimization of MTSs radiating a pencil beam and a conical beam with orbital angular momentum (OAM).