Bayesian hierarchical models of spatial data often use priors that smooth across geographically proximate areal units. In complex urban environments, there may be sharp boundaries intrinsic to the geography or population distribution that results in distinct clusters of areal units exhibiting markedly different trends. Typically, this partition is unknown a priori and the usual stochastic search techniques are computationally prohibitive since these searches must explore a vast discrete space of possible partitions.
In this work, rather than directly sampling from the posterior distribution of partitions, we introduce an ensemble optimization procedure targeting the partitions with largest posterior probability. We run several greedy searches over the posterior distribution of partitions that are made ``mutually aware'' through a penalty that repels search trajectories that are headed to the same point. We demonstrate our method with simulated data and a case study about the crime rate in the city of Philadelphia.