Optimizing Complex Calculations for high-pop Objects

Let's say you have 5,000+ entities that require detailed AI computations at a high frequency (let's say per frame). From my research a common solution to resolve heavy functions for many instances rapidly is to delegate the heaviest workload to a thread (such as AI pathfinding). The workloads I am thinking of is graphical, spacial, ecosystem, genetics, etc.

How would you go about managing per frame and threaded callbacks for smooth / fast AI with many instances? The genetic algorithms series would be an excellent transition if it's included in the AI arguments.