The optimal design of formulated products is a complex and comprehensive technology. In order to obtain formulations with excellent performance and meet the requirements, it is necessary to reasonably select raw materials and determine the dosage ratio relationship of various raw materials through testing, optimization, and identification. Combining the BP neural network and NSGA-II algorithm was used to study the design optimization of tobacco leaf group formulation in this paper. Firstly, the chemical composition and sensory quality data of single-ingredient tobacco samples were collected and normalized, and then correlation analysis was performed to obtain the single ingredient tobacco proportion-chemical composition relationship model and chemical composition-sensory score relationship model. Then the two relationship models were imported into the BP-NSGA-II model to calculate the chemical composition of the leaf group formulation, and the sensory quality score was predicted based on the chemical composition to obtain the optimization results of the proportion of the tobacco leaf group formulation. There was a strong correlation between the chemical composition and sensory quality of tobacco at the significant level of α = 0.01. Except for the aroma index, the mean error of prediction of the methods in this paper for the rest of the sensory quality indicators was smaller than those of SVR and multiple linear regression methods. The absolute error of prediction for all indicators was less than the traditional BP and SVR models. The sensory quality scores of the optimized formulations in this paper are basically consistent with the results of expert evaluation, and the absolute values of relative errors are less than 4%, which is of strong practical significance for the optimization of formulation design of tobacco leaf groups.