Suspending microstrip patch antennas (MPAs) on air is a simple method of improving the bandwidth. However, the probe inductance limits the height of the MPA and hence the bandwidth since it adds a reactive impedance that mismatches the antenna. Proper selection of geometrical patch shape can introduce capacitive effects to compensate the probe inductance and improve the bandwidth. The selection of the geometry can be performed by using an optimizing technique. This article focuses on a multipurpose optimization problem where the optimization tool optimizes not only the bandwidth but also the gain along the broadside direction. Further, it is used to obtain linear polarization in a fixed direction over the whole bandwidth for broadside radiation. Genetic algorithm is used as the optimization technique to find the patch geometry and locate the feed position to achieve these objectives. A variably overlapping cell method has been used in search of the patch geometry. The performance improved MPA has a rectangular profile of 20 × 25 mm2 and operates around 4 GHz. The broadband antenna shows a fractional impedance bandwidth of 60% with S11<−10 dB. It also shows linear polarization and maximum radiation along the broadside direction across the bandwidth with a maximum broadside gain of 7 dB. The antenna has been fabricated and the measurements are in good agreement with the simulated results.