Neuroevolution is a popular branch of Neural Architecture Search (NAS) that searches for high-performing artificial neural network architectures using evolutionary algorithms. Neuroevolution of deeper, more complex architectures, like deep neural networks, however, comes at a great computational cost, as often thousands of architectures need to be trained and evaluated over numerous Graphical Processing Unit days. To address this, research has turned to the use of Surrogate-Assisted Evolutionary Algorithms (SAEAs), where less expensive surrogate models can be used to estimate the fitness of an architecture, without the need to fully train it, resulting in a substantial reduction in the associated computational cost. Ultimately, SAEAs have emerged as a graceful response to tackling computational intensive workflows, such as neuroevolution, however, some notable limitations remain, such as, issues relating to high-dimensionality and complex encoding strategies required in current surrogate-assisted neuroevolution methods. In this thesis, we use a semantic-inspired method to adeptly handle these issues, which in turn, is incorporated into a novel technique named Neuro-Linear Genetic Programming (NeuroLGP). NeuroLGP evolves chain-structured topologies with a representation closely aligned to how neural network architectures are naturally constructed. This allows us to perform an in-depth analysis not only on the surrogate model robustness and architecture performance, but also allows us to analyse how the internal makeup of our architectures change during evolution. From this, we propose a new mechanism, named NeuroLGPMB, that is capable of evolving truly complex modern networks that exhibit multi-branch connections. Our proposed SAEA approach was shown to not only be robust for both NeuroLGP and NeuroLGP-MB but was also able to find high-performing individuals with a substantial reduction in time.