According to wikis, there are a few conditions where they can spawn. Every 5min, when the boss reaches a certain health threshold or dies, etc. Or they can just be there from the start.
At first I'd do the usual method to find them: join a mission, wait 5min in the initial area to give them two opportunities to spawn, and then look around. But after a while just going after them asap ended up being faster; in the time I'd spend waiting around I could try that mission three times.
Also, where you find one you can find both, they just won't spawn at the same time. And it's always going to be on the same location, for example in P3-1 they'll always spawn in area 8, so you don't have to go around the entire map looking for them.