This paper implements the recently developed meta-heuristic algorithms Colliding Bodies Optimization (CBO) and its Enhanced version (ECBO) for the optimization of double-layer barrel vaults. CBO is inspired by governing laws of momentum and energy from physics and is based on one-dimensional collisions between bodies, which uses no internal parameter and no memory in its formulation. The ECBO utilizes memory to save some historically best solutions and uses a random procedure to avoid local optima. Two kinds of double-layer barrel vaults are optimized considering weight of the structure as the objective function, where the design constraints are imposed according to the provisions of AISC-ASD. The numerical results show the successful performance of the CBO and ECBO algorithms in large-scale structural optimization problems such as double-layer barrel vaults.