The only solutions are exact solutions, the search space is very large and the set of solutions is (probably) very small. It's possible you could do something clever to make a genetic algorithm work, but you couldn't just throw one together.
You just need to provide a gradient for the search space. Something like inverse of average gap between tiles. This is standard for any metaheuristic search (of which genetic algorithms are a sub-category), so I wouldn't call it "doing something clever".
Metaheuristics search a problem space to find an exact solution (total plane tiling). In order to search that space, they need direction. The "almost plane tiling" is the direction. You said it would be difficult for a genetic algorithm to find a solution because the set of solutions is very small, but that's missing the point of a metaheuristic. It's the difference between climbing a hill and a cliff. Either way the goal is at the top, but the hill is easier to get up.