If you want to simulate something like that , with only Natural Selection , (IMHO) I'd suggest you add 'strength' , 'intellect' and other skills like those to the villagers. It'll make them 'fight' for better statistics , for their jobs , and will produce , for example , stronger or smarter children , depending on the parent and his job. (In a few words , it'll work like a GA , without the A )

As for pathfinding , I dont have time to read all the posts in here about it , but it shouldnt be ignored and it can be easely build to 'explore' diffrent paths , instead of knowing them all. There are a few articles on GameDev about this 'exploration' with a pre-build lists of paths (or dynamic).