A reconfigurable crossed-Vagi patch antenna (CYPA) that yields a circularly polarized pattern is proposed, and optimized by a novel Jumping-Genes Genetic Algorithm. This antenna is formed by two identical orthogonal reconfigurable linear Vagi patch arrays, around a single driven patch element. The main lobe of the reconfigurable crossed-Yagi patch antenna covers the elevation angles from 0 degrees to 47 degrees with a peak gain of 8.68 dBi. Full azimuthal coverage can be achieved by switching among the four antenna modes. The design justification has been duly demonstrated based on fabricated prototypes. The effect of a MEMS switch on the reconfigurable Vagi antennas is investigated. The reactance introduced by the switch can be offset by modifying the dimensions of a loaded slot. Due to the distinctive features of this antenna, satellite communications and global positioning systems would be the most suitable targets for application.