Those methods applied can be fairly broad, but not every monte carlo algorithm will work. Because of the nature of the problem space (computer programs), it's less common to see methods which assume the existence of a gradient in the space, or that the space is metric. More often you need more general-purpose, "weaker" techniques. You see simulated annealing and hill climbing, various combinatorial optimization techniques (ant colony optimization say), etc., but even now the dominant approach is to use evolutionary computation methods because they make few assumptions about the nature of the space beyond a smoothness criterion, and because they are very highly parallelizable.
-- Which saying that it can be formally just about anything but is knit together by various hunches and analogies.
This sort of approach has a certain strength through flexibility. I would offer that the strength of a fully formally defined system has the strength that is can be meta-analyzed - propositions about what the entire system is capable of can proven (for example, see neural network approximation theorem).
Also, neural networks today have a set-upon using "relu" layers, which basically "nothing but smooth" layers (continuous, piecewise-linear functions) and gradient descent works fine.
This is also usually the default situation, because often we really don't know anything about the problem space.
Of course if you do know something about the problem space in the form of a gradient or probabilistic graph, and then you use those things & you won't be doing GP anymore.
The basic Genetic algorithm, accord to the text
By making fairly reasonable variations of the concept of fitness and "genetic operation", it seems like one could have simulated annealing, stochastic gradient descent, particle filters and a host of other standard algorithms. Remember, they say "Select one or two program(s)" - select one and mutate is any monte carlo algorithm, right?Which is to say GP seems more like a mix-in that can be added what ever algorithm (add some binary operations to the unary operations most algorithms effectively use to evolve). Yet GP is spoken of as an alternative all the other approaches, something wholly different. Plus what is spoken of as "genetic programming proper" is this basic loop plus a bunch of less explicit but very assumed approaches.