Service Function Chains (SFCs) enable programmatic control of the functions and services in a computer network. By leveraging Software Defined Networking to control the links between virtualised network functions, SFCs provide a scalable approach to dealing with the increased pressures on network operation and management. However, embedding SFCs onto the underlying physical network and compute infrastructure is an NP-hard problem. Genetic Algorithms (GAs) have been used to address this issue, but they require significant time to evaluate solution quality (fitness) online, with most existing approaches instead adopting offline simulations or analytical evaluations. To enable online use of GAs in solving the SFC embedding problem, we introduce a hybrid online-offline approach to efficiently evaluate the fitness of generated solutions. At the core of this is BENNS: a surrogate model that approximates fitness and is agnostic to topology, traffic, and SFC-embedding. We evaluate our approach in a static environment across five experiments, varying available resources and traffic loads, and in a dynamic network environment. Our results demonstrate that our approach is capable of exploring thousands of potential configurations and generating deployable solutions in 19.1 minutes on average, compared to online-only approaches, which take 17.8 hours on average to explore ten solutions in our experiments and do not converge on an optimal solution.