Bitumen, aggregate, and air void (VA) are the three primary ingredients of asphalt concrete. VA changes over time as a function of four factors: traffic loads and repetitions, environmental regimes, compaction, and asphalt mix composition. Due to the high as-constructed VA content of the material, it is expected that VA will reduce over time, causing rutting during initial traffic periods. Eventually, the material will undergo shear flow when it reaches its densest state with optimum aggregate interlock or refusal VA content. Therefore, to ensure the quality of construction, VA in asphalt mixture need to be modeled throughout the service life. This study aims to implement a hybrid evolutionary polynomial regression (EPR) combined with a teaching–learning based optimization (TLBO) algorithm and multi-gene genetic programming (MGGP) to predict the VA percentage of asphalt mixture during the service life. For this purpose, 324 data records of VA were collected from the literature. The variables selected as inputs were original as-constructed VA, 𝑉𝐴𝑜𝑟𝑖𝑔 (%); mean annual air temperature, 𝑀𝐴𝐴𝑇 (°F); original viscosity at 77 °F, 𝜂𝑜𝑟𝑖𝑔,77 (Mega-Poises); and 𝑡𝑖𝑚𝑒 (months). EPR-TLBO was found to be superior to MGGP and existing empirical models due to the interquartile ranges of absolute error boxes equal to 0.67%. EPR-TLBO had an R2 value of more than 0.90 in both the training and testing phases, and only less than 20% of the records were predicted utilizing this model with more than 20% deviation from the observed values. As determined by the sensitivity analysis, 𝜂𝑜𝑟𝑖𝑔,77 is the most significant of the four input variables, while time is the least one. A parametric study showed that regardless of 𝑀𝐴𝐴𝑇, 𝜂𝑜𝑟𝑖𝑔,77, of 0.3 Mega-Poises, and 𝑉𝐴𝑜𝑟𝑖𝑔 above 6% can be ideal for improving the pavement service life. It was also witnessed that with an increase of 𝑀𝐴𝐴𝑇 from 37 to 75 °F, the serviceability of asphalt concrete takes 15 months less on average.