Data Mining of self-replicators
Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:


Pick a small random seed pattern
Simulate a moderate number of steps of a modified version of the cellular automaton rule, starting with that seed. The modification is: if you find a small enough set of live cells, separated by far enough from the rest of the pattern, delete them.
If the simulation finds two states that have the same pattern of cells (but possibly shifted with respect to each other), check it against a collection of known repetitions and shifts and, if it seems new, report it. See https://en.wikipedia.org/wiki/Cycle_detection for efficient methods of finding repeated patterns that don't involve testing all against all.


Many replicators eventually reach a state with just two copies of the replicator far from each other, after which the modification to the rule deletes one of them and you get a repetition.