I'm trying to solve the graph partitioning problem on large graphs (between a billion and trillion elements) using GA.

The problem is that even one chromosome will take several gigs of memory. Are there any general compression techniques for chromosome encoding? Or should I look into distributed GA?

NOTE: using some sort of evolutionary algorithm for this problem is a must! GA seems to be the best fit (although not for such large chromosomes).

EDIT: I'm looking for state-of-the-art methods that other authors have used to solved the problem of large chromosomes. Note that I'm looking for either a more general solution or a solution particular to graph partitioning. Basically I'm looking for related works, as I, too, am attempting using GA for the problem of graph partitioning. So far I haven't found anyone that might have this problem of large chromosomes nor has tried to solve it.