This paper presents a novel evolutionary optimization methodology for multiband and wide-band patch antenna designs. The particle swarm optimization (PSO) and the finite-difference time-domain (FDTD) are combined to achieve the optimum antenna satisfying a certain design criterion. The antenna geometric parameters are extracted to be optimized by PSO, and a fitness function is evaluated by FDTD simulations to represent the performance of each candidate design. The optimization process is implemented on parallel clusters to reduce the computational time introduced by full-wave analysis. Two examples are investigated in the paper: first, the design of rectangular patch antennas is presented as a test of the parallel PSO/FDTD algorithm. The optimizer is then applied to design E-shaped patch antennas. It is observed that by using different fitness functions, both dual-frequency and wideband antennas with desired performance are obtained by the optimization. The optimized E-shaped patch antennas are analyzed, fabricated, and measured to validate the robustness of the algorithm. The measured less than - 18 dB return loss (for dual-frequency antenna) and 30.5% bandwidth (for wide-band antenna) exhibit the prospect of the parallel PSO/FDTD algorithm in practical patch antenna designs.