Many of the social insects -- ants and termites and bees, especially -- build "buildings" which have heterogenous rooms specialized for different purposes.

Genetic algorithms, indeed.

I imagine there were hominids building shelters before homo sapiens. And they probably took cues from animals.

Weaver birds, beavers, bees, ants, termites, etc... Hell, we could even call shelled animals like snails and turtles mobile buildings :P