Genetic algorithm (GA) has been a popular optimization technique used for performance improvement of microstrip patch antennas (MPAs). When using GA, the patch geometry is optimized by dividing the patch area into small rectangular cells. This has an inherent problem of adjacent cells being connected to each other with infinitesimal connections, which may not be achievable in practice due to fabrication tolerances in chemical etching. As a solution, this paper presents a novel method of dividing the patch area into cells with nonuniform overlaps. The optimized design, which is obtained by using fixed overlap sizes, shows a quad-band performance covering GSM1800, GSM1900, LTE2300, and Bluetooth bands. In contrast, use of nonuniform overlap sizes leads to obtaining a pentaband design covering GSM1800, GSM1900, UMTS, LTE2300, and Bluetooth bandswith fractional bands with of 38% due to the extra design flexibility.