Histogram shifting (HS) as a typical reversible data hiding (RDH) scheme is widely researched due to its high quality of stego-image. During HS process, the selected side information, i.e., peak and zero bins, usually greatly affects the performance of stego-image. Due to the massive solution space and burden in distortion computation, conventional HS-based schemes commonly utilize some empirical criterions associated with many artificial-designed constraints to determine side information, which could not lead to a global optimal performance for HS-based RDH. Later, our previous work proposed an adaptive information selection scheme for “multiple embedding” method by removing lots of constraints employed in conventional schemes. However, those constraints could not be completely avoided. Those chosen peak and zero bins in “multiple embedding” process are required to be different with each other, since they are commonly determined at one time as side information. In this paper, we employ “multilevel embedding” method and contrive to get rid of these above-mentioned constraints, which are called “unnecessary constraints” in this paper, so as to search essential global optimal side information around the entire solution space for HS-based RDH. Apparently, the process will dramatically increase the solution space and computation complexity. To effectively control the time cost, two novel approaches are proposed: 1) A pattern-based rapid performance evaluation method is designed to compute the rate and distortion; 2) Spirited by our previous work, a problem-oriented designed evolutionary algorithm, i.e., transfer learning-based genetic algorithm, is proposed to perform high-efficiency search around the entire huge solution space. For a given data payload, the proposed scheme could adaptively determine the optimal combination of peak and zero bins without any unnecessary constraint. The experimental results demonstrate the superiority of the proposed scheme compared with other state-of-the-art methods.