A dynamical epidemic model optimized using a genetic algorithm and a cross-validation method to overcome the overfitting problem is proposed. The cross-validation procedure is applied so that available data are split into a training subset used to fit the algorithm’s parameters, and a smaller subset used for validation. This process is tested on Italy, Spain, Germany, and South Korea cases before being applied to Algeria. Interestingly, our study reveals an inverse relationship between the size of the training sample and the number of generations required in the genetic algorithm. Moreover, the enhanced compartmental model presented in this work has proven to be a reliable tool to estimate key epidemic parameters and the non-measurable asymptomatic infected portion of the susceptible population to establish a realistic nowcast and forecast of the epidemic’s evolution. The model is employed to study the COVID-19 outbreak dynamics in Algeria between February 25th, 2020, and May 24th, 2020. The basic reproduction number and effective reproduction number on May 24th, after three months of the outbreak, are estimated to be 3.78 (95% CI 3.033–4.53) and 0.651 (95% CI 0.539–0.761), respectively. Disease incidence, CFR, and IFR are also calculated. Numerical programs developed for this study are made publicly accessible for reproduction and further use.