Say the Species Blarglefart currently hunts Smoot and Smeet. When it encounters either, it spews toxins and charges in to stab with pili.
Then Blarglefart evolves, and it has a few potential mutations. Maybe one of them is a modified toxin. Maybe that toxin will make it more efficient for Blarglefart to hang back and wait for its prey to die instead of charging in. But under my proposed system, the mutation would only be chosen if it makes the current set of behaviours Blarglefart engages in to be more efficient. And it isn't until after a mutation is chosen that makes the current set of behaviours better; that a new set of behaviours is computed. So, for example, if the modified toxin also allows it to hunt Blurp, and the effort spent hunting Blurp has a better payoff than ignoring Blurp encounters and sticking to Smoot and Smeet, then Blarglefart will start hunting Blurp too, perhaps even exclusively, but only if the mutation helped it do something it already did. We first mutate the body to better fit the behaviours, then we mutate the behaviours to better fit the body.
This differs in that we don't recompute optimal behaviours for each potential mutation, meaning we don't have to run multiple fight sims -- indeed, if fights are modelled as decision trees, then we don't even have separate fight sims, but just have them included in the rest of the code which goes through the behaviour tree and checks how the mutation affects it.
The final step, where a new set of behaviours is computed, can be done by incrementally modifying the decision tree that the species currently uses.
As for the datastructure: We'd have a big set of possible, simple behaviours. There would be behaviours controlling how an organism navigates around the world (for example, random walk, does it avoid anything, etc), behaviours directing how it looks for and gets food, behaviours that cover all the possible simple things organisms might do when they encounter another organism (flee, chase, release toxins, aggressive display, etc), behaviours involving shelter, water, poop, mating, marking territory, and so on. Each species would have a graph that dictates, effectively, a state machine of how a member of that species acts under different circumstances. This state machine, most simply, would be used to direct the behaviour of instances of the species in the game; but it's also used to dictate evolutionary fitness.
Every behaviour would have some complex formulas that provide measures of how effectively a species with a particular body plan can do that behaviour. For many, it would be the energy-effectiveness, and perhaps also time-effectiveness, of the behaviour.
We'd compute the total fitness of the species by walking its entire behaviour graph, putting all that effectiveness information together, to give us a measure of how quickly the population can grow. We'd need to know how much the members of the species perform each action (how often, how long they spend, etc), but I think that's relatively easy to do by looking up encounter rates for encounters, and using the specific characteristics for other behaviours (like sleep), and should only require one pass.
Now, while each species would only have one behaviour graph for the entire species, the different circumstances between patches will lead to separate populations spending different amounts of time doing different things -- this is the driver for speciation, since a mutation which improves the hunting of, say, shore fish might reduce the fitness of the species in hunting, say, antelope.
The final step, once a mutation is chosen and the body plan of the species is changed, is to see if the mutation gives rise to any new, easy-to-develop behaviours that are better than what it already does. So we walk through the behaviour graph, and if at any point there is a potential behaviour whose benefits outweigh the potential opportunity costs of doing the other behaviours less, then we add that behaviour too, and potentially add more behaviours from that. I think it would require two passes -- one forwards to see if there are any new behaviours to add to the graph, and one backwards if any were added, to update the measures of how often each is done. This second pass could just be done at the start of the next auto-evo step though.
I guess I've added enough detail that the main point is getting a bit lost, so I'll reiterate it: We first mutate the body to better fit the behaviours, then we mutate the behaviours to better fit the body. This gives us speedups since we don't need to compute a new behaviour graph for every possible mutation; and while it misses certain cases that could theoretically happen, I think it fits with how nature works, since a mutation doesn't become dominant by making an organism very good at something it simply doesn't do (which does not increase fitness), unless it also makes the organism better at something it does already do (which does).