<p>Mining frequent and high utility itemsets (FHUIs) from transaction database is an important task in data mining. In order to overcome the difficulties of parameter setting and huge search space in traditional algorithms for mining FHUIs, the task of mining FHUIs was modeled as a bi-objective problem and then solved by multi-objective evolutionary algorithms (MOEAs) in previous works. However, MOEAs may be inefficient when the number of transactions and items in the transaction database becomes large. To address this problem, we propose a novel efficient bi-objective evolutionary algorithm for mining FHUIs (NBOEA-FHUI). In NBOEA-FHUI, a novel initialization strategy is proposed, which takes the support, utility, and diversity of the initial population into account. The proposed initial strategy can make the initial population have relative high utility and support values with high population diversity. To improve the quality of the offspring, a method for estimating the support and utility value of itemsets and an offspring generation strategy are proposed in NBOEA-FHUI. The support and utility values of itemsets which are roughly proportional to their true values can be calculated by the estimation method with little computation. The proposed offspring generation strategy can generate better offspring based on the estimated support and utility value. Experimental results on several real datasets demonstrate that the proposed algorithm has better performance than the state-of-the-art MOEAs in terms of the convergence speed, search efficiency, and solution accuracy in the task of mining FHUIs.</p>