Cognitive radio (CR) has emerged as a promising solution to the problem of spectrum underutilization. In CR, spectrum sensing is a key feature. It enables the cognitive user or secondary user (SU) to detect spectrum holes and ensure non-interference to primary communication. Spectrum sensing has its own challenges, such as discovery of opportunities for transmission and sensing overhead. High sensing overhead may impair spectral efficiency as the radio is mostly used for detecting primary users (PUs), rather than transmitting data. On the other hand, a less frequent sensing may result in interference to PU, due to the delay in the detection of the PUs reappearance and can lead to loss of transmission opportunities. Thus, it is of paramount importance to optimize the sensing periods for each primary channel in order to maximize the number of transmission opportunities and reduce the sensing overhead incurred. This paper extends our previous letter (Balieiro, Yoshioka, Dias, Cavalcanti, & Cordeiro, 2013) and presents a detailed description of our adaptive sensing optimization scheme for CR Networks based on a multi-objective genetic algorithm (GA) formulation. Our scheme aims at maximizing the spectrum opportunities as well as keeping the sensing overhead always within a user-defined maximum value. The simulation results show that the proposed scheme outperforms the schemes described in the literature, while keeping the sensing overhead within a target value. In addition, it provides different levels of protection to PU communication through the configuration of threshold for sensing overhead.